Im following the algorithm for left recursion elimination from a grammar.It says remove the epsilon production if there is any

I have the following grammer



I can see after removing the epsilon productions the grammer becomes

  1) S-->Aa/a/b


Im confused where the a/b comes in 1) and c/d comes in 2) Can someone explain this?


A is nullable, that is, A has a production which is epsilon.

Given that A is nullable, you have to revisit any productions containing one or more instances of A and replace them with the set of productions formed from every possible replacement of A with null, including no instances replaced and with all instances replaced.

So looking at the production S->Aa we need to replace it with the production where A is not replaced (the same production) and the production where A is replaced with null (which is s->a). Now there's three total productions for S.

S-> Aa/a/b

When we look at the production A-> Ac we have to do the same thing, so Ac is replaced with Ac/c and we get...


You could rearrange it as necessary.

Sd does NOT become replaced with Sd/d because S is not nullable. There is no way to produce epsilon from S, so we don't replace S in productions.


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.