💻 computer science

An Empirical Comparison of General Context-Free Parsers

本文展示了首个对使用 Rust 实现的六种通用上下文无关解析算法进行的统一基准测试，证明了 GLR 系列通过仅产生较 LR(1) 确定性解析器 3 倍的中位数性能开销，即可在支持完整语言表达能力的同时，成为软件工程工具中一个实用的默认选择。

原作者： Huan Vo, Danushka Liyanage, Hong Jin Kang, Sasha Rubin, Rahul Gopinath

发布于 2026-06-09

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Huan Vo, Danushka Liyanage, Hong Jin Kang, Sasha Rubin, Rahul Gopinath

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你是一名试图将一种外语（源代码）转换成计算机能够理解的形式的翻译员。这个过程被称为解析（parsing）。

几十年来，软件工程师使用的翻译员就像是刻板、受规则束缚的机器人。它们速度极快，但也非常挑剔。如果你给出的语言哪怕只有一点点歧义或复杂的句子结构，机器人就会拒绝工作。为了让机器人开心，工程师们不得不花费数小时去“黑入（hacking）”这种语言——重写句子、移除自然结构，并扭曲语法，仅仅是为了去适应机器人狭隘的规则。这就像是因为你手里只有一个正方形的木桩，就非要把圆形的木桩硬塞进方孔里一样。

正因如此，许多工程师放弃了使用这些正式的机器人，转而开始亲手构建自己的翻译员。这些手工构建的翻译员通常漏洞百出、难以维护且不安全。

核心问题
多年来，一直存在一种观点，认为“通用型（General）”解析器——即能够处理任何语言结构而无需进行“黑入”处理的翻译器——由于太慢而无法投入使用。人们认为它们就像是相对于快速、严格的机器人而言，笨拙缓慢的巨人。

这篇论文的作者决定解决这场争论。他们建立了一个“赛道”，用以测试六种不同类型的这些“通用型”解析器与旧有的“严格型”机器人的对决。他们确保每一位赛车手都穿着同样的鞋子、跑在同样的赛道上，并使用同一个秒表（他们用相同的语言 Rust 编写了所有代码，并使用了相同的工具）。

参赛者
他们测试了六种不同的策略：

矩阵移动者（CYK & Valiant）： 它们试图通过填满一个巨大的网格来解开谜题。
自顶向下探索者（Earley & GLL）： 它们试图从上往下猜测结构，同时探索多条路径。
自底向上构建者（RNGLR & BRNGLR）： 它们从底层向上构建结构，通过将注意力同时分散到多条路径上来处理冲突。
严格机器人（LL(1) & LR(1)）： 这些是老派的、快速但挑剔的解析器。

结果：惊喜的赢家

“笨拙的巨人”（CYK & Valiant）： 它们表现得非常糟糕。它们太慢了，以至于在实际任务中几乎毫无用处。它们就像是试图开着坦克穿梭在城市街道中；它们根本行不通。
“自顶向下探索者”（Earley & GLL）：
- Earley 是其中最慢的一个。
- GLL 在某些语言上很快，但在处理其他语言时会变得非常缓慢且极其耗费内存。它就像是一个在直道上表现出色，但在弯道上却会被自己的脚绊倒的跑步者。
“自底向上构建者”（RNGLR & BRNGLR）： 它们是冠军。
- 它们是所有“通用型”解析器中最快的。
- 它们的内存效率极高，使用的内存量几乎与严格型机器人一样少。
- 重大揭秘： 当语言本身足够简单，足以适配严格型机器人时，这些新的“通用型”解析器仅比它们慢了 3 倍。作者认为，为了获得能够处理任何语言而无需进行“黑入”的能力，付出 3 倍速的代价是一个微不足道的代价。

“语法黑入”陷阱
论文还研究了当你试图通过“黑入”语言来使其适配严格型机器人时会发生什么。

速度： 是的，通过黑入语言来适配严格型机器人确实能让速度提升 4 到 7 倍。
代价： 但是，黑入语言往往会让它变成新一代“通用型”解析器最糟糕的场景。这就像是为了让你最喜欢的选手获胜而改变比赛规则，却不小心让整场比赛变得无法进行。
结论： 作者表示，你不应该为了榨取一点额外的速度而对你的语言进行“黑入”。“通用型”解析器对于几乎所有情况都足够快，而且“黑入”语言会让代码更难阅读和维护。

简单的总结
长期以来，软件工程师认为他们必须在速度（使用严格的、经过“黑入”处理的解析器）和灵活性（使用缓慢的、通用的解析器）之间做出选择。

这篇论文证明，这种选择其实是一个伪命题。新型的“通用型”解析器（特别是 GLR 系列）已经足够快，可以作为默认选择。它们就像是一个万能适配器：它们几乎能适配任何插头，虽然它们可能比特定适配器稍微重一点，但它们让你免去了为每一种设备都购买一个不同适配器的麻烦。

简而言之： 停止为了适配那些古老、挑剔的解析器而去“黑入”你的语言。使用这些新的、灵活的“通用型”解析器吧。它们速度够快，占用内存少，并且能让你按照语言自然的形态去编写它们。

技术摘要：通用上下文无关解析器的实证比较

问题陈述

解析是包括编译器、静态分析工具、语言服务器和模糊测试器在内的软件工程工具的基础组件。然而，绝大多数已部署的解析器都局限于确定性上下文无关语言的子类（LL 或 LR）。这种限制迫使开发者进行“语法黑客行为”（grammar hacking）——通过手动重写语法来消除左递归、解决移进-归约冲突，或为了满足解析器约束而扭曲语言结构。这一过程往往以牺牲语言表达能力为代价，增加了维护负担，并导致开发者放弃形式化解析，转而使用容易产生细微错误和安全漏洞的手写解析器。

虽然通用上下文无关解析器（如 CYK、Earley、GLR、GLL）可以接受任何上下文无关语法而无需修改，但由于其 $O(n^3)$ 的最坏情况复杂度，在历史上一直被认为是不切实际的。尽管经过了数十年的算法发展，但对于主要的解析算法族之间仍缺乏严格的、面对面的比较。现有的评估通常过于狭窄，使用不同的实现语言、数据结构或输出表示，使得直接比较变得不可能。因此，关于广义解析成本过高的误解仍然未得到挑战。

方法论

为了填补这一空白，作者实现了一个统一且受控的基准测试，涵盖了六种广义解析算法以及 LL(1) 和 LR(1) 基准。

评估的算法：
- 确定性基准： LL(1) 和 LR(1)。
- 广义（在线，自顶向下）： Earley 和 Generalized LL (GLL)。
- 广义（在线，自底向上）： Right-Nulled GLR (RNGLR) 和 Binary RNGLR (BRNGLR)。
- 广义（离线，自底向上）： CYK 和 Valiant（使用四俄罗斯人方法）。
实现： 所有解析器均在 Rust 中于同一个框架内实现，以消除实现差异带来的影响。它们共享相同的语法表示、词法流格式、抽象语法树（AST）结构和内存管理策略。所有实现均使用相同的优化设置（--release）进行编译。
基准测试： 本研究评估了 22 个语法，范围从简单的表达式和 JSON 到全规模编程语言（C++、Java、ANSI C、Pascal、SQL 等）。
- 对于确定性基准，语法经过了重构（消除左递归、左因子化、规则拆分）以满足 LL(1) 或 LR(1) 的约束。
- 广义解析器则直接消费原始的、未经修改的语法。
输入： 测试输入是通过有界深度基于语法的模糊测试生成的。输入大小被限制以确保最快的解析器能在一秒内完成。
指标： 性能通过多次迭代下的中值运行时间（毫秒）和峰值内存使用量（MB）进行测量，以减轻系统噪声的影响。

核心贡献

首个统一基准： 本文提出了第一个受控的比较，涵盖了四种算法族（基于矩阵的、自顶向下的在线算法、自底向上的在线算法）中的六种广义解析算法，并在真实的软件工程语法上进行了测试。
重构语法分析： 详细比较了在识别相同语言的重构语法上的解析器性能，从而隔离了不同算法族受语法结构影响的情况。
实践指导： 提供实证证据，指导软件工程工具构建者何时应将广义解析作为默认选择，以及何时“语法黑客行为”会适得其反。

结果

1. 离线广义解析器 (CYK 和 Valiant)

尽管 Valiant 具有优于 CYK ( $O(n^3)$ ) 的渐近复杂度 ( $O(n^3 / \log n)$ )，但在实践中 Valiant 明显更慢（例如，在特定输入上慢了 330 倍）。两种离线算法都被证明即使在处理少于 100 个标记（tokens）的输入时也是不切实际的。Earley 的表现显著优于这两种离线算法，这表明离线矩阵乘法方法对于典型的软件工程任务而言并不可行。

2. 在线广义解析器 (Earley, GLL, RNGLR, BRNGLR)

RNGLR 和 BRNGLR： 这些是速度最快的广义解析器，通常比 GLL 快 2–3 倍，比 Earley 快 4–10 倍。它们彼此之间几乎没有区别（运行时差异在 15% 以内）。
GLL： 性能对语法结构高度敏感。GLL 在 LL 友好型（右递归）输入上具有竞争力，但在左递归语法上性能严重下降（例如，在左递归 JSON 上比 RNGLR 慢 20 倍）。
Earley： 在所有语法中，Earley 始终是速度最慢的广义解析器。

3. 确定性解析器 vs. 广义解析器

运行时开销： 在确定性语法上，GLR 系列 (RNGLR/BRNGLR) 的中值减速仅为 3 倍（相对于 LR(1)），且方差较小且可预测（四分位距为 ±0.2×）。
GLL 方差： GLL 显示出更高的方差，其中值开销为 6 倍，在左递归语法上的最坏情况减速达 139 倍。
内存： 确定性解析器和 GLR 变体在所有输入规模下都保持着微不足道的内存使用量（处于约 0.016 MB 的测量底线）。相比之下，GLL 表现出显著的内存增长（在 Pascal 上高达 12.5 MB），而 Earley 虽然也较高，但相对适中。

4. 语法重构 (语法黑客行为)

确定性增益： 将语法重构为 LL(1) 或 LR(1) 相比于针对该特定语法形式的最佳广义解析器，能获得一致的 4–7 倍加速。
结构敏感性： 语法结构显著影响广义解析器。RNGLR 受益于左递归，但在右递归下性能下降；GLL 的行为则相反。将语法重构为满足 LL(1)（引入右递归）可能会在无意中惩罚 GLR 解析器，同时帮助 GLL。
歧义性： 如果底层递归结构保持不变，在递归规则中添加歧义对广义解析器的运行时影响微乎其微。

意义与主张

本文认为，广义化的代价比广泛假设的要低。具体而言：

GLR 是实际的默认选择： 在广义解析器中，GLR 系列 (RNGLR/BRNGLR) 提供了速度和内存效率的最佳结合。其相对于 LR(1) 仅 3 倍的中值开销被认为是对于广泛的软件工程工具（编译器、语言服务器、静态分析工具）是可以接受的。
语法黑客行为的权衡： 虽然通过使语法确定化来实现 LL(1) 或 LR(1) 可以解锁显著的性能提升 (4–7×)，但这会引入维护成本和脆弱性。作者建议，对于大多数工具而言，GLR 带来的适度开销优于复杂重构语法的成本。
算法选择：
- RNGLR/BRNGLR： 推荐作为优先考虑语法灵活性的工具的默认选择。
- LL(1)/LR(1)： 仅推荐用于需要最高吞吐量且语法能严格保持确定性的工具。
- GLL： 如果需要自顶向下的架构风格，可以将其作为合理的替代方案，前提是需仔细选择语法形式以避免左递归陷阱。
- Earley/CYK/Valiant： 由于性能较差或不切实际，不推荐在本文所述语境下用于生产环境。

研究结论指出，广义解析（尤其是 GLR）是一个安全且高效的默认选择，它消除了对受限语法工程的需求，从而支持更健壮、更易于维护的软件工程工具链。