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).

1998-09-25