/* A parser for a grammar in Picat using tabling.
   Exercise: Write a parser in Picat for the left-recursion-free grammar:

    E -> T E'
    E' -> + T E' | - T E' | e

    T -> F T'
    T' -> * F T' | / F T' | e

    F -> ( E ) | a

    As the grammar contains no left recursion, no tabling is needed.
*/

main ?=>
    exp([a,'*','(',a,'+',a,')'],[],Tree),
    writeln(accepted),
    writeln(Tree).
main =>
    writeln(not_accepted).
    
% E -> E + T | E - T | T
table
exp(Si,So,Tree) ?=>
    exp(Si,S1,Tree1),
    S1 = ['+'|S2],
    term(S2,So,Tree2),
    Tree = $add(Tree1,Tree2).
exp(Si,So,Tree) ?=>
    exp(Si,S1,Tree1),
    S1 = ['-'|S2],
    term(S2,So,Tree2),
    Tree = $sub(Tree1,Tree2).
exp(Si,So,Tree) =>
    term(Si,So,Tree).

% T -> T * F | T / F | F
table
term(Si,So,Tree) ?=>
    term(Si,S1,Tree1),
    S1 = ['*'|S2],
    factor(S2,So,Tree2),
    Tree = $mul(Tree1,Tree2).
term(Si,So,Tree) ?=>
    term(Si,S1,Tree1),
    S1 = ['/'|S2],
    factor(S2,So,Tree2),
    Tree = $div(Tree1,Tree2).
term(Si,So,Tree) ?=>
    factor(Si,So,Tree).
    
% F -> ( E ) | a
factor([a|Si],So,Tree) => So = Si, Tree = a.
factor(['('|Si],So,Tree) =>
    exp(Si,S1,Tree),
    S1 = [')'|So].