CODEWITHSUNDEEP
parsingrecursion
user623990
user623990

Reputation:

Eliminating left recursion (can't seem to get it)

I've got the following grammar:

S --> SaA
S --> bB
A --> aB
A --> c
B --> Bb
B --> d

Now, looking at the general rule for solving left recursion, I can say:

B --> dB'
B' --> e | bB'

But that's as far as I can get. I tried expanding S:

S --> SaA | bB
S --> SaaB | Sac | bB

But I can't get it in the proper form for the algorithm.

What am I missing?

Upvotes: 0

Views: 42

Answers (1)

Bergi
Bergi

Reputation: 664980

I wonder why you are trying to "expand" S. The form that it already is in, 

S  -> SaA | bB

fits perfectly to apply the same transformation as you did to B. It'll become

S  -> bBS'
S' -> ε | aA

Now, you can expand that BS' if you want.

Upvotes: 1

Related Questions