Why not use Right Recursion to avoid Left Recursion?

Question

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?

Answer 1

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.

Answer 2

You can use a grammar to recognize a language, but usually you want more: You want to know how a string was parsed. (That's why we want grammars that are unique, otherwise there are sentences that can be parsed in more than one way).

Your changes don't change the language that is recognised, but they change the parse tree. If the sentence is a - b + c, then a left recursive parser might parse it as an operator "+" with two operands "a-b" and "c", while a right recursive one parses it as an operator "-" with operands "a" and "b+c". That's a huge change in meaning. If you want the sentence to mean "take a, subtract b, add c" then you need a lot of extra work with the right recursive parser.

Answer 3

The reason is, associative of the operators will change in the grammar that you have mentioned which may yield a different result But the right recursive grammar given in the book maintains associativity thus giving the same language.