# Remove left recursion from a grammar without necessarily removing epsilon production

Consider the grammar

$$S →Aa∣b$$ $$A →Ac∣Sd∣ϵ$$

Construct an equivalent grammar with no left recursion and with minimum number of production rules. $$\tag {GATE-CS-1998}$$

While solving this question, based on the term "minimum number of production rules", I tried as follows:

First removed indirect left recursion and the grammar becomes:

$$S →Aa∣b$$ $$A →Ac∣Aad∣bd∣ϵ$$

Then using the simple method of removing left recursion based on the following :

$$A \rightarrow A\alpha_1, |A\alpha_2| ... | A\alpha_m | \beta_1 | \beta_2 | ... | \beta_n$$

where no $$\beta_i$$ begins with an $$A$$. Then, we replace the $$A$$-productions by

$$A \rightarrow \beta_1A' | \beta_2 A'| ... | \beta_nA'$$ $$A' \rightarrow \alpha_1A' |\alpha_2A'| ... | \alpha_m A'| \epsilon$$

Assuming $$\beta_1=bd$$ and $$\beta_2=\epsilon$$, I get,

$$S →Aa∣b$$ $$A \rightarrow bdA'∣A'$$ $$A' \rightarrow cA'|adA'|\epsilon$$

A rough analysis shows that this grammar worked out by me, is equivalent to the original grammar.

Now if we consider the algorithm given in the Compilers text by Ullman et. al In the algorithm above, the authors are assuming the input grammar to be free from $$\epsilon$$ productions. Is it strictly necessary? Is there any specific case, where not following the algorithm strictly shall lead to wrong answers.

Application of the Ullman algorithm is easy, but it is increasing the number of productions, mainly due to the removal of the $$\epsilon$$ production

If a grammar includes nullable productions, then it may have hidden left recursion; a production such as $$A\to N A \beta$$ where $$N$$ is nullable. Such a production won't be removed by Ullman's algorithm, but it is nonetheless left-recursive. So it's usual to start by removing $$\epsilon$$ productions, thus guaranteeing that there are no nullable non-terminals and therefore that all left-recursion is visible.
There is no hidden left recursion in the grammar you are working on, but the easiest way to prove that is to remove the $$\epsilon$$ productions :-).
• Thanks @rici for your answer once again. But can you please explain the last line but the easiest algorithmic solution is unlikely to find that modification. I did not get it... :( Jan 11 at 18:36