% Earley recognizer (with tracing output, 
% for pure algorithm see basic_earley.pl)

% Data structures: chart(From,To,Category,Edge-number)
:- dynamic chart/4, edge_nr/1.

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

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

recognize(String) :-
   retractall(chart(_,_,_,_)),
   retractall(edge_nr(_)),
   assert(edge_nr(1)),
   format('START:',[]),
   enter_edge(0,0,state(start,[s])),
   foreach(get_word(Word,JminOne,J,String),
	   (format('~NSCAN ~w (~w):',[J,Word]),
	   enter_edge(JminOne,J,state(Word,[])))),
   length(String,N),
   chart(0,N,state(start,[]),Nr),
   format('SUCCESS: ~w',[Nr]).

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

% a) only add if it does not yet exist:
enter_edge(I,J,State) :- 
	chart(I,J,State,Nr), !,
	format('~t~18|~w~|-~w~`-t~21+~w not added since already in chart as ~w~n',[Nr, I,State,J]).

% b) add to chart and make try prediction/completion
enter_edge(I,J,State) :-
   retract(edge_nr(M)), N is M+1, assert(edge_nr(N)),
   assertz(chart(I,J,State,M)),
   format('~t~18|~t~w:~3+ ~w~|-~w~`-t~21+~w~n',[M,I,State,J]),
   predict(I,J,State,M),
   complete(I,J,State,M).

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

predict(_,J,state(_,[B|_]),M) :- !,
   foreach((B ---> Gamma),
	   (format('~NPRED ~w in ~w:',[B,M]),
            enter_edge(J,J,state(B,Gamma)))).
predict(_,_,_,_).

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

complete(K,J,state(B,[]),M) :- !,
   foreach(chart(I,K,state(A,[B|Beta]),N),
	   (format('~NCOMP ~w + ~w:',[N,M]),
           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(_,_).
