7.2.1 A first example

As our first example, here's our little grammar written as a DCG:

s --> np,vp.
 
np --> det,n.
 
vp --> v,np.
vp --> v.
 
det --> [the].
det --> [a].
 
n --> [woman].
n --> [man].
 
v --> [shoots].

The link with the original context free grammar should be utterly clear: this is definitely the most user friendly notation we have used yet. But how do we use this DCG? In fact, we use it in exactly the same way as we used our difference list recognizer. For example, to find out whether a woman shoots a man is a sentence, we pose the query:

s([a,woman,shoots,a,man],[]).

That is, just as in the difference list recognizer, we ask whether we can get an s by consuming the symbols in [a,woman,shoots,a,man], leaving nothing behind.

Similarly, to generate all the sentences in the grammar, we pose the query:

s(X,[]).

This asks what values we can give to X, such that we get an s by consuming the symbols in X, leaving nothing behind.

Moreover, the queries for other grammatical categories also work the same way. For example, to find out if a woman is a noun phrase we pose the query:

np([a,woman],[]).

And we generate all the noun phrases in the grammar as follows:

np(X,[]).

What's going on? Quite simply, this DCG is our difference list recognizer! That is, DCG notation is essentially syntactic sugar: user friendly notation that lets us write grammars in a natural way. But Prolog translates this notation into the kinds of difference lists discussed before. So we have the best of both worlds: a nice simple notation for working with, and the efficiency of difference lists.

There is an easy way to actually see what Prolog translates DCG rules into. Suppose you are working with this DCG (that is, Prolog has already consulted the rules). Then if you pose the query:

listing(s)

you will get the response

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

This is what Prolog has translated s --> np,vp into. Note that (apart from the choice of variables) this is exactly the difference list rule we used in our second recognizer.

Similarly, if you pose the query

listing(np)

you will get

np(A,B) :-
    det(A,C),
    n(C,B).

This is what Prolog has translated np --> det,n into. Again (apart from the choice of variables) this is the difference list rule we used in our second recognizer.

To get a complete listing of the translations of all the rules, simply type

listing.

There is one thing you may observe. Some Prolog implementations translate rules such as

det --> [the].

not into

det([the|W],W).

which was the form we used in our difference list recognizer, but into

det(A,B) :-
    'C'(A,the,B).

Although the notation is different, the idea is the same. Basically, this says you can get a B from an A by consuming a the. Note that 'C' is an atom.