問題タブ [left-recursion]

私は COOL (教室のオブジェクト指向言語) のパーサー/レクサーを書いています。次のリンクで文法を確認できます: (マニュアルの最後のページ)

http://theory.stanford.edu/~aiken/software/cool/cool-manual.pdf

ANTLR を使用してこのプログラムを作成しています。次の入力を使用して、次の出力が必要です。

入力:

出力:

しかし、私が得ている出力は次のとおりです。

ここに私のパーサー/レクサーコードがあります:

これは、ANTLR の COOL 文法のコード バージョンです。メインコードでコメントされている部分は曖昧さが解消され (意味はあいまいさが取り除かれます!)、2 番目の部分で左再帰が解放されます (数学規則)。

誰かがこれがどこで間違っているのか、そしてなぜ私は望ましい出力を得られないのか指摘できますか?

前もって感謝します！

式ノードにアクセスして実行する操作を決定するときに演算子をオンにする必要のないバイナリ非終端記号のみを含む文法と評価器 (ANTLR パース ツリー ウォーカー) が必要です (左前の因数分解された文法の場合のように) 、訪問者は「additionNode」にアクセスするため、訪問者は追加を行う必要があると静的に想定できます）。

かなり直接的な質問。ANTLR は左再帰をサポートしているため、これは有効な文法です。

気の利いた、しかし、このためのウォーカー/ビジター/コンパイラーバックエンドは、型で独自のディスパッチを行う必要があり、それは悪臭を放ちます:

この戦略の長所と短所:

• antlr はバイナリ ツリーを作成します。ここで、(バイナリ) 各ルールには左と右の引数があります。つまり、kleene クロージャの while ループについて心配する必要はありません。私は本当にこれが好きです
• ノードのタイプではなく、トークンを手動でディスパッチ (切り替え) する必要があります。

より伝統的で、すでに左に分解された文法を使用する

これに対応するビジターには、上記の 2 つの文法とは反対の長所と短所があります: ANTLR は、私のために型に対してこのディスパッチを行います -- まあ、ほとんどの場合、まだ '+' と '-' を区別する必要があります -- しかし、今はこれらの kleene クロージャーに while ループを含めることは、厳密なバイナリ ツリーがもうないためです。これは面倒です。

私の理想の文法はこのようになると思います

そして、これは私の問題をすべて解決しますが、もちろんそれはANTLRでは違法です

But indirect recursion still there in A' production

So how to remove this or am I doing something wrong

This is a question 4.3.1 from Compilers Principles Practice and Tools

次の文法生成を変換しようとしています

Haskell の Parsec 式に。

明らかに問題は左再帰であるため、再帰上昇スタイルで解析しようとしています。私が実装しようとしている疑似コードは次のとおりです。

これをHaskellに翻訳する私の試みは次のとおりです。

primaryExprタイプがIParser Expr あり、IParser は次のように定義されています。

ただし、これにより次のタイプエラーが発生します。

このタイプのエラーを修正するにはどうすればよいですか?

私は ANTLR4 を学んでいて、ある時点で混乱しています。Java に似た言語の場合、次のようなメンバー チェーンなどの構成要素のルールを追加しようとしています。

2 つのルールが相互に左再帰的であるというエラーが表示されます。

上記のルールの組み合わせが左再帰と見なされる理由memberAccessが理解できたと思います。expressionmemberAccessexpression

ただし、( Java の例を見て) の内容を に移動するだけでmemberAccess、 ANTLR4 からエラーが発生しないことを確認したとき、私の理解は崩壊しましたexpression(それでも、必要なものを解析していないにもかかわらず、に陥るようです)ループ):

1. 最初の例は左再帰ですが、2 番目の例はそうではないのはなぜですか?
2. そして、最初の行を実際に解析するにはどうすればよいですか?

SOで見つけたすべての解決策は、「ANTLR4に切り替える」でした。これは、使用しているため、実際にはオプションではありませんantlr4ruby（これはANTLR3であり、4は「for」を意味します）。

プロパティ アクセスのルールを作成したいのですが、次のように一致する必要があります。

ここに私が持っているものがあります:

(VARIABLEとACCESSは後で使用するパーサー トークンでNAMEあり、文字列の一種です)。

これは明らかに左再帰ですが、これを修正する方法がわかりません。

独自のアナライザー/パーサーを作成しようとしています。

なぜ機能しないのかは理解できますが、解決方法がわかりません。

これは私のパーサーの問題部分のコードです。

ご覧のとおり、問題はOR セクションの 3 つのオプションのうち最後の 2 つのCondition()メソッド内にあります。これは、Expression()が最終的に "( Expression() )" になる可能性があるためです。したがって、3 番目と 2 番目のオプションの両方が開き括弧トークンで始まる可能性があります。

ただし、この問題をどのように解決するかはわかりません。以前のパーサーで同様の問題を解決しましたが、Expression() --> Term() --> Factor()の方法と問題コードがすべてFactor()メソッドのずっと下に。

アドバイスをいただければ幸いです。

ありがとう、

トーマス。

編集：

詳細については、このパーサーで動作するはずのコード例を提供しますが、上記のバグが原因で動作しません。

上記のメソッドは、Condition()メソッドの 2 番目の代替手段を使用するため、正常に実行されます。

上記のメソッドは、3 番目の選択肢を使用する必要があるため失敗しますが、'(' が原因でパーサーが 2 番目の選択肢を呼び出すため、これにアクセスできません。