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.

Can you please explain what that function `clean` is supposed to do? — Bergi, Jun 14 '14 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, Jun 14 '14 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, Jun 14 '14 at 23:54

Bergi · Accepted Answer · 2021-11-12T10:09:38.833

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

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 `E1`s instead of `Value`s - 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 :-) — Bergi, Jun 14 '14 at 23:49
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. — Toothbrush, Jun 15 '14 at 00:07
Thank you again. It works perfectly! I must have missed that Wikipedia article. — Toothbrush, Jun 15 '14 at 00:16
How do your rewrite the left-recursive portion when it isn't an infix operator? e.g. something like: `E1 = l:E1 '[' r:E1 ']'`? — Michael, Oct 23 '15 at 01:44
@Michael: What is your base case? But I think you are looking for something like `E1 = l:E2 rs:('[' E1 ']')*` — Bergi, Oct 23 '15 at 04:13
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. — Alex North, Nov 12 '21 at 04:15

score 1 · Answer 2 · answered Aug 28 '18 at 05:36

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

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. — Toothbrush, Aug 28 '18 at 10:49

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

Expression

Expected AST

Generated AST

Code

2 Answers2