CODEWITHSUNDEEP
parsingrecursioncompiler-constructioncontext-free-grammar
techno
techno

Reputation: 6500

Eliminating Epsilon Production for Left Recursion Elimination

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

S-->Aa/b

A-->Ac/Sd/∈

I can see after removing the epsilon productions the grammer becomes

  1) S-->Aa/a/b

  2)A-->Ac/Sd/c/d

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

Upvotes: 1

Views: 2160

Answers (1)

Shlomi
Shlomi

Reputation: 4748

lets look at the rule S->Aa, if A->∈ then S->∈a giving just S->a, so together with the previous rules we get S->Aa|a|b

now lets check the rule A->Ac and A->∈c which gives us A->c.

what about A->Sd? I dont see how you got A->d as a rule. if that is a rule, then the string "da" is accepted by this grammar (S->Aa & A->d --> "da"), but try to construct this string with the original grammar - if you start with S and the string finishes with a, it means you must use S->Aa, but then in order to have a "d" you must use A->Sd, which forces us to have another "a" or "b", meaning we cannot construct this string, and the rule A->d is not correct.

Upvotes: 2

Related Questions