6.2 FIRST、FOLLOW 与错误恢复：预测解析为何能做决定

预测解析器希望只看一个前瞻 token 就选择产生式，还要在输入出错后继续报告后面的结构问题。

递归下降代码看起来像手工分支，但每个分支背后都有一项可检查条件：看到当前 token 后，至多有一条产生式应该被选择。FIRST 和 FOLLOW 集把这种直觉变成算法。

本课目标

• 计算可空、FIRST 和 FOLLOW；
• 构造 LL(1) 预测表并识别冲突；
• 区分消除左递归与左因子提取；
• 使用 panic mode、插入和错误节点恢复。

1. 可空与 FIRST

若非终结符 $A{\Rightarrow }^{\ast }\epsilon$，称 $A$ 可空。FIRST$(\alpha )$ 收集满足 $\alpha {\Rightarrow }^{\ast }a\beta$ 的首终结符 $a$，其中 $\beta$ 是文法符号串；若 $\alpha$ 可空，还包含 $\epsilon$。

文法：

Stmt  → "return" ExprOpt ";"
ExprOpt → Expr | ε
Expr → IDENT | NUMBER

有：

FIRST(Expr)    = { IDENT, NUMBER }
FIRST(ExprOpt) = { IDENT, NUMBER, ε }
FIRST(Stmt)    = { "return" }

计算 FIRST 需要不动点迭代：反复传播产生式信息，直到集合不再变化。递归文法不能只从上到下扫一遍。

2. FOLLOW 处理可空分支

FOLLOW$(A)$ 是在某个句型中可能紧跟 $A$ 的终结符集合。开始符号的 FOLLOW 包含 EOF；EOF 是输入边界标记，不是文法中的普通终结符。这里以 Stmt 为开始符号。

规则要点：

• 若 $X\to \alpha A\beta$，把 FIRST$(\beta )\setminus \{\epsilon \}$ 加入 FOLLOW$(A)$；
• 若 $\beta$ 可空或产生式以 $A$ 结尾，把 FOLLOW$(X)$ 加入 FOLLOW$(A)$。

在上面文法中，ExprOpt 后面固定是 ;，所以：

FOLLOW(ExprOpt) = { ";" }

看到 return ; 时，当前 token ; 不在 FIRST$(Expr)$，却在 FOLLOW$(ExprOpt)$，解析器据此选择 $\epsilon$ 分支。

3. LL(1) 表的填充规则

对产生式 $A\to \alpha$：

1. 对每个 $a\in FIRST(\alpha )\setminus \{\epsilon \}$，把该产生式放入表项 $M[A,a]$；
2. 若 $\epsilon \in FIRST(\alpha )$，对每个 $b\in FOLLOW(A)$，放入 $M[A,b]$。

若一个表格单元需要放两条不同产生式，就存在 LL(1) 冲突。可能原因包括：

• 两个分支 FIRST 相交；
• 某个分支可空，而另一分支的 FIRST 与该非终结符的 FOLLOW 相交；
• 文法二义；
• 文法无二义但不属于 LL(1)。

有冲突不自动证明语言无法用递归下降处理。可通过改写文法、增加 lookahead、使用语义谓词或换解析算法。

4. 左递归与共同前缀是不同问题

直接左递归：

Expr → Expr "+" Term | Term

会让直接递归下降在消费 token 前调用自己。表达式通常改成：

Expr → Term ("+" Term)*

共同前缀：

Stmt → IDENT "=" Expr | IDENT "(" Args ")"

一个 lookahead 只看到 IDENT 无法决定，可提取：

Stmt → IDENT StmtTail
StmtTail → "=" Expr | "(" Args ")"

消左递归防止无进展递归，提取左因子把选择推迟到共同前缀之后。它们都不会自动修正文法二义性或语言设计冲突。

5. 好诊断需要“期望集合”

预测表当前行中的非空项给出这一非终结符的可选前瞻集合；实际 token 对应的空项表示不能据它选择产生式。期望集合还应结合当前调用或栈上下文，尤其要处理可空退出。错误消息应包含：

实际 token + 期望 token 集合 + 源 span + 相关上下文

例如：

line 8:14: 在参数列表中遇到 `}`，需要表达式或 `)`

不要把内部非终结符名称直接抛给用户，如“expected ExprTailPrime”。诊断层应映射为语言概念，并控制期望集合长度。

6. Panic mode 同步

遇错后跳过 token，直到看到同步集合中的边界：

语句同步：;  }  EOF
声明同步：class  fn  let  EOF
参数同步：,  )  EOF

同步集合常参考 FOLLOW，但应结合语言结构人工调整。跳得太少会产生级联错误，跳得太多会吞掉本来可解析的后续代码。

static void synchronize_statement(Parser *p, size_t failed_start) {
    assert(failed_start <= p->current);
    while (peek(p)->kind != TOK_EOF) {
        if (p->current > failed_start
                && p->tokens[p->current - 1].kind == TOK_SEMICOLON) return;
        if (peek(p)->kind == TOK_RIGHT_BRACE) return;
        if (p->current > failed_start && starts_statement(peek(p)->kind)) return;
        p->current++;
    }
}

这是与上一课 Parser 接口配合的恢复片段；starts_statement 由语言的语句规则定义。调用方在尝试解析语句前保存 failed_start = p->current，并保证 0 <= failed_start <= current < count。只有本次尝试已前进，才允许在新语句起点直接返回；查看前一 token 也受这个条件保护。

右花括号留给所属块的调用方消费。若顶层遇到没有所属块的 }，顶层必须报错并消费它，或直接结束，不能原样重试。局部函数“消费或返回”还不够，整个调用循环都要保证前进。

7. 插入、删除与错误节点

如果看到：

print(value

文件在这里结束，parser 可以合成一个零长度 ) token，报告一次缺失，并继续构建调用节点。对多余逗号，则可能删除当前 token 后重试。

恢复操作应有成本与限制：

• 优先少量局部插入或删除；
• 同一位置不重复报告；
• 限制总诊断数；
• AST 中保留 missing/error 节点；
• 后续语义分析识别错误节点，避免制造无意义级联诊断。

8. LL(k) 与手写预测

LL(1) 使用一个 lookahead。LL(k) 使用固定 $k$ 个，文法类随 $k$ 增强，但表可能变大。手写 parser 常在局部查看两个或更多 token，或采用 Pratt parser 处理表达式。

这不妨碍用 FIRST/FOLLOW 检查大部分文法。真正重要的是把例外分支、lookahead 数量和回溯行为写清楚，而不是把“手写”当作无需形式分析。

常见误区

• FIRST 只看产生式第一个符号：若前缀可空，必须继续向后传播。
• FOLLOW 是运行时下一个 token：它是所有可能句型中的集合。
• LL 冲突等于文法二义：无二义文法也可能不是 LL(1)。
• 错误恢复越积极越好：错误修改过多会产生错误 AST 和误导性诊断。

练习

1. 为逗号分隔、允许空列表的参数文法计算 FIRST/FOLLOW。
2. 找出一处 FIRST/FIRST 冲突和一处 FIRST/FOLLOW 冲突。
3. 为块、语句和参数列表分别设计同步集合。
4. 给缺失分号实现零长度 synthetic token，并避免重复报错。

小结

FIRST 告诉解析可能怎样开始，FOLLOW 在可空分支后提供退出依据；二者决定 LL(1) 是否能凭一个 token 做唯一选择。错误恢复则把“判定失败”升级为“产生有边界的诊断并继续工作”。

下一课从另一个方向解析：先移入输入片段，再在句柄出现时归约为非终结符。