Making gramatyki LL (1)

Question

Mam następujący Gramatyka:

S → a S B S | b S a S | ε

Ponieważ staram się napisać dla niego mały kompilator, chciałbym zrobić LL (1). Widzę, że tutaj występuje konflikt PIERWSZY/PODEJŚCIE i wiem, że muszę użyć podstawienia, aby go rozwiązać, ale nie jestem do końca pewien, jak go rozwiązać. Oto moja proponowana gramatyka, ale nie jestem pewien, czy jest poprawna:

S-> aSbT | epsilon

T-> bFaF | epsilon

F-> epsilon

Czy ktoś może pomóc?

Answer 1

W swoim original paper on LR parsing, Knuth daje następującą gramatykę tego języka, który przypuszczenia „to najkrótsza możliwa jednoznaczna gramatyki dla tego języka:”

S → & epsilon; | aAbS | bBaS

A → i epsilon; | aAbA

B → & epsilon; | bBaB

Intuicyjnie próbuje to rozpaść dowolny ciąg As i Bs na bloki, które równoważą się całkowicie. Niektóre bloki zaczynają się od a i kończą na b, podczas gdy inne zaczynają się od b, a kończą na a.

Można obliczyć pierwszym oraz PODĄŻAĆ zestawów w następujący sposób:

pierwszy (s) = {& epsilon ;, a, b}

pierwszego (A) = {& Epsilon ;, a}

pierwszej (b) = {& Epsilon ;, b}

zasad (S) = {$}

zasad (A) = {b}

0.123.

FOLLOW (B) = {a}

Na tej podstawie możemy uzyskać następujące LL (1) analizowania tabeli:

| a | b | $ 
--+-------+-------+------- 
S | aAbS | bBaS | e 
A | aAbA | e | 
B | e | bBaB | 

A więc ta gramatyka to nie tylko LR (1) , ale to także LL (1).

Mam nadzieję, że to pomoże!