%% Description: Code for Chart Parsing based on the Earley Algorithm   %%
%% Writer:  Minhaeng Lee                                                                    %%
%% °ü·Ã¼º: Á¦ 3Àå                                                                              %%
%% Name: kchart.pl                                                                              %%


:- consult('epsg.pl').
:- op(1200,xfx,--->).

chart(W) :- clearmem,
            initialize,
            loop(0,0),
            construct(0,W),
            output_m.

initialize :- foreach(production(s,Alpha),assertz(item(0,0,s,[],Alpha))).
construct(_,[]).
construct(I,[H|T]) :- J is I+1,
                      scanner(I,J,H),
                      loop(J,0),
                      construct(J,T).
scanner(I,J,H) :- foreach(item(N,I,B,Alpha,[H|Beta]),
                  doassert(N,J,B,Alpha+H,Beta)).

loop(J,Old) :- completer(J),
               predictor(J),
               stillmore(New,Old),
               loop(J,New).
loop(_,_).
completer(J) :- foreach(item(I,J,A,_,[]),
                   foreach(item(K,I,B,Omega,[A|Beta]),
                       doassert(K,J,B,Omega+A,Beta))).
predictor(J) :- foreach(item(_,J,_,_,[B|_]),
                   foreach(production(B,Omega),
                     doassert(J,J,B,[],Omega))).
clearmem :- retract(item(_,_,_,_,_)), fail.
clearmem :- assertz(item(i,j,dom,proof,activ)).

production(Left,Right) :- (Left --->  Right).

foreach(X,Y) :- X, do(Y), fail.
foreach(_,_).
do(Y) :- Y, !.
output_m :- foreach(item(A,B,C,D,E), writeln(item(A,B,C,D,E))).
% writeln(X) :- write(X), nl.
doassert(N,J,B,[],Beta) :- item(N,J,B,[],Beta).
doassert(N,J,B,[],Beta) :- assertz(item(N,J,B,[],Beta)).
doassert(N,J,B,Alpha+H,Beta) :- append(Alpha,[H],Proofed),
                                 item(N,J,B,Proofed,Beta).
doassert(N,J,B,Alpha+H,Beta) :- append(Alpha,[H],Proofed),
                                 assertz(item(N,J,B,Proofed,Beta)).
stillmore(New,Old) :- findall(Dummy,item(Dummy,_,_,_,_),Tmpl),
                      lenacc(Tmpl,0,New),
                      New > Old.
lenacc([],N,N).
lenacc([_|T],Acc,N) :- NewAcc is Acc+1, lenacc(T,NewAcc,N).