問題タブ [left-recursion]

この左再帰と左因数分解のトピックは初めてです。この文法が再帰のままか、因数分解のままかを判断するのを手伝ってください。

S-> aAd | BD | あべ | ばえ | CA | cB

とても懐かしく感じたので、ユーザーが複雑な文章を入力できるアドベンチャー ゲーム クリエーターを作成することにしました。

ビジター パターンを使用するレクサーとパーサーを手動で作成しましたが、BNF (Backus-Naur Form) ルールの 1 つで左再帰の問題が発生するまでは、非常にうまく機能します。

この wiki エントリに従って左再帰を削除した後、これは正しく見えますか?

編集:

hereのガイドに従って、C# を使用してレクサーとパーサーを手動でローリングしています。この演習では、パーサー ジェネレーターは使用しません。

また、このウェブサイトからパーサーの BNF ルールを取得しました。

以下は、正常に動作する ANTLR 文法のスニペットです。

これは、tex パーサーになることを目的としています。

everywhereコメントを外してルールを変更する| textと、ANTLR はルールの左再帰を報告しますが、escSeq これは面白いと思います。
左再帰を見つけることができません。目が見えないか、左再帰とは何かを誤解しています。

助言がありますか？

次の文法は、この問題を示しています。

入力 "a,b,c" を指定すると、リスナー イベント トレース出力を取得します

ここで、(は、 Enter punctuatedを表し、)はexit punctuatedを表し、他のすべてのルールは、簡潔さと明確さのために省略されています。

調べてみると、このリスナー イベントの順序は右結合解析を表しています。

一般的な慣行と The Definitive Antlr 4 Reference により、次のリスナー イベント トレースに対応する左連想解析が期待されます。

文法、期待、リスナー イベントの解釈などに何か問題がありますか?

Antlr で文法を書いている最中に、左再帰に何度か遭遇したことがあります。いくつかの調査を行った後、この問題に対処する 2 つの方法を見つけました。ポールのアルゴリズムと、Robert C. Moore の作品で説明されている左隅の変換Removing Left Recursion from Context-Free Grammars, 2000です。ポールのアルゴリズムは非常に非現実的なものですが、一方で左隅の変換は文法規則の数を からO(n)まで増やすだけO(n^2)ですが、ほとんどの場合、これよりもはるかに少ないため、そのアルゴリズムは非常に効率的です。だから私の質問は次のとおりです:左再帰の削除は意図的に実装されておらず、文法の実装者に責任を負っていますか、それともオプションとは見なされていませんか?

ラムダ計算パーサーを作成しようとしていますが、定義した文法は LLR にないようです:

左の再帰を減らします:

正しくないようです。誰か助けてもらえますか?

優先順位を強制する次の文法を思いつきました。

ここで、ID は文字、num は整数です。

問題

次の文字列を解析できます。

次の文字列を解析できません。

私の問題は、 A が再帰の問題を引き起こすことです。バックトラックをしたくないので。文法を書き直して、これを修正しなければなりません。私はこのリンクを見てきました。ただし、試みた修正も機能しません。誰か助けてくれませんか？

試みられた解決策:

ただし、これは私の文法の定義を変更し、まだ再帰的なままであり、解決できないと思いますa[i] + 1 or a[a[i]*i]

追加情報：

私は実際にこれをantlrで実装しています。これを修正するために構文述語を使用しようとしましたが、役に立ちませんでした。おそらく私はそれらを適切に使用していませんでしたか？

これについては引き続きクラックしますが、考えれば考えるほど混乱します。誰か助けてくれませんか？これは、後戻りのない文法を適切に設定する方法について考えている概念的な問題です。しかし、独自のカスタムツールを適切に作成したい場合は、これを行う必要があります.

だから、私はパーサーがどのようなものになるのか疑問に思っていました:

再帰的で無効なままですが、パーサーは

「基本」の定義がまだ「式」を参照している場合でも、有効で機能します。特に、次の形式で式を解析できるようにしたいと考えています。

2つ以上のオペランドに作用する操作を導入することなく。