7.1.1 CFG recognition using append

That's the theory, but how do we work with context free grammars in Prolog? To make things concrete: suppose we are given a context free grammar. How can we write a recognizer for it? And how can we write a parser for it? This week we'll look at the first question in detail. We'll first show how (rather naive) recognizers can be written in Prolog, and then show how more sophisticated recognizers can be written with the help of difference lists. This discussion will lead us to definite clause grammars, Prolog's inbuilt grammar tool. Next week we'll look at definite clause grammars in more detail, and learn (among other things) how to use them to define parsers.

So: given a context free grammar, how do we define a recognizer in Prolog? In fact, Prolog offers a very direct answer to this question: we can simply write down Prolog clauses that correspond, in an obvious way, to the grammar rules. That is, we can simply `turn the grammar into Prolog'.

Here's a simple (though as we shall learn, inefficient) way of doing this. We shall use lists to represent strings. For example, the string a woman shoots a man will be represented by the list  [a,woman,shoots,a,man]. Now, we have already said that the -> symbol used in context free grammars means can consist of, or can be built out of, and this idea is easily modeled using lists. For example, the rule s -> np vp can be thought of as saying: a list of words is an s list if it is the result of concatenating an np list with a vp list. As we know how to concatenate lists in Prolog (we can use append), it should be easy to turn these kinds of rules into Prolog. And what about the rules that tell us about individual words? Even easier: we can simply view n -> woman as saying that the list [woman] is an n list.

If we turn these ideas into Prolog, this is what we get:

s(Z) :- np(X), vp(Y), append(X,Y,Z).
 
np(Z) :- det(X), n(Y), append(X,Y,Z).
 
vp(Z) :-  v(X), np(Y), append(X,Y,Z).
 
vp(Z) :-  v(Z).
 
det([the]).
det([a]).
 
n([woman]).
n([man]).
 
v([shoots]).

The correspondence between the CFG rules and the Prolog should be clear. And to use this program as a recognizer, we simply pose the obvious queries. For example:

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

In fact, because this is a simple declarative Prolog program, we can do more than this: we can also generate all the sentences this grammar produces. In fact, our little grammar generates 20 sentences. Here are the first five:

s(X).
 
X = [the,woman,shoots,the,woman] ;
 
X = [the,woman,shoots,the,man] ;
 
X = [the,woman,shoots,a,woman] ;
 
X = [the,woman,shoots,a,man] ;
 
X = [the,woman,shoots]

Moreover, we're not restricted to posing questions about sentences: we can ask about other grammatical categories. For example:

np([a,woman]).
yes

And we can generate noun phrases with the following query.

np(X).

Now this is rather nice. We have a simple, easy to understand program which corresponds with our CFG in an obvious way. Moreover, if we added more rules to our CFG, it would be easy to alter the program to cope with the new rules.

But there is a problem: the program doesn't use the input sentence to guide the search. Make a trace for the query s([a,man,shoots]) and you will see that the program ``guesses'' noun phrases and verb phrases and then afterwards checks whether these can be combined to form the sentence [a,man,shoots]. Prolog will find that [the,woman] is a noun phrase and [shoots,the,woman] a verb phrase and then it will check whether concatenating these two lists happens to yield [a,man,shoots], which of course fails. So, Prolog starts to backtrack and the next thing it will try is whether concatenating the noun phrase [the,woman] and the verb phrase [shoots,the,man] happens to yield [a,man,shoots]. It will go on like this until it finally produces the noun phrase [the,man] and the verb phrase [shoots]. The problem obviously is, that the goals np(X) and vp(Y) are called with uninstantiated variables as arguments.

So, how about changing the rules in such a way that append becomes the first goal:

s(Z) :- append(X,Y,Z), np(X), vp(Y).
 
np(Z) :- append(X,Y,Z), det(X), n(Y).
 
vp(Z) :-  append(X,Y,Z), v(X), np(Y).
 
vp(Z) :-  v(Z).
 
det([the]).
det([a]).
 
n([woman]).
n([man]).
 
v([shoots]).

Now, we first use append to split up the input list. This instantiates the varibales X and Y, so that the other goals are all called with instantiated arguments. However, the program is still not perfect: it uses append a lot and, even worse, it uses append with uninstantiated variables in the first two arguments. We saw in the previous chapter that that is a source of inefficiency. And indeed, the performance of this recognizer is very bad. It is revealing to trace through what actually happens when this program analyses a sentence such as a woman shoots a man. As you will see, relatively few of the steps are devoted to the real task of recognizing the sentences: most are devoted to using append to decompose lists. This isn't much of a problem for our little grammar, but it certainly would be if we were working with a more realistic grammar capable of generating a large number of sentences. We need to do something about this.