Eliminazione graduale di questa ricorsione indiretta sinistra

Question

Ho visto this algorithm uno dovrebbe essere in grado di utilizzare per rimuovere tutta la ricorsione sinistra. Eppure io sto correndo in problemi con questo particolare grammatica:

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

Qualunque cosa provo io alla fine in loop o con una grammatica che è ancora indiretta ricorsiva sinistra.

Quali sono i passaggi per implementare correttamente this algorithm in questa grammatica?

Answer 1

La regola è che innanzitutto si stabilisce una sorta di ordine per i non-terminali e quindi si trovano tutti i percorsi in cui si verifica la ricorsione indiretta.

In questo caso fine sarebbe A < B < C, e possibili percorsi per ricorsione non terminale C sarebbero

C=> A => Cd 

e

C=> B => Ce 

così nuove regole per C sarebbe

C=> Cd | Ce | f 

ora puoi semplicemente rimuovere la ricorsione diretta a sinistra:

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

e la grammatica non ricorsiva risultante sarebbe:

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

Answer 2

Già calcolato.

La mia confusione era che in questo ordine, l'algoritmo sembrava non fare nulla, quindi ho pensato che doveva essere sbagliato, e ho iniziato a sostituire A -> Cd nella prima iterazione (ignorando j non posso andare oltre i) entrare in loop infiniti .

1) riordinando le regole:

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

2) Sostituire C in A -> Cd

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

3) B non ancora in gamma di j, in modo da lasciare che e sostituire diretta ricorsione sinistra di una

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

4) sostituire C in B -> Ce

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

5) non ancora completato! anche bisogno di sostituire la nuova regola B -> Ae (produzione di A è nella gamma di j)

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

6) sostituire la ricorsione diretta sinistra in produzioni di B

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

Woohoo! grammatica sinistra-ricorsione gratuita!