Usuwanie lewej rekursji

Question

Poniższa gramatyka opuścił rekursji

E= E+T|T 
T= T*F|F 
F= a|b|c 

Jak go usunąć? Czy jest jakaś ogólna procedura dla tego?

Answer 1

Tak istnieje ogólna procedura, patrz np wikipedia.

E = TE' 
E'= (e) | +TE' 
T = FT' 
T'= (e) | *FT' 
F = a | b | c 

Należy wspomnieć, że ta zmienia skojarzenia z + i * od lewej do prawej. To znaczy, że przed a + b + c został przeanalizowany jako (a + b) + c, jest teraz analizowany jako a + (b + c).

To nie jest problem dodawania i mnożenia, ale na przykład problem z odejmowaniem i dzieleniem.

Artykuł w Wikipedii zawiera więcej szczegółów na temat procedury usuwania lewostronnego rekursji i jej zawiłości.

Answer 2

Jak zauważyli inni, istnieje ogólna procedura zastępowania lewej rekursji prawą rekurencją. Pozostałe odpowiedzi pokazują, jak wykorzystać tę ogólną procedurę do usunięcia lewej rekursji w danej gramatyce.

Oto rozwiązanie, które zmienia strukturę gramatyki w sposób właściwy dla tej gramatyki.

E= T+E|T 
T= F*T|F 
F= a|b|c 

Answer 3

Ogólna procedura znajduje się na przykład pod adresem Wikipedia. Będę zademonstrować, że E = E+T|T:

E to lewy-rekurencyjny nie-terminalny. +T jest sekwencją niepustą (alfa). T to sekwencja, która nie rozpoczyna się od E (beta).

Tworzymy nowy nieterminal dla "odpoczynku", czyli. sekwencja inna niż zerowa. To obsługuje rekursję.

E' = epsilon|+TE'

A my zmodyfikować oryginalny przepis do korzystania z nowego nieterminalowi obsłużyć rekursji.

E = TE'

Answer 4

produkcji

E = E+T 
    | T 
T = T*F 
    | F 
F = a|b|c 

idzie

E= T ('+' T)* 
T= F ('*' F)* 
F= a|b|c 

Aby utrzymać taką samą obróbkę gdzie pięści e dysjunktywnej jest przetwarzany A(E,T). nowa wersja używa:

ret = T1; 
while(set.more()) ret = A(ret, set.pop_front().T);