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 回答