如何使用 Abstract Syntax Tree 为左关联 运算符构建 AST ( PEG.js) ？

我试着根据网上的资料写了一些代码，但是我好像犯了一个错误。

我编写的代码为大多数表达式生成了不正确的 AST。

表达式

12-6-4-2*1-1

预期的 AST

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

生成的 AST

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

代码

{

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

对于如何为左关联和右关联运算符构建 AST 的任何帮助或示例代码，我将不胜感激。

编辑:正如@Bergi 所指出的，问题在于 E2 使用 E1 作为运算符列表其余部分的表达式值。但是，Bergi 编写的代码比我的简单得多。

最佳答案

右结合运算符编写起来相对简单，因为它们可以“本地”递归解析:

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

我们可以分别翻译左结合运算符的语法:

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

但我们从中得到的只是一个错误Left recursion detected for rule "E1". 事实上，PEG are not capable of left recursion rules ，但维基百科告诉我们如何解决这个问题:我们需要将递归展开到 * 循环中。您已经这样做了，但是括号的位置有所不同。它们应该匹配上面的递归定义，右边是单个 E2:

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

这样我们就可以使用递归辅助函数轻松地从 s 构建树:

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

或者，您可以使用一个循环，它最匹配右侧循环的括号:

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

作为引用，这里是完整的解析器:

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

关于javascript - 如何使用 PEG.js 构建左关联运算符树？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24174714/