Left/Right 递归和 Bison 解析堆栈行为

Question

因此，在我不到 24 小时的 bison/flex 调查中，我看到很多文档表明左递归优于右递归。有些地方甚至提到，对于左递归，您需要在 Bison 解析器堆栈上使用常量 space，而右递归需要 N space 阶。但是，我找不到任何可以明确解释正在发生的事情的来源。

举个例子（只会加减法的解析器）：

扫描仪：

%%
[0-9]+ {return NUMBER;}
%%

解析器：

%%
/* Left */
expression:
    NUMBER
  | expression '+' NUMBER { $$ =  + ; }
  | expression '-' NUMBER { $$ =  - ; }
  ;
/* Right */
expression:
    NUMBER
  | NUMBER '+' expression { $$ =  + ; }
  | NUMBER '-' expression { $$ =  - ; }
  ;
%%

对于 1+5-2 的例子，它似乎是左递归，解析器从词法分析器接收到 '1' 并看到 '1' 匹配 expression: NUMBER 并将值为 1 的表达式推送到解析器堆栈。它看到 + 并推动。然后它看到 5 和表达式 (1)，+ 和 5 匹配 expression: expression '+' NUMBER 所以它弹出两次，进行数学运算并将一个值为 6 的新表达式压入堆栈，然后重复减法。在任何一点，堆栈中最多有 3 个符号。所以它就像一个就地计算，从左到右运算。

对于正确的递归，我不确定为什么它必须将所有符号加载到堆栈上，但我将尝试描述为什么会是这种情况。它看到一个 1 并匹配 expression: NUMBER，因此它将一个值为 1 的表达式压入堆栈。它将“+”压入堆栈。当它看到 5 时，我的第一个想法是 5 本身可以匹配 expression: NUMBER，因此是一个值 5 的表达式，然后它加上堆栈中的最后两个符号可以匹配 expression: NUMBER '+' expression 但是我的假设是因为 expression 在规则的右边，所以它不能抢先一步将 5 作为一个表达式作为 NUMBER 求值，因为使用 LALR(1)，它已经知道更多的符号即将到来，所以它必须等到它到达列表末尾？

TL；DR；

有人可以详细解释一下 Bison 如何管理其解析堆栈，以及它如何 shift/reduction 使用解析器语法规则吗？ Silly/contrived 欢迎举例！

Answer 1

使用 LR（自下而上）解析，每个非终结符在遇到其最后一个标记时被精确减少。（LALR 解析是一种简化的 LR 解析，它处理前瞻的精确度略低。）在减少非终端之前，它的所有组件都存在于堆栈中。所以如果你使用正确的递归并且你正在解析

NUMBER + NUMBER + NUMBER + NUMBER

减少直到你结束才会开始，因为每个 NUMBER 开始一个 expression 并且所有表达式都在最后一个 NUMBER.[=30= 结束]

如果使用左递归，每个 NUMBER 都会终止一个 expression，因此每次遇到 NUMBER 时都会进行归约。

但这不是使用左递归的原因。您使用左递归是因为它准确地描述了语言。如果您有 7 - 2 - 1，您希望结果为 4，因为这是代数规则所要求的：表达式被解析为就好像它是 (7 - 2) - 1，因此必须首先减少 7 - 2。使用右递归，您会错误地将其计算为 6，因为 2 - 1 会先减少。

大多数运算符关联到左边，所以你使用左递归。对于偶尔向右关联的运算符，您需要正确的递归并且必须忍受堆栈的增长。没什么大不了的。你的机器有很多内存。

例如，考虑赋值。 a = b = 42 表示 a = (b = 42)。如果你这样做是左关联的，你首先将 a 设置为 b，然后尝试将某些东西设置为 42； (a = b) = 42 在大多数语言中都没有意义，这肯定不是预期的操作。

LL（自上而下）解析使用前瞻性来预测哪些生产将减少。它根本无法处理左递归，因为预测以递归循环结束：expression 以 expression 开头，而 expression 以 expression 开头……解析器永远无法预测一个NUMBER。因此，对于 LL 解析器，您必须使用右递归，然后您的语法无法正确描述语言（假设该语言具有左关联运算符，通常是这种情况）。有些人不介意这一点，但我认为语法实际上应该指示正确的解析，而且我发现使语法可被自上而下的解析器解析所必需的修改是混乱且难以阅读的。您的里程可能会有所不同。

顺便说一下，"force down your throat" 是一个非常简陋的文档描述，它试图给你很好的建议。持怀疑态度是件好事——如果你努力弄清楚事情为什么会这样，你就会更好地理解事情——但很多人只是想要好的建议。

Answer 2

因此，在阅读了 bison 文档中这一相当重要的页面之后：

https://www.gnu.org/software/bison/manual/html_node/Lookahead.html#Lookahead

结合运行

%debug

和

yydebug = 1;

在我的 main()

我想我完全明白发生了什么。

使用左递归，它看到 1 并将其移位。超前现在是+。然后它确定它可以通过 expression: NUMBER 将 1 减少到 expression。所以它弹出并在堆栈上放置一个 expression 。它移动 + 和 NUMBER(5)，然后看到它可以通过 expression: expression '+' NUMBER 减少并弹出 3x 并推送一个新表达式 (6)。基本上，通过使用 lookahead 和规则，bison 可以在读取令牌时随时确定是否需要移动或减少。如此重复，解析堆栈上最多有 3 个 symbols/groupings（对于这个简化的表达式求值部分）。

通过右递归，它看到 1 并将其移位。超前现在是+。解析器认为没有理由将 1 减少为表达式 (1)，因为没有规则 expression '+' 所以它只是继续移动每个标记，直到它到达输入的末尾。此时，堆栈上有 [NUMBER, +, NUMBER, -, NUMBER] 所以它发现最近的数字可以减少到 expression(2) 然后移动它。然后开始应用规则（`expression: NUMBER '-' expression'）等

所以我理解的关键是 Bison 使用前瞻标记来做出关于现在减少或只是根据它可以支配的规则移动的智能决策。

Left/Right 递归和 Bison 解析堆栈行为

Left/Right recursion and Bison parsing stack behavior

recursion

bison

flex-lexer

yacc

lex