問題タブ [lalr]

私は現在、カンマ区切りのリストをいくつかのオプションの異なるルールと一致させることを目的とした bison の削減を行っています。

不明な場合は、これを (疑似コードで) 実装することを意図しています。

これを行う方法は、たとえば次のように実装することです。

ただし、後者の定式化は LALR(1) ではありません。Bison がカンマを検出する各ステップで、たとえばシフトして *assignment_list* を探すか、空の *optional_assignment_list* を減らして先に進むかを決定する必要があるためです。 *optional_varargs* を探します。

これを表現するより良い方法があるかどうかを見つけようとしています。*optional_varkwdargs* を導入することで選択肢の数を減らすことができましたが、それでもなお 9 つの選択肢が残ります。これは 16 よりも優れていると思います。

どんなアイデアでも大歓迎です。

重複の可能性:
Python/YACC: シフト/リデュースの競合の解決

Yacc のような LALR(1) パーサーを実装する Ply を使用してパーサーを作成しようとしています。しかし、reduce/reduce の難しい競合に遭遇しました。私が知る限り、私の文法にはあいまいさはありません。代わりに、競合は LALR(1) パーサーの制限された先読みに起因しています。A Aパーサーは、還元するかどうかを決定するために 3 番目のトークンがあるかどうかを知る必要があるため、 が発生したときに問題が発生すると推測してt1います。では、これを単一のトークン先読みのみを必要とする文法にどのように組み込むことができますか?

Ply のデバッグ出力の関連する状態を次に示しますが、あまり意味がわかりません。

標準入力の代わりに文字列から文字を読み取るパーサーとレクサーを (巧妙に) 生成しようとしています。

http://code.google.com/p/lalr-scm/source/browse/trunk/calc.scm?r=52のコードに含まれる電卓の例の修正を開始しました。

問題は次の行にあるようです。

新しい入力ポートを定義しようとしました:

変数プログラムは次のように定義されました。

それでも機能しません。標準入力文字を待ちます。

ドキュメントには詳細が欠けているため、これをどのように解決できるかわかりません。

ありがとうございました

同じ言語を定義する 2 つの文法があるとします: 通常の文法と LALR(1) の文法です。

通常のアルゴリズムと LALR(1) アルゴリズムはどちらも O(n) で、n は入力長です。

正規表現は通常、正規言語の解析に好まれます。なんで？それらがより高速であるという正式な証拠はありますか（またはそれは明らかです）？

PCYACC に BISON のexpect 宣言に相当するキーワードはありますか:

ブール式と算術式の文法を作成しました。次のような算術式を処理したい:

必要なすべての式を処理できます。

私の問題は、ブール式が次のようになる可能性があることです。

そのため、ある時点で、ブール規則が算術式規則を参照する必要があります。文法があいまいになるため、ブール規則で括弧 () を使用できません。理由はわかりますが、この問題の解決策がわかりません。

私はフレックス、バイソンを使って簡単な電卓を作っています。

整数式と実数式の2種類の式を含む文法を開発しました。

文法は次のようになります。

これはLALR（1）ではありません。

たとえば、文字列INT'+'REALについて考えてみます。'INT'では先読みは'+'であり、これだけに基づいて、文字列がintExpであるかrealExpであるかを判別することは不可能です。

あいまいさを解消するために文法を書き直してみましたが、何も起こりませんでした。

解析中に計算を延期し、代わりに解析ツリーを構築できることはわかっています。次に、型チェックを使用すると、問題を解決できます。しかし、それはそのような単純な問題には少し多すぎるようです。

このあいまいさを処理するためにバイソン自体を作成する方法はありますか？それとも、文法をより良い方法で書き直すことができますか？

ply を使用して LALR パーサーを作成していて、乗算を解析しようとしたときに矛盾に遭遇しました。

完全なパーサーリンクは数千行に及ぶため、ここには含めませんが、簡単なデモを作成しました。

PLY によって報告された shift/reduce の競合や reduce/reduce の競合はありませんが、次の矛盾が発生します。

明示的な時間ルールと暗黙の時間ルールの優先順位が同じであるため、これは奇妙に思えます。しかし、PLY が 'times' トークンに優先順位を割り当て、p_plus ルールで式を減らすことを優先してスタックにシフトするという事実が原因である可能性があると思います。どうすればこれを修正できますか?

編集：より簡単なデモンストレーション。

Jison (javascript パーサー) で非常に単純な言語を定義することによって、解析のコツをつかもうとしています。バイソンと同じ/非常によく似た構文を受け入れます。

これが私の文法です：

シフト/削減の競合が 1 つ発生しています。ジソンの出力は次のとおりです。