問題タブ [left-recursion]

私の文法には間接的な左再帰のケースがあるようで、他の同様の質問のいくつかを見て、それらと私の文法の間に精神的なつながりを完全に作ることができず、それを解決する方法について頭を悩ませることができません.

A'は from から呼び出されAますが、またはA'です。これは左再帰を引き起こしています。左再帰を排除しながら、これを同等の文法に再配置するにはどうすればよいでしょうか?cA

次の antlr4 文法があり、相互に左再帰エラーが発生します。どうすれば修正できますか?

次の形式の左再帰文法で Scala の PackratParsers (パーサー コンビネーター) を使用しています。

二項演算子 ":" を左結合にして、フォームの式がx1:x2:...:xnとして解析されるようにしたいと思います。(((x1:x2):x3):...:xn)つまり、フォームの AST につながりFunctionCall(":", FunctionCall(":", FunctionCall(":", x1, x2), x3), ...)ます。

驚くべきことに、上で定義した PackratParsers 文法を使用しても、結果の AST は依然として右結合です。その理由と、それを変えるために何ができるでしょうか?

Scala パーサーのコンビネーターと演算子の結合性に関するこの議論を見つけましたが、ここで私の問題に対する答えが得られないようです。

に対して無期限に繰り返されfunction_call.parseAll("aaa(1)")ます。明らかに、これは 1 が名前を挿入できず、 name が に入り、function_callname が試行され、 funciton 呼び出しに入るからです。そのような状況をどのように解決しますか？

名前を単純な識別子に減らす解決策がありました

name ::= identifier | function_callしかし、VHDL 仕様で BNF 化されており、function_callおそらく他の場所で共有されているため、これを行うことは好みません。ここで見つかった左再帰の消去は、同じ理由で望ましくありません

ところで、私がエラーを修正した場合、name.parseAllは名前ルールの最初の代替としてのみ「aaa」を消費するのか、それとも「aaa(1)」全体を取るのでしょうか? aaa だけを消費する前に、aaa(1) 全体を消費するように名前を付けるにはどうすればよいですか? function_call を名前の最初の選択肢に入れる必要があると思いますが、この場合、スタックオーバーフローがさらに熱心になりますか?

再帰降下パーサーで使用される文法には 2 種類の制限があることを私は知っています。

1. 文法には左再帰生成を含めることはできません
2. 文法は、トークン先読み以上を要求してはなりません。

最初の制限は理解していますが、2 番目の制限については少し迷っています。なぜこの制限が必要なのですか？

練習問題を解こうとしていたのですが、模範解答と自分の解答を比較しようとしたところ問題が発生しました。変換前の文法は次のとおりです。

開始記号はEで、その他の非終端記号はSとDです。

ここでの私の答えは次のとおりです。

回答例では がなくS-> DS'、E が になりE-> DS'*ます。左再帰を削除するために本で使用されている方法により、

があるはずS-> DS'です。私は今、これについて混乱しています。おそらく、この方法を理解していませんでした。誰かがこれについて何かヒントをくれますか? *また、ここにある星印の意味を教えてください。どうもありがとう！