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

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