Dlaczego ta gramatyka LR (1) nie jest LALR (1)?

Question

To nie jest moja praca domowa, staram się zrozumieć gramatykę LALR (k). Więc znalazłem this

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

zrobiłem analizatora (dostępny w formacie PDF w moim git repo jako LR1notLARL1.pdf

Ale nie mogę dowiedzieć się, dlaczego nie jest to gramatyka LR LALR? Może ktoś pomóc ? mi Dziękuję

Answer 1

Zacznijmy od budowy LR zestawy (1) skonfigurowaniu dla gramatyki:

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

Jeśli yo Wskazówka Bedziesz, Zjednoczone (4) i (10) mają ten sam rdzeń, więc w LALR (1) automat chcielibyśmy połączyć je ze sobą, tworząc nowe państwo

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

Która teraz ma zmniejszyć/zredukuj konflikt w nim (wszystkie konflikty w LALR (1), które nie były obecne w parserze LR (1), są przy okazji redukowane/zmniejszane). To wyjaśnia, dlaczego gramatyka to LR (1), ale nie LALR (1).

Mam nadzieję, że to pomoże!