5.2.1 DCGs are a natural notation for context free grammars

DCG motivation and example.

Suppose we are working with a context free grammar, for example, this:

We can immediately turn this into the following DCG (found in dCGExample.pl ):

s --> np,vp.

np --> det,n.

vp --> v,np.

det --> [the].

det --> [a].

n --> [witch].

n --> [wizard].

v --> [curses].

The link between the two formalisms is obvious. About the only thing you have to remember is that in DCG notation, lexical items (that is, the words) have to be written as elements of a one-element list.

What's not quite so obvious is the way DCGs are used. For example, to see whether ``A witch curses the wizard'' is accepted by the grammar we need to pose the following query: s([a,witch,curses,the,wizard],[]).

That is, we have to give two arguments, one of which is the empty list. Similarly, to see if ``the witch'' is a noun phrase in this grammar, we would pose the query np([the,witch],[]).

DCGs can be used to generate (a very useful property). For example, to see all the sentences generated by our little grammar, we would give the following query: s(X,[]),write(X),nl,fail.

To see all the noun phrases produced by the grammar we would pose the query np(X,[]),write(X),nl,fail.