Question

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

Answer 1

Explanation:

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