parser.prolog

% Representation of grammar. Nonterminals expr, term, term_tail, 
% and factor_tail are represented as non(e, _), non(t, _), non(tt, _), 
% and non(ft, _), respectively. Special nonterminal start is encoded
% as non(s, _).
% Terminals num, -, and * are represented by term(num,_), term(minus,_)
% and term(times, _). Special terminal term(eps, _) denotes the epsilon
% symbol.
% 
% Productions are represented with prod(N, [H | T]) --- that is, arguments 
% are the production index N and a list [H | T] where the head of the 
% list H is the left-hand-side of the production, and the tail of
% the list T is the right-hand-side of the production. For example,
% production expr -> term term_tail is represented as
% prod(1, [non(e, _),non(t, _),non(tt, _)]).

%% start -> expr
prod(0, [non(s, _), non(e, _)]).
%% expr -> term term_tail
prod(1, [non(e, _), non(t, _), non(tt, _)]). 
%% term_tail -> - term term_tail
prod(2, [non(tt, _), term(minus, _), non(t, _), non(tt, _)]).
%% term_tail -> epsilon
prod(3, [non(tt, _), term(eps, _)]).
%% term -> num factor_tail
prod(4, [non(t, _), term(num, _), non(ft, _)]).
%% factor_tail -> * num factor_tail
prod(5, [non(ft, _), term(times, _), term(num, _), non(ft, _)]).
%% factor_tail -> epsilon
prod(6, [non(ft, _), term(eps, _)]).

% LL(1) Parsing table.
% predict(non(s, _), term(num, _), 0) stands for "on start and num, predict 
% production 0. start -> expr"
% predict(non(e, _), term(num, _), 1) stands for "on nonterminal expr and
% terminal num, predict production 1. expr -> term term_tail".

predict(non(s, _), term(num, _), 0).
predict(non(e, _), term(num, _), 1).
predict(non(tt, _), term(end_of_input, _), 3).
predict(non(tt, _), term(minus, _), 2).
predict(non(t, _), term(num, _), 4).
predict(non(ft, _), term(end_of_input, _), 6).
predict(non(ft, _), term(minus, _), 6).
predict(non(ft, _), term(times, _), 5).


% sample inputs
input0([3, -, 5]).
input1([3, -, 5, *, 7, -, 18]).


% Write transform(L, R): it takes input list L and transforms it into a
% list where terminals are represented with term(...). The transformed 
% list will be computed in unbound variable R.
% E.g., transform([3, -, 5], R).
% R = [term(num, 3), term(minus, _), term(num, 5)]

determine_terminal(Input, Terminal, Value) :-
                  (Input == *, Terminal = times, Value = _);
                  (Input == -, Terminal = minus, Value = _);
                  (\+Input == *, \+Input == -, Terminal = num, Value = Input).

transform([], []).
transform([L | Tail], R) :-
          transform(Tail, R1),
          determine_terminal(L, Terminal, Value),
          R = [term(Terminal, Value) | R1].

% You will write parseLL(L, ProdSeq): it will take a transformed 
% list R and will produce the production sequence applied by 
% the predictive parser.
% E.g., input0(L), transform(L, R), parseLL(R, ProdSeq).
% ProdSeq = [0, 1, 4, 6, 2, 4, 6, 3].

parseLL1(ProdSeq, [], []).
parseLL1(ProdSeq, [InputHead | InputTail], [StackHead | StackTail]) :-
         (predict(Meow1, InputHead, ProdNum1),
          predict(Meow2, StackHead, ProdNum2),
          ProdNum1 == ProdNum2,
          parseLL1(ProdSeq, InputTail, StackTail));
         (predict(StackHead, InputHead, ProductionNum),
          write('ProductionNum: '),
          write(ProductionNum), nl,
          prod(ProductionNum, [Production | Result]),
          append(Result, [StackHead | StackTail], Stack1),
          parseLL1(ProdSeq1, [InputHead | InputTail], Stack1)),
         ProdSeq = [Production | ProdSeq1].

parseLL([R | Tail], ProdSeq) :-
        predict(NonTerm, R, ProductionNum),
        prod(ProductionNum, [Production | Result]),
        parseLL1(ProdSeq, [R | Tail], Result).

% Later you will augment parseLL with the computation of
% the expression value.
% E.g., input0(L), transform(L, R), parseLL(R, ProdSeq, V).
% ProdSeq = [0, 1, 4, 6, 2, 4, 6, 3],
% V = -2.