% Top-down recognizer with agenda

% Data structures: chart(From,To,Category)

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

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

recognize(String) :-
   enter_string(String,0,N,Agenda),
   FullAgenda = [chart(0,0,state(start,[s])) | Agenda], 
   fill_chart(FullAgenda,[],Chart),
   element(chart(0,N,state(start,[])),Chart).

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

enter_string([],N,N,[]).
enter_string([Word|RestString],JminOne,N,FullAgenda) :-
   J is JminOne + 1,
   findall(chart(JminOne,J,state(Cat,[])),
	   lex(Cat,Word),
	   FirstAgenda),
   enter_string(RestString,J,N,AgendaRest),
   append(FirstAgenda,AgendaRest,FullAgenda).

% ------------------------------------------------------
% enter_edges(+EdgeList,+ChartIn,-ChartOut)

enter_edges([],X,X).
enter_edges([Edge | Edges],ChartIn,ChartOut) :-
   enter_edge(Edge,ChartIn,ChartMid),
   enter_edges(Edges,ChartMid,ChartOut).

enter_edge(Edge,Chart,Chart) :-  member(Edge,Chart),!.
enter_edge(Edge,Chart,[Edge|Chart]).

% ------------------------------------------------------
% fill_chart(+Agenda,+ChartIn,-ChartOut)

fill_chart([],X,X).
fill_chart([Edge|RestAgenda],ChartIn,ChartOut) :-
		  ChartMid = [Edge|ChartIn],
		  %
		  predict(Edge,PredictAgenda),
		  complete(Edge,ChartMid,CompleteAgenda),
		  %
		  append(PredictAgenda,RestAgenda,RestPredAgenda),
		  append(RestPredAgenda,CompleteAgenda,NewAgenda),
		  %
		  fill_chart(NewAgenda,ChartMid,ChartOut).


predict(chart(_,J,state(_,[B|_])),Agenda) :- !,
		  findall(chart(J,J,state(B,Gamma)),
					 (B ---> Gamma),
					 Agenda).
predict(_,[]).


complete(chart(K,J,state(B,[])),Chart,Agenda) :- !, 
		  findall(chart(I,J,state(A,Beta)),
					 element(chart(I,K,state(A,[B|Beta])), Chart),
					 Agenda).
complete(_,_,[]).

% ------------------------------------------------------
% element(?Element,+List)

element(X,[X|_]).
element(X,[_|L]) :-
	element(X,L).

% ------------------------------------------------------
% append(+List,?List,-List) or append(-List,?List,+List) 

append([],L,L).
append([H|T],L,[H|R]) :-
		  append(T,L,R).


