Transform AST tree to another AST tree

Question

I have a simple PEG parser that generates an AST tree. Every operator is right associative, so parsing A + B + C + D returns a tree [1]. Is there a simple way to transform [1] tree to one that would be created by left associative operator [2]?

[1]  +        [2]       +
    / \                / \
   A   +              +   D
      / \            / \
     B   +          +   C
        / \        / \
       C   D      A   B

Answer 1

PEG generate right associative trees by default. You can add a post-processing step to invert it, like this:

{
    function invert(tree, acc) {
        if (acc === undefined) {
            acc = tree[0]
        }
        if (tree.length == 1) {
            return acc;
        }
        return invert(tree[2], [acc, tree[1], tree[2][0]]);
    }
}

Start
  = expr:Expression {
      return invert(expr)
  }

Expression
  = head:Integer tail:(_ "+" _ Expression)* {
      var result = [head]

      for (var i = 0; i < tail.length; i++) {
          result.push(tail[i][1])
          result.push(tail[i][3])
      }

      return result;
    }

Integer "integer"
  = [0-9]+ { return parseInt(text(), 10); }

_ "whitespace"
  = [ \t\n\r]*