Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

compiler design
communitycreator

What is left recursion and how do you eliminate left recursion?

Buchiredddypalli Koushik

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Left recursion

A grammar in the form G = (V, T, S, P) is said to be in left recursive form if it has the production rules of the form A → A α |β.

  • In the production rule above, the variable in the left side occurs at the first position on the right side production, due to which the left recursion occurs.

  • If we have a left recursion in our grammar, then it leads to infinite recursion, due to which we cannot generate the given string.

How to eliminate left recursion

We can eliminate left recursion by replacing a pair of production with:

A → βA′

A′ → αA′|ϵ

Example:

i) E → E+T|T

ii) T → T*F|F

iii) F → (E)|id

The left and right variables are the same in the production rules above, that is, E and T.

So to eliminate the left recursion, we have to change the production rules to a different form.

In the production rules above:

i) E → E+T|T

α=+T and  β=T

E → TE′

E′→ +TE′|ϵ

In the production rule above, we still have left recursion:

ii) T → T*F|F 

α=*F and  β=F

T → FT′

T′→ *FT′|ϵ

After eliminating the left recursion, the final production rules are as follows:


E → TE′

E′→ +TE′|ϵ

T → FT′

T′→ *FT′|ϵ

F → (E)|id

RELATED TAGS

compiler design
communitycreator

CONTRIBUTOR

Buchiredddypalli Koushik

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring