删除 + 和 - 或 * 或 / 的左递归的区别？

Question

移除左递归

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

对于+和*，我确定应该是

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

但是对于 - 或 /，我不确定如何删除左递归，我想出了以下一个，它适合 - 和 / 吗？举个例子，对于加号，a+b = b+a，但对于减号，a - b != b -a。那么如果我们使用下面的右递归，我们是否得到了像a-b这样的问题？

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

有谁知道编译器向我解释的吗？在此先感谢。

Answer 1

左递归消除允许 LL 解析器正确地识别一种语言，但生成的解析器不会生成正确的解析树。特别是，它将 - 和 / 等运算符的左关联解析更改为右关联解析。

为了使用解析来实际解释已解析的字符串，您需要通过反转左关联运算符的关联性来有效地恢复正确的解析树。

或者，您可以只使用自下而上的解析器，例如 yacc/bison 生成的 LALR(1) 解析器。或者您可以编写或改编运算符优先算法（请参阅 "Shunting Yard"）。

如果你打算在递归下降解析器中使用 LL 语法，这个问题是可以避免的，因为递归下降解析器通常有一个显式循环而不是右递归产生式的递归（在伪-代码):

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

删除 + 和 - 或 * 或 / 的左递归的区别？

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

compiler-construction

grammar

left-recursion