compiler-construction - 删除 + 和 - 或 * 或/的左递归的差异？

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) 解析器。或者您可以编写或改编运算符优先算法(请参阅“调车场”)。

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

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