CODEWITHSUNDEEP
parsingrecursioncompiler-constructioncontext-free-grammar
Setu Kumar Basak
Setu Kumar Basak

Reputation: 12022

How to Eliminate Left Recursion having epsilon Production?

I have seen this link.But i am little bit confused how to eliminate the ∈ production here.

I have the following grammer

 S-->Sz|Sxw|xw|yw|∈

I can see after removing the epsilon productions the grammer becomes

 S-->Sz|Sxw|xw|yw|z

Now if i solve this i got like below

  S-->xwS`|zS`|ywS`
  S`-->zS`|xwS`|∈

Now i can see that S-->xwS`|zS` and S`-->zS` |xwS` .This has become same.Is it right or i am doing any mistake??

Upvotes: 0

Views: 831

Answers (1)

Peter Uhnak
Peter Uhnak

Reputation: 10197

There's nothing wrong with the rules being repeated.

One way I often find useful when trying to understand a grammar is to convert it to a regular expression

 S := (xw + yw + z)(z + xw)*

because it gives me a nice overview of the whole grammar and helps with finding errors. So if I split it into this:

 S  := (xw + yw + z)S'
 S' := (z + xw)*

it makes it much more easier to see if I made any mistakes.

Upvotes: 1

Related Questions