問題タブ [lalr]

バックグラウンド：

私はソフトウェアセマンティクスのクラスを取っています.while と呼ばれるおもちゃの言語用の小さなコンパイラとランタイムを作成することになっています. Java のコード スケルトンが与えられましたが、好きな言語を使用することが許可されています。私はこれを文法のリハーサルの機会と考え、代わりに C++ でラボを行うのはクールだと考えました。

現在、ステートメントの優先順位ルールを設定する際に問題が発生しています。これが現在の私のBNFC文法ファイルです。

私が欲しいのは入力です

私の複合ルールに従って次のようなものに解析されます

つまり、割り当てをループ本体の一部にしないでください。しかし、私が得るのは

ご覧のとおり、while ループの本体は複合ステートメントで構成されていますが、これは私が望んでいたものではありません。この効果を得るには、優先ルールをどのように設定すればよいですか?

私はこのような規則を持つ文法を持っています

この文法を LALR(1) に変換する方法はありますか? 私が理解できることから、パーサーがpブロック内を見ると、シフト/抽出の競合が発生します。

私が聞きたい質問は、タイトルに簡潔に示されています。問題の文法の例を挙げましょう。

次に、通常の C 式の文法を追加します。特に、

問題は、この文法 LALR(1) が解析可能かどうか、つまり、自動パーサー ジェネレーターで解析できるかどうかです。それとも手動または GLR パーサーが必要ですか? 文脈依存のキーワードやその他のセクションではなく、このサブセクションについて具体的に知りたいことに注意してください。

私が今考えているのは、パーサーが を見た場合'(' identifier ')'、これには 2 つの有効な解析があるため、パーサーが を見た場合、identifierを先に見て、')'どの解析ツリーを下るかを決定できないということです。ただし、これはシフト/リデュースの競合である可能性がありますが、任意の優先順位を割り当てることで排除できます (おそらく favouring '(' identifier ')')。

編集: 実際、私は文法のこのサブセクションを使用して、新しい言語で同様の機能を盗むことを検討していました. 私はすでに JavaScript に似た無名関数を文法形式で持っていますが、モルモットは多くの用途に対して冗長すぎると不満を漏らし、C# ラムダ式がより理想的な解決策であると指摘しました。私は、この解決策から生じる潜在的なあいまいさを懸念していました。だから、本当に、私はそのサブセクションにしか興味がありませんでした. ジェネリックやキャストなどの他のものは、私にとっては問題ではありません。

私の文法の以前の版は機械的に解析可能であり、私はこの特性を失いたくありません。機械式ジェネレーターに関する私の以前の経験から、自分で試すよりもここで確認するのが最善であることがわかります。私の手巻きのパーサーでは、もちろん'(' identifier、通常よりも少し先を読むという単純な特殊なケースも考えられます。

次の入力があるとします。

と

LALR(1) 文法でシフト/リデュースの競合を回避する方法はありますか? shift/reduce 競合により、 で削減するyか、 まで継続するかが決定されてい(ます。

(これは、変数名が英数字の任意のセットであり、関数呼び出しが括弧が続く任意の英数字のセットであると想定しています。)

式を連結して文字列を形成できるように、連結された文字列を解析しようとしました。あれは、

上記は正しく解析する必要があります。問題は、+シフト削減の競合につながることです。私は次の文法を使用しています。

+shift-reduce 競合を引き起こさない文法を見つけようとしても成功していません。この文法を LALR にする方法があることを願っています。それを見つけるための助けをいただければ幸いです。

次の文法の LALR(1) パーサーを作成しようとしていて、シフト/リデュースの競合を見つけようとしています。

そのため、パーサーは文字列 "ID[ID]" を正しく解析できません。私の質問は、

1. そのような非 LALR(1) 文法を LALR(1) 文法に変換する一般的な方法はありますか?
2. 2 つの文法がまったく同じ言語を生成し、一方が LALR(1) ではないことがわかっている場合、もう一方が LALR(1) であるかどうかを知ることができますか?

上記の文法は一例に過ぎません。私が本当に知りたいのは、これらの文法の問題を解決する一般的な方法です。提案や読書の推奨事項は大歓迎です。

前もって感謝します。

私は LR(k) 解析テーブルの構築について読み始めました。k > 0 のアルゴリズムを説明するすべてのテキストは、アイテム セットを生成する前にすべてのシンボルに対して先読みを計算する必要があることを示唆しています。冗長なものをマージして、最小限の解析テーブルを生成する必要があります。

次の疑似状態/アイテムセット構築ルーチンを検討してください。

1. 先読みなしで状態遷移を決定できると仮定することから始めます (k = 0)
2. 現在の状態のアイテムセット全体を計算する
3. 現在の状態のアクションを決定してみてください。
   • セット内にアイテムが 1 つしかなく、それがすべての入力を消費した場合 (rhs の右側にあるマーカー、アクションはアイテムの lhs に縮小されます。
   • セット内のすべてのアイテムが入力を期待している場合、アクションはシフトして次の状態に進むことです
   • 入力を期待する項目と入力を期待しない項目がある場合、これは shift/reduce 競合です
   • lhs が異なる 2 つ以上のアイテムが入力の最後に達した場合、これは reduce /reduce の競合です。最後の 2 つのケースのいずれかが発生した場合は、状態のアクションを決定する前に先を見据える必要があることを意味します。k を 1 増やして、ステップ 2 に戻ります。
4. アクションがシフトする場合は、入力の組み合わせ (および k > 0 の場合は先読み) をシミュレートしてフォローアップ状態を作成し、新しい状態ごとにステップ 1 に戻ります。

上記の手順を使用して、任意の LR(k) 文法のテーブルを構築することは可能/実行可能でしょうか? そうでない場合、何が欠けていますか？

LR と LALR の両方がボトムアップの解析アルゴリズムであることは理解していますが、この 2 つの違いは何ですか?

LR(0)、LALR(1)、LR(1) 解析の違いは何ですか? 文法が LR(0)、LALR(1)、または LR(1) であるかどうかはどうすればわかりますか?