%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Sample Grammar:
%%
% terminal('+').
% terminal('*').
% terminal('(').
% terminal(')').
% terminal(id).
% terminal(nil).
%
% nonterminal(e).
% nonterminal(eprime).
% nonterminal(t).
% nonterminal(tprime).
% nonterminal(f).
%
% start(e).
%
% p(e,[t,eprime]).
% p(eprime,[nil]).
% p(eprime,['+',t,eprime]).
% p(t,[f,tprime]).
% p(tprime,[nil]).
% p(tprime,['*',f,tprime]).
% p(f,[id]).
% p(f,['(',e,')']).
% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% first(X,L) : Given X, a terminal or non-terminal symbol, returns L = first(X)
%% firstString(S,L) : Given a list S, a string of terminal or non-terminals, 
%%                    returns L = first(S)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
first(X,[X]) :- 
  terminal(X).
first(X,L) :- 
  \+ terminal(X), 
  setof([X,Y],p(X,Y),P), 
  processProductionsFirst(X,P,L).

processProductionsFirst(_,[],[]).
processProductionsFirst(X,[P|L],H) :- 
  setof(Z,firstS(X,P,Z),F), 
  processProductionsFirst(X,L,G), 
  union(F,G,H).
processProductionsFirst(X,[P|L],H) :- 
  \+ setof(Z,firstS(X,P,Z),_), 
  processProductionsFirst(X,L,H).

firstS(X,[X,[nil]],nil).
firstS(X,[X,[]],nil).
firstS(X,[X,[Y1]],Z) :- 
  X \== Y1,
  first(Y1,FY1), 
  member(Z,FY1).
firstS(X,[X,[Y1|_]],Z) :-  
  X \== Y1,
  first(Y1,FY1), 
  \+ member(nil,FY1), 
  member(Z,FY1).
firstS(X,[X,[Y1|_]],Z) :-  
  X \== Y1,
  first(Y1,FY1), 
  member(nil,FY1), 
  member(Z,FY1).
firstS(X,[X,[Y1|Y]],Z) :-  
  X \== Y1,
  first(Y1,FY1), 
  member(nil,FY1), 
  firstS(X,[X,Y],Z).

firstString([],[]).
firstString([X|R],F) :- 
  first(X,L), 
  member(nil,L), 
  firstString(R,RF), 
  union(L,RF,F).
firstString([X|_],L) :- 
  first(X,L), 
  \+ member(nil,L).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% follow(X,L) : Given X, a non-terminal symbol, returns L = follow(X)
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
follow(X,L) :- 
  setof(Y,followS(X,Y),L).

followS(S,'$') :- start(S).
followS(B,X) :-
  p(_,L), nonterminal(B), findBinL(B,L,Beta),
  firstString(Beta,F), member(X,F), X \== nil.
followS(B,X) :-
  p(A,L), nonterminal(B), B \== A, findBinL(B,L,Beta),
  firstString(Beta,F), member(nil,F), followS(A,X).

findBinL(B,[B],[nil]).
findBinL(B,[B|Beta],Beta) :- Beta \== [].
findBinL(B,[B|L],Beta) :- L \== [], findBinL(B,L,Beta).
findBinL(B,[C|L],Beta) :-
  B \== C, findBinL(B,L,Beta).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% predictiveParsingTable(M) : prints (and returns in M) the predictive parsing 
%% table.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
predictiveParsingTable(M) :-
  setof([X,Y],p(X,Y),P), 
  processProductionsTable1(P,M1),
  processProductionsTable2(P,M2),
  union(M1,M2,M),
  write('----------------------------------------'), nl,
  write('Predictive Parsing Table'), nl,
  write('----------------------------------------'), nl,
  printTable(M).

addToTable([],_,[]).
addToTable([nil|S],[A,L],M) :-
  addToTable(S,[A,L],M).
addToTable([X|S],[A,L],[[A,X,[A,L]]|M]) :-
  X \== nil, addToTable(S,[A,L],M).

processProductionsTable1([],[]).
processProductionsTable1([[A,L]|R],M) :-
  firstString(L,F), addToTable(F,[A,L],M1), 
  processProductionsTable1(R,M2), union(M1,M2,M).

processProductionsTable2([],[]).
processProductionsTable2([[_,L]|R],M) :-
  firstString(L,F), \+ member(nil,F), 
  processProductionsTable2(R,M).
processProductionsTable2([[A,L]|R],M) :-
  firstString(L,F), member(nil,F), follow(A,Fw), addToTable(Fw,[A,L],M1), 
  processProductionsTable2(R,M2), union(M1,M2,M).

printTable([]) :- write('----------------------------------------'), nl.
printTable([[A,X,[A,L]]|R]) :-
  write('M['),write(A), write(','), write(X), write('] = ') ,write([A,L]), nl,
  printTable(R).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Table driven predictive parsing
%% predictiveParse(Input) : prints the sequence of production rules to apply to
%% produce a top-dowm leftmost derivation parse for input W.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

predictiveParse(Input) :-
  predictiveParsingTable(M), 
  start(S),
  write('Production rules in top-down LM parse'), nl,
  write('----------------------------------------'), nl,
  pparse(Input, [S,$], M),
  write('----------------------------------------'), nl.

pparse(_,[$],_).
pparse(I,[nil|L],M) :-
  pparse(I,L,M).
pparse([A|L],[A|B],M) :-
  pparse(L,B,M).
pparse([A|_],[X|_],_) :-
  terminal(X), A \== X, write('PARSE ERROR'), nl.
pparse([A|_],[X|_],M) :-
  nonterminal(X), \+ findInM(X,A,M,_), write('PARSE ERROR'), nl.
pparse([A|L],[X|B],M) :-
  nonterminal(X), findInM(X,A,M,[X,R]), append(R,B,NewB), 
  write([X,R]), nl,
  pparse([A|L],NewB,M).

findInM(X,A,[[X,A,P]|_],P).
findInM(X,A,[[Y,_,_]|L],P) :- 
  X \== Y, findInM(X,A,L,P).
findInM(X,A,[[_,B,_]|L],P) :- 
  A \== B, findInM(X,A,L,P).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
