Menu
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?
270
Removing left recursion Left recursion often poses problems for parsers, either because it leads them into infinite recursion (as in the case of most top-down parsers) or because they expect rules in a normal form that forbids it (as in the case of many bottom-up parsers, including the CYK algorithm).
In the production rule above, the variable in the left side occurs at the first position on the right side production, due to which the left recursion occurs. If we have a left recursion in our grammar, then it leads to infinite recursion, due to which we cannot generate the given string.
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.
108
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
