Pereira and Shieber (1987, pp.178-185) present another kind of bottom-up parser called a left-corner parser. Given a structure such as


this parser starts with the terminal ``the'' and attempts to find the structure of which it is the left corner (i.e. the NP ``the actor''). It then attempts to find the structure of which this NP is the left corner (i.e. the whole sentence). In parsing the VP it again starts with its left-most terminal (played'') and finds the structure of which this is the left corner.

The code for the parser (based on that in Pereira and Shieber) is:

parse(Phrase, S0, S):-
     leaf(SubPhrase, S0, S1),
     lc(SubPhrase, Phrase, S1, S).	

leaf(Phrase, [Word | S], S):-
     (Phrase ===> [Word]).

lc(Phrase, Phrase, S, S).
lc(SubPhrase, SuperPhrase, S0, S):-
     (Phrase ---> [SubPhrase|Rest]),
     parse_rest(Rest, S0, S1),
     lc(Phrase, SuperPhrase, S1, S).
     
parse_rest([], S, S).
parse_rest([Phrase|Phrases], S0, S):-
     parse(Phrase, S0, S1),
     parse_rest(Phrases, S1, S).

The parser is run with the a call such as

?- parse(s, [toby,drinks,scotch], []).

Load the program, together with any BH-GRN grammar and lexicon and trace its execution.

Partially execute the parser on a grammar to produce a compiled version.

HINT: leaf/3 is the counterpart of shift/4 in the shift-reduce parser. Its compiled version should therefore be similar to the compiled version of shift/4. In the shift-reduce parser, compilation of the reduction operation results in a call to parse/4 which the first argument of the head of the clause matches a list of daughters and the the first argument of the body matches the mother. With the left-corner parser, the head of the compiled version of lc/4 will contain the left daughter of a rule, the clauses of the body will then parse the remaining daughters (see program 4.10 for ideas on how to do this) and will conclude with another call to lc/4 for the mother of the grammar rule.