Definite clause grammar

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.

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.

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".

[5] 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.

DCG notation is just syntactic sugar for normal definite clauses in Prolog.

This is the same as saying that list concatenation is associative: 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.

[8] This set of DCG rules describes the grammar which generates the language that consists of strings of the form

This can be done by providing "extra arguments" to the functors in the DCG, like in the following rules: One can now query the interpreter to yield a parse tree of any given sentence: DCGs can serve as a convenient syntactic sugar to hide certain parameters in code in other places besides parsing applications.

[12] This formalism was intended in part to make it easier to express certain grammatical phenomena, such as left-extraposition.

[13][14] 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.

[15] Another extension, called definite clause translation grammars (DCTGs) was described by Harvey Abramson in 1984.

[17] The translation of DCTGs into normal Prolog clauses is like that of DCGs, but 3 arguments are added instead of 2.