Step by step elimination of this indirect left rec

问题:

I've seen this algorithm one should be able to use to remove all left recursion. Yet I'm running into problems with this particular grammar:

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

Whatever I try I end up in loops or with a grammar that is still indirect left recursive.

What are the steps to properly implement this algorithm on this grammar?

回答1:

Rule is that you first establish some kind of order for non-terminals, and then find all paths where indirect recursion happens.

In this case order would be A < B < C, and possible paths for recursion of non-terminal C would be

C=> A => Cd

and

C=> B => Ce

so new rules for C would be

C=> Cd | Ce | f

now you can simply just remove direct left recursion:

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

and the resulting non-recursive grammar would be:

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

回答2:

Figured it out already.

My confusion was that in this order, the algorithm seemed to do nothing, so I figured that must be wrong, and started replacing A -> Cd in the first iteration (ignoring j cannot go beyond i) getting into infinite loops.

1) By reordering the rules:

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

2) replace C in A -> Cd

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

3) B not yet in range of j, so leave that and replace direct left recursion of A

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

4) replace C in B -> Ce

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

5) not done yet! also need to replace the new rule B -> Ae (production of A is in range of j)

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

6) replace direct left recursion in productions of B

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

woohoo! left-recursion free grammar!