The main predicate is
leftcorner_recognize/3. It takes the following arguments: 1.) the category that is to be recognized, 2.) the input string, 3.) what's left of the input string after a starting sequence that belongs to the category specified in the first argument has been cut off.
leftcorner_recognize/3 first looks up the category of the first word of the input,
WCat. It then calls
complete/4 which tries to close the hole between
WCat and
Cat.
leftcorner_recognize/3 evaluates to true, if it is possible to build a parse tree that has
Cat at its root and is spanning a prefix of the input, such that
StringOut is left.
leftcorner_recognize(Cat,[Word|StringIn],StringOut) :-
lex(Word,WCat),
complete(Cat,WCat,StringIn,StringOut).
complete/4 has four arguments: 1.)
Cat, the category that we are trying to recognize, 2.)
WCat, the category that we already have recognized (it has to be incorporated into the left part of the parse tree), 3.) the input string that has not been recognized, yet, and 4.) what is left of the input string, once we have managed to recognized
Cat.
In case the first and second argument are the same category (i.e., the category that we are trying to recognize is the same as the category that we have already found), we have completed that part of the parse tree.
complete(Cat,Cat,String,String).
If that is not the case, we need a recursive clause. This clause looks for a rule that has the second argument (the category that we have already recognized) as its left corner. It then calls
matches/3, which will try to recognize strings of the other categories on the right hand side of the rule. If that's successfull, the recursive call of
complete/4 checks whether we already managed to recognize
Cat or whether another left-corner bottom-up step has to be made to fill the hole that's left between
Cat and
LHS.
complete(Cat,SubCat,StringIn,StringOut) :-
LHS ---> [SubCat|Cats],
matches(Cats,StringIn,String1),
complete(Cat,LHS,String1,StringOut).
matches/3 finally checks whether the input begins with a certain sequence of categories and returns what's left of the input. The way it works and the way it is implemented is very similar to the
matches predicate that we saw with the top-down recognizer.
matches([],String,String).
matches([Cat|Cats],StringIn,StringOut) :-
leftcorner_recognize(Cat,StringIn,String1),
matches(Cats,String1,StringOut).
And, lastly, here is a driver predicate:
leftcorner_recognize(String) :-
leftcorner_recognize(s,String,[]).