問題タブ [left-recursion]

説明：

Compiler Design in C book を読んでいるときに、文脈自由文法を説明する次の規則に出くわしました。

1 つまたは複数のステートメントのリストを認識する文法。各ステートメントは算術式の後にセミコロンが続きます。ステートメントは、セミコロンで区切られた一連の式で構成されます。各式は、アスタリスク (乗算の場合) またはプラス記号 (加算の場合) で区切られた一連の数値で構成されます。

そして、ここに文法があります：

この本は、この再帰的な文法には大きな問題があると述べています。プロダクション 3 のように、いくつかのプロダクションの右側が左側に表示され (そして、このプロパティは左再帰と呼ばれます)、再帰降下パーサーなどの特定のパーサーは左再帰プロダクションを処理できません。それらは永遠にループします。

右辺が複数ある非終端記号を置き換えるときに、パーサーが特定のプロダクションを適用することをどのように決定するかを考えると、問題を理解できます。単純なケースは、プロダクション 7 と 8 で明らかです。パーサーは、次の入力シンボルを見て、因子を展開するときに適用するプロダクションを選択できます。このシンボルが数値の場合、コンパイラは Production 7 を適用し、係数を数値に置き換えます。次の入力記号が開き括弧の場合、パーサーはプロダクション 8 を使用します。しかし、プロダクション 5 と 6 の間の選択は、この方法では解決できません。プロダクション 6 の場合、term の右側は因子で始まり、次に、数字または左括弧のいずれかで始まります。その結果、用語が置き換えられ、次の入力記号が数字または左括弧である場合、パーサーは Production 6 を適用したいと考えています。プロダクション 5 - もう一方の右側 - 項で始まり、因子で開始でき、数字または左括弧で開始できます。これらは、プロダクション 6 を選択するために使用されたのと同じ記号です。

質問：

本からの2番目の引用は、私を完全に迷子にさせました。したがって、いくつかのステートメントの例を (たとえば) として使用すると、次のようになり5 + (7*4) + 14ます。

1. factor と term はどう違いますか？同じ例を使用して
2. 再帰降下パーサーが左再帰生成を処理できないのはなぜですか? （2番目の引用を説明してください）。

私はこの文法を持っています:

優先順位は次のとおりです。

優先度を考慮して左再帰を削除する必要があります（そしてすべてJavaCCに書き込みます）。

再帰を削除するのを手伝ってもらえますか?

興味深い間接再帰の問題があり、解決したと思いますが、それが正しいかどうかはよくわかりません。

開始文法:

私の解決策は、最初に A を進化させることでした:

これで、再帰がある場所がわかり、それを削除して、次のようになります。

完全な解決策は、

この文法は正しいですか？

演習として、次の GADT を使用して、Haskell で定義された非常に単純な言語のパーサーを実装しています (私のプロジェクトの実際の文法にはさらに多くの式が含まれますが、この抜粋は質問に対して十分です)。

解析関数は次のとおりです。

式文法の左再帰の性質により、パーサーを1+1使用するような単純なものを解析しようとするexprと、パーサーが無限ループに陥ります。

次のような変換を使用して、ウェブ全体で左再帰を因数分解する方法の例を見てきました。

次のようなものに：

しかし、これをパーサーに適用する方法に苦労しています。

完全を期すために、パーサーを実際に実装するコードを次に示します。

この例で私を助けてくれますか? このサイズで左再帰消去を行うにはどうすればよいですか? より簡単な例でそれを行う方法を知っています。

これは解決策ですか？

エラーが発生しています

文法のどの部分がこのエラーをスローしているのか正確にはわかりません。alt 3,4の他の1つの同じエラー

左再帰を削除するためにどの部分を再配置する必要があるのか​​ わかりません。誰かが指摘してくれればありがたいです。