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
13/57