闭包与 GOTO

计算机如何理解语言的结构？答案不在于蛮力，而在于一种优雅的计算过程，该过程能够将抽象的语法规则映射到一台确定性机器上。这个过程的核心，也是现代语法分析理论的中心，是两个基本操作：​​closure​​ 和 ​​goto​​。这些概念为构建自动机——即分析器的“大脑”——提供了逻辑引擎，使其能够驾驭语法的复杂性，识别有效句子，并以数学般的精确度诊断结构性缺陷。本文旨在解决如何从一组可能存在歧义的规则中创建这样一个确定性分析器。

在接下来的章节中，我们将踏上一段理解这一强大机制的旅程。第一章“原理与机制”将解构 closure 和 goto 操作，展示它们如何协同作用于 LR(0) 项目，从而系统地构建一个完整的自动机。随后的“应用与跨学科联系”一章将揭示，这个自动机不仅是一个分析工具，更是一个供语言设计者使用的深刻诊断设备，也是一个用于理解远超计算机科学领域的结构的多功能模型。

要理解计算机如何领会一门语言——无论是编程语言还是简化的人类语言——我们必须构建一台机器。它不是由齿轮和杠杆构成，而是由逻辑和状态构成，能够遵循我们提供的语法规则。这台机器，即自动机，需要一个能够跟踪其在句子中所处位置以及预期接下来会看到什么的“大脑”。支撑这座“心智大厦”的双柱是两个优雅而强大的操作：​​closure​​ 和 ​​goto​​。让我们来探究这些简单的思想如何催生出一台能够真正理解结构的机器。

想象一下阅读一个句子。在任何时刻，你都清楚已经读了什么，以及接下来可能出现何种语法结构。计算机分析器需要一种形式化的方式来表示这种感知状态。这就是 ​​LR(0) 项目​​ 的作用。

一个 LR(0) 项目就是一个语法产生式，在右侧某处放置了一个点 •。对于像 $E \to E + T$ 这样的规则，我们可以有几个项目：

• [E → • E + T]：“我还没看到任何东西，但我希望能找到一个完整的表达式 E + T。”
• [E → E • + T]：“我刚刚成功识别了一个 E，现在我期望看到一个 + 符号，后面跟着一个 T。”
• [E → E + • T]：“我看到了一个 E 和一个 +，现在我正在寻找一个 T。”
• [E → E + T •]：“我找到了整个序列 E + T。我的假设完成了。”

这个点是我们语法之旅中的“你在此处”标记。这些项目的一个集合代表了分析器在某一时刻完整的“心智状态”——即它当前正在考虑的所有语法可能性的集合。

仅有像 [E → • E + T] 这样的假设是不够的。如果我们期望看到一个 E，就必须为 E 实际的样子做好准备。​​closure​​ 操作就是分析器程序化的预期行为。它通过添加所有由已有假设所引申出的新假设来丰富当前的心智状态。

规则很简单：如果一个状态包含一个点在非终结符之前的项目，例如 [A → α • B β]，那么我们必须将 B 的所有产生式对应的项目（点在最开始的位置）加入到该状态中。例如，如果 B 可以由 γ 或 δ 构成（即产生式为 $B \to \gamma$ 和 $B \to \delta$），我们就把 [B → • γ] 和 [B → • δ] 加入我们的假设集合。

这个过程是递归的，能够揭示出人意料的深层联系。考虑一个具有一连串产生式的文法，如 A → B、B → C 和 C → ε（其中 ε 是空字符串）。如果我们的分析器处于一个期望看到 A 的状态，closure 操作就会启动。期望 A 意味着我们可能实际上是在期望 B。期望 B 又意味着我们可能是在期望 C。而由于 C 可以是空的，我们可能无需消耗任何输入就能找到我们所寻找的东西！closure 操作会自动展开这整个可能性链条，将关于 A、B 和 C 的项目添加到一个单一、全面的状态中。这种对单一规则的简单、重复应用，使得机器无需任何特殊指令就能处理复杂、嵌套甚至不可见的语法结构。

如果说 closure 是思考的行为，那么 ​​goto​​ 就是执行的行为。goto 函数描述了当分析器成功识别输入中的一个符号时，其心智状态如何变化。goto(I, X) 回答了这样一个问题：“如果我处于状态 I 并且看到了符号 X，我的新心智状态是什么？”

其机制非常直观。

1. 首先，我们在当前状态 I 中找出所有正在等待符号 X 的假设。这些都是形如 [A → α • X β] 的项目。
2. 我们将这些项目收集起来，并将每个项目中的点越过 X，从而创建一组新的项目，如 [A → α X • β]。这个新集合被称为下一个状态的​​核心​​。它代表了我们取得的核心进展。
3. 最后，我们对这个核心取 closure。为什么？因为我们已经将点向前移动，到达了一个新位置 (• β)，所以我们必须再次预期 β 可能以何种方式开始。

这种 核心 + [闭包](/sciencepedia/feynman/keyword/closure) 的机制是 LR 分析的基石。从一个状态到下一个状态的转换仅由核心驱动——即那些被输入符号直接满足的项目。在原始状态中由闭包添加的项目仅用于内部记账；它们不会驱动一个它们并未明确寻找的符号的 goto 转换。这确保了过程的高效性和逻辑性。根据其定义，对于任何状态 I 和任何符号 X，goto(I, X) 函数恰好产生一个唯一确定的下一状态。机器永远不会对接下来去哪里感到困惑。

如果我们处于某个状态，而分析器读入了一个其任何活动假设都不期望的符号，会发生什么？例如，如果状态 I 中没有任何项目形如 [...→...• a...]，那么 goto(I, a) 是什么？在这种情况下，下一个状态的核心是空的。空集的闭包仍然是空集。这个空状态是我们机器通用的“错误”信号——一个无法恢复的死胡同。这是分析器在说：“我完全不知道发生了什么。”

有了 closure 和 goto，我们现在可以组装分析器的完整“大脑”了。我们从一个单一的初始状态开始，这个状态由增广开始规则 [S' → • S] 的闭包生成。然后，我们对每个可能的语法符号系统地应用 goto 函数来发现新状态。我们对发现的每个新状态重复此过程，在它们之间创建转换。

因为可能的项目数量（以及因此可能的项目集数量）是有限的，所以这个过程保证会终止。当它完成时，我们就得到了分析器心智的完整地图：一个​​确定性有限自动机 (DFA)​​。每个状态都是一个 LR(0) 项目集，每个转换都是一个 goto 路径。

这个最终生成的地图精美地反映了文法本身的结构。对于具有像 $S \to aS$ 这样的递归规则的文法，自动机构建过程自然会产生一个循环。例如，从某个状态出发，对 a 的 goto 操作可能会导向一个新状态，而这个新状态在另一次对 a 的 goto 操作后又会回到自身，完美地捕捉了规则的重复性。自动机成为了语言抽象规则的动态、可视化的表示。

构建这个自动机不仅仅是一项机械操作；它是一种深刻的发现行为。完成的机器就像一个神谕，揭示了我们文法最深层的属性。有时，它的启示会令人不安。

考虑一个典型算术表达式文法的自动机中的一个状态。我们可能会发现这个状态包含两个有趣的项目：

• [E → T •]
• [T → T • * F]

第一个项目的点在末尾。它是一个已完成的假设。机器在说：“我刚刚看到了一个 T，它可能构成一个完整的 E。也许我应该宣布这部分分析已经完成。” 这对应于一个​​规约​​ (reduce) 操作。

第二个项目的点在一个 * 前面。它是一个进行中的假设。机器在说：“我刚刚看到了一个 T，但如果下一个符号是 *，我应该消耗它并继续分析。” 这对应于一个​​移入​​ (shift) 操作。

冲突就在于此。在这个状态下，当看到一个 * 时，机器应该移入还是规约？它收到了两个相互矛盾的指令。这是一个​​移入-规约冲突​​，我们的 LR(0) 机器以其优雅的简洁性，找到了文法所允许的一个歧义点。这不是机器的失败，而是它最伟大的胜利。它诊断出了一个结构性的复杂问题，这个问题需要更强大的分析策略来解决，例如向前看一个符号（就像 LR(1) 分析器所做的那样）。

closure 和 goto 机制的美妙之处就在于这种统一性。两个简单、确定性的规则，在穷尽应用时，会生成一个语言结构的完整地图。这张地图不仅能引导分析器穿过一个有效的句子，还能清晰地照亮歧义和复杂性存在的精确位置，将抽象的语法规则变成一个具体、可导航的景观。

在了解了 closure 和 goto 错综复杂的机制后，人们可能会倾向于将它们视为一种专业的钟表装置，对钟表匠来说引人入胜，但与普通人关系不大。事实远非如此。这些操作不仅仅是用来构建分析器；它们是理解结构的通用工具。它们提供了一个强大的透镜，一种数学上的 X 射线，让我们能够获取任何一套规则——即一个文法——并生成一张完美的、确定性的地图，标示出所有可能的路径。这张状态自动机地图才是真正的魔力所在。它的形状、连接和死胡同揭示了规则本身的优雅、歧义和隐藏的本质。

想象一下你正在设计一种新的编程语言。你写下了一些看似完全合理的规则。但它们真的合理吗？是否存在某种微妙的歧义，某个你忽略的角落案例，会导致程序出现意想不到的行为？与其依赖猜测，不如将你的文法输入到 closure 和 goto 引擎中。它会运转并生成一个自动机。现在，你来检查这些状态。如果你发现某个状态在面对相同输入时给出了两种不同的指令——例如，是“移入”一个新符号还是“规约”一个已完成的短语——你就找到了一个冲突。你找到了语言设计中的一个缺陷。

著名的“悬空 else”问题正是这种情况。大多数编程语言都有 if-then-else 语句。当你写下 if C1 then if C2 then S1 else S2 时会发生什么？这个 else 是属于内部的 if 还是外部的 if？人类可能会感到困惑，但我们的自动机不会。在构建状态的过程中，closure 和 goto 操作将不可避免地导向一个状态，在该状态下，分析器刚刚看到 ... if C2 then S1，并且正在查看一个 else。从这个角度看，根据规则有两条路径是有效的：它可以“移入” else 来形成一个内部的 if-then-else 块，或者它可以“规约”已完成的 if-then 短语，将 else 留给外部的 if。这是一个典型的移入/规约冲突，是自动机发出的一个红色警报，它以数学的确定性告诉语言设计者：“你这里有歧义。你必须解决它。”

这种诊断能力远不止于简单的 if 语句。考虑一个有很多共享公共前缀的命令的系统，比如 print、print-all 和 print-status。对此类系统的文法进行分析，将会产生“歧义区”状态。例如，在看到前缀 print 后，自动机将处于一个既包含 print 命令的已完成项目，又包含 -all 和 -status 的移入项目的状态。实际上，自动机已经自动识别出由你的命令结构引起的每一个歧义点，精确地告诉你需要在哪里实施策略，例如“最长匹配优先”或“等待用户确认”。 甚至文法中递归的本质——规则引用自身的方式——也精美地反映在自动机的拓扑结构中。一个像 $Seq \to Move\; Seq$ 这样的右递归规则通常会在状态机中创建一个字面上的循环，分析器可以在消耗一系列移动时循环经过同一个状态。

语言的构建不是设计师发号施令、机器遵从的独白，而是一场对话。设计师提出规则，closure/goto 引擎构建地图，然后设计师根据地图的特征改进规则。自动机成为了创作过程中的伙伴。

假设你正在为文本编辑器设计宏。你想要一个表示粗体的宏 b，一个表示追加的宏 a，以及一个组合了“粗体-追加”的宏 ba。描述这些的幼稚文法将是极其模糊的。输入 b 后，用户是调用了粗体宏，还是正在调用粗体-追加宏的半途中？一个用我们的工具构建的 LR(0) 分析器会立即发现一个带有冲突的状态。

但美妙之处在于：解决方案不一定是构建一个更复杂的分析器。自动机的反馈启发了一个更简单、更优雅的解决方案：改变语言本身！通过规定每个宏都必须以一个明确的标记结束，比如一个感叹号 (!)，文法就变成了 b!、a! 和 ba!。现在，看到 b 之后，分析器知道它必须等待 ! 或 a。歧义消失了。当你将这个新的、改进后的文法输入到 closure 和 goto 引擎时，它会生成一个更大、更复杂但完全没有冲突的自动机。这场对话成功了。

“文法分解”这一原则是一个强大的工程工具。通过引入新的中间规则（有时称为“哨兵”非终结符），我们可以将文法中一个复杂的决策点分解为一系列更简单的决策点。这几乎总是会改变最终自动机的形状，通常使其更大，但通过为不同选择创建不同的路径来解决歧义。它凸显了一个深刻的思想：没有唯一的“最佳”文法，只有为特定分析技术所理解而工程化的文法。

从一套规则中识别有效符号序列的问题并不仅限于计算机科学。它无处不在。无论它出现在哪里，closure 和 goto 的原理都为理解它提供了一个框架。

考虑一个用户界面的设计。像 Photoshop 或 Blender 这样的复杂应用程序中的快捷键构成了一种语言。Ctrl+S 是一个完整的命令，还是 Ctrl+S+A 的前缀？UI 设计师可以将其快捷键系统建模为文法，并使用自动机构建来查找所有潜在的歧义。分析表中出现的冲突直接对应于潜在的用户困惑点。

或者想象一个在网格中导航的机器人。它的命令语言可能包括像“北”(n) 和“南”(s) 这样的基本移动。该语言可能还有一个特殊规则，即计划的第一个移动具有不同的含义——也许它是一个“初始化移动”。问题在于，初始化的 n 看起来与常规的 n 完全相同。机器人如何区分？该语言的文法将有像 $P \to I\;Seq$（带初始移动的计划）和 $P \to Seq$（常规计划）这样的规则，以及指定初始移动 $I$ 和常规移动 $M$ 都可以是 n 或 s 的规则。

当我们为这个文法构建自动机时，会发现一些充满不确定性的状态。初始状态在看到一个 n 后，会转换到一个包含两个已完成项目的新状态：$[I \to n \cdot]$ 和 $[M \to n \cdot]$。这是一个规约/规约冲突。这是自动机在说：“我刚看到了一个 n。它可能是一个‘初始移动’的结束，也可能是一个‘常规移动’的结束。根据你给我的规则，我无法区分它们。” 编译器理论家表格中的抽象冲突，对机器人来说是一个真实的语义模糊时刻。

我们一直在探索的原始 LR(0) 自动机是最纯粹的形式，但它仅仅是个开始。它揭示的冲突通常可以通过多一点巧思来解决。

有时，一个冲突并不像看起来那么严重。自动机可能处在一个十字路口，但几步之外就能看到路标。通过“偷看”下一个输入符号（一个符号的向前看），分析器通常可以打破僵局。这是 SLR(1) 分析背后的核心思想。它使用由 closure 和 goto 构建的相同自动机，但它会参考 FOLLOW 集来剔除不可能的规约操作，从而显著增加其能够处理的文法数量。

在追求效率的过程中，专家们设计了更强大的技术，如 LR(1) 分析，它将向前看符号直接融入状态中。这创建了一个非常精确和强大的分析器，但代价通常是生成大量的状态。一种常见的优化方法 LALR(1)，会合并具有相同核心结构的 LR(1) 状态。这可以极大地减小分析器的大小。但正如任何物理学家都知道的，天下没有免费的午餐。合并状态的行为可能会以不幸的方式组合它们的向前看符号，有时会在原本没有冲突的地方制造出新的冲突。 这揭示了模型的能力与其效率之间深刻而美妙的张力——一个在整个科学和工程领域回响的主题。

从诊断编程语言到设计用户界面和引导机器人，closure 和 goto 看似简单的舞蹈，为理解结构的本质提供了一个严谨而富有洞察力的工具。它证明了抽象数学在阐明和解决人类众多领域具体问题方面的强大力量。