¿Por qué esta gramática LR (1) no es LALR (1)?

Question

Esta no es mi tarea, estoy tratando de entender las gramáticas LALR (k). Así que encontré this

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

hice un analizador (disponible en formato PDF en mi git repo como LR1notLARL1.pdf

Pero no puedo averiguar, ¿por qué se esta gramática LR no LALR? puede ayudar a nadie ? me Gracias

Answer 1

Vamos a empezar con la construcción de conjuntos LR (1) configuradora de la gramática:

(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. [$] 

Si yo ua aviso, estados (4) y (10) tienen el mismo núcleo, por lo que en la LALR (1) autómata nos gustaría combinarlos entre sí para formar el nuevo estado

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

que ahora tiene una reducción/reducir el conflicto en él (todos los conflictos en LALR (1) que no estaban presentes en el analizador LR (1) son de reducción/reducción, por cierto). Esto explica por qué la gramática es LR (1) pero no LALR (1).

Espero que esto ayude!