Scribd
Upload
5 views9 pages

Left Recursion Elimination in Compilers

Uploaded by

ankurvatsa3
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
5 views9 pages

Left Recursion Elimination in Compilers

Uploaded by

ankurvatsa3
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

BCSE307L

Compiler Design
MODULE – 2
Dr. WI. Sureshkumar
Associate Professor
School of Computer Science and Engineering (SCOPE)
VIT Vellore
[Link]@[Link]
SJT413A34
Left Recursion
Left Recursion
Example -1
E→E+T/T
T→T*F/F
F → ( E ) / id
Eliminate the immediate left recursion,
E → TE’
E’ → +TE’ / 
T → FT’
T’ → *FT’ / 
F → ( E ) / id
Example -2
S → Aa / b
A → Ac / Sd / 
Here both S and A are left recursive,
S  Aa  Sda
Since S is not immediate left recursive, keep S- productions as it is. Use
the S-production in A-productions,
A → Ac / Aad / bd /
Now eliminate left recursion in A-productions,
A → bdA’ / A’
A’ → cA’ / adA’ /  S → Aa / b
Problem
Eliminate left-recursion from the following grammar,
S→( L )/a
L→L,S/S

S→( L )/a
L → SL’
L’ →, SL’ / 
Left factoring
Left factoring
Left factoring

You might also like