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?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top