% CYK recognizer

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

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

% ------------------------------------------------
% recognize(+WordList,?Startsymbol)
% top-level predicate for CYK recognizer

recognize(S,Cat) :-
   retractall(chart(_,_,_)),
   length(S,N),
   fill(0,N,S),
   chart(0,N,Cat).

%------------------------------------------------
% fill(+Current minus one,+Last,+WordList)
% Main j-loop from 1 to number of words in string.

fill(N,N,[]).
fill(JminOne,N,[W|Ws]) :-
   J is JminOne + 1,
   write(j=J),nl,
   lexical_chart_fill(J,JminOne,W),
   %
   I is J - 2,
   syntactic_chart_fill(I,J),
   %
   fill(J,N,Ws).

%------------------------------------------------
% lexical_chart_fill(+J,+JminOne,+Word)
% fill main diagonal with preterminal categories

lexical_chart_fill(J,JminOne,W) :-
   findall_unique(X,(X ---> [W]),Cats),
   add_all_to_chart(JminOne,J,Cats).

%------------------------------------------------
% syntactic_chart_fill(+I,+J)
% i-loop from J-2 down to 0

syntactic_chart_fill(-1,_) :- !.
syntactic_chart_fill(I,J) :-
   tab(4),write(i=I),nl,
   K is I+1,
   build_phrases_from_to(I,K,J),
   IminOne is I-1,
   syntactic_chart_fill(IminOne,J).

%------------------------------------------------
% build_phrases_from_to(+From,+Current,+To)

build_phrases_from_to(_,J,J) :- !.
build_phrases_from_to(I,K,J) :-
   tab(8),write(k=K),nl,
   findall_unique(A,(chart(I,K,B),
		     chart(K,J,C),
		     (A ---> [B,C])),
		  List),
   add_all_to_chart(I,J,List),
   KplusOne is K+1,
   build_phrases_from_to(I,KplusOne,J).

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

% a) only add if it does not yet exist:
add_one_to_chart(From,To,Cat) :- 
   chart(From,To,Cat), !,
   inform_user(From,To,Cat,' not added to chart since already there').

% b) add a chart entry 
add_one_to_chart(From,To,Cat) :-
   assertz(chart(From,To,Cat)),
   inform_user(From,To,Cat,'').

add_all_to_chart(_,_,[]).
add_all_to_chart(From,To,[Cat|Cats]) :-
   add_one_to_chart(From,To,Cat),
   add_all_to_chart(From,To,Cats).


inform_user(From,To,Cat,Info) :-
	tab(14),write(From),write('-'),
	write(Cat),write('-'),write(To),
	write(Info),nl.

% ------------------------------------------------
% findall_unique(+Var,+CallWithVar,-ResultList)
% Obtain the list of all call results without duplicates.
% (uses builtin predicates findall/3 and sort/3)

findall_unique(Var,Goal,UniqueResults) :-
	findall(Var,Goal,Results),
	sort(Results,UniqueResults).
