Gecko：一款支持自动语法错误恢复的快速 GLR 解析器

# Gecko：支持自动语法错误恢复的快速 GLR 解析器 来源：https://vnmakarov.github.io/parsing/compilers/c/open-source/2026/04/22/gecko-glr.html ## Gecko：C 语言实现的快速独立 GLR 解析库 解析器是每一种编程语言实现的骨架，解析技术的选择对语言设计者影响深远。 LALR(1)（https://en.wikipedia.org/wiki/LALR_parser）解析器如 YACC（https://invisible-island.net/byacc） 和 Bison（https://www.gnu.org/software/bison/） 统治了数十年，却强迫语法作者为避免冲突而扭曲文法。 广义解析器——能够处理全部 上下文无关文法（https://en.wikipedia.org/wiki/Context-free_grammar），包括 歧义文法（https://en.wikipedia.org/wiki/Ambiguous_grammar）——历来被认为太慢，不适合生产环境。 Gecko 是一个新的 GLR（https://en.wikipedia.org/wiki/GLR_parser） 解析库，挑战了这一假设：它支持**任何**上下文无关文法，提供**零修改的自动语法错误恢复**，速度却与 YACC 在无歧义文法上处于同一水平。 本文将介绍 Gecko 的设计目标、核心特性、如何在项目中使用，以及验证其性能的基准测试。 ## 为何再造解析器？ 解析器生成器的世界早已拥挤：YACC 与 Bison 自 1970 年代就已存在；近年又出现了 PEG（https://en.wikipedia.org/wiki/Parsing_expression_grammar）解析器、 解析器组合子（https://en.wikipedia.org/wiki/Parser_combinator），以及各种 Earley（https://en.wikipedia.org/wiki/Earley_parser） 系工具。为什么还要写一个？ 职业生涯中我写过若干编译器生成器。第一个是 1985 年用 Pascal 写的 LALR(1) 解析器（可查阅 1985 年俄文期刊《Программирование》）。九十年代又写了 MSTA（https://github.com/cocom-org/msta）， 一个带多项优化的 LALR(k)/LR(k) 解析器，速度超越 YACC/Bison。 使用它时我发现，解析器速度并非最重要，现代 CPU 已足够快；LR(k) 也无法覆盖真实语言的全部语法。 于是约十年前我写了 YAEP（https://github.com/vnmakarov/yaep）： 一个支持任意上下文无关文法的 Earley 解析器，并把它优化到我所知最快。 然而我对它在无歧义或轻度歧义文法上的速度与内存占用仍不满意——Earley 算法的内在特性导致难以再突破。 因此最近我转向 GLR 解析，Gecko 便是这一路线的新实现。 **我尚未见任何工具能同时提供 Gecko 的以下组合**： 1. **完整 CFG 支持**——对文法结构零限制，包括歧义文法 2. **库形态**——可嵌入任何 C 程序，无需外部代码生成 3. **运算符优先级/结合性**（https://en.wikipedia.org/wiki/Order_of_operations）（https://en.wikipedia.org/wiki/Operator_associativity）——沿用 YACC 用户熟悉数十年的机制 4. **自动错误恢复**——无需 `error` 令牌，无需改动文法，只需最小跳字即可得到正确语法树 5. **可竞争的速度**——无歧义文法下与 YACC 差距 5–10%，歧义文法下远快于其它 GLR 实现 下面逐项详解。 ## 特性概览 ### 小巧简洁 Gecko 核心约 2800 行 C 代码（SLOC），另含 6 个头文件级工具库（自定义分配器、位图、哈希、哈希表、变长对象、对象栈）共约 900 行。 **总计约 3,700 行 C**（SLOC），x86-64 下编译后仅 **90 KB**。 除 C 标准库外零依赖，**直接丢源文件即可编译嵌入**。 ### 完整上下文无关文法支持 YACC/Bison 限 LALR(1)；Bison 虽声称支持 GLR，我却无法用歧义文法使其正常工作： 对 Gecko 与 ElkHound（https://github.com/WeiDUorg/elkhound） 共用的歧义 C 文法，Bison 在第三行就报语法错误； 对最简单的歧义文法 `E : E '+' E | 'a'`，它在第 23 个令牌处报错。 Gecko 则能解析**任意上下文无关文法**，包括歧义文法。 这对 C 语言尤其有用：著名的“typedef 问题”（`T * x;` 是指针声明还是乘法？）若在词法阶段不区分类型名与标识符，就会产生真实歧义。 用 Gecko，可统一只发一种标识符令牌，让解析器并行探索两种解释，歧义在生成的语法树中结构体现，无需词法-语法反馈 hack。 ### 简洁的语法制导翻译 Gecko 不像 YACC 那样用语义动作，而是采用**抽象语法树（AST）**（https://en.wikipedia.org/wiki/Abstract_syntax_tree） 输出，规则右侧用紧凑记法指明哪些子节点参与构成 AST： ``` E : T # 0 | E '+' T # plus (0 2) ; T : F # 0 | T '*' F # mult (0 2) ; F : 'a' # 0 | '(' E ')' # 1 ; ``` 每条候选后的 `#` 指明翻译方式： - `# 0` 表示“本规则翻译等于右侧第 0 号符号的翻译”（透传） - `# plus (0 2)` 表示“创建名为 `plus` 的抽象节点，子节点取右侧第 0、2 号符号的翻译” - `# 1` 表示“翻译等于右侧第 1 号符号的翻译”（跳过左括号） 这种写法比 YACC 动作简单：无需在文法里写 C 代码即可得到干净 AST。 生成的树由 `GP_TERM`（终结符）、`GP_ANODE`（带命名子节点的抽象节点）、`GP_NIL`（空翻译）、`GP_ALT`（歧义候选）、`GP_OPT`（上下文相关候选）构成。 对上述文法与输入 `a+a*(a*a+a)`，Gecko 会生成如下树： AST for a+a*(a*a+a) 其中 `ANODE`、`TERM` 为节点类型（`GP_ANODE`、`GP_TERM`），`plus`、`mult` 为抽象节点的 `name` 字段，`a` 为输入令牌属性。 ### 运算符文法 真实文法常含几十级优先级的表达式语法。按优先级逐级写非终结符既繁琐又易错。 Gecko 支持**运算符优先级与结合性声明**，语法与 YACC/Bison 相同： ``` LEFT '+'; LEFT '*'; E : 'a' # 0 | '(' E ')' # 1 | E '+' E # plus (0 2) | E '*' E # mult (0 2) ; ``` `LEFT '+'` 与 `LEFT '*'` 声明左结合运算符，且 `*` 优先级高于 `+`（后声明者更高）。 于是可放心写看似歧义的 `E '+' E`，Gecko 会像 YACC 一样解决冲突；若文法其他部分真有歧义，GLR 机制仍保留完整能力。 支持 `LEFT`、`RIGHT`、`NONASSOC`，同行列出的记号共享优先级。 与 YACC 一样，使用运算符声明并配合左递归规则，可获得更快解析速度与更低内存占用。 ### 库架构 Gecko 是**库**，而非独立工具。这是根本设计差异。 YACC/Bison 生成 C 源文件再编译链接；Gecko 则直接链接进程序。 文法可通过函数调用（`gp_read_grammar`）或类 YACC 描述字符串（`gp_parse_grammar`）提供。 这意味着： - **构建过程无需代码生成步骤** - **同一程序可并存多个文法** - **文法可在运行时更换**——从配置读取、动态构造、或在多遍解析中切换 - **读入文法后启动极快** 核心 API 故意极简： ```c struct grammar *g = gp_create_grammar(); gp_parse_grammar(g, true, description); gp_parse(g, read_token, &root, &ambiguity, NULL); gp_fin(g); ``` 四步即可从文法到语法树。 ### 自动语法错误恢复 用过 YACC/Bison 的人都知道，实现高质量语法错误恢复极其困难。 据我经验，这项任务花费的时间——以及后续在语义检查中处理语法错误的时间——远超最初写文法。 因此 Gecko 项目把“简化错误恢复”作为重点。 Gecko 的语法错误恢复**完全自动**，无需任何 `error` 令牌，**零文法改动**。 这得益于 GLR 架构天然同时维护多栈状态。 #### 工作机制 当检测到语法错误（当前没有任何栈能移进或归约该令牌）时，恢复算法启动： 1. **拒绝并弹出**。对每个失败栈，Gecko 丢弃当前令牌，并持续弹出栈顶直到新栈能对原令牌执行动作。 2. **寻找最小代价成功**。当某候选栈以最小代价连续成功消费可配置数量的令牌（默认 5，可通过 `gp_set_recovery_match` 修改）未再遇错误，或到达 EOF，即认为恢复成功。 3. **恢复正常解析**。所有至少匹配到一个令牌的栈成为新的继续解析起点。 #### 核心保证 Gecko 保证**解析器始终生成对应“语法正确输入”的语法树**。 实现思路很直观：在出错点前后忽略最少数量的令牌，使剩余令牌流对文法而言合法。 解析器通过用户可配的错误回调报告哪些令牌被涉及。 以简单表达式文法（见前）和输入 `a+a*(a*+a)` 为例——注意 `*` 后多出一个 `+`。 Gecko 在 `+` 处检测到错误，发现跳过第二个 `*` 即可得到合法续解析，于是生成如同输入为 `a+a*(a+a)` 的语法树。 错误回调报告问题令牌，解析继续。 该方案在实践中表现良好： - **文法无关**——任何文法白送错误恢复 - **局部最小代价**——非任意修复 - **多错误支持**——各错误独立恢复 - **输出树始终结构合法** 注意“最小代价”仅指局部搜索空间内的最小；据我所知尚无解析器做全局最小代价错误恢复。 例如 YAEP 仅在有限意义上全局搜索：它最小化被特殊文法终结符 `error` 覆盖的令牌数。 ## 文法描述语言 Gecko 通过 `gp_parse_grammar` 接受类 YACC 的文本格式，支持： ### 终结符声明 命名终结符可显式指定编码： ``` TERM IDENTIFIER = 300 CONSTANT = 338 STRING_LITERAL = 340; ``` 同一 `TERM` 语句可声明多个终结符，均可选 `= code`。 单字符字面量（`'a'`、`'+'` 等）自动以 ASCII 值为编码，无需在 TERM 中声明。 ### 运算符优先级 ``` LEFT '+' '-'; LEFT '*' '/' '%'; RIGHT ELSE; NONASSOC '<' '>'; ``` 同行记号共享优先级，后行优先级更高，语义与 YACC/Bison 完全一致。 ### 规则 ``` lhs : rhs_symbol_1 rhs_symbol_2 ... # translation | alternative_rhs ... # translation ; ``` 终结符可以是单字符字面量（`'a'`、`'+'`）或命名令牌（`IDENTIFIER`）。 非终结符为未声明成终结符的任意名字。 Gecko 要求文法公理（开始符号）只有一条规则。 因此使用 `gp_read_grammar` 时通常需显式加开始规则如 `$S : E`； 使用 `gp_parse_grammar` 时 Geckco 会自动添加。 ### 翻译说明 `#` 之后： - 单个数字 `N` 表示翻译取右侧第 N 号符号的翻译（0 基） - `name (i j k)` 创建指定名字的抽象节点，子节点取右侧 i、j、k 位置符号的翻译 - 省略 `#` 表示空翻译 可选**守卫**可跟在翻译后：`? N` 给该规则候选分配守卫号 N（见“配置中的规则守卫”）。 文法描述中支持 C 风格 `/* ... */` 注释。 ## 程序化构造文法 为最大灵活性，Gecko 亦支持通过 `gp_read_grammar` 函数以编程方式逐条构建文法。 需提供两个回调： **`read_terminal`**——反复返回终结符定义： ```c const char *read_terminal(int *code, int *priority, enum gp_assoc *assoc) { // 返回终结符名字，并设置编码、优先级、结合性。 // 返回 NULL 表示结束。 } ``` **`read_rule`**——反复返回语法规则： ```c const char *read_rule(const char ***rhs, const char **abs_node, int **transl, int *guard_num) { // 返回左侧名字，并设置右侧数组、抽象节点名、翻译数组、守卫号。 // 返回 NULL 表示结束。 } ``` 假设有简单表达式文法： ``` LEFT '+'; E : 'a' # 1 | E '+' E # plus (0 2) | '(' E ')' # 1 ; ``` 以下给出完整的程序化构造示例： （注：原文代码被截断，此处保留原文片段，未作补全）