$S \rightarrow Sa \mid S \mid \epsilon$

This is a weird case where I have only one non-terminal. I'm trying to apply the algorithm 4.19 in the dragon book. It don't think it should be applicable but I think it gives something like that :

$S \rightarrow S'$

$S' \rightarrow aS \mid S' \mid \epsilon $

but this is equivalent to say

$S' \rightarrow aS' \mid S' \mid \epsilon $

Is this the right way to think about this?


Yes that is correct. Also you can safely remove $A\rightarrow A$ type of production rules. So the equivalent grammar is $S'\rightarrow aS'\ |\ \epsilon$.

If you analyze carefully you will see that you are not applying Algorithm 4.19 at all. We are just removing left recursion where we have only immediate left recursion.

Cycles are of the form $A\rightarrow B, B\rightarrow C, C\rightarrow A$. When we remove left recursion in immediate left recursive grammars, we are ignoring $S\rightarrow S$.

Also presence of $\epsilon$ creates problem for the algorithm 4.19 given in the red dragon book (2007 edition), but the method of removing left recursion in immediate left recursive grammar works even in the presence of $\epsilon$.

  • 1
    $\begingroup$ It is weird that it works in a sense because it says in the book that I must not have a $\epsilon$ production nor a cycle but I have both so why do they say that then? $\endgroup$ – Maxime Roussin-Bélanger Feb 24 '16 at 23:36
  • $\begingroup$ @Mike I have added explanation in the answer. $\endgroup$ – Shreesh Feb 25 '16 at 11:43

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.