%% Model solution to tutorial 6
%% James Cheney
%% Nov 5 2009

%%% Part 1
%% Here's a mechanical translation

s(L0,L) :- t(L0,L1), u(a,L1,L2), v(L2,L).
t(L0,L) :- L0 = [a|L1], u(c,L1,L2), L2 = [b|L].
u(_,L0,L) :- L0 = L.
u(X,L0,L) :- L0 = [X|L1], L1 = [X|L].
v(L0,L) :- L0 = [a|L].
v(L0,L) :- L0 = [a|L1], v(L1,L).

%% Here's an optimized translation
s0(L0,L) :- t0(L0,L1), u0(a,L1,L2), v0(L2,L).
t0([a|L1],L) :- u0(c,L1, [b|L]).
u0(_,L,L).
u0(X,[X,X|L],L).
v0([a|L],L).
v0([a|L1],L) :- v0(L1,L).

%% Part 2(a)
%% Actually, v above almost does this already.

astar --> [].
astar --> [a],astar.

%% Part 2(b).
star(_) --> [].
star(X) --> [X],star(X).


%% Part 3
%% (a): Naive grammar for fully parenthesized expressions

exp --> [N], {number(N)}.
exp --> ['('], exp, ['+'], exp,  [')'].
exp --> ['('], exp, ['-'], exp,  [')'].
exp --> ['('], exp, ['*'], exp,  [')'].
exp --> ['('], exp, ['/'], exp,  [')'].
exp --> ['('], exp, ['^'], [N],  [')'], {number(N)}.

%%(b): Naive grammar with evaluation

exp(N) --> [N], {number(N)}.
exp(V) --> ['('], exp(V1), ['+'], exp(V2),  [')'], {V is V1+V2}.
exp(V) --> ['('], exp(V1), ['-'], exp(V2),  [')'], {V is V1-V2}.
exp(V) --> ['('], exp(V1), ['*'], exp(V2),  [')'], {V is V1*V2}.
exp(V) --> ['('], exp(V1), ['/'], exp(V2),  [')'], {V is V1/V2}.
exp(V) --> ['('], exp(V1), ['^'], [N],  [')'], {number(N)}, {V is exp(V1,N)}.

%%(c): Precedence parsing

prec_exp(V) --> plusminus_exp(V).

plusminus_exp(V) --> timesdiv_exp(V1), ['+'], plusminus_exp(V2), {V is V1+V2}.
plusminus_exp(V) --> timesdiv_exp(V1), ['-'], plusminus_exp(V2), {V is V1-V2}.
plusminus_exp(V) --> timesdiv_exp(V).

timesdiv_exp(V) --> power_exp(V1), ['*'], timesdiv_exp(V2), {V is V1*V2}.
timesdiv_exp(V) --> power_exp(V1), ['/'], timesdiv_exp(V2), {V is V1/V2}.
timesdiv_exp(V) --> power_exp(V).

power_exp(V) --> basic_exp(V1), ['^'], [N], {number(N),V is exp(V1,N)}.
power_exp(V) --> basic_exp(V).

basic_exp(N) --> [N], {number(N)}.
basic_exp(V) --> ['('], prec_exp(V), [')'].
