Need to remove indirect left recursion from CFG

Question

I need to remove indirect left recursion from the following CFG: remove indirect left recursion from the following CFG. $$A → Ba| b$$ $$B → Cd | e$$ $$C → Df | g$$ $$D → Df | Aa | Cg$$

In the following solution, I have expanded all the non-terminals to get them converted to direct recursion, instead of indirect recursion (if applicable), so that I may apply Rule for removal of direct left recursion:

$$A → Ba → Cda → Dfda → Aafda$$ $$C → Df → Cgf$$ $$D → Df$$ $$D → Cg → Dfg$$ $$D → Aa → Dfdaa$$ So, it becomes: $$A → Aafda| b$$ $$B → Cd | e$$ $$C → Cgf | g$$ $$D → Df | Dfg | Dfdaa | ba | gg$$ So, it becomes (after removal of direct left recursions): $$A → bA'$$ $$A' → afdaA'| eps$$ $$B → Cd | e$$ $$C → gC'$$ $$C' → gfC' | eps$$ $$D → baD' | gg D'$$ $$D'→ fD' | fgD' | fdaaD' | eps$$

My specific Question is: Do I have to follow this way (convert all production rules emanating from all non-terminals or should I do that for only one, e.g. D?

Answer 1

You should focus on trying to only modify productions that aren't "good". A production is "good" if it :

1. Starts with a terminal,
2. Is an epsilon production, or

3. Is in the form A->B (followed by a series of terminals and non-terminals) and we can partially order the non-terminals so that A<B. We'd also have to do some extra checks if B being nullable. That is, if B is nullable, we'd have to consider all productions in which B occurs and is nulled. For example, suppose we have the grammar:

   A -> BAa
   B -> b | esp
   

   At first glance, the rule A->BAa might appear good (because we can assert that A<B), but if B is nulled, we end up with the production A->Aa which is bad. This is usually not a big problem, but you've got to make sure you cover all your cases. Note that this doesn't apply to your example, but I'd figure I'd be thorough.

For your grammar:

• A->Ba is good since we can assert that A<B.

• b is good because this is a terminal.

• For similar reasons, all the productions of B and C are also "good", so we shouldn't change them.

• For D, there are several problems. Obviously, we cannot assert that D<D, and we also can't assert that D<A or D<C (since we assumed that A<B<C<D in our previous step). However, the productions for A, B, and C are all "good", so we can substitute those in and expose the hidden left recursion (as you've done in your work).

In short, you should only worry about modifying "bad" productions and leaving any "good" ones as they are. It's not always possible to do this, but in general, it'll save you work.