预测分析（进阶）
复习
- 递归下降分析：每个非终结符对应一个函数
- 上下文无关文法：产生式与推导
- 前瞻：递归下降遇到分支时需要提前看，才能选对产生式
本章为进阶内容，零基础读者可以跳过，不影响后续阅读。
TL;DR
- 预测分析只向前看固定的词数，就能决定用哪条产生式
- 它可以用一张分析表来查“当前该怎么做”
- LL(1) 指只看一个词的情况
- 它把递归下降变成查表，无需回溯
正文
递归下降在遇到分支时，要“提前看”才能选对产生式。如果把“该看什么、该选哪条”事先整理成一张表，分析就能变成纯粹的查表——这就是预测分析（predictive parsing）。
先算清楚“该看什么”
要建这张表，先得回答两个问题：
- 对某个非终结符的某条产生式，它的“开头”可能长什么样？（这组开头的词，叫 FIRST 集）
- 如果这条产生式可能推导出空串，那它后面又能跟什么词？（这组词，叫 FOLLOW 集）
把这些信息整理出来，就能为每个“非终结符 + 当前词”的组合，指定“该用哪条产生式”。这就形成了一张分析表。
查表，不用猜
有了分析表，分析过程就是一个循环：
- 看栈顶的非终结符和当前输入词
- 查表，决定用哪条产生式
- 把该产生式右边的内容压栈，继续
整个过程不需要回溯：每一步该做什么，表里都写得明明白白。只向前看一个词就能唯一决定的文法，叫 LL(1) 文法。
可以看出，预测分析其实是递归下降的“表格化版本”：递归下降用函数调用来展开，预测分析用一张表和一个栈来展开。本质一样，形式不同。
但很多文法不满足
麻烦在于，现实里的程序语言文法，很多不是 LL(1) 的。比如有左递归（规则自己开头又调用自己），或者有多条产生式开头相同，都会让表出现“冲突”，无法唯一决定。
这时就要先改写文法：消除左递归、提取公共前缀等，把它变成等价的 LL(1) 形式。改写在理论上可行，但会让文法和语法树都变得不那么自然。
正因为这个限制，工业界处理复杂语言时，往往转向另一类方法——从下往上“归约”。下一章来看。
思考题 1
预测分析为什么“不需要回溯”？
思考题 2
为什么有些文法不能直接用预测分析，需要先改写？
小结
知识点
- 预测分析用 FIRST／FOLLOW 集构造分析表
- 借助分析表和栈，只向前看固定词数即可确定动作
- LL(1) 只需向前看一个词
- 非 LL(1) 文法需先改写，如消除左递归
参考资料
- Wikipedia(zh)：LL解析器：自顶向下、向前看的解析器
- Wikipedia(zh)：语法分析：自顶向下与自底向上的解析方法
思考题答案（仅供参考）
思考题 1
因为分析表已经事先规定好“在当前非终结符和当前词下该用哪条产生式”。分析时只需查表，按表执行即可，不必像回溯那样先试一条、失败再退回，因此不需要回溯。
思考题 2
因为很多语言的文法存在左递归，或多条产生式的开头相同，导致分析表出现冲突，无法唯一决定动作（不是 LL(1)）。此时需要先消除左递归、提取公共前缀，把文法改写成等价的 LL(1) 形式。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪