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. A basic example of DCGs helps to illustrate what they are and what they look like. 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 codice_1. Similarly, one can test whether a sentence is valid in the language by typing something like codice_2. DCG notation is just syntactic sugar for normal definite clauses in Prolog. For example, the previous example could be translated into the following:  The arguments to each functor, such as codice_3 and codice_4 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 codice_5 can be seen as the difference between codice_6 and codice_7, and thus represented with the pair codice_8, for instance. Saying that codice_9 is the difference between codice_10 and codice_11 is the same as saying that codice_12 holds. Or in the case of the previous example, codice_13. 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 codice_3 and codice_4 is just codice_16. Indeed, codice_17 entails codice_18. 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.