删除+和-或*或/的左递归的区别 [英] Difference to remove left recursion for + and - or * or /?

问题描述

要删除左递归

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

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

for + and *, I am sure it should be

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

但是对于-或/，我不确定如何删除左递归，我想出了下一个，对-和/是否正确？举个例子，正号为a + b = b + a，负号为a-b！= b -a。因此，如果我们使用以下正确的递归，是否会遇到像a-b这样的问题？

but for - or /, I am not sure how to remove left recursion, and I came up with the following one, is it right for - and /? Take an example, for plus, a+b = b+a, but for minus, a - b != b -a. So if we use the following right recursive, do we got the problem like a-b?

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

有人知道编译器向我解释过吗？

Anyone know compiler explains to me?Thanks in advance.

推荐答案

左递归消除允许LL解析器以正确地识别一种语言，但是生成的解析器不能产生正确的解析树。尤其是，它会为操作符（例如-和 / ）的左关联分析更改为右关联分析。

Left-recursion elimination allows an LL parser to correctly recognize a language, but the resulting parser does not produce the correct parse tree. In particular, it changes left-associative parses for operators such as - and / with right-associative parses.

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

In order to use the parse to actually interpret the parsed strings, you need to recover the correct parse tree, effectively by reversing the associativity for left-associative operators.

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

Alternatively, you could just use a bottom-up parser such as an LALR(1) parser generated by yacc/bison. Or you could write or adapt the operator-precedence algorithm (see "Shunting Yard").

如果您要在递归下降解析器中使用LL语法，之所以可以避免此问题，是因为递归下降解析器通常具有显式循环，而不是对右递归产生式进行递归（使用伪代码）：

If you're going to use the LL grammar in a recursive descent parser, the problem can be avoided since the recursive descent parser typically has an explicit loop instead of a recursion on the right-recursive production (in pseudo-code):

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

这篇关于删除+和-或*或/的左递归的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！