The following grammar has left recursion:
T -> Tx | TYx | YX | x
X -> xx
Y -> Yy | Yx | y
How do you go about removing left recursion. I read the wikipedia explanation, but I'm fairly new to CFGs so it did not make a lot of sense. Any help is appreciated? A plain english explanation would be even more appreciated.
In this example, you can follow Robert C. Moore's general algorithm to convert a rule with left recursion to a rule with right recursion:
In our first case:
A=T, a1=x, a2=Yx, b1=y, b2=x
... (similarly forY
)