13

PEG.jsを使用して、左結合演算子の AST ( Abstract Syntax Tree ) をどのように構築しますか?

インターネットで見つけた情報に基づいてコードを記述しようとしましたが、間違いを犯したようです。

私が書いたコードは、ほとんどの式に対して間違った 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使用されることでした。しかし、Bergi が書いたコードは私のものよりずっと単純です。E1Value

4

2 に答える 2

16

右結合演算子は、「ネイティブに」再帰的に解析できるため、比較的簡単に記述できます。

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 は左再帰規則に対応していませんが、ウィキペディアはこれに対抗する方法を教えてくれます。再帰を*ループに展開する必要があります。すでにこれを行っていますが、括弧を別の方法で配置します。それらは、上記の再帰的な定義と一致する必要があり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; }
于 2014-06-14T23:44:40.840 に答える