Почему эта грамматика LR (1) не является LALR (1)?

Question

Это не моя домашняя работа, я пытаюсь понять LALR (k) грамматику.Итак, я нашел это

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

Я сделал анализатор (доступен в формате PDF в моем GIT-репо как LR1notLARL1.pdf

Но я могуНе могу понять, почему эта грамматика LR не является LALR? Кто-нибудь может мне помочь? Спасибо

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]

Который теперь имеет конфликт уменьшения / уменьшения (кстати, все конфликты в LALR (1), которых не было в анализаторе LR (1), уменьшаются / уменьшаются). Это объясняет, почему грамматика LR (1), но не LALR (1).

Надеюсь, это поможет!