I want to remove left recursion in grammar:

$G = ({S, A,B,C,D}, {a,b,c},P,S)$

$S → A$

$A → Aa | Bc$

$B → B a |CD$

$C →C b | ε$

$D → Bb | a$

We see that this grammar contains direct recursion ( $A → Aa$ ) and indirect recursion ( $B → CD → D → Bb$ ). We need to remove indirect recursion and convert it into direct recursion.

The problem in this grammar is $C → ε$ rule , so we remove epsilon rules , after that we are left with

$B → B a |CD |D$ which is another indirect recursion so we remove simple rules.

Then we can remove left recursion step by step by alghoritm.

My question is , having large grammar , finding indirect recursion may be difficult. Is there any universal way how to convert indirect recursion to direct recursion? Thanks for answers


1 Answer 1


$S\to A$

$A\to aA'|EP$

$B\to CDB'$

$B'\to AB'|EP$

$C\to bC|EP$

$D\to aD'|bC'DB'bD'$

$D'\to B'bD'|EP$

There is a standard algorithm to remove indirect left recursion check here https://en.wikipedia.org/wiki/Left_recursion#Indirect_left_recursion

  • 2
    $\begingroup$ Something seems wrong with this grammar. It uses the non-terminal $A'$ but there is no rule for $A'$, so $A'$ can never derive any string. This makes me think there is something missing in your answer. And what's $EP$? Also, we prefer that answers come with explanation. How did you get this? Why is it the right answer? Finally, please proof-read your answer to make sure it is readable, and isn't just a jumble of symbols. Deep Joshi kindly edited it for you to show you how to make it easier to read. You can use Markdown and Latex here to improve the formatting of your answer. $\endgroup$
    – D.W.
    Apr 17, 2017 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.