左递归

玻尔百科

核心要点

左递归是一种文法规则，它将一个非终结符定义为以其自身作为第一个符号，从而导致自顶向下解析器陷入无限循环。
消除左递归涉及将文法转换为等价的右递归形式，这种形式巧妙地利用程序的调用栈来管理从左到右的状态。
虽然左递归对自顶向下解析器来说是个问题，但它能自然地为左结合运算建模，并且可以被自底向上解析器高效处理。
如何处理左递归的选择揭示了在文法设计、解析策略选择和整体算法效率之间的根本性权衡。

引言

在计算机科学的世界里，文法是定义语言结构的蓝图，从复杂的编程语言到简单的数据格式都概莫能外。解析器作为这些蓝图的解释者，必须遵循其规则来理解代码。然而，一种看似无害的模式，即左递归，却带来了一个根本性的挑战，能让解析器寸步难行。这个问题中，一条规则将一个实体定义为其自身的第一个组成部分，从而产生了一个逻辑循环，这对某些优雅的解析策略是致命的。本文将深入探讨左递归的核心，解决其直观表述与问题实现之间的鸿沟。在接下来的章节中，我们将首先揭示这一概念的内部工作原理，探索其失败的原因以及修复它的巧妙转换。然后，我们将拓宽视野，看看这个“缺陷”如何在其他情境下成为一种强大的工具，将编译器设计与更广泛的计算和语言学领域联系起来。

原理与机制

要真正理解任何思想，我们绝不能满足于仅仅知道它是什么；我们必须踏上一段旅程，去发现它为何如此，去观察其内部运作，并欣赏赋予其生命的精巧机制。计算机科学中的左递归概念也不例外。表面上看，它似乎只是编译器编写者遇到的一个技术麻烦。但如果我们仔细观察，就会发现它为了解结构、语言以及连接二者的算法的本质打开了一扇迷人的窗口。

让我们想象一位程序员，即我们的“解析器”，是一位一丝不苟的故事讲述者。这位讲述者有一本文法书，里面包含一套构建句子的规则，其工作是读取一串单词并弄清楚故事的结构。它以“自顶向下”的方式执行此操作：从最宏大的概念开始，比如“表达式”，然后尝试根据其规则手册将其分解为更小的部分。这种分解过程自然是递归的。

自我引用的陷阱

我们的故事讲述者从文法书中挑选了一条看起来非常直观的规则来定义算术表达式：“一个表达式可以是另一个表达式，后跟一个 + 号和一个数字。”用形式文法表示，这看起来异常简洁：

$E \to E + T$

在这里， $E$ 代表“表达式”（Expression）， $T$ 代表“项”（Term）（在此暂且视为一个数字）。对我们人类的直觉来说，这完全合理。但对我们刻板的故事讲述者来说，这是一个陷阱。为了理解一个 Expression，规则告诉它要做的第一件事就是……理解一个 Expression。于是，它递归地调用了自己。这个新的调用查看同一条规则，并立即再次调用自己。一次又一次。故事讲述者陷入了一个恶性循环，就像一个词典条目写着“递归：见递归”。它甚至没有机会查看输入文本中是否有 + 号。它无法取得任何进展，其待处理任务的堆栈无限增长，最终导致壮观的崩溃——栈溢出。

这就是左递归的本质：一条文法规则中，一个非终结符（如 $E$ ）在其产生式的右侧以自身作为第一个符号。对于一大类简单而优雅的自顶向下解析器，比如我们所设想的递归下降解析器，这是一个根本性的障碍。

有趣的是，这并非一个普遍存在的问题。另一种类型的解析器，即“自底向上”解析器，则不会遇到这个问题。它的工作方式是从输入标记开始逐步构建结构，所以它会愉快地识别出一个 Term，然后是一个 Expression，接着看到一个 + 和另一个 Term，然后说：“啊哈！我可以把这个 Expression 和 Term 组合成一个更大的 Expression。”但我们的目标是拯救我们直观的自顶向下故事讲述者，而不是替换它。为此，我们不能改变故事讲述者；我们必须巧妙地重写它的文法书。

一个巧妙的转换：化恶性循环为链条

解决左递归的方法是一套优美的智力体操。我们取其自我引用的规则并重新表述它。我们不再说“一个表达式是一个表达式加一个项”，而是说“一个表达式以一个必需的项开始，后跟一个由零个或多个 + Term 片段组成的链条”。

把它想象成一列火车。旧规则试图通过说“一列火车是一列火车后面跟着一节车厢”来定义火车，这是一个逻辑循环。新规则说：“一列火车是一个火车头，后面跟着一个可选的车厢序列。”火车头是必需的，这为我们提供了一个具体的起点。

形式上，我们取一个像这样的文法： $E \to E + T \mid T$ 并将其转换为一个等价的文法：

E \to T \, E' \\ E' \to + \, T \, E' \mid \epsilon \end{align*}$$ 让我们来剖析一下。关于 $E$ 的新规则说，一个表达式*必须*以一个 $T$ 开始。这打破了无限循环，因为我们的解析器现在可以立即尝试在输入中寻找一个数字。在找到一个 $T$ 之后，它接着寻找一个 $E'$（我们的“车厢链”）。关于 $E'$ 的规则说，它既可以是一个 `+` 号和另一个 $T$，后跟链条的其余部分（递归的 $E'$），也可以什么都不是（用 $\epsilon$ 表示，即空字符串）。 ​**​左递归​**​被转换成了​**​右递归​**​。恶性循环变成了一条有限的、线性的链条。有了这个转换后的文法，我们的解析器处理一连串加法的时间不再是无限的；它与输入的长度成正比，是一个简洁的 $\Theta(n)$。我们拯救了我们的故事讲述者。但是，在这样做的时候，我们不知不觉地创造了什么机制呢？ ### 机器中的幽灵：[调用栈](/sciencepedia/feynman/keyword/call_stack)如何记住一切 这个转换看起来纯粹是一个句法上的技巧。但它对我们的解析器如何“思考”以及如何计算结果产生了深远的影响。假设我们不仅要识别表达式，还要计算它的值。 对于原始文法 $E \to E_1 + T$，语义规则简单且自底向上：$E.val = E_1.val + T.val$。更大表达式的值就是其各部分值的总和。这是一个纯粹的​**​综合属性​**​；值是从[解析树](/sciencepedia/feynman/keyword/parse_trees)的子节点综合或构建起来的。 但是我们的转换改变了[解析树](/sciencepedia/feynman/keyword/parse_trees)的结构！对于像 `n1 + n2 + n3` 这样的输入，新文法不会首先组合 `(n1 + n2)`。相反，它看到 `n1`，然后是其余部分 `+ n2 + n3`。它如何能计算出正确的从左到右的和呢？ 答案在于计算机自身的内存：​**​[调用栈](/sciencepedia/feynman/keyword/call_stack)​**​。调用栈是计算机用来跟踪活动[函数调用](/sciencepedia/feynman/keyword/procedure_call)的一堆笔记。当我们的解析器处理新文法时，它不仅将[调用栈](/sciencepedia/feynman/keyword/call_stack)用于递归，还将其作为工作内存。 下面是展开的优雅之舞： 1. 解析器从 $E \to T E'$ 开始。它首先解析一个 $T$（比如 `n1`）并获取其值。 2. 在调用处理 $E'$ 的函数之前，它将这个值*向下*传递给它，就像接力赛中的接力棒一样。这是一个​**​继承属性​**​。我们可以将规则想象成 $E'.inh = T.val$。现在，$E'$ 函数“知道”当前的运行总计是 `n1` 的值。 3. 处理 $E'$ 的函数现在查看输入。如果它看到 `+ T`（例如 `+ n2`），它会解析 `n2`，将其值加到继承的总和上（$E'.inh + T.val$），然后递归调用自身，将这个*新*的运行总计向下传递给链中的下一个 $E'$。 4. 这个过程一直持续到表达式的末尾。最后一个 $E'$ 看不到更多的 `+` 号，于是选择了 $E' \to \epsilon$ 规则。此时，它的继承属性持有最终的和。 5. 然后，它将这个最终的和作为​**​综合属性​**​ *向上*传回[调用栈](/sciencepedia/feynman/keyword/call_stack)。每个 `E'` 函数返回它从下面的调用中接收到的值，直到最终的值到达顶层的 $E$ 节点。 这揭示了一种美妙的统一性。纯粹的句法文法转换迫使语义信息的流动也发生了相应的变化。我们不得不从纯粹自底向上的​**​[S-属性定义](/sciencepedia/feynman/keyword/s_attributed_definition)​**​转变为混合流的​**​L-属性定义​**​，后者使用继承属性在解析过程中将信息从左到右传递。[调用栈](/sciencepedia/feynman/keyword/call_stack)，这个程序执行的基本组件，成为了这种从左到右信息流的物理体现。 ### 结构、性能与思维形态 这种转换告诉了我们关于结构和性能的什么信息？对于像 `x1 + x2 + ... + xn` 这样的扁平表达式，原始的左结合文法意味着一个深度不平衡或“倾斜”的[抽象语法树](/sciencepedia/feynman/keyword/abstract_syntax_tree)（AST）。这棵[树的高度](/sciencepedia/feynman/keyword/tree_height)是线性的，即 $\Theta(n)$。 我们的文法转换旨在保持其含义（左[结合性](/sciencepedia/feynman/keyword/associativity)），因此必须产生一个行为能反映这种倾斜结构的解析器。确实，对 $E'$ 的递归调用链导致的最大调用栈深度也是线性的，即 $\Theta(n)$。解析器的栈深度直接反映了它正在构建的概念[树的高度](/sciencepedia/feynman/keyword/tree_height)。右结合文法只会将树和[调用栈](/sciencepedia/feynman/keyword/call_stack)向另一个方向倾斜，但线性深度将保持不变。一个真正平衡的、对数深度的树，即 $\Theta(\log n)$，只有在输入本身通过平衡的括号进行结构化时才会出现，例如 `((x1+x2)+(x3+x4))`，从而强制进行平衡分组。 这段旅程向我们表明，左递归的挑战并非一个孤立的缺陷。这是一个关于文法结构与解析器操作策略之间兼容性的深层次问题。虽然我们的转换对于自顶向下解析器是一个优雅的解决方案，但它并非唯一。还存在其他更强大的解析算法，如 ​**​Earley 解析器​**​，它使用一种巧妙的动态规划技术来构建一个可能性的“图表”。这种方法可以直接处理左递归文法，无需任何转换，通过记住并重用子解析的结果来避免无限循环。 最终，左递归的故事本身就是计算机科学的一个缩影。我们从一个直观的想法开始，通过严格的分析发现其局限性，设计一个巧妙的转换来克服它们，并在此过程中，揭示了句法、语义和计算底层机制之间一种美妙而出乎意料的统一性。

应用与跨学科联系

我们花了一些时间来了解左递归，这个在我们文法规则中看似奇特的循环，其中一个事物在其定义的最左边由其自身来定义。初看之下，它可能像一个缺陷，一个在开始任何严肃工作之前需要被解开和“消除”的逻辑疙瘩。但在科学和工程领域，我们经常发现，最初被标记为“问题”的现象，实际上是通往更深层次理解的钥匙，或者在适当的情境下，是出人意料的优雅解决方案。

左递归也是如此。现在，让我们踏上一段旅程，去看看这个所谓的缺陷在哪些地方根本不是缺陷，而是一种强大、优美且极其有用的工具，它将抽象的文法世界与具体的计算任务联系起来。

机器的自然语言

你如何计算 $3 * 4 * 5$ ？你几乎肯定会从左到右计算：首先 $3 * 4$ 得 $12$ ，然后 $12 * 5$ 得 $60$ 。这种属性，即左结合性，已深深植根于我们对算术的理解中。如果一个编译器要将人类可读的代码翻译成机器可执行的指令，它必须尊重这一约定。我们如何教一台机器这种从左到右的特性呢？

一种方法是编写一个体现这种特性的文法。像 $E \to E * T$ 这样的左递归文法完美地做到了这一点。文法本身的结构反映了计算的结构。要解析像 w * x * y * z 这样的表达式，文法会自然地将其分组为 (((w * x) * y) * z)。

这不仅仅是一种美学上的匹配；它为生成代码提供了一个直接的蓝图。想象一个简单的基于栈的计算器。要计算 $A * B$ ，你将 $A$ 推入栈，将 $B$ 推入栈，然后执行一条 MUL 指令，该指令弹出它们，将它们相乘，并将结果推回栈中。左递归文法可以用来极其优雅地生成这一系列指令。规则 $E \to E_1 * T$ 转化为一个简单的配方：首先，为子表达式 $E_1$ 生成代码（这会将其结果留在栈上），然后为 $T$ 生成代码（这会将其结果放在第一个结果之上），最后，追加 MUL 指令。这个过程，被称为语法指导的翻译，展示了左递归最光辉的时刻：不是一个需要解决的问题，而是一个将文法结构直接、直观地转化为计算行动的指南。

转换的代价

正如我们所见，一些解析方法——特别是那些试图从根向下构建解析树的自顶向下解析器——会在左递归上“窒息”，进入无限循环。对它们而言，我们必须进行转换，将像 $S \to S a \mid b$ 这样的规则变成一组非左递归的规则，例如 $S \to b S'$ 和 $S' \to a S' \mid \epsilon$ 。这巧妙地解决了自顶向下解析器的无限循环问题。

但这种转换是“免费的午餐”吗？如果我们把这个新的、“修复”过的文法交给一个自底向上解析器会发生什么？这种解析器从叶子向上构建树，通常对左递归没有问题。

为了找出答案，我们可以看看自底向上解析器的“大脑”：一个名为 LR 自动机的状态机。这个机器中的每个状态代表了解析器可能正在识别的一组模式。状态的总数是解析器复杂度的粗略度量。当我们进行这个实验——为原始的左递归文法和转换后的文法构建自动机时——一个显著的结果出现了。转换后的文法，即为自顶向下解析器“修复”过的那个，通常会生成一个具有更多状态的自动机。

消除左递归的行为引入了新的规则和空（ $\epsilon$ ）产生式，这迫使自底向上自动机需要跟踪更多的可能性，从而使其复杂度膨胀。这是一个关于权衡的深刻教训。“解决方案”在一个领域中，却在另一个领域中引起了新的复杂性。它教导我们，文法的优雅并非绝对属性，而是相对于我们用来解释它的工具而言。

在选择的迷宫中航行

即使对于能够适应左递归的自底向上解析器，它仍然可能带来有趣的挑战，推动我们走向更复杂的设计。考虑一个典型的算术文法： $E \to E + T \mid T$ 。想象一个自底向上解析器刚刚成功地将一串标记识别为一个有效的 $T$ 。根据文法，这个 $T$ 也可能是一个有效的 $E$ （通过 $E \to T$ ）。所以现在解析器处于一种模棱两可的状态。假设输入中的下一个符号是 * 号。解析器知道它不能在一个 $E$ 后面附加一个 *。但也许它刚刚找到的 $T$ 是一个更大的乘法的一部分，比如 $T * F$ 。

这就是“移入-归约冲突”的核心。解析器是应该“归约”它找到的 $T$ 成为一个 $E$ ，从而完成一条规则？还是应该“移入”即将到来的 * 号到它的栈上，希望能构建一个更大的表达式？一个简单的 $LR(0)$ 解析器，它只看当前状态，无法做出决定。它看到了两条有效的前进路径，因而陷入瘫痪。这不是文法的失败，而是解析器的局限性。文法通过其左递归，优美地揭示了需要更强智能的必要性。解决方案是赋予解析器“前瞻”输入流中下一个标记的能力——这种能力称为前瞻。正是这种源于左递归结构的冲突，是开发更强大的解析器如 SLR、LALR 和 LR(1) 的主要动机，这些解析器是现代编译器构造的主力军。

从左到右的意义流

到目前为止，我们一直专注于使用文法来识别输入的结构。但解析也是通往理解其意义的门户。这就是属性文法的领域，我们在这里为我们的文法规则附加计算。

想象一个简单的用于逗号分隔列表的左递归文法： $L \to L, \text{id} \mid \text{id}$ 。现在，假设我们不仅要验证列表，还想计算每个逗号的确切字符位置。要找到第三个项目后的逗号的位置，我们需要知道前三个项目的总长度加上前面两个逗号的长度。这个信息必须在我们处理列表时从左到右流动。

在这里，左递归结构是这种计算的完美伙伴。当解析器构建向下向左生长的树时，我们可以使用“继承属性”沿着树的左侧主干向下传递信息。在每个对应于规则 $L_1 \to L_2, \text{id}$ 的节点上，我们可以继承到目前为止整个列表的起始位置。一旦子列表 $L_2$ 被完全处理，它就可以计算自己的长度，并将该信息作为“综合属性”向上传递。有了起始位置和子列表的长度，计算逗号的位置就变得轻而易举。这种信息在解析树上向下流动然后向上传递的优雅舞蹈，正是由文法的左递归结构所促成的。文法形式和计算流程之间的这种协同作用是语法指导设计的基石。

通用机与通往人类语言的桥梁

我们已经看到，左递归可以是朋友也可以是敌人，这取决于解析策略。这就引出了一个问题：我们能否发明一种强大到不在乎这些的解析器？一个能接受我们能想到的任何上下文无关文法的解析器，无论是左递归、歧义性还是其他问题？

答案是响亮的“是”。像 Earley 解析器和 GLR（广义 LR）这样的算法正是如此。这些算法诞生于处理自然语言（NLP）这一困难而混乱的领域，人类语言以其臭名昭著的歧义性和对简单语法限制的抗拒而闻名，这些解析器是解析领域的通用机器。它们使用巧妙的动态规划技术（通常称为图表解析）来同时探索所有可能的解析路径，巧妙地避开了自顶向下解析器的无限循环和确定性自底向上解析器的冲突。

一个 Earley 解析器只是从容地处理左递归规则，将适当的项目添加到其图表中，然后继续前进，其记忆化方案保护它免受无限循环的影响。如果一个文法有歧义，它不会失败；它会勤奋地生成所有可能解析树的紧凑表示。

当然，这种巨大的能力和灵活性是有代价的：性能。对于定义大多数编程语言的那些行为良好、确定性的文法，LALR(1) 解析器生成器速度极快。而 Earley 解析器在最坏情况下的速度则较慢。在这里，我们发现了计算机科学的一个宏大、统一的原则：通用性与效率之间的权衡。

因此，左递归不仅仅是编译器构造中的一个技术细节。它是一个镜头，通过它我们可以审视这一根本性的权衡。它教导我们要明智地选择我们的工具：为可预测的、工程化的环境选择专门化的高速工具，为人类语言的狂野和不可预测的领域或新思想的快速原型设计选择稳健的通用工具。它是一座桥梁，连接着编程语言的形式世界和语言学的复杂世界，提醒我们，即使在机器的精确逻辑中，也存在着不同视角、策略和设计哲学的空间。