How do you build an AST (Abstract Syntax Tree) for left-associative operators using PEG.js?

I've tried to write some code based on the information I found on the internet, but I seem to have made a mistake.

The code I wrote generates an incorrect AST for most expressions.

Expression

12-6-4-2*1-1

Expected AST

{
    "left": {
        "left": {
            "left": {
                "left": 12,
                "operator": "-",
                "right": 6
            },
            "operator": "-",
            "right": 4
        },
        "operator": "-",
        "right": {
            "left": 2,
            "operator": "*",
            "right": 1
        }
    },
    "operator": "-",
    "right": 1
}

Generated AST

{
   "left": {
      "left": {
         "left": 12,
         "operator": "-",
         "right": 6
      },
      "operator": "-",
      "right": 4
   },
   "operator": "-",
   "right": {
      "left": 2,
      "operator": "*",
      "right": {
         "left": 1,
         "operator": "-",
         "right": 1
      }
   }
}

Code

{

    function operator(first, rest) {
        if (rest.length === 0) return first;

        return { left: first, right: rest };
    };

    function makeOperator(left, operator, right) {
        return { left: left, operator: operator[0], right: clean(right[1]) };
    };

    function clean(expression) {
        if (!expression.right) return expression;

        var result = makeOperator(expression.left, expression.right[0], expression.right[0]);

        for (var counter = 1, len = expression.right.length; counter < len; counter++) {
            result = makeOperator(result, expression.right[counter], expression.right[counter]);
        }

        return result;
    };

}

Start = E

E
  = expression:E1

    { return clean(expression); }

E1
  = expression:E2 rest:(("+" / "-") E2)*

    { return operator(expression, rest); }

E2
  = expression:Value rest:(("*" / "/") E1)*

    { return operator(expression, rest); }


Value
  = Number
  / BracketedExpression

Number
  = [1-9][0-9]*

    { return parseInt(text(), 10); }

BracketedExpression
  = "(" expression:E1 ")"

    { return expression; }

I would really appreciate any help or example code on how to build ASTs for both left-associative and right-associative operators.

Edit: As @Bergi pointed out, the problem was that E2 used E1 as the expression for the rest of the operator list instead of Value. However, the code that Bergi wrote is much simpler than mine.

How do you build an AST (Abstract Syntax Tree) for left-associative operators using PEG.js?

I've tried to write some code based on the information I found on the internet, but I seem to have made a mistake.

The code I wrote generates an incorrect AST for most expressions.

Expression

12-6-4-2*1-1

Expected AST

{
    "left": {
        "left": {
            "left": {
                "left": 12,
                "operator": "-",
                "right": 6
            },
            "operator": "-",
            "right": 4
        },
        "operator": "-",
        "right": {
            "left": 2,
            "operator": "*",
            "right": 1
        }
    },
    "operator": "-",
    "right": 1
}

Generated AST

{
   "left": {
      "left": {
         "left": 12,
         "operator": "-",
         "right": 6
      },
      "operator": "-",
      "right": 4
   },
   "operator": "-",
   "right": {
      "left": 2,
      "operator": "*",
      "right": {
         "left": 1,
         "operator": "-",
         "right": 1
      }
   }
}

Code

{

    function operator(first, rest) {
        if (rest.length === 0) return first;

        return { left: first, right: rest };
    };

    function makeOperator(left, operator, right) {
        return { left: left, operator: operator[0], right: clean(right[1]) };
    };

    function clean(expression) {
        if (!expression.right) return expression;

        var result = makeOperator(expression.left, expression.right[0], expression.right[0]);

        for (var counter = 1, len = expression.right.length; counter < len; counter++) {
            result = makeOperator(result, expression.right[counter], expression.right[counter]);
        }

        return result;
    };

}

Start = E

E
  = expression:E1

    { return clean(expression); }

E1
  = expression:E2 rest:(("+" / "-") E2)*

    { return operator(expression, rest); }

E2
  = expression:Value rest:(("*" / "/") E1)*

    { return operator(expression, rest); }


Value
  = Number
  / BracketedExpression

Number
  = [1-9][0-9]*

    { return parseInt(text(), 10); }

BracketedExpression
  = "(" expression:E1 ")"

    { return expression; }

I would really appreciate any help or example code on how to build ASTs for both left-associative and right-associative operators.

Edit: As @Bergi pointed out, the problem was that E2 used E1 as the expression for the rest of the operator list instead of Value. However, the code that Bergi wrote is much simpler than mine.

• javascript
• grammar
• abstract-syntax-tree
• peg
• pegjs

• Can you please explain what that function clean is supposed to do? – Bergi Commented Jun 14, 2014 at 22:27
• @Bergi clean takes an expression array and transform it into an AST. If you change it to just return expression;, you will see what the expression is. – Toothbrush Commented Jun 14, 2014 at 23:25
• OK, now that I've written an answer I understand its purpose. However, you apply clean as a recursive post-processing transformation, you'd better call it from operator() and not from makeOperator() (and omit the E step entirely). That did confuse me a bit. – Bergi Commented Jun 14, 2014 at 23:54

2 Answers 2

Right-associative operators are relatively trivial to write, since they can be parsed "natively" recursive:

E2
  = l:Value op:("*" / "/") r:E2
    { return {left:l, operator:op, right:r}; }
  / Value

// or equivalently (but more efficiently):

E2
  = l:Value r:(("*" / "/") E2)?
    { if (!r) return l;
      return {left:l, operator:r[0], right:r[1]}
    }

We can translate the grammar for left-associative operators respectively:

// [Do not use]
E1
  = l:E1 op:("-" / "+") r:E2
    { return {left2:l, operator:op, right2:r}; }
  / E2

but all we get from this is an error Left recursion detected for rule "E1". Indeed, PEG are not capable of left recursion rules, but Wikipedia tells us how to counter this: we will need to unroll the recursion into a * loop. You already did this, but put the parenthesis differently. They should match the recursive definition above, with the single E2 on the right:

E1
  = ls:(E2 ("+" / "-"))* r:E2

so that we can build the tree from the s easily with a recursive helper function:

    { return leftAssociative(ls, r); }

    function leftAssociative(ls, r) {
        if (!ls.length) return r;
        var last = ls.pop();
        return {left:leftAssociative(ls, last[0]), operator:last[1], right:r};
    }

Alternatively, you can use a loop, which best matches the bracketing with the loop on the right side:

E1
  = l:E2 rs:(("+" / "-") E2)*
    { var e = l;
      for (var i=0; i<rs.length; i++)
          e = {left:e, operator:rs[i][0], right:rs[i][1]};
      return e;
    }

For reference, here is the complete parser:

{ 
    function leftAssoc(rest, val) {
        if (!rest.length) return val;
        var last = rest.pop();
        return {left:leftAssoc(rest, last[0]), operator:last[1], right:val};
    }
    function rightAssoc(val, rest) {
        if (!rest.length) return val;
        var first = rest.shift();
        return {left:val, operator:first[0], right:rightAssoc(first[1], rest)};
    }
}

Start = E1
 
E1 = rest:(E2 ("+" / "-"))* v:E2
     { return leftAssoc(rest, v); }

E2 = v:Value rest:(("*" / "/") Value)*
     { return rightAssoc(v, rest); }

Value = Number
      / BracketedExpression

Number = [1-9][0-9]*
         { return parseInt(text(), 10); }

BracketedExpression = "(" expression:E1 ")"
                      { return expression; }

Here is a way to achive this while leverging modern Javascript.

The example below, uses Array.reduce, an arrow function and object spread syntax to achieve what is essentially a one liner.

Start 
  = head:E1 tail:(a:"->" b:E2 {return {operator:a, right:b}})* 
  {return tail.reduce((t,h) => ({...h, left:t}), head)}

// example expressions for operands ...
// (assuming non-commutative operator)
E1 = [pqr]
E2 = [xyz]

// input of: `p->y->z`
// results in output:
/*
```json
{
    "operator": "->",
    "right": "z",
    "left": {
      "operator": "->",
      "right": "y",
      "left": "p"
    }
}
```
*/