Left Recursion Replacement
A
A
x
y
…
Illustration:
Idea: Replace rules of the form A ® Ax, A ® y with A ® yA’, A’ ® xA’, A’ ® e, where A’ is a new nonterminal.
Example:
E ® E+T
E ® T  
T ® T*F
T ® F
F ® (E)
F ® i
x
A
A
x
…
A’
x
y
…
x
A
x
…
A’
A’
A’
e
E ® TE’, E’ ® +TE’, E’ ® e
T ® FT’, T’ ® *FT’, T’ ® e
F ® (E)
F ® i
13/57