%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                           %
%       file:           lc.pl                                               %
%       purpose:        to illustrate termination problems of lc parsers    %
%       author:         Sebastian Varges                                    %
%       date:           Tue Sep 10 11:01:05 MET DST 1996                    %
%       related refs:   [Covington 94]                                      %
%                                                                           %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% left-corner parser from [Covington 94]:

parse(C,[Word|S2],S) :-
	word(W,Word),
	link(W,C),
	complete(W,C,S2,S).

parse(C,S2,S) :-
	rule(W,[]),
	link(W,C),
	complete(W,C,S2,S).

parse_list([C|Cs],S1,S) :-
	parse(C,S1,S2),
	parse_list(Cs,S2,S).

parse_list([],S,S).

complete(C,C,S,S).
complete(W,C,S1,S) :-
	rule(P,[W|Rest]),
	parse_list(Rest,S1,S2),
	complete(P,C,S2,S).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% In [NLP for Prolog programmers(1994,p.162-165)] Covington describes how
% links inferred from a grammar help a left-corner parser to 
% handle null constituents if it is not the grammar itself which
% defines an infinite number of parses. 

% This simple grammar causes the lc parser to loop
% (the rules are given in the format of [Covington 94]):

rule(s,[x,y]).     % s --> x,y.
rule(y,[x]).       % y --> x.   %% this causes the problem
rule(x,[]).        % x --> 0.

word(x,w1).
word(y,w2).

% links inferred the grammar:
link(x,s).
link(x,y).         %% this causes the problem
link(X,X).

% This grammar defines five strings: [],[w1],[w2],[w1,w1] and [w1,w2].
% The parser is only able to handle [w2] and [w1,w2]. Parsing
% the other strings (and all ungrammatical ones) causes the parser
% to loop.  

% For example, given the goal parse(s,[],[]). the parser makes
% the following steps and does not fail finitely. No backtracking
% is involved:
/*
% example trace:
{trace}
| ?- parse(s,[],[]).
   1  1  Call: parse(s,[],[]) ?   % parse s as empty element
   2  2  Call: rule(_337,[]) ?    % find rule which defines empty element
   2  2  Exit: rule(x,[]) ?       % rule `x --> 0' found
   3  2  Call: link(x,s) ?     
   3  2  Exit: link(x,s) ?        % link relation holds
   4  2  Call: complete(x,s,[],[]) ? 
   5  3  Call: rule(_1261,[x|_1259]) ? % find rule x is a left corner of
   5  3  Exit: rule(s,[x,y]) ?         % rule `s --> x,y' found
   6  3  Call: parse_list([y],[],_1254) ? % remaining dtr: y
   7  4  Call: parse(y,[],_1830) ?     % parse y as empty element
   8  5  Call: rule(_2041,[]) ? 
   8  5  Exit: rule(x,[]) ?       % rule `x --> 0' defines empty element ...
   9  5  Call: link(x,y) ?  
   9  5  Exit: link(x,y) ?        % ... and is linked to y
   10  5  Call: complete(x,y,[],_1830) ? 
   11  6  Call: rule(_2965,[x|_2963]) ? % find rule x is a left corner of 
   11  6  Exit: rule(s,[x,y]) ?         % rule `s --> x,y' found (= 5)
   12  6  Call: parse_list([y],[],_2958) ? % remaining dtr: y (= 6)
   13  7  Call: parse(y,[],_3534) ?     % parse y as empty element (= 7)
   14  8  Call: rule(_3745,[]) ? 
   14  8  Exit: rule(x,[]) ?      % rule `x --> 0' defines empty element ... (= 8)
   15  8  Call: link(x,y) ? 
   15  8  Exit: link(x,y) ?       % ... and is linked to y (= 9) 
   16  8  Call: complete(x,y,[],_3534) ? 
   17  9  Call: rule(_4669,[x|_4667]) ?     % find rule x is a left corner of 
   17  9  Exit: rule(s,[x,y]) ?             % rule `s --> x,y' found (= 5, = 11)
   18  9  Call: parse_list([y],[],_4662) ?  % remaining dtr: y (= 6, = 12)
   19  10  Call: parse(y,[],_5238) ? n
Prolog interruption (h for help)? a
{Execution aborted}
*/
% A parsed constituent `x' can be used to complete two grammar rules:
% `s --> x,y' and `y --> x'. Here the parser always tries to complete
% the first one, so there's always a `y' left to be parsed. If the ordering of
% these grammar rules is changed, the problem occurs when backtracking is used
% (`?- parse(s,[],[]),fail.' does not fail finitely).