問題タブ [lr]

数日前にSLR(1) と LALR(1) と Reduceについて質問 します。多くの検索と教授への連絡を行っていますが、2番目の問題の解決策が正しいか間違っているかを要約できませんでした。2 つの異なる年の入試で 2 つの質問があります。

二問は選択式です。2010年の質問では、次のようにしています。

1) 次のような SLR(1) Grammar G があります。SLR(1) パーサー ジェネレーターを使用して、G の解析テーブル S を生成します。LALR(1) パーサー ジェネレーターを使用して、G の解析テーブル L を生成します。

そして、質問デザイナーは次のようにソリューションを選択します。

2 年後、デザイナーは次のように質問します。

2) T1、T2 が任意の文法 G の SLR(1) と LALR(1) で作成されたとします。G が SLR(1) 文法の場合、次のうちどれが真ですか?

a) T1 と T2 に違いはありません。

b) T1 の非エラー エントリの合計数が T2 より少ない

c) T1 のエラー エントリの合計数が T2 より少ない

解決：

私の質問は：

誰かが以前の投稿で 2 つの解決策が正しいと答えましたが、非常に整形式であるとは説明していません。

とにかく私は混乱から抜け出す専門家を待っています!!!

LR(1) 文法に関する質問を解決しようとしています:

次の場合、状態 4 でスタックしました。

aこの競合のために、この文法は LR(1)およびASLR A(1) ではないと見なす必要がありますか?

引用符で囲まれた文字列が終端記号であると想定される、次のような LR 文法の試みを検討してください。

これは競合のない LR(1) 文法であるように思われます。

それでも、私は（？）現実世界のパーサーは機械的にそれを

ここでU、 とVは、解析ツリー内の子によって直接置換されるシンボルです。

結果の文法は LR(∞) です。LR(k < ∞) の reduce-reduce 競合があります - 実際にはそうすべきではないという事実にもかかわらず!

ここで、この例をもっと複雑にすることが可能であることに気付きました (たとえば、論理和だけでなく反復も使用します)。実際、私の知る限り、そのような状況を検出することは、2 つの文脈自由文法の同等性をテストすることになります。これは (私の記憶が正しければ) 決定不可能な問題です。

私の質問は：

1. これが実際の問題であるということは正しいですか、それとも実用的な解決策がありませんか?

2. この問題に対処する最善の方法は何ですか? 競合を報告するのが最善の方法ですか、それとも実際に問題を解消するために使用されるヒューリスティックはありますか?

この文法があいまいであるかどうかについて少し混乱しています

このためにDFAを構築しようとしましたが、これは次のいずれかの状態で得られます。

これは shift-reduce の競合ではないので、文法が LR(1) ではないということでしょうか? それとも、$ と u の両方が C の次のセットに含まれているため、関係なく削減されますか?

代入式は、C 演算子を使用して可能な任意の代入式です=, +=, -=, *=, /=。

markerそしてNextどちらもEMPTYルール

上記の文法規則と実装の問題は、式が次の場合に正しいコードを生成できないことです。

代入式にはreloporORまたはANDtoが含まれている必要がありますgenerate correct code。この場合、relop同じケースの比較を行うため、 と に適用されORますAND。

しかし、上記のコードのように、このコードには何も含まれていないため、正しいコードを生成できません。次のルールを使用して正しいコードを生成できますが、これはtwo reduce-reduce conflict.

文法規則が期待どおりに機能するようにするには、文法規則でどのような変更を行う必要がありますか?

here と Dragon book のIF ELSE 文法規則を試しましたが、これを解決できませんでした。文法全体はGithubで見つけることができます