用于生成紧凑型LR(1)解析器的APLR(1)算法比IELR(1)更简单且功能更强

# 用于生成紧凑 LR(1) 解析器的 APLR(1) 算法比 IELR(1) 更简单且能力更强 来源：https://branchtaken.com/reports/aplr1/aplr1 作为 [Hemlock](https://github.com/BranchTaken/Hemlock) 编程语言项目一部分的 [Hocc](https://github.com/BranchTaken/Hemlock/blob/main/doc/tools/hocc.md) 解析器生成器，实现了一种新颖的 LR(1) 族解析器生成算法，称为充分性保持 LR(1)（Adequacy Preservation LR(1)）。APLR(1) 生成紧凑的解析器，即使对于非确定性/歧义文法，也不存在 LR(1) 相对不充分性。因此，APLR(1) 解析器自动机适用于 [广义 LR (GLR)](https://en.wikipedia.org/wiki/GLR_parser) 解析技术，但对确定性解析的实际意义在于，在文法开发过程中绝不会出现神秘的冲突。此外，APLR(1) 可结合任何可能引入不必要状态分裂的 LR(1) 族解析器生成算法使用。以 Hocc 的 IELR+(1) 算法为例，它是原始 [Bison](https://en.wikipedia.org/wiki/GNU_Bison) IELR(1) 算法的广义扩展，也支持非确定性/歧义文法，但此算法有时会引发最终不必要的预防性状态分裂，而 APLR(1) 增强了 IELR+(1)，使得 APLR(1) 和 IELR+(1) 可以互换使用。 ## 引言 Knuth 在六十多年前发现了 [LR(k) 算法](https://branchtaken.com/reports/aplr1/aplr1#fn:knuth1965) 用于解析[确定性上下文无关文法](https://en.wikipedia.org/wiki/Deterministic_context-free_grammar)，并指出 LR(1) 是一种合理的限制，但在当时即使是 LR(1) 也因计算量过大而无法使用。[LALR(1) 算法](https://branchtaken.com/reports/aplr1/aplr1#fn:deremer1969) 的能力不如规范 LR(1)，但尽管后来发现了更好的替代方案，LALR(1) 仍然是 *事实上的* LR(1) 族首选算法。PGM LR(1) 算法 [][5](https://branchtaken.com/reports/aplr1/aplr1#fn:spector1981)[6](https://branchtaken.com/reports/aplr1/aplr1#fn:spector1988) 的相对默默无闻似乎是由于相关车道追踪研究中的混淆，加上被通过 [Yacc](https://en.wikipedia.org/wiki/Yacc) 解析器生成器快速传播的 LALR(1) 算法所掩盖。IELR(1) 的有限采用至少部分归因于其概念上的复杂性（恰好也是一种车道追踪方法）。相比之下，APLR(1) 是子图同构搜索的直接应用，只需要基本的图论知识和 LR(1) 自动机结构的有限知识即可理解。 什么构成了实用的 LR(1) 族解析器？算法复杂性包括执行和数据两个方面；为了实用，解析器必须既足够快又足够小。此外，解析器的*生成* 与解析不同，即使解析时性能出色，过高的生成时间开销也可能使算法不实用。在 LR(1) 被发现时，解析器生成和解析都不实用，最关键的原因是规范 LR(1) 自动机即使对于规模适中的文法也可能非常庞大。所有确定性 LR(1) 族解析器都使用相同的[下推自动机 (PDA)](https://en.wikipedia.org/wiki/Pushdown_automaton) 算法，因此关于高效 PDA 的研究通常都适用；解析器生成算法通过生成更小的自动机来区分自己，在某些情况下会限制可表达的文法范围。以下是对本报告中讨论的算法所固有权衡的现代视角。 | 算法 | 年份 | LR(1) 相对能力 | 自动机大小 | 生成开销 | |------|------|----------------|------------|----------| | LR(1) | 1965 | = | 最大 | 中等 | | LALR(1) | 1969 | ⊂ | 不充分 | 低 | | PGM LR(1) | 1977 | =¹ | 紧凑² | 低 | | IELR(1) | 2010 | = | 紧凑 | 低-中等 | | IELR+(1) | 2024 | ⊃³ | 紧凑 | 中等-高 | | APLR(1) | 2026 | ⊃³ | 紧凑 | 中等-高 | 1 — 不支持优先级/结合性。 2 — 假设弱兼容性测试；强兼容性保证最小性。 3 — 支持非确定性/歧义，技术上 LR(1) 自动机也成立。 规范 LR(1) 自动机是最大的，因为任何进一步的拆分都会导致冗余的相同状态；LALR(1) 自动机是不充分的，因为盲目执行了所有可能的状态合并；紧凑自动机通常是最小的，但贪婪算法不保证最小性。最大自动机在现代计算机上由于其生成的代码大小和低执行局部性而仍然笨重，尽管并非难以处理。应避免使用不充分的自动机。紧凑自动机在解析时间上没有任何妥协，生成时间的妥协也较小，随着硬件不断改进，正迅速趋于可忽略不计。 LALR(1) 算法 [2](https://branchtaken.com/reports/aplr1/aplr1#fn:deremer1969) 如此普遍，以至于许多从业者不加质疑地接受其缺点。尽管 LALR(1) 在解析期间使用符号向前看，但 LALR(1) 自动机是通过合并具有相同 LR(0) 项集（即忽略向前看）的状态生成的。可能产生三种类型的神秘冲突。众所周知的由 LALR(1) 状态合并引起的 *** 神秘新冲突 *** 始终是 *** 规约-规约冲突 ***，但状态合并也可能创建 *** 神秘侵入性冲突 ***，这是通过将 *** 移进-规约冲突 *** 合并到原本会执行规约动作的状态中引起的。此外，通过合并具有不同解决方法的多个规约-规约冲突，可能创建 *** 神秘变异冲突 ***。这种 **LR(1) 相对不充分性** 通常会导致 LALR(1) 解析器识别与相应 LR(1) 解析器不同的语言，并且推理这些差异充满风险。 文法规范中的 **优先级** 和 **结合性** 如此普遍，以至于很容易忘记这些实际上是消除非 LR(1) 文法歧义的机制。LR 文法家族本质上是确定性的，给定配置的多个解析动作表示文法歧义。优先级规范对动作进行排序，以便只要一个动作具有比所有其他替代方案更高的优先级，就可以解决歧义。结合性提供了次要机制，用于偏好左结合性（规约而非移进）、右结合性（移进而非规约）等。这些机制具有很大的实用价值，但它们是可选的；文法总是可以重新表述（尽管有些不方便且对隐含的解析树有负面影响）以移除优先级/结合性，而不影响解析器识别的语言。 PGM LR(1) 算法 [][7](https://branchtaken.com/reports/aplr1/aplr1#fn:pottier) 在自动机生成期间增量地合并状态，前提是它能确保随后不会出现神秘冲突。然而，该算法仅对 LR(1) 文法可靠工作；尽管不会出现来自优先级/结合性消歧的神秘新冲突，但仍可能出现神秘的侵入性/变异冲突。IELR(1) 算法 [8](https://branchtaken.com/reports/aplr1/aplr1#fn:denny2010a) 分析一个未解决的 LALR(1) 自动机（所有可能的冲突都存在），并从冲突向后追踪车道足够远，以确定哪些状态可能需要分裂以避免神秘冲突。然后它生成一个 IELR(1) 自动机，该自动机消除了所有 LR(1) 相对不充分性。车道追踪非常快，因为该算法假设相应的 LR(1) 自动机中没有歧义，这意味着在 LR(1) 自动机中每条车道最多贡献一个动作。 广义 LR (GLR) [9](https://branchtaken.com/reports/aplr1/aplr1#fn:tomita1986) 支持非确定性。非 LR(1) 文法包含“歧义的”非单元素动作集，而 GLR 将歧义视为非确定性，并并行应用非单元素动作集，如果任何并行自动机执行达到接受状态，则接受输入。尽管 GLR 在文法开发期间提供了（太多？）额外的自由度，但在将 GLR 与自动机配对时仍然需要谨慎。例如，使用具有冲突解决能力的 LALR(1) 自动机是不安全的，因为神秘冲突可能被解决，使得 GLR 永远不会考虑对完整文法识别至关重要的动作。不幸的是，这种操作模式混淆了对偶然性与基本性文法非确定性的分析。IELR(1) 与 GLR 结合使用时同样不安全，因为它将冲突解决应用于由于无法处理未完全解决的非 LR(1) 文法而产生的神秘冲突。 IELR+(1) 算法 [10](https://branchtaken.com/reports/aplr1/aplr1#fn:evans2024) 与 IELR(1) 的不同之处在于，它不对相应 LR(1) 自动机中的歧义做任何假设。多个（冲突的）动作可能通过 LR(1) 自动机中的每条车道流动。车道追踪更加复杂，因为必须达到闭包（全局不动点），而不是在任何贡献动作集为空或单元素时终止追踪。此外，归因于闭包的循环依赖有时会在 IELR+(1) 自动机生成期间强制进行预防性状态分裂，而这些分裂最终被证明是不必要的，但这些分裂状态可以使用与 APLR(1) 相同的算法重新合并。 作为 IELR(1) 和 IELR+(1) 差异的一个例子，考虑 [Gawk](https://www.gnu.org/software/gawk/) 3.10 文法，它曾是一个 IELR(1) 案例研究 [8](https://branchtaken.com/reports/aplr1/aplr1#fn:denny2010a)。 | 算法 | 解决冲突 | 状态数 | S/R 冲突 | R/R 冲突 | |------|----------|--------|-----------|-----------| | LALR(1) | 是 | 320 | 65 | 0 | | IELR(1) | 329 | 65 | 0 | | IELR+(1) | 367 | 66 | 0 | | LALR(1) | 否 | 320 | 41 | 0 | | IELR(1) | 320 | 41 | 0 | | IELR+(1) | 367 | 41 | 0 | IELR(1) 在相应 LR(1) 自动机中存在未解决的冲突时生成与 LALR(1) 相同的状态，而 IELR+(1) 则分裂额外状态以消除（未完全消歧的）LR(1) 相对不充分性。额外的移进/规约冲突（66 vs 65）表明 IELR+(1) 避免了 IELR(1) 无意中解决的神秘冲突。这种算法上的区别值得注意，因为 IELR+(1) 和 APLR(1) 是彼此的二元对，使得它们都比 IELR(1) 能力更强。 APLR(1) 算法分析 LR(1) 自动机，详尽搜索可以重新合并而不改变识别语言的分裂状态子图，然后执行所有重新合并。APLR(1) 将重新合并算法应用于规范 LR(1) 自动机，但 Hocc 也默认对 IELR+(1) 和 PGM LR(1) 生成的自动机应用重新合并算法。Hocc 的早期版本实现了一个更简单的迭代状态对重新合并算法 [10](https://branchtaken.com/reports/aplr1/aplr1#fn:evans2024)，由 Lenka 和 Kumar [11](https://branchtaken.com/reports/aplr1/aplr1#fn:lenka2006) 独立发现。迭代算法的缺点是无法重新合并非单元素循环子图。 有一个微妙的结果影响上述所有算法：即一系列规约动作可能导致进入一个对当前向前看符号没有动作的状态，即语法错误。这可能会混淆错误报告，因为关注的解析配置是第一次此类规约动作之前存在的配置。幸运的是，有一个直接的解决方案，通常称为向前看纠正 (LAC) [12](https://branchtaken.com/reports/aplr1/aplr1#fn:denny2010b)。这种缓解措施在规约前捕获解析器状态，并在遇到错误时恢复状态。Hocc 仅支持纯语义动作（即不允许副作用），因此 LAC 简单、廉价且通用。 本报告的其余部分详细描述了 Hocc 实现的 LR(1) 和 APLR(1) 算法，足以实现独立重实现，随后是解析器生成算法的实验比较。 ## 规范 LR(1) ### 术语 以下在 Hocc 格式中的常见示例“算术”文法足以定义 Hocc 源代码中使用的各种相关术语。 `` hocc left mul left add < mul token STAR "*" prec mul token SLASH "/" prec mul token PLUS "+" prec add token MINUS "-" prec add token INT token EOI nonterm MulOp ::= | "*" | "/" nonterm AddOp ::= | "+" | "-" nonterm Expr ::= | Expr MulOp Expr prec mul | Expr AddOp Expr prec add | INT start Answer ::= Expr EOI `` 一个文法由产生式规则组成，缩写为 *** prod(s) ***。`Answer ::= Expr EOI` 和 `Expr ::= INT` 是 prod 的例子。一个 prod 有一个左侧 (LHS)，它总是一个非终结符号，缩写为 *** nonterm ***。`Answer` 和 `Expr` 是 nonterm 的例子。一个 prod 也有一个右侧 (RHS)，它是一系列 nonterm 和 *** 记号 ***。`STAR`、它的别名 `"*"` 和 `EOI` 是记号的例子。每个记号和 nonterm 都有一个关联的 *** first 集 ***（可能首先出现的记号集合）和一个 *** follow 集 ***（可能紧随其后的记号集合）。每个记号的 first 集平凡地包含该记号本身，并且记号的 first 集作为计算所有符号的 first/follow 集闭包的初始状态。有关详细的 first/follow 集闭包算法，请参见 Hocc 源代码或编译器教科书 [13](https://branchtaken.com/reports/aplr1/aplr1#fn:aho2007)[14](https://branchtaken.com/reports/aplr1/aplr1#fn:cooper2023)。 一个 *** LR(0) 项 *** 是一个带有位置的 prod，其中当前位置用点表示。例如，`Answer ::= · Expr EOI`、`Answer ::= Expr · EOI` 和 `Answer ::= Expr EOI ·` 是基于同一 prod 的不同 LR(0) 项。一个 *** LR(1) 项 *** 是一个带有关联 *** follow 集 *** 的 LR(0) 项，即可能立即跟随该 prod 的记号集合。例如，`MulOp ::= · "\*", {INT}` 表示一个乘法运算符后只能跟一个整数。一个不太明显的例子，`Expr ::= · INT, {"\*", "/", "\+", "\-", EOI}` 表示一个整数后可以跟一个数学运算符或输入结束 (EOI)。注意，点的位置与 follow 集无关；无论当前点的位置如何，相同的符号可能跟随该 prod。相反，点的位置 *与* *** first 集 *** 相关，即可能立即跟随点的记号集合。 一个 *** LR(0) 项集 ***，也称为一个 *** 核心 ***，就是一组 LR(0) 项的集合。如果两个核心同构，即它们由相同的 LR(0) 项集构成，则它们是 *** 等核心 ***。一个 *** LR(1) 项集 ***，也称为一个 *** 内核 ***，就是一组 LR(1) 项的集合，也称为 *** 内核项 ***。如果两个内核同构，即它们由相同的 LR(1) 项集构成，则它们是 *** 等内核 ***。通过从所有 LR(1) 项中提取 LR(0) 项，可以将内核映射到核心。LR(1) 族解析器生成算法的不同之处仅在于它们如何积极地对具有相同核心但不同内核的状态进行分裂/合并；规范 LR(1) 和 LALR(1) 处于这个连续体的两端。 一个 *** LR(1) 项集闭包 *** 由一个内核和一个 LR(1) 项的 *** 附加集 *** 组成，该附加集对应从内核出发而不推进输入即可到达的产生式集合。一个 *** 状态 *** 包含一个 LR(1) 项集闭包、每个预期记号的