Step by step elimination of this indirect left recursion

Question

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?

Answer 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