// file;        additiveMultiplicativeTree.rex
// author:      Robert Keller
// purpose:     Demonstrate parsing in rex
// description: See additive.rex
//              A is a parse function for additive expressions and M the
//              parse function for multiplicative expressions.
//
//                  A -> M | M + A
//
//                  M -> V | V * M
//
//                  V -> 'a' | 'b' | 'c'

FAILURE = "failure";
SUCCESS = "success";
VARS = ['a', 'b', 'c'];

A(input) = 
    Mresult = M(input),                                   // try for M
    [tree1, residue1] = Mresult,
    failed(tree1) ? Mresult                               // failure

  : residue1 == [] ? Mresult                              // use A -> M

  : first(residue1) == '+' ? 

      ( [tree2, residue2] = A(rest(residue1)),            // try A -> M + A
        failed(tree2) ? 
          Mresult                                         // use A -> M only
        : [mkTree('+', tree1, tree2), residue2]           // use A -> M + A
      )

  : Mresult;                                              // use A -> M

M(input) = 
    Vresult = V(input),                                   // try for V
    [tree1, residue1] = Vresult,
    failed(tree1) ? Vresult                               // failure

  :  residue1 == [] ? Vresult                              // use M -> V

  : first(residue1) == '*' ? 

      ( [tree2, residue2] = M(rest(residue1)),            // try M -> V * M
        failed(tree2) ? 
          Vresult                                         // use M -> V only
        : [mkTree('*', tree1, tree2), residue2]           // use M -> V + M
      )

  : Vresult;                                              // use M -> V

V([]) => [FAILURE, []];                                   // no input
V([char | chars]) => isVar(char) ? [mkTree(char), chars]; // variable
V([char | chars]) => [FAILURE, [char | chars]];           // not a variable

isVar(char) = member(char, VARS);

failed(result) = result == FAILURE;

mkTree(Var) = Var;
mkTree(Op, Tree1, Tree2) = [Op, Tree1, Tree2];

test(A(explode("a")), ['a', []]);

test(A(explode("a+b")), [['+', 'a', 'b'], []]);

test(A(explode("a+b+c")), [['+', 'a', ['+', 'b', 'c']], []]);

test(A(explode("a+b*c")), [['+', 'a', ['*', 'b', 'c']], []]);

test(A(explode("a*b+c")), [['+', ['*', 'a', 'b'], 'c'], []]);

test(A(explode("a+b+c+a")), [['+', 'a', ['+', 'b', ['+', 'c', 'a']]], []]);

test(A(explode("a*b+c+a")), [['+', ['*', 'a', 'b'], ['+', 'c', 'a']], []]);

test(A(explode("a+b*c+a")), [['+', 'a', ['+', ['*', 'b', 'c'], 'a']], []]);

test(A(explode("a+b+c*a")), [['+', 'a', ['+', 'b', ['*', 'c', 'a']]], []]);

test(A(explode("a*b*c+a")), [['+', ['*', 'a', ['*', 'b', 'c']], 'a'], []]);

test(A(explode("a*b+c*a")), [['+', ['*', 'a', 'b'], ['*', 'c', 'a']], []]);

test(A(explode("a+b*c*a")), [['+', 'a', ['*', 'b', ['*', 'c', 'a']]], []]);

test(A(explode("")), [FAILURE, []]);

test(A(explode("+")), [FAILURE, ['+']]);

test(A(explode("ab")), ['a', ['b']]);

test(A(explode("a+b+")), [['+', 'a', 'b'], ['+']]);

test(A(explode("a+b+c+")), [['+', 'a', ['+', 'b', 'c']], ['+']]);

test(A(explode("ab+c")), ['a', ['b', '+', 'c']]);

test(A(explode("a+b+")), [['+', 'a', 'b'], ['+']]);