5.1 FIRST 与 FOLLOW 集

自顶向下分析本质上是一场“提前承诺”。当语法分析器（parser）面对一个有多条产生式的非终结符时，它必须在尚未读完整个结构前选择一条产生式。FIRST 与 FOLLOW 集把这种选择变成有限、可检查的向前看信息。它们不是实现细节，而是 LL(1) 语法分析器能否成立的证明依据，也是本章后面错误恢复的重要基础。

下面使用一份小语言文法。词法单元（token）名称是终结符，epsilon 表示空串：

Program  -> StmtList EOF
StmtList -> Stmt StmtList | epsilon
Stmt     -> let IDENT = Expr ; | print Expr ;
Expr     -> Term ExprTail
ExprTail -> + Term ExprTail | epsilon
Term     -> NUMBER | IDENT | ( Expr )

前一章已经做过必要的左递归消除和左因子提取。这不是形式上的清理；FIRST 与 FOLLOW 会揭示经过改写的文法是否真的能由一个词法单元的向前看驱动。

FIRST：这里可能以什么开始？

对文法符号或符号串 alpha，FIRST(alpha) 包含 alpha 能推导出的某个串最前面可能出现的所有终结符。如果 alpha 能推出空串，集合还包含 epsilon。

基本规则很短：

• 若 a 是终结符，则 FIRST(a) = { a }。

• FIRST(epsilon) = { epsilon }。

• 对非终结符 A，合并 A 每个右部的 FIRST 信息。

真正容易出错的是符号串。对 X1 X2 ... Xn，先加入 FIRST(X1) 中除去 epsilon 的部分；若 X1 可空，继续查看 X2；所有符号都可空时，才把 epsilon 放入结果。

例如：

FIRST(Term)     = { NUMBER, IDENT, ( }
FIRST(ExprTail) = { +, epsilon }
FIRST(Expr)     = { NUMBER, IDENT, ( }
FIRST(Stmt)     = { let, print }
FIRST(StmtList) = { let, print, epsilon }

注意 FIRST(StmtList) 与 FIRST(Stmt StmtList) 的区别。前者包含 epsilon，因为整个语句列表可以结束；后者不包含，因为 Stmt 本身不可空。多放一个 epsilon 就可能把错误的产生式放进分析表，所以“可空”不是模糊的“好像可选”，而是对某个具体符号串的形式性质。

FOLLOW：完成后紧接着可能出现什么？

FOLLOW(A) 解决的是另一件事：从开始符号推导的某个句型中，一个完整 A 的右侧紧接着可能出现哪些终结符？非终结符不会出现在最终词法单元流中，因此 FOLLOW 总是终结符集合。完整程序后应当到达输入末尾，所以 EOF 属于 FOLLOW(Program)。

不断应用下面三条规则，直到集合不再变化：

1. 把 EOF 放进 FOLLOW(Start)。

2. 对每条 A -> alpha B beta，把 FIRST(beta) - { epsilon } 加入 FOLLOW(B)。

3. 在同一产生式中，若 beta 能推出 epsilon（包括 beta 为空），把 FOLLOW(A) 加入 FOLLOW(B)。

看 Expr -> Term ExprTail。FIRST(ExprTail) - { epsilon } 会把 + 加进 FOLLOW(Term)；又因为 ExprTail 可空，所有跟在 Expr 后面的词法单元也都可能跟在 Term 后面。这个“可空后缀让外层上下文向前传播”的步骤最容易遗漏。

该文法的一个不动点结果为：

FOLLOW(Program)  = { EOF }
FOLLOW(StmtList) = { EOF }
FOLLOW(Stmt)     = { let, print, EOF }
FOLLOW(Expr)     = { ;, ) }
FOLLOW(ExprTail) = { ;, ) }
FOLLOW(Term)     = { +, ;, ) }

FOLLOW(Stmt) 有 let 与 print，是因为一条完成的语句后可以立刻开始下一条语句。这是文法事实，不代表语言一定不需要分隔符；换行、分号等约束仍由其他产生式描述。

计算到不动点，再用语言直觉验证

相互递归的文法不能靠一次扫描算完。可靠实现应把所有集合初始化为空，加入基础事实，然后反复扫描产生式，直到一轮没有任何集合增长。集合只会增加，而终结符数目有限，所以过程一定终止。

repeat
  changed = false
  for each production A -> alpha:
    changed |= addFirstFacts(A, alpha)
until not changed

repeat
  changed = false
  for each production A -> alpha B beta:
    changed |= add(FOLLOW(B), FIRST(beta) - { epsilon })
    if epsilon in FIRST(beta):
      changed |= add(FOLLOW(B), FOLLOW(A))
until not changed

在工程代码里，firstOfSequence 应该是独立、充分测试的辅助函数（helper），因为 FIRST 计算和分析表构造都会调用它。最好还能记录词法单元为什么进入集合，例如 ) 由于 Factor -> ( Expr ) 而进入 FOLLOW(Expr)。这种来源信息能把神秘的分析表冲突变成可定位的文法事实。

最后用语言直觉做完整性检查（sanity check），但不要用直觉替代算法。带括号表达式的语言里，FOLLOW(Expr) 理应有 )；它通常不该有 NUMBER，因为两个基本项不能无运算符直接相连。若出现意外词法单元，就沿着具体产生式与可空后缀追查。

从左到右计算符号串

对 A -> B C D，右部 FIRST 先取 FIRST(B) 去掉 epsilon；只有 B 可空才看 C，B/C 都可空才看 D。这个停止规则是错误分析表最常见来源。FOLLOW 则反向传播：C 的 FIRST 进入 FOLLOW(B)，只有 C 可消失时 FOLLOW(A) 才能到 B。

为每个加入集合的词法单元记来源，例如“) 由 Factor -> ( Expr ) 进入 FOLLOW(Expr)”。出现冲突时，来源信息能把集合恢复为可解释的文法事实。