7.2.2 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: we need simply use recursive rules. Here's an example. Let's add the following rules to our little grammar:

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.

It is easy to turn this grammar into DCG rules. In fact, we just need to add the rules

s --> s,conj,s.
 
conj --> [and].
conj --> [or].
conj --> [but].

But what does Prolog do with a DCG like this? Let's have a look.

First, let's add the 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 gets into an infinte 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)... In short, it goes into infinite loop and does no useful work.

Second, let's add the recursive rule s --> s,conj,s at the end of the knowledge base, so that Prolog always ecounters the translation of the non-recursive rule first. What happens now, when we pose the query s([a,woman,shoots],[])? Well, Prolog seems to be able to handle it and gives an anwer. But what happens when we pose the query s([woman,shoot],[]), i.e. an ungrammatical sentence that is not accepted by our grammar? Prolog again gets into an infinite loop. Since, it is impossible to recognize [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 loop as before.

Notice, that we are having the same problems that we had when we were changing the order of the rules and goals in the definition of descend in the chapter on recursion. In that case, the trick was to change the goals of the recursive rule so that the recursive goal was not the first one in the body of the rule. In the case of our recursive DCG, however, this is not a possible solution. Since the order of the goals determines the order of the words in the sentence, we cannot change it just like that. It does make a 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).

So, by just reordering clauses or goals, we won't solve the problem. The only possible solution is to introduce a new nonterminal symbol. 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].

Make sure that you understand why Prolog doesn't get into infinite loops with this grammar as it did with the previous version.

The moral is: DCGs aren't magic. They are a nice notation, but you can't always expect just to `write down the grammar as a DCG' and have it work. DCG rules are really ordinary Prolog rules in disguise, and this means that you must pay attention to what your Prolog interpreter does with them.