parsing - このLR（1）文法がLALR（1）ではないのはなぜですか？

Question

これは私の宿題ではありません。LALR（1）の文法を理解しようとしています。だから私はこれを見つけました

S -> aEa | bEb | aFb | bFa
E -> e
F -> e

LRアイテムを作成しましたが、なぜこれがLR（1）文法であり、LALR（1）ではないのか理解できません。

誰か助けてもらえますか？ありがとうございました

Answer 1

文法のLR（1）構成セットを作成することから始めましょう。

 (1)
 S' -> .S [$]
 S  -> .aEa [$]
 S  -> .aFb [$]
 S  -> .bFa [$]
 S  -> .bEb [$]

 (2)
 S' -> S. [$]

 (3)
 S  -> a.Ea [$]
 S  -> a.Fb [$]
 E  -> .e   [a]
 F  -> .e   [b]

 (4)
 E  -> e.   [a]
 F  -> e.   [b]

 (5)
 S  -> aE.a [$]

 (6)
 S  -> aEa. [$]

 (7)
 S  -> aF.b [$]

 (8)
 S  -> aFb. [$]

 (9)
 S  -> b.Fa [$]
 S  -> b.Eb [$]
 E  -> .e   [b]
 F  -> .e   [a]

 (10)
 E  -> e.   [b]
 F  -> e.   [a]

 (11)
 S  -> bF.a [$]

 (12)
 S  -> bFa. [$]

 (13)
 S  -> bE.b [$]

 (14)
 S  -> bEb. [$]

お気づきの方もいらっしゃると思いますが、状態（4）と（10）は同じコアを持っているため、LALR（1）オートマトンでは、これらをマージして新しい状態を形成します。

 (4, 10)
 E -> e. [a, b]
 F -> e. [a, b]

現在、reduce / reduceの競合があります（ちなみに、LR（1）パーサーに存在しなかったLALR（1）のすべての競合はreduce / reduceです）。これは、文法がLR（1）であるが、LALR（1）ではない理由を説明しています。

お役に立てれば！