問題タブ [left-recursion]

文脈自由文法で左再帰を削除することを理解しようとしています。私は特定のフォームに慣れていますが、これには少し戸惑います.

また、適切なパーサーを設計する必要がありますが、それは可能です。ただし、この左再帰 (特に最初の再帰) を理解すると、混乱します。

次のルールで左再帰を削除するにはどうすればよいですか。

S -> aSAbb | aA

S -> SA | で実行する方法を理解しています。あ

これは S -> A になります | なので'; S' -> A | AS'、しかし端末はこの質問で私を怒らせます。

編集：

申し訳ありませんが、左再帰とは何かについて混乱していたようです。右側から左側のシンボルを削除する方法を尋ねる必要がありました。

構築しようとしている新しい汎用プログラミング言語用の文法ファイルがあります。私はこの言語を堅牢で自然に使えるようにしようとしています (Ruby などから大きな影響を受けています)。そのために、いくつかの左再帰規則を導入しました。

次の左再帰ルールを示していると思われる例をいくつか見てきました。

次のように変更することで、非左再帰にすることができます。

私には、これには別の問題があり、それでも失敗するように見えます。私は正しいですか、それともこれは「うまくいく」でしょうか？

私が (見つけて) 排除しようとしている特定の左再帰は、この文法ファイルにあります。どのルールが影響を受けるかはわかりませんが、少なくともいくつかは左再帰があると指摘されました。(ちなみに、範囲のルールを強化することで、彼が言及した特定の範囲の問題を排除しようとしました。)

非プログラマーによって作成される vb6 コード (機能のサブセットのみを使用する) の小さなスニペットがあります。これらはルールと呼ばれます。これらを書いている人にとってはデバッグが難しいので、誰かが一種のアドホックパーサーを書いて、部分式を評価し、それによって問題がどこにあるかをよりよく示すことができるようにしました。

このアドホック パーサーは非常に悪く、実際には機能しません。だから私は本当のパーサーを書こうとしています（私はそれを手で書いているので（vb6バックエンドで理解できるパーサージェネレーターはありません）、再帰的なまともなパーサーを使いたいです）。何でも見つけることができたので、文法をリバースエンジニアリングする必要がありました。(最終的に何かhttp://www.notebar.com/GoldParserEngine.htmlを見つけましたが、その LALR と必要以上に大きい)

VB のサブセットの文法は次のとおりです。

全体として、ここではいくつかの簡単な例を示します。

のように見える

今私の問題は何ですか？

このようなコードがある場合(( true OR false ) AND true)、無限再帰がありますが、本当の問題は (true OR false) AND true(最初の の後( expr )) が のみとして理解されることです(true or false)。

パースツリーは次のとおりです。

では、これを解決する方法。どういうわけか文法を変更するか、実装ハックを使用する必要がありますか?

必要な場合に備えて、何か難しい例を示します。

a > 2私は小さなカスタム スクリプト言語を持っており、やなどのブール式を使用できるように更新しようとしていa > 2 and (b < 3 or c > 5)ます。ここで問題を抱えているのは括弧表現です。

これは（@Bart Kiersからの回答に基づいて元の投稿から編集された）問題を示す完全な文法です。これは私の実際の文法を簡略化したものですが、ここでも問題が発生します。

ルールa > 2 or (b < 3)のコメントアウトされた行にあるような括弧付きのブール式に対応するための私の試み。atomこの行のコメントを外して文法に含めると、ANTLR で次のエラーが表示されます。

[致命的] alt 1、2 から到達可能な再帰的なルール呼び出しにより、ルール アトムに非 LL(*) 決定があります。左因数分解するか、構文述語を使用するか、backtrack=true オプションを使用して解決します。

再帰を削除することでこれに対処したいのですが、左再帰を削除する方法に関するウィキペディアの説明から自分のものに移行できないようです。

この文法を使用する際に、abc という名前の変数に値を代入するstatementなどの入力でルートとして使用したい場合があります。また、文法を使用して、 などの入力をルートとabc = 2 + 3する式を評価したい場合もあります。@Bart の回答をモデルとして使用しようとすると、 で使用される文法の部分を で使用される部分とマージしようとするまではうまくいきました。どちらも を使用できるはずですが、この左再帰エラーで立ち往生しています。booleanabc > 3 and (xyz < 5 or xyz > 10)statementbooleanexpression

では、括弧を処理し、左再帰の問題を回避するにはどうすればよいでしょうか?

プロローグで DCG 文法を解決しようとしていて、ある程度まで成功しました。これらのような中括弧を含む式の評価に行き詰まっています。 expr( T, [’(’, 5, +, 4, ’)’, *, 7], []),

coffeescript grammar の Antlr/Xtext パーサーを作成しています。それはまだ始まったばかりで、元の文法のサブセットを移動しただけで、表現に行き詰まっています。それは恐ろしい「ルール式に非 LL(*) 決定があります」というエラーです。ここでいくつかの関連する質問を見つけました。Help with left factoring a grammar to remove left recursion and ANTLR Grammar for Expression . How to remove global backtracking from your grammarも試しましたが、実際には使用できない非常に単純なケースを示しています。ANTLR 文法のヒント: LL() と左因数分解に関する投稿は、より多くの洞察を与えてくれましたが、まだ理解できていません。

私の質問は、次の文法を修正する方法です (申し訳ありませんが、単純化できず、エラーを保持できませんでした)。トラブルメーカーがtermルールだと思うので、全体を変更するのではなく、ローカルで修正していただければ幸いです (元の文法のルールに近づけるように努めています)。この種の誤った文法を頭の中で「デバッグ」する方法のヒントへのポインターも歓迎します。

更新: 最終的な解決策は、重要な空白を処理する複雑さを避けるために、外部レクサーで Xtext を使用します。これが私の Xtext バージョンのスニペットです。

私の戦略は、使用可能な AST を使用せずに、最初に動作する Antlr パーサーを作成することです。（まあ、これが実現可能なアプローチである場合は、別の質問に値するでしょう。）したがって、現時点ではトークンについては気にしません。トークンは開発を容易にするために含まれています。

元の文法が LR であることは承知しています。LLに変身するときどこまで近づけるかわかりません。

UPDATE2 と解決策: Bart の回答から得られた洞察を使用して、問題を単純化できました。これは、関数呼び出しを使用して簡単な式を処理するための実用的な文法です。前のコメントexpressionは私の洞察を示しています。

私の言語では、配列または構造体の要素にアクセスするためのドット演算子という 1 つの追加機能を備えた s 式を使用しています。

現在、私のパーサーは、access演算子を使用してこのコードで動作します -

ただし、次のようなドット演算子を使用して代替解析を追加したい-

どちらも同等の AST に解析されます。ここで左再帰が問題になるのは、式 like(f x).yが同様に解析されるためです(access :m:y (f x))

しかし、FParsec でこの種の左再帰解析を処理する方法や、左再帰に代わる方法がわかりません。

次の構文を含むことができる ANTLR を使用して言語を解析しようとしています。

これは私がこれまでに思いついたANTLR文法でありaccess_operation、エラーがスローされます

The following sets of rules are mutually left-recursive [access_operation, expression]:

これまでに管理できたのは、ノードに操作の右側のみが含まれる AST を生成するaccess_operationルールをリファクタリングすることでした。'.' expressionaccess_operation

代わりに私が探しているのは次のようなものです:

この場合、左再帰の問題はどのように解決できますか?