语法分析错误恢复：让编译器在报错中继续前行

可视化演示

语法错误恢复使编译器在遇到错误后继续分析以发现更多错误。本文介绍恐慌模式跳过符号直到同步token、短语级恢复... 切换模式查看不同维度。

一、问题本质

总厨翻开一本新的后厨指令单，头三行就有两处错：不是调料写反，就是数量写成「2 盐克」。他当然不能把整本单子扔掉——后面还有几十道菜等着上桌。他真正要做的是：记下这个错，继续读，把整本单子的问题一次性找全，让服务员（用户）一次拿到完整的修改清单。语法分析器面对源程序时也是同样的处境：词法分析送来的 token 流里，任何一个与文法不符的符号，都可能导致整个解析停摆。

所谓语法错误，抽象地看就是一段输入 token 序列不属于该文法定义的语言。理解这一点，就能明白错误恢复的本质——不是「修复程序」，而是「让分析器继续前进，从而暴露更多错误」。

错误恢复的目标因此有两个：一是尽量发现更多真实的错误，二是避免「一错再错」的级联误报——就像总厨如果因为一行乱码就怀疑后面所有菜都错了，那这份修改清单就彻底没法用了。为了在分析中稳住阵脚，人们引入了「同步」概念：选定若干可靠的 token 作为恢复锚点，只要分析器找到锚点，就能像总厨看到下一道菜的大标题一样，重新稳住节奏。这一个概念，是后面所有策略的基石。

二、恐慌模式

总厨遇到一行完全读不懂的乱码时，最省事的办法就是直接把这一行撕掉，然后快速往后翻，直到看见下一个「新菜式标题」——比如「第三道：清蒸鲈鱼」这种明显的章节标志——才停下来继续核对。这就是恐慌模式：当错误出现时，不是停下来分析这行为什么错，而是扔掉接下来的输入 token，一路跳过，直到遇见一个「同步 token」。

这个策略里最关键的问题只有一个：哪些 token 值得作为「章节标题」？答案是看 Follow 集合。某个非终结符 $A$ 的 Follow 集合，就是语法中所有可能紧跟在 $A$ 后面出现的 token 集合——好比总厨知道一道「清蒸鲈鱼」之后，下一行必然会出现「蒸锅」这类固定词。分析出错时，这些 Follow 集合的成员就是天然的恢复点。再把语言里的语句结束符（分号 ;、右花括号 } 等）也加进去，就构成了一张同步 token 清单。

恐慌模式的优点正是它的简单：实现容易，且绝不可能陷入死循环，因为每次错误必然丢弃至少一个输入符号。缺点也很明显——被撕掉的「菜」里可能藏着真实错误，导致漏报。但作为工程中最重要的兜底方案，几乎所有 LL(1) 分析器和大多数手写递归下降分析器都默认使用它。总厨的直觉是对的：先保证整本菜单能继续读下去，细节错误后面再补查。

三、短语级恢复

恐慌模式虽然痛快，但总厨总觉得不甘心：一行里明明只有「取 3 西红柿个」这半句写错，把「个」挪到「西红柿」后面就通顺了，何必撕掉整行？这种想法催生了短语级恢复——在错误发生的位置，直接对 token 流做插入、删除或替换，用最小改动让语法分析继续。

这就像总厨用笔把「3 西红柿个」涂改成「3 个西红柿」：修改范围仅限于出错的「短语」，不动后面的内容。在 LL(1) 分析器中有一个很自然的落点：预测分析表里那些空表项。当查表发现「当前非终结符 × 当前输入 token」这个格子是空的，就说明当前 token 不该出现在这里——此时短语级恢复会尝试把输入 token 替换成表中期望的 token，或者干脆插入一个期望 token 后继续匹配，让分析最少地偏离原输入。

短语级恢复的优点是定位准确、不轻易丢失后续 token；代价是恢复规则需要精心设计，修得不好反而会引入新的错误，造成级联误报——好比总厨手一抖把「盐」改成了「糖」，后面所有菜的味道判断全乱了。因此实际工程中，短语级恢复常和恐慌模式搭配使用：先尝试小修，小修无效就果断跳段。经验丰富的总厨都明白：能小改的菜绝不大改，但也不能为救一道菜废掉整桌席。

四、错误产生式

有经验的后厨会准备一块「常见笔误对照表」贴在灶台上：「西红柿」常被写成「西红柿个」、「宫保鸡丁」常被写成「宫鸡保丁」。一旦总厨瞄到这种熟悉的错误模式，根本不需要思考，直接按对照表处理。错误产生式就是把这种「预案」写进文法本身：在文法中预埋带有特殊非终结符 error 的产生式，专门匹配那些「常见错误区域」。

例如在 Yacc 中，你可以写一条规则：某个语句产生式允许在中间出现 error，后面跟着一条语句结束符。分析器一旦进入错误状态，就会丢弃输入，直到找到能匹配该产生式后续部分的 token（比如分号），然后通过这条产生式完成一次归约。归约时绑定的语义动作还能输出针对性的错误信息，比如「第 5 行语句缺少分号」——这比笼统的「语法错误」有用得多。

错误产生式与前两种策略最大的不同是：它不是「事后补救」，而是「事前设防」。对语言中反复出现的典型错误，这条通路既快又准，还能附带最好的错误提示。局限在于它只能覆盖「预案里写过的错误」，遇到没预料的错误，仍然要退回恐慌模式或短语级恢复。总厨的对照表再厚，也不能穷尽所有笔误——但它能覆盖 80% 的日常情况，这就值得贴在最显眼的地方。

五、全局纠正

现在让我们设想一个更极端的总厨：他拿到一份错得比较离谱的指令单，不是改一两行就能救。他决定把整份单子重新誊写一遍，用最少的改动让它从头到尾通顺。这就是全局纠正：在全局范围内搜索所有可能的修复方案，选择「编辑距离」最小、也就是修改代价最小的那一个。

这种思路的理论基础是字符串编辑距离。把一个 token 序列改成另一个合法序列，需要的操作包括插入、删除、替换各算一步代价，动态规划可以在 $O(mn)$ 时间内求出最小步数。理论上，全局纠正能找到最优修复，错误报告也最精确；但代价极大——整个搜索过程开销高、实现复杂，而且「最小修改」未必是「程序原本想表达的意思」，甚至可能把错的程序改成另一段同样错的程序。

正是这种「通盘考虑」的特性，让全局纠正成为一种理论上漂亮、工程上却不太实惠的方案。主流编译器在实际实现中几乎不会对整个输入做全局纠正，因为用户等不起总厨把整本指令单重新誊写一遍。但在小范围的候选集内（比如为单个错误 token 枚举几种最可能的修复），它的思想被广泛借鉴——就像总厨虽然不重誊整本菜单，但对着同一行字涂改时，心里也要择出改动最少的那种改法。

六、实践工具

理论再漂亮，最终要落到后厨的工具箱里。对语法分析器来说，这个工具箱里最趁手的家伙就是 Yacc/Bison 这类解析器生成器。它们在 LR 自动机中内建了错误处理的完整链路：遇到错误时调用 yyerror 报告信息，进入特殊错误状态，然后按照用户写的 error 产生式继续分析；分析恢复后，调用 yyerrok 重置错误状态，防止同一条错误被反复报告上千次。

举个例子，如果你想告诉用户「语句缺分号」，可以在文法的语句规则中加一条产生式：由 error 吸收从出错点到分号之间的所有 token，然后归约成一个合法语句，并在语义动作中输出定制的错误信息。这也是错误产生式思想在 LR 分析器里的标准实现。对 LL 分析器来说，手写递归下降分析器时则可以灵活组合「同步 token 跳过 + 局部插入替换」两招，但核心依然是那四个字：同步、继续。

工程中真正重要的，不是掌握某个工具的参数，而是理解工具背后的权衡。Yacc 的 error 规则给了你自由，但每加一条规则都要想清楚：这个错误真的常见吗？同步点选得稳吗？会不会吞掉后面一大段有效代码？一个有经验的总厨不会把所有食材都堆在案板上，而是知道哪道菜用什么刀法——同理，一个熟练的编译工程师，会针对语言的常见错误模式，在「恐慌的粗暴」与「短语级恢复的精细」之间调制出一种恰到好处的方案。

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-"""演示 LL(1) 预测分析器中的恐慌模式错误恢复。 文法：E  -> T E'E' -> + T E' | epsT  -> F T'T' -> * F T' | epsF  -> ( E ) | id"""import re # 预测分析表：非终结符 -> 终结符 -> 产生式右部table = {    'E':  {'id': ['T', "E'"], '(': ['T', "E'"]},    "E'": {'+': ['+', 'T', "E'"], ')': ['eps'], ';': ['eps']},    'T':  {'id': ['F', "T'"], '(': ['F', "T'"]},    "T'": {'*': ['*', 'F', "T'"], '+': ['eps'], ')': ['eps'], ';': ['eps']},    'F':  {'id': ['id'], '(': ['(', 'E', ')']},} # 每个非终结符的同步 token 集合（模拟 Follow 集的子集）sync = {    'E':  {';', ')'},    "E'": {';', ')'},    'T':  {';', ')', '+'},    "T'": {';', ')', '+'},    'F':  {';', ')', '+', '*'},}  def tokenize(s):    return re.findall(r'id|\+|\*|\(|\)|;', s)  def parse(src):    tokens = tokenize(src) + [';']   # 末尾补文件结束符    pos = 0    stack = ['E']    errors = []     while stack:        top = stack.pop()        tok = tokens[pos]         if top == 'eps':            continue        if top in table:                     # 非终结符            if tok in table[top]:                stack.extend(reversed(table[top][tok]))            else:                errors.append(f'at "{tok}": expected {list(table[top].keys())}')                # 恐慌模式：跳过输入直到同步 token                while pos < len(tokens) and tok not in sync[top]:                    pos += 1                    tok = tokens[pos]        else:                                # 终结符            if top == tok:                pos += 1            else:                errors.append(f'at "{tok}": expected "{top}"')                while pos < len(tokens) and tok not in sync.get(top, set()):                    pos += 1                    tok = tokens[pos]     return tokens, errors  if __name__ == '__main__':    for src in ['id + id * id ;', 'id = id ;', 'id + * id ;']:        tks, errs = parse(src)        print(f'input : {src}')        print(f'tokens: {" ".join(tks)}')        if errs:            for e in errs:                print('  [error]', e)        else:            print('  parse ok, no errors.')        print('---')

1. stack = ['E']初始化分析栈，栈顶是文法的开始符号，一路推导下去就是语法树。
2. if tok in table[top]查预测分析表：当前非终结符与当前输入 token 有产生式则正常推导。
3. errors.append(f'at "{tok}": expected {list(table[top].keys())}')记录期望错误，让用户一眼看到「这里原本该出现什么」。
4. while pos < len(tokens) and tok not in sync[top]: pos += 1恐慌模式的核心：循环丢弃输入 token，直到命中同步集合里的安全 token。
5. stack.extend(reversed(table[top][tok]))逆序压栈，保证产生式右部从左到右依次出栈，实现最左推导。

常见误区

面试题