Difference to remove left recursion for + and - or * or /?

Question

To remove the left recursion

E->E+T|E-T|T
T->T*F|T/F|F

for + and *, I am sure it should be

E->TE'
E'->+TE'|(e) (e) is empty string
T->FT'
T'->*FT'|(e)

but for - or /, I am not sure how to remove left recursion, and I came up with the following one, is it right for - and /? Take an example, for plus, a+b = b+a, but for minus, a - b != b -a. So if we use the following right recursive, do we got the problem like a-b?

E->TE'
E'->+TE'|-TE'|(e) 
T->FT'
T'->*FT'|/FT'|(e)

Anyone know compiler explains to me?Thanks in advance.

Answer 1

Left-recursion elimination allows an LL parser to correctly recognize a language, but the resulting parser does not produce the correct parse tree. In particular, it changes left-associative parses for operators such as - and / with right-associative parses.

In order to use the parse to actually interpret the parsed strings, you need to recover the correct parse tree, effectively by reversing the associativity for left-associative operators.

Alternatively, you could just use a bottom-up parser such as an LALR(1) parser generated by yacc/bison. Or you could write or adapt the operator-precedence algorithm (see "Shunting Yard").

If you're going to use the LL grammar in a recursive descent parser, the problem can be avoided since the recursive descent parser typically has an explicit loop instead of a recursion on the right-recursive production (in pseudo-code):

parse_term(): 
  f = parse_factor()
  while peek() is in ('*', '/'):
    op = token()
    f2 = parse_factor()
    f = apply_operator(op, f, f2)
  return f