A head-corner parser

The main omission of the following version of the head-corner parser is the administration concerning the well-formed substring table, packing and the possibility of rules with an empty right hand side. In the head-corner parser used in the experiment the parse predicate and the head-corner predicate are memo-ized. Furthermore items for the parse forest are asserted in the head-corner predicate. Finally some special arrangements are made to allow for rules with an empty right hand side, by allowing underspecification of the string position in the comparison predicates.

The relation hc_table(Cat,P0,P,Goal,Q0,Q) implements the head-corner table. If P0=Q0 the phrase is head-initial; if P=Q the phrase is head-final. Rules and lexical entries are represented as before.

% parse(Cat,P0,P,E0,E) if there is 
% Cat from P0 to P, within range E0,E
parse(Goal,P0,P,E0,E) :-
   predict(Goal,P0,P,Lex,Q0,Q,E0,E), 
   head_corner(Lex,Q0,Q,Goal,P0,P,E0,E).

% head_corner(Cat,C0,C,Goal,G0,G,E0,E)
% if Cat from C0 to C is a head-corner of 
% Goal from G0 to G within E0 to E.
head_corner(Cat,Q0,Q,Cat,Q0,Q,_,_).
head_corner(Small,Q1,Q2,Goal,P0,P,E0,E) :-
   rule(Small,Mid,Left,Right),
   left(Left,Q0,Q1,E0), 
   right(Right,Q2,Q,E),
   hc_table(Mid,Q0,Q,Goal,P0,P), 
   head_corner(Mid,Q0,Q,Goal,P0,P,E0,E).

% predict(Goal,P0,P,Lex,Q0,Q,E0,E) 
% if Lex from Q0 to Q may be head-corner 
% of Goal from P0 to P within E0, E.
predict(Goal,P0,P,Lex,Q0,Q,E0,E) :-
   hc_table(Lex,Q0,Q,Goal,P0,P), 
   lex(Lex,Q0,Q), 
   E0 =< Q0, 
   Q =< E.

% left(Ds,P0,P,E0) if (reversed) Ds exist 
% from P to P0 with left-extreme E0
left([],P,P,_).
left([H|T],P0,P,E0) :- 
   parse(H,P1,P,E0,P), 
   left(T,P0,P1,E0).

% right(Ds,P0,P,E) if Ds exist from 
% P0 to P with right-extreme E
right([],P,P,_).
right([H|T],P0,P,E):- 
   parse(H,P0,P1,P0,E), 
   right(T,P1,P,E).