Definite clause grammar
Encyclopedia
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
. 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.
, 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 Colmeraur and Kowalski, and they note that DCGs are a special case of Colmeraur'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 Sheiber on a book called "Prolog and Natural Language Analysis", that was intended as a general introduction to computational linguistics using logic programming.
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 in 1984. DCTG notation looks very similar to DCG notation; the major difference is that one uses
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
for normal definite clauses in Prolog. For example, the previous example could be translated into the following:
sentence(S1,S3) :- noun_phrase(S1,S2), verb_phrase(S2,S3).
noun_phrase(S1,S3) :- det(S1,S2), noun(S2,S3).
verb_phrase(S1,S3) :- verb(S1,S2), noun_phrase(S2,S3).
det([the|X], X).
det([a|X], X).
noun([cat|X], X).
noun([bat|X], X).
verb([eats|X], X).
Difference lists are used to represent lists with DCGs for reasons of efficiency. It is much more efficient to concatenate difference lists, in the circumstances that they can be used, because the concatenation of
s; 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 --> 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
, by structurally representing 
.
s 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".
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)))) ? ;
Natural language
In the philosophy of language, a natural language is any language which arises in an unpremeditated fashion as the result of the innate facility for language possessed by the human intellect. A natural language is typically used for communication, and may be spoken, signed, or written...
or formal
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
languages, in a logic programming language such as Prolog
Prolog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
. 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
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate 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 Marseilles, France, and Edinburgh, Scotland. According to Robert KowalskiRobert Kowalski
Robert "Bob" Anthony Kowalski is a British logician and computer scientist, who has spent most of his career in the United Kingdom....
, an early developer of Prolog, the first Prolog system was developed in 1972 by Alain Colmerauer
Alain Colmerauer
Alain Colmerauer is a French computer scientist.After completing his Ph.D. at the University of Grenoble, he spent 1967–1970 as Assistant Professor at the University of Montreal, where he created Q-Systems, one of the earliest linguistic formalisms used in the development of the TAUM-METEO machine...
and Phillipe Roussel. The first program written in the language was a large natural-language processing system. Fernando Pereira and David Warren
David H. D. Warren
David H. D. Warren is a computer scientist .In the 1970s and 1980s he worked primarily on logic programming and in particular the programming language Prolog. Warren wrote the first compiler for Prolog...
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 Colmeraur and Kowalski, and they note that DCGs are a special case of Colmeraur'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 Sheiber on a book called "Prolog and Natural Language Analysis", that was intended as a general introduction to computational linguistics using logic programming.
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.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 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.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 sugarSyntactic sugar
Syntactic sugar is a computer science term that refers to syntax within a programming language that is designed to make things easier to read or to express....
for normal definite clauses in Prolog. For example, the previous example could be translated into the following:
sentence(S1,S3) :- noun_phrase(S1,S2), verb_phrase(S2,S3).
noun_phrase(S1,S3) :- det(S1,S2), noun(S2,S3).
verb_phrase(S1,S3) :- verb(S1,S2), noun_phrase(S2,S3).
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(S1,S3) and (S1,S2) are difference lists; difference lists are a way of representing a list as the difference of two lists. Using Prolog's notation for lists, a list L can be represented with the pair ([L|X],X).Difference lists are used to represent lists with DCGs for reasons of efficiency. It is much more efficient to concatenate difference lists, in the circumstances that they can be used, because the concatenation of
(S1,S2) and (S2,S3) is just (S1,S3).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 grammarContext-free grammar
In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....
s; there is only one argument on the left side of the production
Production (computer science)
A production or production rule in computer science is a rewrite rule specifying a symbol substitution that can be recursively performed to generate new symbol sequences. A finite set of productions P is the main component in the specification of a formal grammar...
. However, context-sensitive grammars can also be expressed with DCGs, by providing extra arguments, such as in the following example:
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
, by structurally representing .Representing features
Various linguistic featureFeature (linguistics)
A feature is a concept applied to several fields of linguistics, typically involving the assignment of binary or unary conditions which act as constraints.-In phonology:...
s 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
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 programming language Mercury, which borrows DCG syntax from Prolog, for example, DCGs are used to hideio__state arguments in I/O code. They are also used in other, similar situations in Mercury.See also
- Natural language processingNatural language processingNatural language processing is a field of computer science and linguistics concerned with the interactions between computers and human languages; it began as a branch of artificial intelligence....
- Phrase structure grammarPhrase structure grammarThe term phrase structure grammar was originally introduced by Noam Chomsky as the term for grammars as defined by phrase structure rules, i.e. rewrite rules of the type studied previously by Emil Post and Axel Thue...
- Chomsky hierarchyChomsky hierarchyWithin the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy is a containment hierarchy of classes of formal grammars....
- Context-free grammarContext-free grammarIn formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....