文法がLR(0)かどうかを決定する
-
21-12-2019 - |
質問
私は編集の対象に新しく、ボトムアップ解析のための運動を始めたばかりです。
次の問題に座っています。
次の文法のためのLR(0)解析テーブルの構築:
1) E –> E + T
2) E –> T
3) T –> (E)
4) T –> id
I0 :
E' –> .E
E –> .E + T
E –> .T
T –> .(E)
T –> .id
.
E上の次の状態は次のとおりです。
I1:
E' -> E.
E -> E. + T
.
これまでに学んだことからこのS-Rの紛争はありませんか? パーサーはそれを減らすか変化するかどうかわからないから 先読みの変数はありませんか? だからこれはlr(0)文法になされてはいけませんか?
しかし読み取っているPDFはLR(0)表を構築しました。 それで、PDFに間違いがありますか、それとも概念を理解すると間違っていましたか?
解決
これは実際にはシフト/リダクションの競合です。この文法はLR(0)ではありません。これを見ることもできます。 prefix-free ではありません。文法には、互いの接頭辞である複数の文字列が含まれているため、LR(0)にはできません。
は、まだLR(0)設定セットをすべて作成してLR(0)オートマトンを作成することができます。競合のシフト/軽減のため、それは決意には決まりません。したがって、あなたが正しいと配布資料が正しいことが可能です。
これが助けに役立つことを願っています!
他のヒント
GrammarをE' -> E
で増強しました。通常、E' -> E $
のような生産で増強されることは、$が文法では発生しない(ターミナル)シンボルであり、入力終了を表す。
SO I1は実際には
E' -> E. $
E -> E. + T
.
と衝突はありません。(そして私は文法がLr(0)であると思います。)
所属していません StackOverflow