5.2.2 DCGs are really Syntactic Sugar for Difference Lists

DCGs are really are a user friendly notation for grammars written in terms of difference lists.

[Background]

Why the two arguments when we make queries? Because DCGs are really "syntactic sugar" for something else. They are a nice user friendly notation for grammars written in terms of difference lists. For example, when the above grammar is given to Prolog, the Prolog interpreter will immediately translate the first rule into something like this:

s(A,B) :-
    np(A,C),
    vp(C,B).

The lexical rule for ``the'' will translate into something like this

det([the|W],W).

This is not the place to go into how this works, but we will make two remarks: First, the difference list representation of grammars, while a bit complicated at first sight, is a very efficient way of representing grammars. In particular, the use of difference lists allows us to avoid using the append/3 predicate, thus DCGs are a useful way of writing even quite large grammars. Second, notice that the translated clauses all have two arguments --- which explains why the above queries needed two arguments.

Summing up: DCG notation is a natural notation that lets us write context free grammars in a natural way. DCGs translate into a difference list representation that allows far more efficient processing than a naive single-list representation that relies on using append/3.