Search code examples
compiler-constructiongrammar

Removing left recursion

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?

Solution

  • 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.