9 Get the algorithm to remove the indirect left recursion fr

9. Get the algorithm to remove the indirect left recursion from a grammar from Aho et al. (2006). Use this algorithm to remove all left recursion from the following grammar: S Aa | Bb A Aa | Abc | c I Sb B bb

Solution

9)

Here is the gramamr
S -> Aa | Bb
A -> Aa | Abc | c | Sb
B -> bb

-----------------------------------------------------------------------------------------------------------------------
Now for first gramamr step introduce new symbol S\'

S -> BbS\'
S\' -> e | S\'aA

----------------------------------------------------------------------------------------------------------------------------------------------------
Now for second gramamr statement...

A -> SbA\' | cA\'
A\' -> e | A\'a | A\'bc

---------------------------------------------------------------------------------------------------------------------------------------------
For third grammar statement it is not required since it doesn\'t contain any recursion

So final gramamr will be

S -> BbS\'
S\' -> e | S\'aA
A -> SbA\' | cA\'
A\' -> e | A\'a | A\'bc
B -> bb