Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
% 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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.