recursion - 左/右递归和 Bison 解析堆栈行为

Question

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

举个例子(只加减法的解析器):

扫描器:

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

解析器:

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

对于 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)，它已经知道更多符号即将到来，所以它必须等到到达列表末尾？

长话短说；

有人可以详细解释一下 Bison 如何管理其解析堆栈，以及它如何使用解析器语法规则进行移位/归约？欢迎愚蠢/人为的例子!

Answer 1

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

NUMBER + NUMBER + NUMBER + NUMBER

在你到达结尾之前不会开始减少，因为每个 NUMBER 开始一个 expression 并且所有表达式都在最后一个 NUMBER.

如果您使用左递归，每个 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 解析器，您必须使用右递归，然后您的语法无法正确描述语言(假设该语言具有左关联运算符，通常是这种情况)。有些人不介意这一点，但我认为语法实际上应该指示正确的解析，而且我发现使语法可被自上而下的解析器解析所必需的修改是困惑且难以阅读的。您的里程可能会有所不同。

---

顺便说一下，“强制你的喉咙”是对试图给你好的建议的文档的一种非常吝啬的描述。持怀疑态度是件好事——如果你努力弄清楚事情为什么会这样运作，你就会更好地理解事情——但许多人只是想要好的建议。