Removing left recursion

Question

The following grammar has left recursion

E= E+T|T
T= T*F|F
F= a|b|c

How to remove it? Is there any general procedure for it?

Answer 1

Yes, there is a general procedure, see e.g. wikipedia.

E = TE'
E'= (e) | +TE'
T = FT'
T'= (e) | *FT'
F = a | b | c

// (e) is "epsilon" which is defined as the empty string

It should be mentioned that this alters the associativity of + and * from left to right. That is, where before a + b + c was parsed as (a + b) + c, it is now parsed as a + (b + c).

This is not a problem for addition and multiplication, but it would be a problem for subtraction and division, for example.

Wikipedia article has more detail on the left-recursion removal procedure and its intricacies.

Answer 2

The general procedure is found at Wikipedia, for example. I'll demonstrate for E = E+T|T:

E is the left-recursive non-terminal. +T is the non-null sequence (alpha). T is the sequence which doesn't start with E (beta).

We create a new nonterminal for the "rest", ie. the non-null sequence. This handles the recursion.

E' = epsilon|+TE'

And we modify the original rule to use the new nonterminal to handle the recursion.

E = TE'

Answer 3

As others have pointed out, there is a general procedure for replacing left recursion with right recursion. The other answers show well how to use that general procedure to remove the left recursion in the given grammar.

Here is a solution that restructures the given grammar in a way that is specific for that grammar.

E= T+E|T
T= F*T|F
F= a|b|c

Answer 4

the production

E = E+T
  | T
T = T*F
  | F
F = a|b|c

goes to

E= T ('+' T)*
T= F ('*' F)*
F= a|b|c

To maintain the same processing where the fist E disjunct is processed with A(E,T). the new version uses:

ret = T1;
while(set.more()) ret = A(ret, set.pop_front().T);