Пример грамматики, которая работает в LR (1), но не LALR (1)?

Question

Я не могу понять разницу между LALR (1) и LR (1), за исключением того, что LALR (1), кажется, имеет меньше состояний, чем LR (1).

Интересно, кто-нибудьесть пример, чтобы показать разницу и некоторые объяснения.

Спасибо

Answer 1

В книге Dragon есть пример (пример 4.44; 4.58, если у вас есть второе издание):

S' → S
S  → aAd | bBd | aBe | bAe
A  → c
B  → c

Поскольку грамматика генерирует только четыре строки, создать наборы элементов LR достаточно просто.Когда вы это сделаете, вы увидите, что есть два набора с одинаковыми предметами, но разными взглядами, соответствующими префиксам ac и bc.Конфликтов нет, поэтому грамматика LR (1).

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