0
$\begingroup$

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

enter image description here


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

$\endgroup$

1 Answer 1

1
$\begingroup$

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 :-).

Sometimes it is possible to remove nullable productions without increasing the number of productions. You could do that with your grammar if you wanted to, but the easiest algorithmic solution is unlikely to find that modification.

$\endgroup$
3
  • $\begingroup$ 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... :( $\endgroup$ Jan 11 at 18:36
  • 1
    $\begingroup$ @AbhishekGhosh: the algorithm to remove epsilon productions does not have the goal of minimising grammar size, which is a Hard Problem. So it is not likely to find a smaller ε-free grammar even though one exists. $\endgroup$
    – rici
    Jan 11 at 20:26
  • $\begingroup$ Thanks @rici. Got the point.. $\endgroup$ Jan 11 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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