// file:        additiveTree.rex
// author:      Robert Keller
// purpose:     Demonstrate parsing in rex
// description: A is a parse function that scans a list of characters from
//              left to right to see if that list, as a string, could
//              be derived from the following grammar:
//
//                  A -> V | V + A
//
//                  V -> 'a' | 'b' | 'c'

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

A(input) = 
    Vresult = V(input),                                   // try for V

    [tree1, residue1] = Vresult,                          // separate

    failed(tree1) ? Vresult                               // V failed

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

  : first(residue1) == '+' ?                              // see if '+' follows

      ( 
        [tree2, residue2] = A(rest(residue1)),            // try A -> V + A

        failed(tree2) ? Vresult                           // use A -> V only

      : [mkTree('+', tree1, tree2), residue2]             // use A -> V + A

      )

  : Vresult;                                              // use A -> 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")), [['+', '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'], ['+']]);