% Implementation of an Earley parser

% Don't fail, Prolog
:- unknown(_,fail).

% Parse is the outer predicate that just takes the input and passes it on to the core.
parse(C,S1,S) :- 
	clear_chart,
	store(chart(start,S1,[C],S1)),
	process(S1),
	chart(C,S1,[],S).

% process on empty list: cut and don't even go through the rest.
process([]) :- !.

process(Position) :-
	predictor(Position),
	scanner(Position,NewPosition),
	completer(NewPosition),
	process(NewPosition).

% Enter the three magicians.

% PREDICT0R

predictor(Position) :-
	chart(_,_,[Goal|_],Position),
	predict(Goal,Position),
	fail.

predictor(_).

predict(Goal,Position) :-
	rule(Goal,[H|T]),
	store(chart(Goal,Position,[H|T],Position)),
	predict(H,Position),
	fail.

predict(Goal,Position) :-
	rule(Goal,[]),
	store(chart(Goal,Position,[],Position)),
	complete(Goal,Position,Position),
	fail.

predict(_,_).


% SCANNER

scanner([W|Words],Words) :-
	chart(C,PC,[G|Goals],[W|Words]),
	word(G,W),
	store(chart(C,PC,Goals,Words)),
	fail.

scanner([_|Words],Words).

% COMPLETER

completer(Position) :-
	chart(C,PC,[],Position),
	complete(C,PC,Position),
	fail.

completer(_).

complete(C,PC,Position) :-
	chart(C0,PC0,[C|Goals],PC),
	store(chart(C0,PC0,Goals,Position)),
	Goals== [],
	complete(C0,PC0,Position),
	fail.

complete(_,_,_).

% Exeunt

% Store values in the chart
store(chart(A,B,C,D)) :-
	\+ chart(A,B,C,D),
	asserta(chart(A,B,C,D)).

clear_chart :-
	abolish(chart/4).

increment(N,M) :-
	M is N + 1.
