5

オンライン BASIC インタープリター実験用に、4 つの演算子すべてを使用して数式を解析するために、 PEG.jsの文法例を拡張しようとしています。

http://www.dantonag.it/basicjs/basicjs.html

しかし、すべての式が正しく解析されるわけではありません。

これは私のPEG文法です:

expression = additive

additive = left:multiplicative atag:("+" / "-") right:additive { return {tag: atag, left:left, right:right}; } / multiplicative

multiplicative = left:primary atag:("*" / "/") right:multiplicative { return {tag: atag, left:left, right:right}; } / primary

primary = number / "(" additive:additive ")" { return additive; }

number = digits:[0-9]+ { return parseInt(digits.join(""), 10); }

2*3+1 (7 を与える) のような式は正しく解析しますが、0 ではなく 2 を与える 2-1-1 のような式は解析しません。

これを改善してデバッグするのを手伝ってもらえますか?

前もって感謝します。

編集：文法に「数」ルールを追加しました。はい、私の文法は出力として解析木に類似した再帰構造を与えます。

4

2 に答える 2

9

マットの答えは正しいものですが、pegjs内で左結合を実装する方法について：

expression = additive

additive
  = first:multiplicative rest:(("+" / "-") multiplicative)+ {
    return rest.reduce(function(memo, curr) {
      return {atag: curr[0], left: memo, right: curr[1]};
    }, first);
  }
  / multiplicative

multiplicative
  = first:primary rest:(("*" / "/") primary)+ {
    return rest.reduce(function(memo, curr) {
      return {atag: curr[0], left: memo, right: curr[1]};
    }, first);
  }
  / primary

primary
  = number
  / "(" additive:additive ")" { return additive; }

number
  = digits:[0-9]+ { return parseInt(digits.join(""), 10); }

Matt がリンクしているjavascript.pegjsの例では、同様の方法を使用しています。重要なのは、操作の文字列をリストと同じ優先順位で処理することです。これにより、正しい結合性でツリーを構築できます。

于 2015-06-12T08:34:11.667 に答える
6

まず、文法にnumberルールがありません。また、ご承知のとおり、文法を ( を追加した後にnumber) 例に実行しても 2 ではなく、解析ツリーのようなものが得られます。これら2つの問題を修正するために質問を更新していただけませんか?

問題: 結合性に遭遇したようです。結合性は、優先順位が同じ 2 つの演算子がオペランドをめぐって競合する場合に発生します。あなたの例で-は、と競合しています--明らかにそれ自体と同じ優先順位があります-しかし、結合性は、との間、およびとの間の+関係を断ち切るためにも重要になります。 -*/

2 つの演算子の優先順位が異なるため、 が正しく解析されると仮定します。つまり、結合性が機能せず、文法が優先順位を正しく実装していることを意味します (これは、乗算が加算よりも優先順位が高いことを示すためのより標準的な例であることに2*3+1注意してください)2+3*1の単純な左から右への解析で2*3+1は、パーサーと同じ結果が得られるため)。

左結合にしたいと思います-が、次の例に基づいて、文法では右結合のようです。

  • 入力：

    1-2-3

  • 出力 (として解析1-(2-3)):

    {
   "tag": "-",
   "left": "1",
   "right": {
      "tag": "-",
      "left": "2",
      "right": "3"
   }
}

左連想ツリーは次のようになります ( から(1-2)-3)。

{
   "tag": "-",
   "left": {
      "tag": "-",
      "left": "1",
      "right": "2"
   },
   "right": "3"
}

他の演算子も、左結合ではなく右結合のように見えることに注意してください。

解決策: peg.js がどのように機能するかはよくわかりませんが、簡単なグーグル検索でこれが見つかりました。

演算子の優先順位と結合性に対する文法ベースのソリューションは、しばしば非常に厄介です (証拠については、Python の文法を参照してください)。そのため、[トップダウン] 演算子の優先順位解析を調べて、より柔軟で表現力豊かな代替手段を検討することをお勧めします。Douglas Crockford、Vaughn Pratt、および Annika Aasa は、このテーマに関する優れた記事をいくつか書いています。

于 2013-10-16T14:33:30.413 に答える