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

Question

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

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

Я сделал анализатор (доступен в формате PDF в моем git repo как 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. [$] 

Если йо u'll уведомления состояния (4) и (10) имеют то же самое ядро, так и в (1) автомата LALR мы бы объединить их вместе, чтобы сформировать новое государство-

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

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

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