Hint

The recognizer we have built is a simple (though inefficient) recognizer which carries out the algorithm sketched in class. The predicate recognize_bottomup/1 takes as input a list of symbols (for example, [vincent,shot,marsellus]) and tries to build the list [s] (that is, a sentence). Here is its definition:

recognize_bottomup([s]).
recognize_bottomup(String) :-
split(String,Front,Middle,Back),
( Cat ---> Middle
;
(Middle = [Word], lex(Word,Cat)) ),

append(Front,[Cat|Back],NewString),
recognize_bottomup(NewString).

The first clause, recognize_bottomup([s]), tells us that we have succeeded if we find the list [s]. Incidentally, if you glance down at the following clause, you will see that recognize_bottomup/1 is recursive. This first clause is the base clause of the recursion. In the second clause we have:

split(String,Front,Middle,Back)

The predicate split/4 splits a list into three parts. It is defined as follows:

split(ABC, A, B, C) :-
append(A, BC, ABC),
append(B, C, BC).

split/4 uses the standard append/3 predicate to split up the incoming list by calling it with uninstantiated varibles in the first two arguments. append/3 is called twice: The first time the incoming list is split in two parts, and the second time one of the parts is again split into two parts, resulting in three parts altogether. Unfortunately, using append/3 in this way is very inefficient.

So --- split/4 splits the string into three parts: Front, Middle, and Back. Next comes a disjunction:

Cat ---> Middle
;
(Middle = [Word], lex(Word,Cat))

It succeeds if we have either a phrase structure rule with Middle as its right hand side, or if Middle is actually a word that we can map to a category by a lexical rule.

Now for the key step. Suppose we have such a rule. Then

append(Front,[Cat|Back],NewString)

builds a new string by replacing Middle with Cat. That is, from

Front Middle Rest

we get the new string

Front Cat Rest

In short: we have used our rule right to left to build a new string.

The rest is simple. We recursively call

recognize_bottomup(NewString),

on the new string we have built. If we have a sentence on our hands, this recursion will eventually produce [s], and we will succeed using the first clause. Note that every call to recognize_bottomup/1 makes use of append/3 to decompose the input list. So, via backtracking, we will eventually find all possible ways of decomposing the input list --- thus if the input really is a sentence, we will eventually succeed in showing this.

Back to lab 2.