# Why not use Right Recursion to avoid Left Recursion?

I am reading about Representative Grammars from book, where I encountered the following grammar:

$$E \rightarrow E + T \ | \ T$$ $$T \rightarrow T * F \ | \ F$$ $$F \rightarrow (E) \ | \ id$$

The above grammar is left-recursive, which is bad. So in order to eliminate left recursion, they changed it to the following:

$$E \rightarrow TE'$$ $$E' \rightarrow +TE' \ | \ \epsilon$$ $$T \rightarrow FT'$$ $$T' \rightarrow *FT' \ | \ \epsilon$$ $$F \rightarrow (E) \ | \ id$$

But why bother so much? Why not simply use a right recursion instead, like the following:

$$E \rightarrow T + E \ | \ T$$ $$T \rightarrow F * T \ | \ F$$ $$F \rightarrow (E) \ | \ id$$

• So I am confused about whether the Right Recursive Grammar I thought of is same as the original grammar or not?
• If not, what's the difference?
• If they are same, why don't we write all grammars as Right Recursion?
• "left-recursive, which is bad" -- perhaps you should try to better understand what "bad" actually means here. E.g. one might say it is bad because it is not LL(1), but then the right recursive variant has the same issue, so it is also "bad".
– chi
Jun 3 '17 at 12:30

The left recursive and the right recursive grammars describe the same language. But grammars do more than give the set of allowed strings in the language, they also give a structure to such strings and that structure is sometimes meaningful. Consider a+b+c; the structure implied by the left recursive grammar is {a+b}+c (I'm using braces and not parenthesis to show the structure to avoid confusion with the common mathematical meaning of parenthesis) the structure implied by the right recursive grammar is a+{b+c}. If mathematically both are equivalent for addition, it is not the case for all operations. Consider subtraction a-{b-c} is not equal to {a-b}-c and that is the later that we usually consider the value of a-b-c.
The version with left-recursion removed is also right-recursive. But its structure is different, and easier to map to the desired structure. With a-b-c-d we have {{a-b}-c}-d for the left-recursive structure, a-{b-{c-d}} for the right-recursive and a{-b{-c{-d}}} for the result of left-recursion removal; that structure allow more easily than the right recursive one to get the intended meaning.
• Why do you say it's easier to convert a{-b{-c{-d}}} than it is to convert a-{b-{c-d}}? You need to do some kind of tree rewriting, either way. Apr 6 '19 at 5:09