すべてのLR（0）文法はSLR（1）ですが、その逆も必ずしも真実である必要はありません。なぜですか？

Question

すべてのLR（0）文法はSLR（1）ですが、その逆も必ずしも真実である必要はありません。なぜですか？

Answer 1

基本的に、SLR（1）文法は、対応するLR（0）文法に存在するシフトレデュース競合を解決できます。ウィキペディアの文法の例を取ります SLRパーサー ページ（これはより低い、より厳格なレベルで説明しています）：

1. s→e
2. E→1 e
3. 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のメモ テキサス大学で。