DCGs are a natural notation for context free grammars
Abstract:
DCG motivation and example.
Suppose we are working with a context free grammar, for example, this: S→NPVPNP→DetNVP→VNPDet→theDet→aN→witchN→wizardV→curses
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.