How do you build a left-associative operator tree using PEG.js?

Question

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.

Gerdy

Can you please explain what that function clean is supposed to do? – Dozy

@Dozy 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. – Gerdy

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. – Dozy

Answer 1

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; }

Dozy

Damn, right after having written this I realized that you've got the right idea in your solution, but let the loop in your E2 rule consist of E1s instead of Values - needs a minimal fix only. This mistake did allow for the subtraction to slip in as the right argument to the multiplication in your test case. I still hope my extensive answer is worth the bounty :-) – Dozy

Thank you very much for your help. Your answer is certainly worth the bounty. Give me a minute to try it, and I'll accept it. – Gerdy

Thank you again. It works perfectly! I must have missed that Wikipedia article. – Gerdy

How do your rewrite the left-recursive portion when it isn't an infix operator? e.g. something like: E1 = l:E1 '[' r:E1 ']'? – Jerkin

@Michael: What is your base case? But I think you are looking for something like E1 = l:E2 rs:('[' E1 ']')* – Dozy

Thanks for this very helpful answer. In deploying it noticed that the first way you wrote it, with zero-or-more ls and one r produces a very inefficient grammar. The reason is that in parsing a bare symbol, the parser first descends the left hand side, then realises it isn't followed by an operator, aborts the repetition, then descends the singleton right hand side. The cost goes exponential if this pattern is repeated down a few levels of operator precedence. – Varuna

Answer 2

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"
    }
}
```
*/

Radford

Thanks, that is nice and clean. And it doesn’t have a deep stack trace. It shows how much things can change in the web environment in a few years. – Gerdy