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?