問題タブ [lalr]

Bison の文法に問題があります。私は問題のないシフト/リデュースのペアと、6 つのリデュース/リデュースを持っています。問題は、パーサーが事前にトークンから選択するものを知っている必要があるため、reduce/reduce の競合がどのように発生するのか理解できないことです。

これが私の文法です。Bison は、function_argument_definitionとprimary_expression、および と の間のfunction_argument_definitionあいまいさが想定されていることに問題を提起しfunction_argumentます。ただし、そのようなものに遭遇するまでに、どちらを選択するかをすでに知っているはずです。これらのあいまいさをどのように解決できますか?

私はこのバイソンの紹介を読んでいます。

私には2つの質問がありますが、誰かが私を理解するのを手伝ってくれるといいですね。

1. 用語context free grammarはどういう意味ですか？

2. 上記のリンクから：すべての文脈自由言語をBisonで処理できるわけではなく、LALR（1）である言語のみを処理できます。簡単に言うと、これは、先読みのトークンを1つだけ使用して、入力文字列の任意の部分を解析する方法を指示できる必要があることを意味します。「先読みのトークンを1つだけ使用して、入力文字列の任意の部分を解析する方法を指示できる」とはどういう意味ですか。

ネストされたリストを解析するための LALR 文法を作成したいのですが、常にシフト/リデュースの競合が発生します。

type1 アイテムと list2 のリストである list1 があります。

そして、type2 項目のリストである list2 があります。

この文法はシフト/リデュース エラーを生成します。どうすれば回避できますか？

これは具体的なBiglooソースです。

ターミナルは、コメント、改行、テキストチャンク、および空白です。非ターミナルは、input、node-list、node、および text です。

Bigloo は、テキストからテキストチャンクへの reduce ルールについて不平を言っています。

しかし、これは Bigloo の問題ではないと思います。文法の問題のようです。

私は非常に単純な文法を持っています:

そして、unar操作をサポートするように拡張したいと思います（私見、これは正しい文法ですが、文法、パーサー、レクサーなどでは本当のn00bであるため、間違っている可能性があります）：

本当の問題は、解析テーブルを更新しようとしているときに発生します。

問題は、単項演算のサポートを提供するためにこのテーブルをどのように編集すればよいか (記述された文法に基づいて) ですか?

PSとにかく、LR（k）（またはLALR）パーサーを使用してJava（または他のオブジェクト指向言語）で算術式を解析するのを手伝ってくれてとても感謝しています^_^

PS2。この場合、パーサージェネレーターは適していません。

独自のカスタム パーサーを作成している場合、再帰的上昇パーサーを作成しているかどうかはどうすればわかりますか? 私は間違いなく LALR 構文解析の O(n) の複雑さに興味があり (さらに、既に LALR 文法を持っています)、代わりに LL パーサーを作成したことを後で知りたくありません。

編集：自動テーブル駆動パーサーと、生成された単純な再帰パーサーの例をいくつか見たことがあります。そのため、ルールを処理するための「明白な」コードを実際のアルゴリズムと関連付けるのはちょっと難しいです。

たとえば、比較的単純なルールのコードを使用する場合

私が翻訳したもの

それについては、右も左もありません。知っておくと便利で重要な情報であることは明らかですが、私はそれを見ていません。ここで明らかな唯一の事実は、再帰的であるということです。

編集：申し訳ありませんが、悪い例です。このようなものはどうですか：

文法ファイル (実際には、 coffee-scriptのJison文法)を視覚化したいと思います。したがって、入力ファイルは Bison/Yacc スタイルの文法ファイルです。予想される出力は、Graphviz ドット ファイルまたは類似のものである可能性があります。

GOLDのような完全な IDE を必ずしも探しているわけではありません。しかし、LALR 入力を処理できることが重要です。そのため、優れたANLTRWorksは考慮されません。

ウィキペディアでパーサーの比較も確認しましたが、IDE のサポートのみが含まれており、視覚化は含まれていません。

これが実際に視覚化したいcoffeescript 文法ファイルです。

LALR(1) パーサーでは、文法のルールが解析テーブルに変換され、「これまでにこの入力があり、先読みトークンが X である場合、状態 Y に移行するか、ルール R によって削減されます」と効果的に記述されます。 .

ジェネレーターを使用するのではなく、実行時に解析テーブルを計算し、その解析テーブルを使用して入力を評価する、インタープリター言語 (ruby) で LALR(1) パーサーを正常に構築しました。これは驚くほどうまく機能し、テーブルの生成は非常に簡単で (これには少し驚きました)、自己参照ルールと左右の関連付けがサポートされています。

ただし、理解するのに少し苦労していることの 1 つは、yacc/bison が空のルール定義を概念的に処理する方法です。テーブルを生成する際に各ルールの各シンボルを再帰的に調べ、「空」はレクサーから来るものでも、ルールによって削減されるものでもないため、私のパーサーはそれらを処理できません。では、LALR(1) パーサーは空のルールをどのように処理するのでしょうか? 彼らはそれを特別に扱っていますか、それとも、そのような概念を特に意識する必要さえなくても、有効なアルゴリズムがうまく機能する「自然な」概念ですか?

たとえば、途中に何もないペアの括弧の任意の数に一致できるルールを考えてみましょう:

次のような入力は、このルールに一致します。

これは、'(' を読み取り、先読みトークンで ')' を確認すると、パーサーが以下を選択することを意味します。

1. ')' をシフトする (不可)
2. 他のルールに従って入力を減らす (不可能)
3. 何か他の...

「シフト」または「縮小」のコアアルゴリズムには完全には適合しません。パーサーは事実上、スタックに何もシフトせず、「何もない」を に還元してからexpr、次のトークン をシフトし')'、 を与え'(' expr ')'、もちろんこれは に還元さexprれます。

私を混乱させているのは「何もシフトしない」ことです。解析テーブルはそのような概念をどのように伝えますか? また、空の値を減らすと値を返す何らかのセマンティック アクションを呼び出すことができるはずであることも考慮してください。そのため、解析テーブルからそれをスキップして、スタックと先読みで単に変換する必要が$$あるというかなり単純なビューシフトは、真に sequenceを生成するのではなく、単に sequence を生成します。'('')''(' expr ')''(' ')'

C＃とJavaの文法はLALR（x）なのかしら？はいの場合、xの値は何ですか？

編集：

本当の答えを受け入れた後、私は次のようにQを変更する方が良いと思います。

Java（バージョン7）またはC＃（バージョン4）の現在のリリースを解析できるLALR（x）パーサーはありますか？はいの場合、xの値は何ですか？

これは私の宿題ではありません。LALR（1）の文法を理解しようとしています。だから私はこれを見つけました

LRアイテムを作成しましたが、なぜこれがLR（1）文法であり、LALR（1）ではないのか理解できません。

誰か助けてもらえますか？ありがとうございました

Recursive Descent vs. LALR のこの投稿によると、任意の LALR(k) は「因数分解」によって LALR(1) に変換できます。私は投稿で言及されている Dragon Book を所有していません。その因数分解を行う方法について、オンラインのどこかに説明や例がありますか?