7.2 Definite Clause Grammars
So, what are DCGs? Quite simply, a nice notation for writing grammars that hides the underlying difference list variables. Let’s look at three examples.
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 transparent: 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 recogniser. 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 recogniser, 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 recogniser! To put it another way, 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 see what Prolog translates DCG rules into. Suppose you are working with the DCG just given (that is, suppose that 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 recogniser.
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 recogniser.
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 recogniser, but into
det(A,B) :-
'C'(A,the,B).
But although the notation is different, the idea is the same. This says you can get a list B from a list A by consuming a the . That is, once again this is a difference list representation. Note that ’C’ is an atom.
Adding recursive rules
Our original context free grammar generated only 20 sentences. However it is easy to write context free grammars that generate infinitely many sentences: simply use recursive rules. Here’s an example. Let’s add the following rules to our little grammar:
| s -> s conj s |
| conj -> and |
| conj -> or |
| conj -> but |
This rule allows us to join as many sentences together as we like using the words and , but , and or . So this grammar classifies sentences such as The woman shoots the man or the man shoots the woman as grammatical.
Now, in principle it is easy to turn this grammar into a DCG. We need merely add the rules
s --> s,conj,s. conj --> [and]. conj --> [or]. conj --> [but].
But there is a problem lurking under the surface. What does Prolog actually do with this DCG? Let’s have a look.
First, let’s add the new rules at the beginning of the knowledge base, before the rule s --> np,vp . What happens if we then pose the query s([a,woman,shoots],[]) ? Prolog immediately goes into a loop.
Can you see why? The point is this. Prolog translates DCG rules into ordinary Prolog rules. If we place the recursive rule s --> s,conj,s in the knowledge base before the non-recursive rule s --> np,vp then the knowledge base will contain the following two Prolog rules, in this order:
s(A, B) :-
s(A, C),
conj(C, D),
s(D, B).
s(A, B) :-
np(A, C),
vp(C, B).
Now, from a declarative perspective this is fine, but from a procedural perspective this is fatal. When it tries to use the first rule, Prolog immediately encounters the goal s(A,C) , which it then tries to satisfy using the first rule, whereupon it immediately encounters the goal s(A, C) , which it then tries to satisfy using the first rule, whereupon it immediately encounters the goal s(A, C) , and so on. In short, it goes into an infinite loop and does no useful work.
So let’s add the recursive rule s --> s,conj,s at the end of the knowledge base, so that Prolog always encounters the translation of the non-recursive rule first. What happens now, when we pose the query s([a,woman,shoots],[]) ? Well, now Prolog handles this and gives an answer. But what happens when we pose the query s([woman,shoot],[]) ? Note that this is an ungrammatical sentence that is not accepted by our grammar. Once again, Prolog gets into an infinite loop. Since it is impossible to recognise [woman,shoot] as a sentence consisting of a noun phrase and a verb phrase, Prolog tries to analyse it with the rule s --> s,conj,s , and ends up in the same unending loop as before.
In short, we are having the same problems that we met when we discussed recursion, and rule and goal ordering, in Chapter 3 . In a nutshell, s --> s,conj,s translates into a left-recursive rule, and that’s bad news. Moreover, as we saw earlier, we can’t fix such problems simply by tinkering with the rule ordering: the way out of such difficulties is to change the goal order of the recursive rule so that the recursive goal is not the first one in the body of the rule. That is, ideally we should rewrite the rule so that it is no longer left-recursive.
Nice idea, but unfortunately, it is not an option here. Why not? Because the order of the goals determines the order of the words in the sentence! It makes an important difference, for example, whether our grammar accepts the woman shoots the man and the man shoots the woman ( s --> s,conj,s ) or whether it accepts and the woman shoots the man the man shoots the woman ( s --> conj,s,s ).
But there is a way out. The standard solution is to introduce a new non-terminal symbol and rewrite the DCG. We could, for example, use the category simple_s for sentences without embedded sentences. Our grammar would then look like this:
s --> simple_s. s --> simple_s,conj,s. simple_s --> np,vp. np --> det,n. vp --> v,np. vp --> v. det --> [the]. det --> [a]. n --> [woman]. n --> [man]. v --> [shoots]. conj --> [and]. conj --> [or]. conj --> [but].
As you should check, Prolog doesn’t get into infinite loops with this grammar as it did with the previous one, so from a computational perspective the solution is satisfactory. But it leaves something to be desired from a linguistic perspective. The DCG that looped was at least faithful to the linguistic intuitions about the structure of sentences made using and , but , and or . The new DCG imposes an additional layer of structure that is motivated by processing rather than linguistic considerations; we are no longer simply turning grammars into Prolog.
The moral is: DCGs aren’t magic. They are a nice notation, but you can’t expect to write down an arbitrary CFG as a DCG and have it run without problems. DCG rules are ordinary Prolog rules in disguise, and this means that you must pay attention to what your Prolog interpreter is going to do with them. And in particular, you have to keep an eye out for left-recursion.
A DCG for a simple formal language
As our last example, we shall define a DCG for the formal language a n b n . What is this language? And what is a formal language anyway?
A formal language is simply a set of strings. The term “formal language” is intended to contrast with the term “natural language”: whereas natural languages are languages that human beings actually use, formal languages are mathematical objects that computer scientists, logicians, and mathematicians define and study for various purposes.
A simple example of a formal language is a n b n . The words in this language are built up from two symbols: the symbol a and the symbol b . In fact, the language a n b n consists of all strings made up from these two symbols that have the following form: the string must consist of an unbroken block of a s of length n , followed by an unbroken block of b s of length n , and nothing else. So the strings ab , aabb , aaabbb and aaaabbbb all belong to a n b n . (Note that the empty string belongs to a n b n too: after all, the empty string consists of a block of a s of length zero followed by a block of b s of length zero.) On the other hand, aba and abba do not belong to a n b n .
Now, it is easy to write a context free grammar that generates this language:
| s -> ϵ |
| s -> l s r |
| l -> a |
| r -> b |
The first rule says that an s can be realised as nothing at all. The second rule says that an s can be made up of an l (for left) element, followed by an s , followed by an r (for right) element. The last two rules say that l elements and r elements can be realised as a s and b s respectively. It should be clear that this grammar really does generate all and only the elements of a n b n , including the empty string.
Moreover, it is easy to turn this grammar into DCG. We can do so as follows:
s --> []. s --> l,s,r. l --> [a]. r --> [b].
Note that the second rule is recursive (but, thankfully, not left recursive). And in fact this DCG works exactly as we would hope. For example, to the query
?- s([a,a,a,b,b,b],[]).
we get the answer yes, while to the query
?- s([a,a,a,b,b,b,b],[]).
we get the answer no. The query
?- s(X,[]).
enumerates the strings in the language, starting from [] .
