3

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

4

1 に答える 1

4

基本的に、SLR（1）文法は、対応するLR（0）文法に存在するshift-reduceの競合を解決できます。ウィキペディアのSLRパーサーページの文法例を見てください（これは、より低く、より厳密なレベルで説明されています）。

  1. S→E
  2. E→1E
  3. E→1

LR（0）パーサーがEを解析していて、「1」が次の入力シンボルである場合、Eを認識して縮小するか（ルール3）、次のEを解析するためにシフトすることができます（ルール2）。先を見越すことができないため、LR（0）はどちらを実行するかを決定できません。これは、LR（0）が「1」（文字列の終わりの記号が追加されている）に遭遇したときに処理できる項目を見ると、より明白になります。

  • E→1•E$
  • E→1•$

1つ目はシフトが必要で、2つ目はリデュースが必要です。

上記の文法を使用すると、SLR（1）文法は、1つの記号を先読みして、実行するアクションを決定できます。Eの後には$のみを続けることができるため、reduceアクションは文字列の最後でのみ有効です。これは2番目の項目に対応し、次の記号が「$」であることがわかります。

LR（0）ではなくSLR（1）である別の文法例については、テキサス大学のCSE5317/4305に関するFegarasのメモを参照してください。

于 2010-11-13T23:33:35.163 に答える