3

删除左递归

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。所以如果我们使用下面的右递归，我们会遇到像ab这样的问题吗？ 

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

任何人都知道编译器向我解释？在此先感谢。

4

1 回答 1

3

左递归消除允许 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
于 2015-10-25T18:39:40.033 回答