预测分析表全解析：从FIRST/FOLLOW集到自动构造器)
1. 为什么是那张表自顶向下语法分析的两个死穴语法分析在编译原理课程链条里的位置各位应该都清楚词法分析把源代码切成 token 流语法分析要把 token 流组织成一棵语法树。自顶向下分析的核心思路是“从开始符号出发反复用产生式右部去替换非终结符直到整棵树的叶子都是终结符”。听起来很直白但真写分析器的时候会撞上两个非常现实的问题。第一个死穴是“选哪条产生式”。语法分析器每读入一个非终结符就要决定下一步到底展开它的哪条候选式。比如有产生式E - E T | T当前要展开 E到底选E T还是选T如果只看文法本身没有额外的信息就只能猜。猜错怎么办得回溯。回溯意味着前面已经读入的 token 要吐回来分析状态要存档恢复整个分析过程的时间复杂度可能指数爆炸工程上完全不可接受。第二个死穴是“左递归”。只要文法里有形如A - Aα这样的产生式自顶向下分析就会陷入死循环为了展开 A先去展开 Aexpand 永远不会向前消耗一个输入符号。这是初学者最常踩的坑很多人看到E - E T第一反应是“这不就是循环展开吗”但机器真的按推导逻辑走的时候连第一步都迈不出去。所以工业界也好课堂教学也罢都会努力把文法做“规整”规整到这两个死穴都消失。规整的结果叫 LL(1) 文法。LL(1) 这个名字拆开是第一个 L 表示从左到右扫描输入第二个 L 表示推导过程产生最左推导括号里的 1 表示分析时只需要向前看一个输入符号就能做决策。“只向前看一个符号”听起来很神奇实际做法就是把决策信息提前算好集中存到一张二维表里——这就是预测分析表。行是非终结符列是终结符外加一个输入结束符$表项是“当前遇到这个输入符号时该用哪条产生式”。一旦这张表构造出来自顶向下的分析就变成了查表和压栈的机械过程。而构造表所需的全部前置材料就是两个集合FIRST 集和 FOLLOW 集。很多人学到这里会觉得头大因为课程里 FIRST、FOLLOW、预测分析表三块内容连在一起讲中间还夹着一堆定义和定理信息量特别大。但换个角度看这套东西就是一个流水线文法进表出。中间每一步都是确定性算法没有玄学。文章下面的内容我按这条流水线的顺序把每一个环节掰开讲清楚最后手把手带你从头到尾推一张完整的表出来。2. FIRST 集推导方向上的“前瞻情报”到底怎么算2.1 FIRST 集中的 FIRST 指什么先定义一下对任意一个文法符号串 αFIRST(α) 是“从 α 出发通过一步或多步推导能出现在串首的所有终结符的集合”。通俗地说我拿到一个产生式右部想知道“这东西将来展开后第一个吐出来的 token 可能是哪些”这个集合就是 FIRST 集。这个集合的用途在填表时非常直接如果我在分析过程中要展开非终结符 A而当前输入符号是 a而 A 恰好存在一条产生式A - α且a ∈ FIRST(α)说明这条产生式可以先吐出一个和当前输入匹配的 token那就应该选它。计算 FIRST 集的顺序十分重要这里我直接给出经过实践验证的完整计算流程宁可啰嗦也要把边界情况照顾到对所有终结符 aFIRST(a) {a}。对所有非终结符 A初始 FIRST(A) ∅。反复扫描所有形如A - X1 X2 ... Xn的产生式做下面的事情令 i 1。把 FIRST(Xi) 中所有非空终结符加入 FIRST(A)。如果ε ∈ FIRST(Xi)继续看下一个符号 X(i1)否则终止对这一条产生式的处理。如果扫描完所有 Xi 都含 ε即 X1...Xn 整体能推导出 ε把 ε 也加入 FIRST(A)。注意第 3 步里“ε 要不要继续往后传染”这个逻辑是整个算法的灵魂。很多资料会写“如果 X1 可以推空则看 X2依此类推”但实际操作时漏掉“传染”或者过度传染都是常见问题。2.2 一个边算边体会的例子光说规则太干我拿一个稍后会反复使用的例子文法先做了消除左因子的预处理走一遍E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id第一步终结符的 FIRST 集不用算FIRST(id) {id}FIRST() {}FIRST() {}FIRST(() {(}FIRST()) {)}。第二步对所有非终结符初始化。然后开始迭代扫描产生式。第一轮扫描处理F - ( E ) | id直接得到 FIRST(F) {(, id}。这俩右部第一个符号都是终结符不需要往后传染。处理T - F T由于 FIRST(F) 现在已经是 {(, id}直接加入 FIRST(T)。处理E - T E同理把 FIRST(T) 的值复制进 FIRST(E)。注意这里 E 的 FIRST 是跟着 T 走的T 的 FIRST 又跟着 F 走。这一轮结束三个集合的值是 FIRST(E) FIRST(T) FIRST(F) {(, id}。第二轮扫描处理E - T E | ε第一条右部第一个符号是终结符所以 FIRST(E) 加入第二条右部就是 ε所以 ε 也加入 FIRST(E)。处理T - * F T | ε同理FIRST(T) {*, ε}。到这里所有集合都稳定了。你发现没有这个文法里的非终结符编号顺序恰好是从 F 到 E一层一层往上推一轮就能算完。但如果文法里存在间接依赖比如A - B...、B - A...这种一轮就不够了必须反复迭代直到所有集合都不再变化。后面写到自动构造器时这个迭代退出条件就是整个程序能不能跑对的关键。2.3 初学者最容易忽略的两种情况第一种是“产生式右部以非终结符开头但该非终结符能推出 ε”。例如A - B c如果ε ∈ FIRST(B)那么 FIRST(A) 除了包含 FIRST(B) 去掉 ε 的部分还必须包含c。很多人算到这里就把c丢了最后表填出来少项查错能查一晚上。我们上面例子里的E - T E不涉及这个问题因为 FIRST(T) 里没有 ε所以直接复制就完事但换成A - B c、B - ε | d这种文法就必须处理“推空后继续往右看”的逻辑。第二种是右部整体可推空。例如S - B CB - εC - ε最后 ε 必须进入 FIRST(S)。epsilon 这个特殊成员在 FOLLOW 集计算里会继续开花结果所以不能嫌麻烦跳过。刚才例子里的E - T E | ε就直接演示了这一点ε 进 FIRST(E) 是下面算 FOLLOW 的必要输入。提示使用“不动点迭代法”算 FIRST 时建议在纸上写一张大表每一轮扫描的所有集合值都记下来。我本科时贪快把多轮合并成一步心算结果算到 FOLLOW 时发现前面某个值该有却没有整张预测分析表全部返工。后来老老实实画表迭代出错概率低了很多。3. 终结符后面跟什么FOLLOW 集的推导与三条核心规则3.1 FOLLOW 集存在的意义FIRST 集只能告诉你“一个符号串开头能有哪些终结符”但在自顶向下分析中还有一类更隐蔽的问题当某个非终结符 A 在推导过程中可以被替换为 ε 时我们实际上会把 A 直接“跳过”那接下来的输入符号必须能和 A 后面出现的终结符对上。这个“A 后面可能紧跟着哪些输入符号”就是 FOLLOW(A) 的定义。FOLLOW 集的另一个关键用途和预测分析表的特殊表项有关当一个非终结符 A 的某条产生式右部能推出 ε就相当于“让 A 消失”这时候要不要继续往下匹配只能靠 FOLLOW(A) 来决定。换句话说FIRST 管的是“该往哪条路走”FOLLOW 管的是“实在没路走的时候哪条路兜底”。FOLLOW 集的计算核心就三条规则我把它们逐个拆开规则一对文法的开始符号 S把输入结束符$放入 FOLLOW(S)。这个$是输入串的哨兵表示“分析已经进行到输入末尾”它必须能对上开始符号的结尾。规则二如果有产生式A - α B β那么 FIRST(β) 中除 ε 之外的所有终结符都要加入 FOLLOW(B)。理由很直观B 后面跟着 ββ 的第一个符号当然可能出现在 B 的后面。规则三如果有产生式A - α B或者A - α B β且ε ∈ FIRST(β)那么 FOLLOW(A) 的所有成员都要加入 FOLLOW(B)。这条规则最容易被无视道理是B 是 A 右部的最后一部分或者 B 后面那一段能推空那么任何能跟在 A 后面的符号也必然能跟在 B 后面。三个规则之间的关系用一个生活化类比可能更好懂A 是“一家公司”FOLLOW(A) 是“这家公司往下一步所有可能的合作方类型”B 是公司里的一个具体部门如果部门 B 参与的项目是公司收尾项目或者项目后面那段会“蒸发”那么公司的合作方也会直接变成这个部门下游的合作方。3.2 继续用表达式文法走 FOLLOW 集沿用上面那个文法我按上面三条规则一步步算因为 E 是开始符号FOLLOW(E) 初始为 {$}。扫描所有产生式找“非终结符后面跟着别的东西”的形态在F - ( E )里E 后面跟着)所以)加入 FOLLOW(E)。在E - T E和T - F T这类产生式里考察每个非终结符后面跟的符号串。处理规则三的部分E - T EE 在右部末尾所以 FOLLOW(E) 的东西全给 FOLLOW(E)。E - T E这一条里T 后面是 E而 FIRST(E) {, ε}ε 在里面所以 FOLLOW(E) 给 FOLLOW(T)又因为 E 也在末尾FOLLOW(E) 再次并入自身。T - F TT 在末尾FOLLOW(T) 给 FOLLOW(T)。T - * F TF 后面是 TFIRST(T) {*, ε}所以*加入 FOLLOW(F)同时 FOLLOW(T) 并入 FOLLOW(F)T 在末尾FOLLOW(T) 并入自身。F - ( E )这里是(和 E 和)的结构E 后面有)以及括号内的递归关系没有其他非终结符处于末尾。完整迭代一轮之后各集合稳定值如下非终结符FOLLOW 集E{$,)}E{$,)}T{,$,)}T{,$,)}F{*, ,$,)}这个结果对不对可以用一个直觉检验表达式文法里一个因子后面要么跟着乘法运算符*要么跟着加法运算符要么是整个表达式结束$要么是右括号结束。完全符合对表达式的认知。这里要特别提醒一个我自己反复踩过的坑FOLLOW 集的计算也必须做不动点迭代而且规则三的传播往往不是一轮就能结束的。比如FOLLOW(E)里的$要传播到FOLLOW(E)FOLLOW(E)再传播到FOLLOW(T)FOLLOW(T)才传播到FOLLOW(F)。这中间跨了四级一轮扫描不可能全部完成。初学者容易犯的毛病是扫描一遍就宣布算完结果表填出来在几个非终结符上缺项找半天找不到原因。4. 预测分析表的填表动作从两个集合到一张二维表4.1 表格结构先行预测分析表 M 是一个二维数组行由所有非终结符构成列由所有终结符加上$构成。每个表项M[A, a]存放的内容要么是一条产生式A - α要么是空表示此处报错。表的规模很容易估算非终结符数量 × 终结符数量 1。表达式文法 5 个非终结符、6 个终结符含$表也就是 5 行 7 列。即使一个文法有三四十个非终结符手工填表虽然累但表依然是可读的这恰恰说明表格方法在可形式化上的优势。4.2 填表算法的完整规则填表的核心算法用自然语言描述就是两步循环但中间有一个细节绝不能漏对文法中的每一条产生式A - α执行以下两步如果 α 不能推出 ε对 FIRST(α) 中的每一个终结符 a把A - α填入M[A, a]。如果 ε ∈ FIRST(α)对 FOLLOW(A) 中的每一个终结符 b记住 FOLLOW 集合里的$也算把A - α填入M[A, b]。如果 b 本身就是$填入M[A, $]如果 BOTHε ∈ FIRST(α)且$ ∈ FOLLOW(A)这条产生式还会占M[A, $]。这里每一步的背后逻辑值得再强调一遍。第一步很好理解α 能吐出一个确定的终结符那输入符号就对该终结符选这条产生式天经地义。第二步稍微绕一点α 能推空意味着展开 A 时可以不消耗任何输入符号直接把 A 从栈顶丢掉此时必须保证当前输入符号是 A 的合法后继也就是 FOLLOW(A) 里的成员。第二步如果漏掉最常见的结果是表里大量M[A, a]空着导致分析器在实际分析时遇到本该“推空继续”的输入符号直接报错。比如表达式文法里E - ε这条产生式就要填到M[E, $]和M[E, )]两个位置。如果你只填了M[E, $]那么分析(idid)这种带括号的输入时到idid)右括号那里E 该推空却找不到表项就会直接报“语法错误”。这种 bug 的特征非常典型简单的idid能过一旦带括号就崩。4.3 冲突检测建表顺带完成的合法性验证如果填表时发现某个表项已经被一条产生式占位又要填进另一条不一样产生式说明这个文法不是 LL(1) 文法。冲突的类型通常有这两种FIRST/FIRST 冲突一个非终结符 A 有两条产生式A - α和A - β但 FIRST(α) 和 FIRST(β) 有交集。典型例子是未经提取左因子的文法S - if E then S | if E then S else S两条右部的 FIRST 都是 {if}填表时M[S, if]就会冲突。FIRST/FOLLOW 冲突一条产生式 α 能推空FIRST(α) 里的某个终结符同时又是 FOLLOW(A) 的成员但这两条产生式又不是同一条。这种冲突比较隐蔽常见于文法的 ε 产生式和普通产生式搅在一起。遇到冲突正确的处理方式不是跳过也不是硬选一个优先级而是回到文法本身去修提取左因子消除 FIRST/FIRST 冲突改写产生式消除 FIRST/FOLLOW 冲突。这一条我在后面完整例子里会实际演示。注意LL(1) 是文法性质不是表性质。表构造过程只是把这个性质显式暴露出来。就算你手工造表时“手动消除冲突”文法的 LL(1) 性也不会因此变好后续扩展或者换工具生成时会再次踩雷。5. 从文法到表一次通关表达式文法完整手工推导5.1 原始文法为什么要先“整形”我们最开始给出的表达式文法其实不是原始形态而是经过两步预处理之后的样子。现在我把预处理步骤补上因为很多读者会问“教材里一开始给的文法就是这种规整形态吗怎么来的”原始表达式文法通常是E - E T | T T - T * F | F F - ( E ) | id这个文法有直接左递归不能用于自顶向下分析。第一步是做消除左递归。以E - E T | T为例它符合A - Aα | β的模式其中 α Tβ T。消除左递归的通用方法是引入新非终结符 AA - β A A - α A | ε代入到 E 和 T 上就得到E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id恰好就是我们前面的文法。这个变形是等价的但会产生一个副作用多出来的 E、T 都有 ε 产生式这正是后面 FIRST/FOLLOW 集计算麻烦的来源。如果原始文法里还有公共前缀比如S - if E then S | if E then S else S还得用提取左因子消除 FIRST 冲突这里暂时不展开但考试和面试里经常会和左递归消除一起考。5.2 现在把两个集合和一张表完整落纸前面 2.2 和 3.2 两节已经把 FIRST 和 FOLLOW 都算完了汇总一下非终结符FIRSTFOLLOWE{(, id}{$,)}E{, ε}{$,)}T{(, id}{,$,)}T{*, ε}{,$,)}F{(, id}{*, ,$,)}现在对每一条产生式做填表操作。我把过程逐条列出来方便对表E - T EFIRST(T E) FIRST(T) {(, id}不含 ε。填入M[E, (]和M[E, id]表项都是E - T E。E - T EFIRST(右部) {}。填入M[E, ]。E - ε右部能推空看 FOLLOW(E) {$,)}。填入M[E, $]和M[E, )]表项都是E - ε。T - F TFIRST(F T) FIRST(F) {(, id}。填入M[T, (]和M[T, id]。T - * F TFIRST(右部) {*}。填入M[T, *]。T - ε看 FOLLOW(T) {,$,)}。填入M[T, ]、M[T, $]、M[T, )]。F - ( E )FIRST(右部) {(}。填入M[F, (]。F - idFIRST(右部) {id}。填入M[F, id]。最终表格如下非终结符id*()$EE → T EE → T EEE → T EE → εE → εTT → F TT → F TTT → εT → * F TT → εT → εFF → idF → ( E )这张表有非常明显的规律E 和 T 只在两个“操作数起点”上有产生式E 在上递推、在)和$上收尾T 同理。这个规律可以帮助你做结果的自检如果填出来的表在某个终结符列上所有格都空着就要回头检查这个终结符是不是从来不会出现在合法输入中如果某个非终结符整行都空则这个非终结符不可达文法设计有问题。到这里LL(1) 预测分析表的构造全流程就被走完了文法变形 → FIRST 集 → FOLLOW 集 → 二维表填表。手工流程至此完整闭环。6. 表建好以后怎么用预测分析算法的驱动逻辑很多教程讲到表构造完就停了但一张表只是“词典”分析器才是用词典造句的人。只有看到表被用起来你才能真正理解为什么前面所有步骤是必要设计。预测分析算法的核心数据结构就是一个分析栈栈里先压入结束符$和开始符号。伪代码如下栈: [$, E] 输入串: id id * id $ 当前符号 输入串头 while 栈非空: X 栈顶 if X 当前符号: 弹栈 前进一个输入符号 elif X 是终结符: 报错不匹配 elif M[X, 当前符号] 是空: 报错无对应产生式 else: 取产生式 X - Y1 Y2 ... Yk 弹栈 将 Yk, ..., Y1 逆序压栈分析器每做一次“查表展开”实际上就是在执行一次最左推导栈顶内容就是当前推导中尚未匹配的剩余符号串。所以整个分析过程可以边分析边输出产生式序号这套序号序列就叫最左推导序列。拿上面的表达式文法分析输入串id id * id栈的变化是初始栈 [$, E]输入id id * id $查表 M[E, id] E - T E压栈后栈变为 [$, E, T]注意逆序压栈后 T 在顶。栈顶 T查表 M[T, id] T - F T栈变为 [$, E, T, F]。栈顶 F查表 M[F, id] F - id栈变为 [$, E, T, id]。栈顶id和当前输入符号id匹配弹栈并读入下一个符号。栈顶 T查表 M[T, ] T - ε弹栈不读入。栈顶 E查表 M[E, ] E - T E栈变为 [$, E, T, ]。继续匹配最终栈清空时输入恰好读完整个输出产生式序列就是一棵语法树的先序遍历顺序。这个序列验证了一个关键结论LL(1) 分析本质上就是“用栈模拟最左推导”。表是静态的栈是动态的两者配合把整棵语法树一点点“长”出来。关于压栈顺序有个小细节值得提一下。产生式右部如果从左到右是Y1 Y2 ... Yk那么分析时需要先展开的是左边的Y1所以入栈顺序必须反过来最后压Y1让它待在栈顶。这个细节我见过不少人在程序里写反结果分析第一步就弹出右部最右侧的符号整个推导完全错位查错时又很难看出来因为不是立刻崩溃而是过几步才乱。7. 自动构造器落地把手工流程写成可复用代码7.1 数据结构怎么设计最顺拿 Python 为例文法存储通常直接用字典最方便key 是非终结符value 是该非终结符对应的产生式右部字符串列表。比如E - T E | T就存成{E: [T E\, T]}。终结符判断可以用一个简单的条件不是非终结符且不等于 ε 的符号就是终结符。FIRST 集可以用defaultdict(set)存储。迭代算法中最关键的部分是非终结符“能不能推出 ε”的判断这个属性在计算 FIRST 时反复用到建议单独缓存成一个can_derive_epsilon布尔字典避免每次重复扫描产生式。FOLLOW 集的存储同样用defaultdict(set)但初始化和迭代顺序要小心。初始化时只有开始符号的集合里有$。迭代时每次往集合里加元素都记录一下“本次有没有新增”没有新增就退出循环。7.2 核心代码骨架下面的代码不是完整工程而是把最核心的迭代逻辑单独抽出来方便理解也方便改成其他语言from collections import defaultdict terminals {(, ), , *, id} nonterminals {E, E\, T, T\, F} start E eps ε productions { E: [T E\], E\: [ T E\, eps], T: [F T\], T\: [* F T\, eps], F: [( E ), id], } first defaultdict(set) # 终结符初始化 for t in terminals: first[t] {t} changed True while changed: changed False for A, rhss in productions.items(): for rhs in rhss: symbols rhs.split() # 对右部符号逐个分析处理 ε 传染 all_derive_eps True for sym in symbols: if sym eps: first[sym] {eps} before len(first[A]) if sym in terminals: first[A].add(sym) break else: # 非终结符去掉 ε 后并入 first[A].update(first[sym] - {eps}) if eps not in first[sym]: break # 如果含 ε继续看下一个符号 after len(first[A]) if after before: changed True else: # 右部所有符号都能推空 if eps not in first[A]: first[A].add(eps) changed True这个循环看起来简单但里面隐含了好几个容易写错的地方。一是update(first[sym] - {eps})这个减集操作不能省因为 FIRST(A) 里能不能放 ε 是由“整个右部是否都能推空”决定的不是由右部开头非终结符是否含 ε 决定的。二是break和for...else的配合如果右部中间某个符号不含 ε循环直接 break否则完整跑完 for-else把 ε 加入 FIRST(A)。FOLLOW 集的迭代代码核心是三条规则。第三条规则实现的时候判断“B 是否在右部末尾”用pos len(symbols) - 1判断“B 后面的符号串整体能否推出 ε”则依赖一个辅助函数derives_epsilon_seqdef payload_can_derive_epsilon(symbols): return all(sym eps or (sym in first and eps in first[sym]) for sym in symbols) follow defaultdict(set) follow[start].add($) changed True while changed: changed False for A, rhss in productions.items(): for rhs in rhss: symbols rhs.split() for i, B in enumerate(symbols): if B not in nonterminals: continue # 规则二B 后面的 FIRST去掉 ε after symbols[i1:] if after: for sym in after: if sym in terminals: follow[B].add(sym) break else: follow[B].update(first[sym] - {eps}) if eps not in first[sym]: break if payload_can_derive_epsilon(after): before len(follow[B]) follow[B].update(follow[A]) if len(follow[B]) before: changed True else: # 规则三B 在末尾 before len(follow[B]) follow[B].update(follow[A]) if len(follow[B]) before: changed True这段代码的复杂度里最容易出问题的还是after为空时直接走规则三和after非空但整体能推空时也要走规则三这两条路径。很多人只写了after为空的情况漏了“整体能推空”的情况导致 FOLLOW 集少传一层。填表部分反而最简单两重循环直接照抄前面手工流程table {} for A, rhss in productions.items(): for rhs in rhss: symbols rhs.split() if rhs eps: keys follow[A] else: # 使用 FIRST(右部)这里用一个递归函数/迭代计算 first_rhs compute_first_of_sequence(symbols, first, eps) keys first_rhs - {eps} if eps in first_rhs: keys | follow[A] for key in keys: if (A, key) in table: raise Exception(f冲突: M[{A}, {key}] 已有 {table[(A, key)]}又想填入 {rhs}) table[(A, key)] rhs当rhs eps时直接把 FOLLOW(A) 当作待填符号集合否则把 FIRST(右部) 放入表项。如果 FIRST(右部) 含 ε还需要额外把 FOLLOW(A) 也放进来。这一步实现时要注意集合操作不要原地修改了first_rhs本身用set复制或者先 copy 再 update否则下一轮循环数据会被污染。7.3 用自动构造器验证前面的手工结果跑一遍上面的代码输出的表项和我们在第 5 节手工填出来的表格完全一致。这才是“梭哈”完手工与自动验证后的体验当你手推一遍、代码自动出一遍两边对上了这个知识点才真正算彻底吃透。从工程角度这个自动构造器稍加改造就能处理更大的语法文法从输入的 grammar 文件读出产生式、自动检测终结符和非终结符、输出冲突报告、生成分析表。很多课程实验的“LL(1) 分析器”项目本质上就是把上面三段代码串起来再加一个驱动分析主循环和输入 token 流即可。8. 冲突检测与错误恢复把表从作业变成能用的工具8.1 FIRST/FIRST 冲突的典型形态自己实现自动构造器后第一个常见的实战场景就是跑一个不是 LL(1) 文法的输入观察冲突报告。看一下这个简单的判断语句文法S - if E then S | if E then S else S | id : E两条以if开头的产生式计算 FIRST 右部后都以if在 FIRST 集合中两个表项都会试图填到M[S, if]冲突立刻被报出来。遇到这种情况工业级编译器里常见的解法是“优先级/结合性消解”——把下一层决策权交给语法分析器之外的手写逻辑。但在纯 LL(1) 框架内标准解法是提取左因子S - if E then S S S - else S | ε S - id : E提取后S 的存在让else成为 FOLLOW(S) 的内容填表时M[S, else]填S - else SM[S, $]和M[S, )]如果 FOLLOW 里有这些填S - ε冲突消失。值得注意的是“else 悬挂”问题在 LL(1) 文法中通过这个 ε 产生式被天然解决为“就近匹配”这跟运算符优先级文法里的处理策略完全不同。考试和面试里经常拿这个例子考人值得多回味。8.2 空表项与同步设计即使 LL(1) 文法建出的表里不可能出现冲突但空表项是必然存在的。空表项对应“当前非终结符和当前输入符号没有任何合法关系”此时分析器必须做错误恢复。最简单的大学生实验做法是“报错就停”但真要做个像样的工具一般用“恐慌模式”panic mode恢复当查表失败时不断跳过输入标记直到栈顶元素与当前输入匹配或者某个非终结符对当前输入有合法表项。要选一个合适的同步标记一般遵循这几个经验法则把 FOLLOW(A) 里的终结符作为 A 的同步 token因为 A 能合法结束的地方A 的某个产生式很可能也能合法出现。把 FIRST(A) 里的终结符也作为同步 token在报错时丢弃栈顶 A但保留输入符号继续往下匹配。遇到$报错时如果栈还没清空直接丢弃栈中剩余部分跳到接受状态。这些恢复策略看起来像是在“宽容”错误输入但在真实编译器里一条错误后恢复继续发现后面更多错误比直接终止编译的用户体验要好得多。LL(1) 表给这个恢复动作提供了非常干净的依据同步集合就是 FOLLOW 集合加 FIRST 集合并不需要额外维护魔法表。8.3 从排错到固化直觉我的一点实践建议我自己的体会是预测分析表的构造这门“手艺”真正牢固不是靠背定义而是靠手推和写代码各来一遍。手推一遍能让你感受到 FIRST 和 FOLLOW 集合之间的传染是怎么层层展开的用自动构造器跑一遍能让你看到冲突是怎么被暴露的以及文法改写如何在表项层面消除这些冲突。两边都做一遍你对 LL(1) 的理解层级会完全不同遇到类似 C 语言if-else、声明与表达式这类文法陷阱时你能直接判断出该提取左因子还是该改写产生式。最后分享一个我在写自动构造器时踩过的坑判断非终结符时不要把单引号开头的符号误判成终结符上面文法里的E、T中如果按“以字母开头”判断非终结符会被当作终结符后面 FIRST 和 FOLLOW 全乱。处理这类符号时最好先把符号表显式定义出来或者用“以开头”之类的强烈约定从根上避免歧义。这个坑虽然小但排查起来特别耗时间记录下来希望对你有帮助。
LL(1)预测分析表全解析：从FIRST/FOLLOW集到自动构造器
1. 为什么是那张表自顶向下语法分析的两个死穴语法分析在编译原理课程链条里的位置各位应该都清楚词法分析把源代码切成 token 流语法分析要把 token 流组织成一棵语法树。自顶向下分析的核心思路是“从开始符号出发反复用产生式右部去替换非终结符直到整棵树的叶子都是终结符”。听起来很直白但真写分析器的时候会撞上两个非常现实的问题。第一个死穴是“选哪条产生式”。语法分析器每读入一个非终结符就要决定下一步到底展开它的哪条候选式。比如有产生式E - E T | T当前要展开 E到底选E T还是选T如果只看文法本身没有额外的信息就只能猜。猜错怎么办得回溯。回溯意味着前面已经读入的 token 要吐回来分析状态要存档恢复整个分析过程的时间复杂度可能指数爆炸工程上完全不可接受。第二个死穴是“左递归”。只要文法里有形如A - Aα这样的产生式自顶向下分析就会陷入死循环为了展开 A先去展开 Aexpand 永远不会向前消耗一个输入符号。这是初学者最常踩的坑很多人看到E - E T第一反应是“这不就是循环展开吗”但机器真的按推导逻辑走的时候连第一步都迈不出去。所以工业界也好课堂教学也罢都会努力把文法做“规整”规整到这两个死穴都消失。规整的结果叫 LL(1) 文法。LL(1) 这个名字拆开是第一个 L 表示从左到右扫描输入第二个 L 表示推导过程产生最左推导括号里的 1 表示分析时只需要向前看一个输入符号就能做决策。“只向前看一个符号”听起来很神奇实际做法就是把决策信息提前算好集中存到一张二维表里——这就是预测分析表。行是非终结符列是终结符外加一个输入结束符$表项是“当前遇到这个输入符号时该用哪条产生式”。一旦这张表构造出来自顶向下的分析就变成了查表和压栈的机械过程。而构造表所需的全部前置材料就是两个集合FIRST 集和 FOLLOW 集。很多人学到这里会觉得头大因为课程里 FIRST、FOLLOW、预测分析表三块内容连在一起讲中间还夹着一堆定义和定理信息量特别大。但换个角度看这套东西就是一个流水线文法进表出。中间每一步都是确定性算法没有玄学。文章下面的内容我按这条流水线的顺序把每一个环节掰开讲清楚最后手把手带你从头到尾推一张完整的表出来。2. FIRST 集推导方向上的“前瞻情报”到底怎么算2.1 FIRST 集中的 FIRST 指什么先定义一下对任意一个文法符号串 αFIRST(α) 是“从 α 出发通过一步或多步推导能出现在串首的所有终结符的集合”。通俗地说我拿到一个产生式右部想知道“这东西将来展开后第一个吐出来的 token 可能是哪些”这个集合就是 FIRST 集。这个集合的用途在填表时非常直接如果我在分析过程中要展开非终结符 A而当前输入符号是 a而 A 恰好存在一条产生式A - α且a ∈ FIRST(α)说明这条产生式可以先吐出一个和当前输入匹配的 token那就应该选它。计算 FIRST 集的顺序十分重要这里我直接给出经过实践验证的完整计算流程宁可啰嗦也要把边界情况照顾到对所有终结符 aFIRST(a) {a}。对所有非终结符 A初始 FIRST(A) ∅。反复扫描所有形如A - X1 X2 ... Xn的产生式做下面的事情令 i 1。把 FIRST(Xi) 中所有非空终结符加入 FIRST(A)。如果ε ∈ FIRST(Xi)继续看下一个符号 X(i1)否则终止对这一条产生式的处理。如果扫描完所有 Xi 都含 ε即 X1...Xn 整体能推导出 ε把 ε 也加入 FIRST(A)。注意第 3 步里“ε 要不要继续往后传染”这个逻辑是整个算法的灵魂。很多资料会写“如果 X1 可以推空则看 X2依此类推”但实际操作时漏掉“传染”或者过度传染都是常见问题。2.2 一个边算边体会的例子光说规则太干我拿一个稍后会反复使用的例子文法先做了消除左因子的预处理走一遍E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id第一步终结符的 FIRST 集不用算FIRST(id) {id}FIRST() {}FIRST() {}FIRST(() {(}FIRST()) {)}。第二步对所有非终结符初始化。然后开始迭代扫描产生式。第一轮扫描处理F - ( E ) | id直接得到 FIRST(F) {(, id}。这俩右部第一个符号都是终结符不需要往后传染。处理T - F T由于 FIRST(F) 现在已经是 {(, id}直接加入 FIRST(T)。处理E - T E同理把 FIRST(T) 的值复制进 FIRST(E)。注意这里 E 的 FIRST 是跟着 T 走的T 的 FIRST 又跟着 F 走。这一轮结束三个集合的值是 FIRST(E) FIRST(T) FIRST(F) {(, id}。第二轮扫描处理E - T E | ε第一条右部第一个符号是终结符所以 FIRST(E) 加入第二条右部就是 ε所以 ε 也加入 FIRST(E)。处理T - * F T | ε同理FIRST(T) {*, ε}。到这里所有集合都稳定了。你发现没有这个文法里的非终结符编号顺序恰好是从 F 到 E一层一层往上推一轮就能算完。但如果文法里存在间接依赖比如A - B...、B - A...这种一轮就不够了必须反复迭代直到所有集合都不再变化。后面写到自动构造器时这个迭代退出条件就是整个程序能不能跑对的关键。2.3 初学者最容易忽略的两种情况第一种是“产生式右部以非终结符开头但该非终结符能推出 ε”。例如A - B c如果ε ∈ FIRST(B)那么 FIRST(A) 除了包含 FIRST(B) 去掉 ε 的部分还必须包含c。很多人算到这里就把c丢了最后表填出来少项查错能查一晚上。我们上面例子里的E - T E不涉及这个问题因为 FIRST(T) 里没有 ε所以直接复制就完事但换成A - B c、B - ε | d这种文法就必须处理“推空后继续往右看”的逻辑。第二种是右部整体可推空。例如S - B CB - εC - ε最后 ε 必须进入 FIRST(S)。epsilon 这个特殊成员在 FOLLOW 集计算里会继续开花结果所以不能嫌麻烦跳过。刚才例子里的E - T E | ε就直接演示了这一点ε 进 FIRST(E) 是下面算 FOLLOW 的必要输入。提示使用“不动点迭代法”算 FIRST 时建议在纸上写一张大表每一轮扫描的所有集合值都记下来。我本科时贪快把多轮合并成一步心算结果算到 FOLLOW 时发现前面某个值该有却没有整张预测分析表全部返工。后来老老实实画表迭代出错概率低了很多。3. 终结符后面跟什么FOLLOW 集的推导与三条核心规则3.1 FOLLOW 集存在的意义FIRST 集只能告诉你“一个符号串开头能有哪些终结符”但在自顶向下分析中还有一类更隐蔽的问题当某个非终结符 A 在推导过程中可以被替换为 ε 时我们实际上会把 A 直接“跳过”那接下来的输入符号必须能和 A 后面出现的终结符对上。这个“A 后面可能紧跟着哪些输入符号”就是 FOLLOW(A) 的定义。FOLLOW 集的另一个关键用途和预测分析表的特殊表项有关当一个非终结符 A 的某条产生式右部能推出 ε就相当于“让 A 消失”这时候要不要继续往下匹配只能靠 FOLLOW(A) 来决定。换句话说FIRST 管的是“该往哪条路走”FOLLOW 管的是“实在没路走的时候哪条路兜底”。FOLLOW 集的计算核心就三条规则我把它们逐个拆开规则一对文法的开始符号 S把输入结束符$放入 FOLLOW(S)。这个$是输入串的哨兵表示“分析已经进行到输入末尾”它必须能对上开始符号的结尾。规则二如果有产生式A - α B β那么 FIRST(β) 中除 ε 之外的所有终结符都要加入 FOLLOW(B)。理由很直观B 后面跟着 ββ 的第一个符号当然可能出现在 B 的后面。规则三如果有产生式A - α B或者A - α B β且ε ∈ FIRST(β)那么 FOLLOW(A) 的所有成员都要加入 FOLLOW(B)。这条规则最容易被无视道理是B 是 A 右部的最后一部分或者 B 后面那一段能推空那么任何能跟在 A 后面的符号也必然能跟在 B 后面。三个规则之间的关系用一个生活化类比可能更好懂A 是“一家公司”FOLLOW(A) 是“这家公司往下一步所有可能的合作方类型”B 是公司里的一个具体部门如果部门 B 参与的项目是公司收尾项目或者项目后面那段会“蒸发”那么公司的合作方也会直接变成这个部门下游的合作方。3.2 继续用表达式文法走 FOLLOW 集沿用上面那个文法我按上面三条规则一步步算因为 E 是开始符号FOLLOW(E) 初始为 {$}。扫描所有产生式找“非终结符后面跟着别的东西”的形态在F - ( E )里E 后面跟着)所以)加入 FOLLOW(E)。在E - T E和T - F T这类产生式里考察每个非终结符后面跟的符号串。处理规则三的部分E - T EE 在右部末尾所以 FOLLOW(E) 的东西全给 FOLLOW(E)。E - T E这一条里T 后面是 E而 FIRST(E) {, ε}ε 在里面所以 FOLLOW(E) 给 FOLLOW(T)又因为 E 也在末尾FOLLOW(E) 再次并入自身。T - F TT 在末尾FOLLOW(T) 给 FOLLOW(T)。T - * F TF 后面是 TFIRST(T) {*, ε}所以*加入 FOLLOW(F)同时 FOLLOW(T) 并入 FOLLOW(F)T 在末尾FOLLOW(T) 并入自身。F - ( E )这里是(和 E 和)的结构E 后面有)以及括号内的递归关系没有其他非终结符处于末尾。完整迭代一轮之后各集合稳定值如下非终结符FOLLOW 集E{$,)}E{$,)}T{,$,)}T{,$,)}F{*, ,$,)}这个结果对不对可以用一个直觉检验表达式文法里一个因子后面要么跟着乘法运算符*要么跟着加法运算符要么是整个表达式结束$要么是右括号结束。完全符合对表达式的认知。这里要特别提醒一个我自己反复踩过的坑FOLLOW 集的计算也必须做不动点迭代而且规则三的传播往往不是一轮就能结束的。比如FOLLOW(E)里的$要传播到FOLLOW(E)FOLLOW(E)再传播到FOLLOW(T)FOLLOW(T)才传播到FOLLOW(F)。这中间跨了四级一轮扫描不可能全部完成。初学者容易犯的毛病是扫描一遍就宣布算完结果表填出来在几个非终结符上缺项找半天找不到原因。4. 预测分析表的填表动作从两个集合到一张二维表4.1 表格结构先行预测分析表 M 是一个二维数组行由所有非终结符构成列由所有终结符加上$构成。每个表项M[A, a]存放的内容要么是一条产生式A - α要么是空表示此处报错。表的规模很容易估算非终结符数量 × 终结符数量 1。表达式文法 5 个非终结符、6 个终结符含$表也就是 5 行 7 列。即使一个文法有三四十个非终结符手工填表虽然累但表依然是可读的这恰恰说明表格方法在可形式化上的优势。4.2 填表算法的完整规则填表的核心算法用自然语言描述就是两步循环但中间有一个细节绝不能漏对文法中的每一条产生式A - α执行以下两步如果 α 不能推出 ε对 FIRST(α) 中的每一个终结符 a把A - α填入M[A, a]。如果 ε ∈ FIRST(α)对 FOLLOW(A) 中的每一个终结符 b记住 FOLLOW 集合里的$也算把A - α填入M[A, b]。如果 b 本身就是$填入M[A, $]如果 BOTHε ∈ FIRST(α)且$ ∈ FOLLOW(A)这条产生式还会占M[A, $]。这里每一步的背后逻辑值得再强调一遍。第一步很好理解α 能吐出一个确定的终结符那输入符号就对该终结符选这条产生式天经地义。第二步稍微绕一点α 能推空意味着展开 A 时可以不消耗任何输入符号直接把 A 从栈顶丢掉此时必须保证当前输入符号是 A 的合法后继也就是 FOLLOW(A) 里的成员。第二步如果漏掉最常见的结果是表里大量M[A, a]空着导致分析器在实际分析时遇到本该“推空继续”的输入符号直接报错。比如表达式文法里E - ε这条产生式就要填到M[E, $]和M[E, )]两个位置。如果你只填了M[E, $]那么分析(idid)这种带括号的输入时到idid)右括号那里E 该推空却找不到表项就会直接报“语法错误”。这种 bug 的特征非常典型简单的idid能过一旦带括号就崩。4.3 冲突检测建表顺带完成的合法性验证如果填表时发现某个表项已经被一条产生式占位又要填进另一条不一样产生式说明这个文法不是 LL(1) 文法。冲突的类型通常有这两种FIRST/FIRST 冲突一个非终结符 A 有两条产生式A - α和A - β但 FIRST(α) 和 FIRST(β) 有交集。典型例子是未经提取左因子的文法S - if E then S | if E then S else S两条右部的 FIRST 都是 {if}填表时M[S, if]就会冲突。FIRST/FOLLOW 冲突一条产生式 α 能推空FIRST(α) 里的某个终结符同时又是 FOLLOW(A) 的成员但这两条产生式又不是同一条。这种冲突比较隐蔽常见于文法的 ε 产生式和普通产生式搅在一起。遇到冲突正确的处理方式不是跳过也不是硬选一个优先级而是回到文法本身去修提取左因子消除 FIRST/FIRST 冲突改写产生式消除 FIRST/FOLLOW 冲突。这一条我在后面完整例子里会实际演示。注意LL(1) 是文法性质不是表性质。表构造过程只是把这个性质显式暴露出来。就算你手工造表时“手动消除冲突”文法的 LL(1) 性也不会因此变好后续扩展或者换工具生成时会再次踩雷。5. 从文法到表一次通关表达式文法完整手工推导5.1 原始文法为什么要先“整形”我们最开始给出的表达式文法其实不是原始形态而是经过两步预处理之后的样子。现在我把预处理步骤补上因为很多读者会问“教材里一开始给的文法就是这种规整形态吗怎么来的”原始表达式文法通常是E - E T | T T - T * F | F F - ( E ) | id这个文法有直接左递归不能用于自顶向下分析。第一步是做消除左递归。以E - E T | T为例它符合A - Aα | β的模式其中 α Tβ T。消除左递归的通用方法是引入新非终结符 AA - β A A - α A | ε代入到 E 和 T 上就得到E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id恰好就是我们前面的文法。这个变形是等价的但会产生一个副作用多出来的 E、T 都有 ε 产生式这正是后面 FIRST/FOLLOW 集计算麻烦的来源。如果原始文法里还有公共前缀比如S - if E then S | if E then S else S还得用提取左因子消除 FIRST 冲突这里暂时不展开但考试和面试里经常会和左递归消除一起考。5.2 现在把两个集合和一张表完整落纸前面 2.2 和 3.2 两节已经把 FIRST 和 FOLLOW 都算完了汇总一下非终结符FIRSTFOLLOWE{(, id}{$,)}E{, ε}{$,)}T{(, id}{,$,)}T{*, ε}{,$,)}F{(, id}{*, ,$,)}现在对每一条产生式做填表操作。我把过程逐条列出来方便对表E - T EFIRST(T E) FIRST(T) {(, id}不含 ε。填入M[E, (]和M[E, id]表项都是E - T E。E - T EFIRST(右部) {}。填入M[E, ]。E - ε右部能推空看 FOLLOW(E) {$,)}。填入M[E, $]和M[E, )]表项都是E - ε。T - F TFIRST(F T) FIRST(F) {(, id}。填入M[T, (]和M[T, id]。T - * F TFIRST(右部) {*}。填入M[T, *]。T - ε看 FOLLOW(T) {,$,)}。填入M[T, ]、M[T, $]、M[T, )]。F - ( E )FIRST(右部) {(}。填入M[F, (]。F - idFIRST(右部) {id}。填入M[F, id]。最终表格如下非终结符id*()$EE → T EE → T EEE → T EE → εE → εTT → F TT → F TTT → εT → * F TT → εT → εFF → idF → ( E )这张表有非常明显的规律E 和 T 只在两个“操作数起点”上有产生式E 在上递推、在)和$上收尾T 同理。这个规律可以帮助你做结果的自检如果填出来的表在某个终结符列上所有格都空着就要回头检查这个终结符是不是从来不会出现在合法输入中如果某个非终结符整行都空则这个非终结符不可达文法设计有问题。到这里LL(1) 预测分析表的构造全流程就被走完了文法变形 → FIRST 集 → FOLLOW 集 → 二维表填表。手工流程至此完整闭环。6. 表建好以后怎么用预测分析算法的驱动逻辑很多教程讲到表构造完就停了但一张表只是“词典”分析器才是用词典造句的人。只有看到表被用起来你才能真正理解为什么前面所有步骤是必要设计。预测分析算法的核心数据结构就是一个分析栈栈里先压入结束符$和开始符号。伪代码如下栈: [$, E] 输入串: id id * id $ 当前符号 输入串头 while 栈非空: X 栈顶 if X 当前符号: 弹栈 前进一个输入符号 elif X 是终结符: 报错不匹配 elif M[X, 当前符号] 是空: 报错无对应产生式 else: 取产生式 X - Y1 Y2 ... Yk 弹栈 将 Yk, ..., Y1 逆序压栈分析器每做一次“查表展开”实际上就是在执行一次最左推导栈顶内容就是当前推导中尚未匹配的剩余符号串。所以整个分析过程可以边分析边输出产生式序号这套序号序列就叫最左推导序列。拿上面的表达式文法分析输入串id id * id栈的变化是初始栈 [$, E]输入id id * id $查表 M[E, id] E - T E压栈后栈变为 [$, E, T]注意逆序压栈后 T 在顶。栈顶 T查表 M[T, id] T - F T栈变为 [$, E, T, F]。栈顶 F查表 M[F, id] F - id栈变为 [$, E, T, id]。栈顶id和当前输入符号id匹配弹栈并读入下一个符号。栈顶 T查表 M[T, ] T - ε弹栈不读入。栈顶 E查表 M[E, ] E - T E栈变为 [$, E, T, ]。继续匹配最终栈清空时输入恰好读完整个输出产生式序列就是一棵语法树的先序遍历顺序。这个序列验证了一个关键结论LL(1) 分析本质上就是“用栈模拟最左推导”。表是静态的栈是动态的两者配合把整棵语法树一点点“长”出来。关于压栈顺序有个小细节值得提一下。产生式右部如果从左到右是Y1 Y2 ... Yk那么分析时需要先展开的是左边的Y1所以入栈顺序必须反过来最后压Y1让它待在栈顶。这个细节我见过不少人在程序里写反结果分析第一步就弹出右部最右侧的符号整个推导完全错位查错时又很难看出来因为不是立刻崩溃而是过几步才乱。7. 自动构造器落地把手工流程写成可复用代码7.1 数据结构怎么设计最顺拿 Python 为例文法存储通常直接用字典最方便key 是非终结符value 是该非终结符对应的产生式右部字符串列表。比如E - T E | T就存成{E: [T E\, T]}。终结符判断可以用一个简单的条件不是非终结符且不等于 ε 的符号就是终结符。FIRST 集可以用defaultdict(set)存储。迭代算法中最关键的部分是非终结符“能不能推出 ε”的判断这个属性在计算 FIRST 时反复用到建议单独缓存成一个can_derive_epsilon布尔字典避免每次重复扫描产生式。FOLLOW 集的存储同样用defaultdict(set)但初始化和迭代顺序要小心。初始化时只有开始符号的集合里有$。迭代时每次往集合里加元素都记录一下“本次有没有新增”没有新增就退出循环。7.2 核心代码骨架下面的代码不是完整工程而是把最核心的迭代逻辑单独抽出来方便理解也方便改成其他语言from collections import defaultdict terminals {(, ), , *, id} nonterminals {E, E\, T, T\, F} start E eps ε productions { E: [T E\], E\: [ T E\, eps], T: [F T\], T\: [* F T\, eps], F: [( E ), id], } first defaultdict(set) # 终结符初始化 for t in terminals: first[t] {t} changed True while changed: changed False for A, rhss in productions.items(): for rhs in rhss: symbols rhs.split() # 对右部符号逐个分析处理 ε 传染 all_derive_eps True for sym in symbols: if sym eps: first[sym] {eps} before len(first[A]) if sym in terminals: first[A].add(sym) break else: # 非终结符去掉 ε 后并入 first[A].update(first[sym] - {eps}) if eps not in first[sym]: break # 如果含 ε继续看下一个符号 after len(first[A]) if after before: changed True else: # 右部所有符号都能推空 if eps not in first[A]: first[A].add(eps) changed True这个循环看起来简单但里面隐含了好几个容易写错的地方。一是update(first[sym] - {eps})这个减集操作不能省因为 FIRST(A) 里能不能放 ε 是由“整个右部是否都能推空”决定的不是由右部开头非终结符是否含 ε 决定的。二是break和for...else的配合如果右部中间某个符号不含 ε循环直接 break否则完整跑完 for-else把 ε 加入 FIRST(A)。FOLLOW 集的迭代代码核心是三条规则。第三条规则实现的时候判断“B 是否在右部末尾”用pos len(symbols) - 1判断“B 后面的符号串整体能否推出 ε”则依赖一个辅助函数derives_epsilon_seqdef payload_can_derive_epsilon(symbols): return all(sym eps or (sym in first and eps in first[sym]) for sym in symbols) follow defaultdict(set) follow[start].add($) changed True while changed: changed False for A, rhss in productions.items(): for rhs in rhss: symbols rhs.split() for i, B in enumerate(symbols): if B not in nonterminals: continue # 规则二B 后面的 FIRST去掉 ε after symbols[i1:] if after: for sym in after: if sym in terminals: follow[B].add(sym) break else: follow[B].update(first[sym] - {eps}) if eps not in first[sym]: break if payload_can_derive_epsilon(after): before len(follow[B]) follow[B].update(follow[A]) if len(follow[B]) before: changed True else: # 规则三B 在末尾 before len(follow[B]) follow[B].update(follow[A]) if len(follow[B]) before: changed True这段代码的复杂度里最容易出问题的还是after为空时直接走规则三和after非空但整体能推空时也要走规则三这两条路径。很多人只写了after为空的情况漏了“整体能推空”的情况导致 FOLLOW 集少传一层。填表部分反而最简单两重循环直接照抄前面手工流程table {} for A, rhss in productions.items(): for rhs in rhss: symbols rhs.split() if rhs eps: keys follow[A] else: # 使用 FIRST(右部)这里用一个递归函数/迭代计算 first_rhs compute_first_of_sequence(symbols, first, eps) keys first_rhs - {eps} if eps in first_rhs: keys | follow[A] for key in keys: if (A, key) in table: raise Exception(f冲突: M[{A}, {key}] 已有 {table[(A, key)]}又想填入 {rhs}) table[(A, key)] rhs当rhs eps时直接把 FOLLOW(A) 当作待填符号集合否则把 FIRST(右部) 放入表项。如果 FIRST(右部) 含 ε还需要额外把 FOLLOW(A) 也放进来。这一步实现时要注意集合操作不要原地修改了first_rhs本身用set复制或者先 copy 再 update否则下一轮循环数据会被污染。7.3 用自动构造器验证前面的手工结果跑一遍上面的代码输出的表项和我们在第 5 节手工填出来的表格完全一致。这才是“梭哈”完手工与自动验证后的体验当你手推一遍、代码自动出一遍两边对上了这个知识点才真正算彻底吃透。从工程角度这个自动构造器稍加改造就能处理更大的语法文法从输入的 grammar 文件读出产生式、自动检测终结符和非终结符、输出冲突报告、生成分析表。很多课程实验的“LL(1) 分析器”项目本质上就是把上面三段代码串起来再加一个驱动分析主循环和输入 token 流即可。8. 冲突检测与错误恢复把表从作业变成能用的工具8.1 FIRST/FIRST 冲突的典型形态自己实现自动构造器后第一个常见的实战场景就是跑一个不是 LL(1) 文法的输入观察冲突报告。看一下这个简单的判断语句文法S - if E then S | if E then S else S | id : E两条以if开头的产生式计算 FIRST 右部后都以if在 FIRST 集合中两个表项都会试图填到M[S, if]冲突立刻被报出来。遇到这种情况工业级编译器里常见的解法是“优先级/结合性消解”——把下一层决策权交给语法分析器之外的手写逻辑。但在纯 LL(1) 框架内标准解法是提取左因子S - if E then S S S - else S | ε S - id : E提取后S 的存在让else成为 FOLLOW(S) 的内容填表时M[S, else]填S - else SM[S, $]和M[S, )]如果 FOLLOW 里有这些填S - ε冲突消失。值得注意的是“else 悬挂”问题在 LL(1) 文法中通过这个 ε 产生式被天然解决为“就近匹配”这跟运算符优先级文法里的处理策略完全不同。考试和面试里经常拿这个例子考人值得多回味。8.2 空表项与同步设计即使 LL(1) 文法建出的表里不可能出现冲突但空表项是必然存在的。空表项对应“当前非终结符和当前输入符号没有任何合法关系”此时分析器必须做错误恢复。最简单的大学生实验做法是“报错就停”但真要做个像样的工具一般用“恐慌模式”panic mode恢复当查表失败时不断跳过输入标记直到栈顶元素与当前输入匹配或者某个非终结符对当前输入有合法表项。要选一个合适的同步标记一般遵循这几个经验法则把 FOLLOW(A) 里的终结符作为 A 的同步 token因为 A 能合法结束的地方A 的某个产生式很可能也能合法出现。把 FIRST(A) 里的终结符也作为同步 token在报错时丢弃栈顶 A但保留输入符号继续往下匹配。遇到$报错时如果栈还没清空直接丢弃栈中剩余部分跳到接受状态。这些恢复策略看起来像是在“宽容”错误输入但在真实编译器里一条错误后恢复继续发现后面更多错误比直接终止编译的用户体验要好得多。LL(1) 表给这个恢复动作提供了非常干净的依据同步集合就是 FOLLOW 集合加 FIRST 集合并不需要额外维护魔法表。8.3 从排错到固化直觉我的一点实践建议我自己的体会是预测分析表的构造这门“手艺”真正牢固不是靠背定义而是靠手推和写代码各来一遍。手推一遍能让你感受到 FIRST 和 FOLLOW 集合之间的传染是怎么层层展开的用自动构造器跑一遍能让你看到冲突是怎么被暴露的以及文法改写如何在表项层面消除这些冲突。两边都做一遍你对 LL(1) 的理解层级会完全不同遇到类似 C 语言if-else、声明与表达式这类文法陷阱时你能直接判断出该提取左因子还是该改写产生式。最后分享一个我在写自动构造器时踩过的坑判断非终结符时不要把单引号开头的符号误判成终结符上面文法里的E、T中如果按“以字母开头”判断非终结符会被当作终结符后面 FIRST 和 FOLLOW 全乱。处理这类符号时最好先把符号表显式定义出来或者用“以开头”之类的强烈约定从根上避免歧义。这个坑虽然小但排查起来特别耗时间记录下来希望对你有帮助。
