A head-driven chart parser

The main omission consists of the administration concerning the packed items, for the recovery of parse-trees. Also this version assumes that no empty productions occur in the grammar.

Rules are of the form rule(Head, LHS, LeftDs, RightDs), where LeftDs is in reversed order. The predicate lex(Cat,P0,P) is true if the word connecting the positions P0 and P has category Cat.

The chart consists of (dynamically asserted) facts of the form item(Cat,ToParse,P0,P), indicating that if there is a list of categories ToParse from position P to Q then there is category Cat from position P0 to Q. The predicate assertz_check is used to asserts such items. That predicate asserts its argument only if no more general clause exists; furthermore it deletes all more specific clauses.

% scan(+P0,+P) parses from P0 to P, 
% P is current position
scan(P,P).
scan(P0,P) :- 
   P1 is P0 + 1, 
   ( lex(Cat,P0,P1), 
     add_item(Cat,[],P0,P1), 
     fail 
   ; scan(P1,P) 
   ).

% add_item(+Cat,+ToParse,+Begin,+End)
% asserts item and computes all its 
% consequences, if inactive item
add_item(Cat,[],B,E) :- 
   assertz_check(item(Cat,[],B,E)), 
   closure(Cat,B,E).
add_item(Cat,[H|T],B,E) :- 
   assertz_check(item(Cat,[H|T],B,E)).

% closure(+Cat,+Begin,+End)
% computes all the items on basis 
% of item Cat from Begin to End
closure(Cat,P1,P) :-
   item(Lhs,[Cat|ToParse],P0,P1), 
   add_item(Lhs,ToParse,P0,P), 
   fail.
closure(Cat,P1,P) :-
   rule(Cat,Lhs,Left,Right), 
   left(Left,P0,P1), 
   add_item(Lhs,Right,P0,P), 
   fail.
closure(_,_,_).

% left(+Ds,?Begin,+End) if there are Ds 
% from right from Begin to End
left([],B0,B0).
left([D|Ds],B0,E) :- 
   item(D,[],B,E), 
   left(Ds,B0,B).