CODEWITHSUNDEEP
recursiongrammarcontext-free-grammarleft-recursion
user3562135
user3562135

Reputation: 159

Removing Left Recursion Process

I'm just curious about something when doing left recursion, i've done this question and when i've done left recursion i've added F to everything in S. Do we always do this for left recursion (My teacher hasn't explained it very well). 

1)
S -> aSb | bSb | Sc | bc

left recursion:
S -> aSbF | bsbF | bcF
F -> cF | ε

Factorising:

S -> aSbF | bX
X -> aSbFbF | bXbF | cF
F -> cF |  ε

Upvotes: 0

Views: 147

Answers (1)

Joshua Duxbury
Joshua Duxbury

Reputation: 5260

You would do that every time you have immediate left recursion. (Where it calls itself directly)

The only other time you wouldn't do this is if you have In-direct recursion, for example..

This is a long one to solve..

A -> Ba
B -> dab | Cb
C -> cB | Ac

The above is an example of indirect left recursion. The term "C" calls A. in this case you would need to move the contents of A to C..

C -> cB | Bac

More steps are needed to complete this example.. But eventually you will end up with immediate left recursion, where C will call itself.

Upvotes: 1

Related Questions