Definite clause grammar

A definite clause grammar (DCG) is a way of expressing grammar, either for natural or formal languages, in a logic programming language such as Prolog. It is closely related to the concept of attribute grammars / affix grammars. DCGs are usually associated with Prolog, but similar languages such as Mercury also include DCGs. They are called definite clause grammars because they represent a grammar as a set of definite clauses in first-order logic.

The term DCG refers to the specific type of expression in Prolog and other similar languages; not all ways of expressing grammars using definite clauses are considered DCGs. However, all of the capabilities or properties of DCGs will be the same for any grammar that is represented with definite clauses in essentially the same way as in Prolog.

The definite clauses of a DCG can be considered a set of axioms where the validity of a sentence, and the fact that it has a certain parse tree can be considered theorems that follow from these axioms. This has the advantage of making it so that recognition and parsing of expressions in a language becomes a general matter of proving statements, such as statements in a logic programming language.

History

The history of DCGs is closely tied to the history of Prolog, and the history of Prolog revolves around several researchers in both Marseille, France, and Edinburgh, Scotland. According to Robert Kowalski, an early developer of Prolog, the first Prolog system was developed in 1972 by Alain Colmerauer and Phillipe Roussel. The first program written in the language was a large natural-language processing system. Fernando Pereira and David Warren at the University of Edinburgh were also involved in the early development of Prolog.

Colmerauer had previously worked on a language processing system called Q-systems that was used to translate between English and French. In 1978, Colmerauer wrote a paper about a way of representing grammars called metamorphosis grammars which were part of the early version of Prolog called Marseille Prolog. In this paper, he gave a formal description of metamorphosis grammars and some examples of programs that use them.

Fernando Pereira and David Warren, two other early architects of Prolog, coined the term "definite clause grammar" and created the notation for DCGs that is used in Prolog today. They gave credit for the idea to Colmerauer and Kowalski, and they note that DCGs are a special case of Colmerauer's metamorphosis grammars. They introduced the idea in an article called "Definite Clause Grammars for Language Analysis", where they describe DCGs as a "formalism ... in which grammars are expressed clauses of first-order predicate logic" that "constitute effective programs of the programming language Prolog".

Pereira, Warren, and other pioneers of Prolog later wrote about several other aspects of DCGs. Pereira and Warren wrote an article called "Parsing as Deduction", describing things such as how the Earley Deduction proof procedure is used for parsing. Pereira also collaborated with Stuart M. Shieber on a book called "Prolog and Natural Language Analysis", that was intended as a general introduction to computational linguistics using logic programming.

Example

A basic example of DCGs helps to illustrate what they are and what they look like.

 sentence --> noun_phrase, verb_phrase.
 noun_phrase --> det, noun.
 verb_phrase --> verb, noun_phrase.
 det --> [the].
 det --> [a].
 noun --> [cat].
 noun --> [bat].
 verb --> [eats].

This generates sentences such as "the cat eats the bat", "a bat eats the cat". One can generate all of the valid expressions in the language generated by this grammar at a Prolog interpreter by typing sentence(X,[]). Similarly, one can test whether a sentence is valid in the language by typing something like sentence([the,bat,eats,the,bat],[]).

Translation into definite clauses

DCG notation is just syntactic sugar for normal definite clauses in Prolog. For example, the previous example could be translated into the following:

 sentence(A,Z) :- noun_phrase(A,B), verb_phrase(B,Z).
 noun_phrase(A,Z) :- det(A,B), noun(B,Z).
 verb_phrase(A,Z) :- verb(A,B), noun_phrase(B,Z).
 det([the|X], X).
 det([a|X], X).
 noun([cat|X], X).
 noun([bat|X], X).
 verb([eats|X], X).

Difference lists

The arguments to each functor, such as (A,B) and (B,Z) are difference lists; difference lists are a way of representing a prefix of a list as the difference between its two suffixes (the bigger including the smaller one). Using Prolog's notation for lists, a singleton list prefix P = [H] can be seen as the difference between [H|X] and X, and thus represented with the pair ([H|X],X), for instance.

Saying that P is the difference between A and B is the same as saying that append(P,B,A) holds. Or in the case of the previous example, append([H],X,[H|X]).

Difference lists are used to represent lists with DCGs for reasons of efficiency. It is much more efficient to concatenate list differences (prefixes), in the circumstances that they can be used, because the concatenation of (A,B) and (B,Z) is just (A,Z).

Indeed, append(P,B,A), append(Q,Z,B) entails append(P,Q,S), append(S,Z,A). This is the same as saying that list concatenation is associative:

A = P + B = P + (Q + Z) = (P + Q) + Z = S + Z = A

Non-context-free grammars

In pure Prolog, normal DCG rules with no extra arguments on the functors, such as the previous example, can only express context-free grammars; there is only one argument on the left side of the production. However, context-sensitive grammars can also be expressed with DCGs, by providing extra arguments, such as in the following example:

 s --> a(N), b(N), c(N).
 a(0) --> [].
 a(M) --> [a], a(N), {M is N + 1}.
 b(0) --> [].
 b(M) --> [b], b(N), {M is N + 1}.
 c(0) --> [].
 c(M) --> [c], c(N), {M is N + 1}.

This set of DCG rules describes the grammar which generates the language that consists of strings of the form $a^{n}b^{n}c^{n}$.

 s --> symbols(Sem,a), symbols(Sem,b), symbols(Sem,c).
 symbols(end,_) --> [].
 symbols(s(Sem),S) --> [S], symbols(Sem,S).

This set of DCG rules describes the grammar which generates the language that consists of strings of the form $a^{n}b^{n}c^{n}$, by structurally representing n

Representing features

Various linguistic features can also be represented fairly concisely with DCGs by providing extra arguments to the functors. For example, consider the following set of DCG rules:

 sentence --> pronoun(subject), verb_phrase.
 verb_phrase --> verb, pronoun(object).
 pronoun(subject) --> [he].
 pronoun(subject) --> [she].
 pronoun(object) --> [him].
 pronoun(object) --> [her].
 verb --> [likes].

This grammar allows sentences like "he likes her" and "he likes him", but not "her likes he" and "him likes him".

Parsing with DCGs

An example parse tree for this grammar.

The main practical use of a DCG is to parse sentences of the given grammar, i.e. to construct a parse tree. This can be done by providing "extra arguments" to the functors in the DCG, like in the following rules:

 sentence(s(NP,VP)) --> noun_phrase(NP), verb_phrase(VP).
 noun_phrase(np(D,N)) --> det(D), noun(N).
 verb_phrase(vp(V,NP)) --> verb(V), noun_phrase(NP).
 det(d(the)) --> [the].
 det(d(a)) --> [a].
 noun(n(bat)) --> [bat].
 noun(n(cat)) --> [cat].
 verb(v(eats)) --> [eats].

One can now query the interpreter to yield a parse tree of any given sentence:

 | ?- sentence(Parse_tree, [the,bat,eats,a,cat], []).
 Parse_tree = s(np(d(the),n(bat)),vp(v(eats),np(d(a),n(cat)))) ? ;

Other uses

DCGs can serve as a convenient syntactic sugar to hide certain parameters in code in other places besides parsing applications. In the declaratively pure programming language Mercury I/O must be represented by a pair of io.state arguments. DCG notation can be used to make using I/O more convenient, although state variable notation is usually preferred. DCG notation is also used for parsing and similar things in Mercury as it is in Prolog.

Extensions

Since DCGs were introduced by Pereira and Warren, several extensions have been proposed. Pereira himself proposed an extension called extraposition grammars (XGs). This formalism was intended in part to make it easier to express certain grammatical phenomena, such as left-extraposition. Pereira states, "The difference between XG rules and DCG rules is then that the left-hand side of an XG rule may contain several symbols." This makes it easier to express rules for context-sensitive grammars.

Peter Van Roy extended DCGs to allow multiple accumulators.

Another, more recent, extension was made by researchers at NEC Corporation called Multi-Modal Definite Clause Grammars (MM-DCGs) in 1995. Their extensions were intended to allow the recognizing and parsing expressions that include non-textual parts such as pictures.

Another extension, called definite clause translation grammars (DCTGs) was described by Harvey Abramson in 1984. DCTG notation looks very similar to DCG notation; the major difference is that one uses ::= instead of --> in the rules. It was devised to handle grammatical attributes conveniently. The translation of DCTGs into normal Prolog clauses is like that of DCGs, but 3 arguments are added instead of 2.

See also

• Chomsky hierarchy
• Context-free grammar
• Natural language processing
• Phrase structure grammar

External links

• NLP with Prolog
• Context-free grammars and DCGs
• Definite Clause Grammars: Not Just for Parsing Anymore
• Definite Clause Grammars for Language Analysis