Eliminacja tej pośredniej lewej rekursji krok po kroku

Question

Zauważyłem, że this algorithm należy użyć, aby usunąć całą lewą rekursję. jednak używam do problemów z tym konkretnym gramatyki:

A -> Cd 
B -> Ce 
C -> A | B | f 

Cokolwiek staram skończę w pętli lub z gramatyki, który jest nadal pośrednia lewa rekurencyjne.

Jakie są kroki, aby prawidłowo wdrożyć this algorithm w tej gramatyce?

Answer 1

Reguła polega na tym, że najpierw ustalasz jakąś kolejność dla nie-terminali, a następnie znajdujesz wszystkie ścieżki, w których dochodzi do pośredniej rekursji.

W tym celu przypadku byłaby < B < C i możliwe ścieżki na rekursji nie końcowych C będzie

C=> A => Cd 

i

C=> B => Ce 

więc nowe zasady C byłoby

C=> Cd | Ce | f 

teraz możesz po prostu usunąć bezpośrednią lewą rekursję:

C=> fC' 
C'=> dC' | eC' | eps 

i otrzymaną gramatyka nierekursywnych byłoby:

A => Cd 
B => Ce 
C => fC' 
C' => dC' | eC' | eps 

Answer 2

Już to wymyśliłem.

Moje zamieszanie polegało na tym, że w tej kolejności algorytm wydawał się nie robić nic, więc pomyślałem, że to musi być złe i zacząłem zastępować A -> Cd w pierwszej iteracji (ignorując j nie może wyjść poza i) wchodząc w nieskończone pętle .

1) poprzez uporządkowanie zasad:

C -> A | B | f 
A -> Cd 
B -> Ce 

2) zastąpić C w -> Cd

C -> A | B | f 
A -> Ad | Bd | fd 
B -> Ce 

3) B nie ma jeszcze w zakresie j, więc zostaw to i zastąpić bezpośredniej lewo rekursji A

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> Ce 

4) zastąpienie C w B -> Ce

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> Ae | Be | fe 

5) jeszcze nie gotowe! także trzeba zastąpić nową regułę B -> Ae (produkcja w zakresie j)

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> BdA'e | fdA'e | Be | fe 

6) zastąpić lewy bezpośredniej rekursji w produkcjach B

C -> A | B | f 
A -> BdA' | fdA' 
A'-> dA' | epsylon 
B -> fdA'eB' | feB' 
B'-> dA'eB' | eB' | epsylon 

woohoo! Gramatyka wolna od rekursji lewej!