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

Question

因此，在我< 24 小时的野牛/ 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)，它已经知道更多的符号即将到来，所以它必须等到它到达列表的末尾？

TL; 博士;

有人可以详细解释一下 Bison 如何管理其解析堆栈相对于它如何使用解析器语法规则进行移位/减少？欢迎愚蠢/人为的例子！

Answer 1

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

NUMBER + NUMBER + NUMBER + NUMBER

减少直到你结束才会开始，因为每个都NUMBER以 an 开头，expression并且所有表达式都以最后一个NUMBER.

如果使用左递归，则每个都NUMBER终止 an expression，因此每次NUMBER遇到a 时都会发生减少。

但这不是使用左递归的原因。您使用左递归是因为它准确地描述了语言。如果有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以 anexpression开头，以expression...开头，而解析器永远无法预测 a NUMBER。因此，对于 LL 解析器，您必须使用右递归，然后您的语法无法正确描述该语言（假设该语言具有左关联运算符，这通常是这种情况）。有些人不介意这一点，但我认为语法实际上应该指示正确的解析，而且我发现使用自上而下的解析器使语法可解析所需的修改是混乱且难以阅读的。你的旅费可能会改变。

顺便说一句，“强行压抑你的喉咙”是对文档的非常粗鲁的描述，它试图为您提供很好的建议。持怀疑态度是件好事——如果你努力弄清楚为什么他们会这样工作，你就会更好地理解事情——但很多人只想要好的建议。