すべてのLR(0)文法はSLR(1)ですが、その逆も必ずしも真実である必要はありません。なぜですか?
-
09-10-2019 - |
質問
すべてのLR(0)文法はSLR(1)ですが、その逆も必ずしも真実である必要はありません。なぜですか?
解決
基本的に、SLR(1)文法は、対応するLR(0)文法に存在するシフトレデュース競合を解決できます。ウィキペディアの文法の例を取ります SLRパーサー ページ(これはより低い、より厳格なレベルで説明しています):
- s→e
- E→1 e
- E→1
LR(0)パーサーが解析しているとき e そして、「1」は次の入力記号であり、認識できます e また、次のE(ルール2)を解析するために削減(ルール3)またはシフトする可能性があります。それは先を見ることができないので、LR(0)はどちらをすべきかを決定することはできません。これを見ると、これはより明白になります アイテム LR(0)は、「1」に遭遇したときに処理される可能性があります(ストリングの終わりのシンボルが追加されました):
- E→1•E $
- E→1•$
1つ目にはシフトが必要になり、2番目のシフトには減少が必要です。
上記の文法により、SLR(1)の文法は、1つのシンボルを先取りして、どのアクションをとるべきかを決定できます。 e $のみに続くことができるため、削減アクションは文字列の最後にのみ有効です。これは2番目のアイテムに対応し、次のシンボルが「$」であることがわかります。
LR(0)ではなくSLR(1)である別の例については、Fegarasを参照してください。 CSE 5317/4305のメモ テキサス大学で。
所属していません StackOverflow