% Earley recognizer (without any tracing output)

% Data structures: chart(From,To,Category)
:- dynamic chart/3.

% Operator for grammar rules
:- op(1200,xfx,'--->'). 

% ------------------------------------------------------
% recognize(+WordList)
% top-level predicate for Earley recognizer

recognize(String) :-
   retractall(chart(_,_,_)),
   enter_edge(0,0,state(start,[s])),
   foreach((get_word(Word,JminOne,J,String),
	    lex(Cat,Word)),
	   enter_edge(JminOne,J,state(Cat,[]))),
   length(String,N),
   chart(0,N,state(start,[])).

% ------------------------------------------------------
% enter_edge(+FromIndex,+ToIndex,+Contents)

% a) only add if it does not yet exist:
enter_edge(I,J,State) :- chart(I,J,State), !.

% b) add to chart and make try prediction/completion
enter_edge(I,J,State) :-
   assertz(chart(I,J,State)),
   predict(I,J,State),
   complete(I,J,State).

% ------------------------------------------------------

predict(_,J,state(_,[B|_])) :- !,
   foreach((B ---> Gamma),
	   enter_edge(J,J,state(B,Gamma))).
predict(_,_,_).

% ------------------------------------------------------

complete(K,J,state(B,[])) :- !,
   foreach(chart(I,K,state(A,[B|Beta])),
	   enter_edge(I,J,state(A,Beta))).
complete(_,_,_).

% ------------------------------------------------------
% get_word(-Element,-JminOne,J,+List)

get_word(Word,0,1,[Word|_]).
get_word(Word,JminOne,J,[_|L]) :- 
	get_word(Word,_,JminOne,L), 
	J is JminOne+1.

% ------------------------------------------------------
% foreach(+Goal1,+Goal2)
% loop over all solutions of Goal1 with Goal2
% Goal1 is assumed to have alternative solutions, Goal2 not

foreach(X,Y) :- X, Y, fail.
foreach(_,_).
