凡是学过编译原理的人碰到LL(1)预测分析表基本都要被折腾几天。这个东西课本上讲起来特别工整先求FIRST集、再求FOLLOW集、最后填表一副完全机械化的样子但真轮到自己动手做实验、做课程设计或者想手写一个递归下降解析器的时候才发现到处都是坑FIRST集怎么求才算对FOLLOW集什么时候要加ε表填完了出现冲突怎么排查很多问题不是“记住规则”就能解决的而是得真刀真枪算过一遍、填过一遍之后才明白。这篇文章我就拿一个最经典的表达式文法从文法改造、FIRST/FOLLOW集计算到预测分析表逐格填充完整走一遍流程。同时把填表规则背后的原理、常见冲突的排查思路以及我在实际手工构造过程中踩过的坑一并写出来。适合正在上编译原理课的学生、准备面试的开发者以及想自己写一个语法分析器但不想直接用工具的人。1. LL(1)到底是什么一张表解决“下一步怎么走”很多同学一上来就背定义LL(1)中的第一个L表示从左到右扫描输入串第二个L表示产生最左推导1表示每次决策只看一个向前看符号。这个定义背起来简单但跟预测分析表有什么关系我换个方式说你马上就理解了。LL(1)分析的过程可以想象成你在迷宫里走路当前你站在某个路口栈顶的非终结符面前有几条岔路多个候选产生式。问题是你只能往前看一步向前看一个终结符然后必须立刻决定走哪条路。预测分析表M[A, a]就是这张路标告诉你当栈顶是非终结符A、当前输入符号是a的时候应该选择A的哪个产生式来展开。剩下的格子如果没填任何产生式就说明这条路走不通输入串串不属于这个文法。本质上预测分析表就是“决策函数”的查表实现而FIRST集和FOLLOW集就是构造这个决策函数的原材料。LL(1)能工作的前提是整个表不能有“一个格子多条产生式”的情况也就是不能有冲突。只要有冲突就说明一个展望符号不足以确定下一步动作这样自顶向下、逐符号预测就会有二义性程序就无法可靠地做决定。所以LL(1)文法的判定其实就是在问这张表构造出来之后有没有冲突搞清楚LL(1)的定位很重要。它不是编译中唯一的方法但却是最容易手写、最容易理解递归下降解析原理的起点。很多工业级解析器比如ANTLR早期版本都基于LL(1)思想的扩展而预测分析表正是理解整个体系的最佳切入口。1.1 LL(1)分析的两种形态表驱动和递归下降LL(1)分析在实现上有两种主流形态。第一种是表驱动分析也就是用一个二维数组存储M[A, a]再用一个显式的栈配合分析表做推导第二种是递归下降分析把每个非终结符写成一个函数函数体内部根据当前输入符号调用相应的候选分支。表驱动直观安全性高但运行时有查表开销递归下降代码效率高、调试方便但本质上是把预测分析表“熔”进了代码逻辑里。不管哪种形态构造分析表的思想都是同一个。理解了表驱动递归下降就顺理成章反过来如果你先掌握了递归下降的原理再看表驱动也会觉得很自然。1.2 为什么非要有FIRST和FOLLOWLL(1)分析的核心问题就一个给定非终结符A和当前输入符号a我们应该选择A的哪个产生式如果A的某个候选产生式能推出的串是以a开头的那显然应该选它。这就需要FIRST集FIRST(A)就是A能推导出的所有终结符串的“首终结符”集合。只要a属于某个候选产生式的FIRST集这个候选就有资格被选中。但如果某个候选产生式能推导出空串ε情况就不同了既然它能推出空那当前符号a就不一定由它“产出”而可能是由A后面的符号产出。这时候就得看FOLLOW(A)——在所有句型中紧跟在A后面的终结符有哪些。如果a属于FOLLOW(A)说明A可以在这里默默消失把位置让给后面的符号。这就是FOLLOW集的用途。所以说白了FIRST集解决“哪个候选开头的符号能匹配当前输入”FOLLOW集解决“哪个候选可以推导为空并且不影响后面匹配”。没有这两套集合填表规则就无从谈起。2. 动手前的必修课文法改造很多同学拿到一个文法就急着求FIRST、FOLLOW结果算到一半发现表里一堆冲突又回头改文法白白浪费大量时间。我的经验是构造预测分析表之前必须先保证文法具备LL(1)的“候选条件”也就是没有左递归、没有公共前缀导致的左公因子问题、并且消除掉明显的二义性。这几项不处理后面再怎么精算FIRST和FOLLOW表都是碎的。2.1 消除左递归直接左递归的公式化处理一个文法如果存在形如 A → A α 的直接左递归或者通过多个非终结符传递形成的间接左递归LL(1)立刻就没法用因为在处理A时还没读入任何终结符就要先递归展开A根本停不下来。消除直接左递归有固定套路对于产生式 A → A α | β其中β不以A开头可以改写为A → β A A → α A | ε每一步都引入一个新非终结符A来“承接”递归部分把左递归转成右递归。右递归是允许的因为它在展开时总是先消耗一个β打底的终结符从而让决策可以推进。间接左递归稍微复杂一点需要先对非终结符排序逐一把间接递归替换成直接递归再套上面的公式。这个过程虽然机械但绝对不能省因为只要存在左递归FIRST集算起来也会出现循环依赖。2.2 提取左公因子两个候选产生式有相同的前缀比如 S → if E then S | if E then S else S在填表时这两个产生式会落到同一个格子里因为它们的FIRST集有重叠部分。解决方法就是提取公共因子。把 S → α β1 | α β2 改写为S → α S S → β1 | β2这和代数里的提公因式完全一个思路。注意提取之后新的S可能还是不满足LL(1)条件需要继续检查甚至可能要递归提取。提取左公因子能消除一部分冲突但它并不能消除所有二义性这一点决策前要有心理准备。2.3 一个经典的反面教材如果你拿一个没有消除左递归也没有提取左公因子的表达式文法直接构造分析表比如 E → E T | T你会发现M[E, id]这个格子里两套产生式的FIRST集都是{(, id}二选一根本选不出来。这就是冲突的来源。所以构造LL(1)预测分析表本质上不是在“算表”而是在“验证文法是否合格”。把文法改造这一步做得足够干净后面才会顺。3. FIRST集和FOLLOW集规则、推导和避坑点在具体动手之前我把FIRST集和FOLLOW集的计算规则完整过一遍然后用例子带大家一遍遍推。规则本身不难难的是搞清楚每条规则为什么存在。3.1 FIRST集计算规则详解FIRST集是一个符号串能推导出的所有终结符的集合包括可能的ε。对于单个符号X如果X是终结符FIRST(X) {X}。如果X是非终结符则看X的所有产生式X → Y1Y2...Yk。先看Y1的FIRST集把它加入FIRST(X)如果Y1能推出ε再看Y2依次类推直到碰到一个不能推出ε的符号或者所有Yi都能推出ε。如果所有Yi都能推出ε说明整条产生式右侧能推出ε所以ε也加入FIRST(X)。这里的“符号串能推出ε”的判断是很多人容易犯错的地方。比如 X → Y Z只有Y和Z都能推出ε时X才能推出ε。只要中途碰到一个不能推出ε的符号后面的符号即使能推出ε也不影响整个串不能推出空。对于候选产生式 α Y1Y2...Yk 求FIRST(α)规则是一样的依次把FIRST(Yi)ε除外加入FIRST(α)第一个不能推出ε的Yi之后的符号不再考虑如果所有Yi都能推出ε则把ε也加入FIRST(α)。我给个建议先列出哪些非终结符能推出ε再按依赖顺序求FIRST集能大幅减少重复计算。比如T能推出εE能推出εE、T、F都不能推出ε。做FIRST集前先把ε关系表列出来后面每一步都有底气。3.2 FOLLOW集计算规则详解FOLLOW集是针对非终结符定义的表示在句型中可以紧跟在它后面的终结符集合。注意FOLLOW集永远不包含ε因为“后面没有符号”这种情况由结束符$来表示而$在LL(1)分析中会被当作特殊的输入结束标志。FOLLOW集的计算规则把$加入FOLLOW(S)其中S是开始符号。对形如 A → α B β 的产生式如果β不是空串那么FIRST(β)中的所有终结符ε除外都加入FOLLOW(B)。对形如 A → α B 的产生式或者 A → α B β 且 β ⇒* ε那么FOLLOW(A)的全部内容都加入FOLLOW(B)。这条规则也可以合并理解B后面跟着β所以β能开头的那些终结符都是B的FOLLOW如果β能推空那B后面实际上接的是A后面的内容所以FOLLOW(A)里的元素也都是B的FOLLOW。FOLLOW集的计算需要反复扫描所有产生式直到没有任何集合发生变化为止。手工计算时可以按依赖顺序做两三轮第一轮先把容易确定的填上第二轮再补充通常就能收敛。这里有一个初学者普遍困惑的地方为什么A → α B β且β能推出ε时要把FOLLOW(A)也加入FOLLOW(B)因为B在产生式中出现后β被推成空于是B就“暴露”在A的位置上A后面跟什么B后面也跟着能跟什么。逻辑上是对称的。3.3 FOLLOW集不能有ε的思想实验为了彻底理解FOLLOW集不含ε可以做一个思想实验。文法 S → AA → a | ε。求FOLLOW(A)时由规则FOLLOW(S)的内容要加入FOLLOW(A)FOLLOW(S)是{$}所以FOLLOW(A) {$}。那ε为什么不在里面因为A推导为空的时候它的“后面”其实还是S的后面也就是$。ε在这里表示“A自己消失了”而FOLLOW集问的是“A还存在时它后面允许跟什么”一旦A消失你看到的是A后面的东西而不是ε本身。把ε塞进FOLLOW集唯一的作用就是把问题搞乱。这个坎想通了基本就没什么会绊住你了。4. 预测分析表构造的核心规则有了FIRST集和FOLLOW集就可以进入正题填表。填表规则课本上通常写四条看起来很干但几乎每个字都对应一个分析中会遇到的决策场景。4.1 填表规则的另一种记忆方式设当前非终结符为A候选产生式为A → α当前输入符号为a。如果a ∈ FIRST(α)在M[A, a]填A → α。如果α ⇒* ε且a ∈ FOLLOW(A)在M[A, a]填A → α。如果α ⇒* ε且a $在M[A, $]填A → α。其余情况M[A, a]为空表示出错。第1条好理解候选串开头能匹配a就选它。第2、3条是空候选的情况产生式能推导为空而这里确实需要它为空所以填表。仔细观察就会发现第3条其实是第2条的特例因为$本身就包含在FOLLOW(A)里——我们一开始就把$放进了FOLLOW(开始符号)。所以我把这四条简化成两条心法候选串的首终结符集合包含a就选它候选串能推空且FOLLOW(A)包含a或a就是$也选它。心法记住后再看表里每个格子你就不会只看到一堆产生式而是能看到“这条路能从候选串的首符号方向到达当前输入符号或者能通过清空自己让路给后面的合法符号”。理解到这一层LL(1)预测分析表就不再是一张死表而是一张活的决策路径图。4.2 空候选为什么这么特殊关于ε那条规则我想多说几句。在实际手工填表时空候选往往是处理起来最绕的因为它不按“FIRST”走而是按“FOLLOW”走。一个非终结符如果有多个候选其中一个候选是ε那它的FIRST集和FOLLOW集很可能“分摊”不同的列。比如E → TE | ε前者FIRST集是{}后者的适用条件是FOLLOW(E)里的、或$。于是在表里E只在这一列用产生式展开而在)和$这两列直接把E弹出栈。这就是“E可以消失”的具体体现。没有把这条规则理解透的人最常见的错误就是在E的FIRST集里看到ε就把产生式E → ε填到M[E, id]这样的格子里。这完全错了因为id不在FOLLOW(E)里如果输入是id开头E消失了谁来匹配id逻辑上根本说不通。希望读到这里的读者不要再踩这个坑。5. 完整实操从经典文法到最终分析表光讲规则还是不够。接下来我们完整吃透一个经典文法从消除左递归开始一直做到分析表填出来再用表去实际分析一个输入串。这套流程每一步我都会详细解释并且标出值得注意的小地方。这个例子我会做得很细因为只要真正从头到尾推一遍其他文法基本都是依葫芦画瓢。5.1 文法改造全过程原始文法为E → E T | T T → T * F | F F → (E) | id这个文法直接求FIRST集就会遇到E → E T这种左递归。按环境规则先处理EE → T E E → T E | ε再处理TT → F T T → * F T | εF的产生式已经是基本形式保留。最终文法为1. E → T E 2. E → T E | ε 3. T → F T 4. T → * F T | ε 5. F → ( E ) | id经过这个改造文法从“人类看着顺眼”变成了“分析器能做决定”的形态。这里要注意改造前后生成的串是完全一样的只是推导过程从“递归嵌套”变成了“一层层展开”。5.2 逐步计算FIRST集先判断哪些非终结符能推出εE能产生式E → εT能产生式T → εE、T、F不能。然后从最底层的F开始求FIRST(F) {(, id}因为F → (E)以(开头F → id以id开头。FIRST(T) FIRST(F) {(, id}因为T → F T。FIRST(E) FIRST(T) {(, id}因为E → T E。FIRST(E) {, ε}因为E → T E的FIRST含有E → ε把ε加入。FIRST(T) {*, ε}同理。这里有个依赖次序问题求E的FIRST集时T已经算出来所以可以直接取而T的FIRST又取决于F因此F要先求。如果你从E开始求反而会产生循环。所以我的习惯是先列关系树E依赖TT依赖FE和T各自独立按这个顺序算一步到位。5.3 逐步计算FOLLOW集计算FOLLOW集之前把$放入FOLLOW(E)E是开始符号。然后按非终结符逐个分析FOLLOW(E)已经放了$。看产生式F → (E)E后面是)所以把)加入FOLLOW(E)。因此FOLLOW(E) {$, )}。FOLLOW(E)看产生式E → T EE在产生式末尾所以FOLLOW(E)的内容全部加入FOLLOW(E)。因此FOLLOW(E) {$, )}。FOLLOW(T)看E → T ET后面是EFIRST(E)去掉ε是{}所以加入FOLLOW(T)。由于E ⇒* εFOLLOW(E)也全部加入FOLLOW(T)。FOLLOW(E)是{$, )}。因此FOLLOW(T) {, $, )}。FOLLOW(T)看T → F TT在末尾所以FOLLOW(T)全部加入FOLLOW(T)。因此FOLLOW(T) {, $, )}。FOLLOW(F)看T → F TF后面是TFIRST(T)去掉ε是{}所以加入FOLLOW(F)。因为T ⇒* εFOLLOW(T)也全部加入FOLLOW(F)集合为{, $, )}。因此FOLLOW(F) {*, , $, )}。FOLLOW集汇总非终结符FOLLOW集E{$, )}E{$, )}T{, $, )}T{, $, )}F{*, , $, )}计算FOLLOW集时最需要注意的是规则“B后面能跟什么”和“B所在产生式左侧非终结符的FOLLOW集”要区分清楚。我在实际练习中发现很多同学在求FOLLOW(F)时容易漏掉第一个产生式之外的内容只看到T → F T和T → *F T但实际上通过FOLLOW(T)传递过来的)和$也都在。多算两遍自然就熟练了。5.4 逐格填充预测分析表现在开始填表。分析表的行为非终结符列为终结符和$。我们按每个非终结符逐行处理。E行M[E, (]看E → T EFIRST(T E) FIRST(T) {(, id}所以填入E → T E。在(这一列填E → T E。M[E, id]同理id也在FIRST(T E)中填入E → T E。其余列留空。E行M[E, ]看E → T EFIRST( T E) {}所以在列填入E → T E。M[E, )]候选E → ε能推空而) ∈ FOLLOW(E)所以在)列填入E → ε。M[E, $]候选E → ε能推空且$ ∈ FOLLOW(E)所以在$列填入E → ε。T行T → F T的FIRST集是{(, id}所以M[T, (]和M[T, id]都填T → F T。T行T → * F T的FIRST是{}所以在列填T → * F T。T → ε能推空FOLLOW(T) {, $, )}所以在、)、$三列都填T → ε。F行F → id 在id列填F → id。F → ( E ) 在(列填F → ( E )。最终得到预测分析表非终结符id*()$EE → T EE → T EEE → T EE → εE → εTT → F TT → F TTT → εT → * F TT → εT → εFF → idF → ( E )看到这个表你最直观的感受应该是没有哪一个格子出现了两条产生式说明这个文法经过改造后是LL(1)文法。表里的空位是出错入口代表输入串在这里不合法。这里的“空位出错”不是运行时才发现而是在分析过程中一旦匹配不到动作就立即终止并报错这就是LL(1)预测分析高效的原因之一不需要回溯错了就报线性时间完成分析。5.5 用分析表实战解析一个输入串表构造完成后我们拿输入串id id * id来走一遍栈式匹配流程。栈一开始是$和开始符号E输入串末尾也放$步骤栈右侧为顶剩余输入流动作1$ Eid id * id $查M[E, id]用E → T E2$ E Tid id * id $查M[T, id]用T → F T3$ E T Fid id * id $查M[F, id]用F → id4$ E T idid id * id $栈顶终结符id匹配输入id弹出5$ E T id * id $查M[T, ]用T → ε6$ E id * id $查M[E, ]用E → T E7$ E T id * id $匹配弹出8$ E Tid * id $查M[T, id]用T → F T9$ E T Fid * id $查M[F, id]用F → id10$ E T idid * id $匹配id弹出11$ E T* id $查M[T, *]用T → * F T12$ E T F ** id $匹配*弹出13$ E T Fid $查M[F, id]用F → id14$ E T idid $匹配id弹出15$ E T$查M[T, $]用T → ε16$ E$查M[E, $]用E → ε17$$匹配$分析成功每一步都严格查表没有一步需要猜测或回溯。这就是预测分析的名字来源整个过程是确定的预测就意味着不回头。把这张表的每一步手推一遍你基本就能自己分析任何符合LL(1)条件的文法了。6. 表冲突判定与高频问题排查构造完表之后还需要再做一道质检工序检查所有格子是否只有一个入口。如果同一对(A, a)出现两个不同的产生式就叫表冲突对应的文法不是LL(1)文法。这一节把冲突的分类、常见错误以及工程实践中的建议一次性讲透。6.1 冲突的两大类型FIRST与FIRST冲突、FIRST与FOLLOW冲突第一种冲突是FIRST与FIRST冲突典型场景是A的两个候选产生式FIRST集有交集。比如S → if E then S | if E then S else S两个候选都从if开始FIRST集重叠填表时M[S, if]就会有两个产生式。这种情况要通过提取左公因子来解决提取后变成S → if E then S SS → else S | ε但注意提取后S在else列依然有可能和后面的产生式冲突实际中需要进一步分析有时候还需要修改文法结构。第二种冲突是FIRST与FOLLOW冲突典型场景是A → α (FIRST含a) 和 A → β (β ⇒* ε且a ∈ FOLLOW(A)) 同时存在导致M[A, a]出现两条。直观解释是相同输入a既可以被α开头匹配也可以通过消去A来让后面跟随a。这种冲突经常出现在二义性文法或者某产生式右侧能“意外吃空”的场景中。解决办法远比提取左公因子复杂可能要改写文法甚至要考虑LL(1)根本处理不了需要改用LL(2)或LR分析。6.2 悬空else问题与LL(1)的天花板最经典的冲突案例是“悬空else”也就是前面提到的if-then-else。这个问题对LL(1)来说几乎是宿敌即使提取了左公因子还是在else分支上难以完全消除冲突。真正能处理这类问题的往往要引入优先级、就近匹配规则或者干脆转向LR族分析器。所以构造LL(1)预测分析表时如果发现文法本身带有二义性不要指望通过细抠FIRST/FOLLOW能“抠”出解法那是死路。遇到明显的二义性文法正确姿势是先修改文法结构或者直接换分析方案。这是不少学校的实验课里最容易让人浪费大量时间的坑一个本身二义的文法怎么算表都是冲突你却以为是自己FIRST或FOLLOW求错了。6.3 手工构造时最常见的五个错误根据我自己的练习和帮人改错的经验手工构造LL(1)分析表时以下五个错误出现频率最高FIRST集里提前填入ε。只有当产生式右侧所有符号都能推导出ε时ε才能加入FIRST集。很多人在第一步就把能推出ε的非终结符的ε放进各种FIRST里导致后面填表全面错乱。FOLLOW集里填了ε。前面详细分析过FOLLOW集定义上就不含ε。如果有人告诉你FOLLOW里也放ε那一定是他记错了或者教错了。忘记给开始符号的FOLLOW加$。这一条在做第二个文法时特别容易漏导致表里$列对不上。问自己一句如果输入串长正好摊到起始符结束$该匹配谁当然是起始符。所以$进FOLLOW(开始符号)是铁的规则。填表时只按FIRST集不管ε候选。一旦候选能推出ε必须额外检查FOLLOW集把FOLLOW里的每一列都填上对应的ε产生式否则就会漏格子导致合法输入被误判出错。用非终结符当列。预测分析表的列必须是终结符和$有人把非终结符也当成列来填在概念上就混乱了。firm记住表是M[非终结符, 终结符] → 产生式。6.4 这一算法在工程实践里的落位预测分析表在理论学习中占重要位置但在实际工程里编译器很少直接拿这种表去跑语法分析。原因主要是LL(1)对语法的限制太严格工业语言的语法要让LL(1)老老实实工作往往需要大幅改造文法。更普遍的做法是手动编写递归下降解析器本质上参考了LL(1)的思想但允许在少数地方做多符号预读甚至回溯以换取更好的可读性和可维护性。ANTLR、手写的JSON或SQL解析器大多走的是这个路线。但话说回来如果不先弄懂预测分析表你就很难理解递归下降里那些if分支到底在查什么“表”。这张表是理解自顶向下分析家族的钥匙也是面试时考察编译原理硬实力的核心考点。最后再分享一个小技巧手工填表做熟了以后可以自己写个小脚本来自动化FIRST、FOLLOW生成和填表用Python写起来不复杂核心就是集合运算和迭代收敛。代码跑出来的结果能反过来验证手工算的结果遇到复杂文法时特别有帮助。我就是靠这个办法在期末实验里熬过来的如果对自动化构造有兴趣这个方向可以深入玩一玩对理解不动点迭代也很有好处。