语法分析：从FIRST/FOLLOW集到预测分析表的完整实战指南)
1. 项目概述为什么我们需要LL(1)分析法如果你写过简单的表达式解析器或者尝试过自己定义一种小型的配置文件格式你大概率会遇到一个头疼的问题如何让程序“读懂”你写的文本比如面对一行a 3 5 * b程序怎么知道先算乘法再算加法这就是语法分析要解决的核心问题。在众多语法分析方法中LL(1)分析法因其清晰的逻辑和相对简单的实现成为了入门编译原理、理解“自顶向下”分析思想的绝佳起点。它不像LR分析那样需要构造复杂的状态机也不像递归下降那样容易陷入左递归的陷阱而需要手动改造文法。LL(1)提供了一套基于预测分析表的、机械化的流程让你能像查字典一样根据当前输入符号和栈顶状态决定下一步该做什么。简单来说LL(1)分析法就是一个“向前看一个符号”的语法分析器。第一个“L”表示从左向右扫描输入串第二个“L”表示产生最左推导而“(1)”则表示在分析过程中只需要向前查看一个输入符号就能确定该选用哪条产生式。它的价值在于它将语法分析这个抽象过程转化为了填充和查表预测分析表的具体操作极大地降低了理解门槛。对于学习者而言通过手动计算FIRST集、FOLLOW集再到构造预测分析表最后驱动分析栈进行推导这一整套流程走下来你对文法二义性、左递归、回溯等概念的理解会异常深刻。这不仅是应付考试更是为你日后设计领域特定语言、编写配置文件解析器甚至理解IDE的语法高亮和错误提示打下坚实的基础。2. 核心概念拆解FIRST集与FOLLOW集的计算逻辑在动手构造预测分析表之前我们必须先打好两个地基FIRST集和FOLLOW集。它们是LL(1)文法的“预言”工具决定了在某个位置我们可能看到或期望看到什么符号。2.1 FIRST集一个符号串可能打头的终结符集合FIRST(α) 定义为能从符号串 α 推导出的所有终结符号串的第一个终结符的集合。如果 α 可以推导出空串 ε那么 ε 也属于 FIRST(α)。计算FIRST集遵循一套迭代规则我习惯用手工推导的方式来理解这比死记硬背公式有效得多。核心规则有三条对于终结符 aFIRST(a) { a }。这是最直接的。对于非终结符 A及其产生式 A - X1 X2 ... Xk将 FIRST(X1) 中除了 ε的所有元素加入 FIRST(A)。如果 ε 在 FIRST(X1) 中则继续查看 FIRST(X2)将其非 ε 元素加入 FIRST(A)。重复此过程直到某个 Xi 的 FIRST 集不包含 ε或者所有 k 个符号的 FIRST 集都包含 ε此时将 ε 加入 FIRST(A)。对于符号串 α Y1 Y2 ... Yn计算 FIRST(α) 的过程类似于规则2。从 FIRST(Y1) 开始加入非 ε 元素如果包含 ε 则继续看 Y2以此类推。如果所有 Yi 都能推出 ε则将 ε 加入 FIRST(α)。注意计算时务必反复迭代直到所有非终结符的FIRST集不再变化。通常需要多轮扫描所有产生式。让我们通过一个经典例题来固化理解 考虑文法 GE - T EE - T E | εT - F TT - * F T | εF - ( E ) | id这是一个消除左递归和提取左因子后的表达式文法。我们来计算FIRST集FIRST(F)看产生式5。F - ( E )第一个符号是终结符(所以 FIRST(F) 包含(F - id第一个符号是终结符id所以包含id。故FIRST(F) { (, id }。FIRST(T)看产生式4。T - * F T第一个符号是*包含*T - ε包含ε。故FIRST(T) { *, ε }。FIRST(T)看产生式3。T - F T因此我们需要 FIRST(F T)。FIRST(F) { (, id }且其中不含 ε所以 FIRST(T) FIRST(F) { (, id }。注意这里不需要考虑T因为F的FIRST集不含ε推导路径在F处就确定了。FIRST(E)看产生式2。E - T E第一个符号是包含E - ε包含ε。故FIRST(E) { , ε }。FIRST(E)看产生式1。E - T E因此需要 FIRST(T E)。FIRST(T) { (, id }不含 ε所以 FIRST(E) FIRST(T) { (, id }。实操心得在计算A - B C D这类产生式时判断是否要继续看后面的符号C、D唯一标准就是看前面符号的FIRST集是否包含 ε。包含就继续不包含就停止。这个判断在后续构造预测分析表时至关重要。2.2 FOLLOW集可能跟在某个非终结符后面的终结符集合FOLLOW(A) 定义为在所有规范句型可以理解为最右推导过程中产生的句型中能够直接出现在非终结符 A之后的终结符的集合。如果 A 可以是某个句型的最后一个符号那么句子结束符$也属于 FOLLOW(A)。计算FOLLOW集的规则更强调“上下文”和“传递”对于开始符号 S将$加入 FOLLOW(S)。$是输入串的结束标记。对于产生式 A - α B β将 FIRST(β) 中除了 ε的所有元素加入 FOLLOW(B)。对于产生式 A - α B 或 A - α B β 且 β 可以推出 ε将 FOLLOW(A) 中的所有元素加入 FOLLOW(B)。这条规则是难点它意味着“B后面可能跟着的就是A后面该跟着的东西”。注意FOLLOW集只针对非终结符。计算时必须反复应用规则直到所有FOLLOW集不再变化。通常从开始符号开始遍历所有产生式多轮。继续上面的例题计算FOLLOW集 首先E是开始符号规则1FOLLOW(E) { $ }。 然后我们遍历所有产生式产生式1E - T E对应规则A-αBβ这里 AE, α空, BT, βE。规则2FIRST(β) FIRST(E) { , ε }。将非 ε 元素加入FOLLOW(T)。所以 FOLLOW(T) 现在有。规则3因为 β (E) 可以推出 ε所以还要将 FOLLOW(A) 即 FOLLOW(E) 加入 FOLLOW(B) 即 FOLLOW(T)。所以将$加入FOLLOW(T)。同时这个产生式也符合A-αB形式B是E‘所以将 FOLLOW(E) 加入 FOLLOW(E’)。将$加入FOLLOW(E)。产生式2E - T E对应A-αBβAE, α, BT, βE。规则2FIRST(β)FIRST(E){, ε}。将加入FOLLOW(T)已存在。规则3β (E) 可推出 ε所以将 FOLLOW(A) 即 FOLLOW(E) 加入 FOLLOW(B) 即 FOLLOW(T)。目前 FOLLOW(E) 有$所以将$加入 FOLLOW(T)已存在。同时这也符合A-αBB是E‘所以将 FOLLOW(E) 加入 FOLLOW(E) 自身递归但不会增加新元素。产生式3T - F T对应A-αBβAT, α空, BF, βT。规则2FIRST(β)FIRST(T){*, ε}。将*加入FOLLOW(F)。规则3β (T) 可推出 ε所以将 FOLLOW(A) 即 FOLLOW(T) 加入 FOLLOW(B) 即 FOLLOW(F)。FOLLOW(T) 目前有 {, $}所以将它们加入FOLLOW(F)。同时这也符合A-αBB是T‘所以将 FOLLOW(T) 加入 FOLLOW(T)。产生式4T - * F T分析类似会将 FIRST(T) 的非 ε 元素即*加入 FOLLOW(F)以及由于T‘可推空将FOLLOW(T’)加入FOLLOW(F)和FOLLOW(T)自身。产生式5F - ( E )这是一个关键。对应A-αBβAF, α(, BE, β)。规则2FIRST(β) FIRST()) {)}。将)加入FOLLOW(E)。这里β是终结符)不能推出ε所以不触发规则3。经过多轮迭代确保所有规则应用后集合稳定我们得到FOLLOW(E) { $, ) }FOLLOW(E) { $ } // 主要来自E-T E和E自身的传递FOLLOW(T) { , $ } // 来自E-T E 和 E-T EFOLLOW(T) { , $ } // 来自T-F T继承了FOLLOW(T)FOLLOW(F) { *, , $ } // 来自T-F T*和FOLLOW(T)以及T-*F T的传递避坑技巧计算FOLLOW集时最容易漏掉的是规则3的传递尤其是产生式右部末尾的非终结符。一个检查方法是如果一个非终结符能出现在产生式右部的最末尾那么它就应该“继承”产生式左部非终结符的FOLLOW集。比如T在T-F T的末尾所以FOLLOW(T)要包含FOLLOW(T)。3. 预测分析表的构造将文法转化为可查的“地图”有了FIRST和FOLLOW集我们就可以构造LL(1)分析的核心——预测分析表M[A, a]。这是一个二维表行是非终结符列是终结符包括结束符$。表项M[A, a]存放着当栈顶是非终结符A当前输入符号是a时应该使用的产生式。如果表项为空则表示语法错误。构造算法 对于文法中的每一条产生式A - α执行以下两步对于FIRST(α)中的每个终结符 a注意a ≠ ε将产生式A - α填入表项M[A, a]。如果ε 在 FIRST(α) 中那么对于FOLLOW(A)中的每个终结符 b包括$将产生式A - α填入表项M[A, b]。关键点第二步是处理可空非终结符的关键。它意味着当A可以推出空且当前输入符号正好是A后面允许出现的符号FOLLOW(A)时我们就选择让A推出空应用A - ε从而“跳过”A继续分析后面的内容。继续我们的例题构造预测分析表 终结符集合{ id, , *, (, ), $ } 非终结符集合{ E, E, T, T, F }我们逐条产生式处理E - T EFIRST(T E) FIRST(T) { (, id }。不含ε。对于终结符(和id在 M[E, (] 和 M[E, id] 中填入E - T E。E - T EFIRST( T E) { }。不含ε。在 M[E, ] 中填入E - T E。E - εFIRST(ε) { ε }。包含ε。FOLLOW(E) { $ }。对于FOLLOW(E)中的终结符$在 M[E, $] 中填入E - ε。注意FOLLOW(E’) 是否包含)我们之前计算 FOLLOW(E) 包含)但 FOLLOW(E’) 不包含。因为)是跟在E后面的而E’在E的后面。在句型中)出现时E‘已经推导完毕通常为空。所以这里不填。T - F TFIRST(F T) FIRST(F) { (, id }。不含ε。在 M[T, (] 和 M[T, id] 中填入T - F T。T - * F TFIRST(* F T) { * }。不含ε。在 M[T, *] 中填入T - * F T。T - εFIRST(ε) { ε }。包含ε。FOLLOW(T) { , $ }。对于终结符和$在 M[T, ] 和 M[T, $] 中填入T - ε。F - ( E )FIRST(( E )) { ( }。不含ε。在 M[F, (] 中填入F - ( E )。F - idFIRST(id) { id }。不含ε。在 M[F, id] 中填入F - id。最终得到的预测分析表如下非终结符id*()$EE - T EE - T EEE - T EE - εTT - F TT - F TTT - εT - * F TT - εFF - idF - ( E )重要检查LL(1)文法要求预测分析表的每个格子至多只有一条产生式。如果同一个格子出现了两条或以上说明文法不是LL(1)的可能存在二义性、需要左递归消除或左因子提取。我们这个表每个格子最多一条所以该文法是LL(1)文法。4. 驱动分析过程模拟栈与输入串的共舞预测分析表是一张地图而分析栈和输入串就是我们的旅行者。分析器通常维护一个栈初始化时将结束符$和文法开始符号压栈$在底开始符号在顶。同时输入串末尾追加$。算法步骤 设X是栈顶符号a是当前输入指针所指的符号。如果X a $分析成功接受输入串。如果X a ≠ $匹配成功将X弹出栈输入指针前移一位。如果X是一个非终结符去查预测分析表M[X, a]。如果M[X, a]中有一条产生式X - Y1 Y2 ... Yk则将X弹出栈并将Yk, ..., Y2, Y1逆序压入栈中保证Y1在栈顶。如果M[X, a]为空则报错输入串不是该文法的句子。让我们用输入串id id * id来完整演练一遍。输入串后加$。 初始化栈[ $, E ]右侧为栈顶 输入缓冲区id id * id $我们用表格记录每一步步骤分析栈剩余输入串动作说明1$ Eid id * id $栈顶E是非终结符查表 M[E, id] 得到E - T E。弹出E将T E逆序压栈先压E再压T。2$ E Tid id * id $栈顶T是非终结符查表 M[T, id] 得到T - F T。弹出T压入T F。3$ E T Fid id * id $栈顶F是非终结符查表 M[F, id] 得到F - id。弹出F压入 id。4$ E T idid id * id $栈顶id是终结符与输入串首id匹配。弹出栈顶id输入指针后移。5$ E T id * id $栈顶T是非终结符查表 M[T, ] 得到T - ε。弹出T压入ε即不压入任何东西相当于只弹出。6$ E id * id $栈顶E是非终结符查表 M[E, ] 得到E - T E。弹出E压入E T 。注意顺序产生式右部是 T E逆序压栈后栈顶是。7$ E T id * id $栈顶是终结符与输入匹配。弹出输入指针后移。8$ E Tid * id $栈顶T是非终结符查表 M[T, id] 得到T - F T。弹出T压入T F。9$ E T Fid * id $栈顶F查表 M[F, id] 得到F - id。弹出F压入id。10$ E T idid * id $栈顶id匹配输入id。弹出id输入指针后移。11$ E T* id $栈顶T查表 M[T, *] 得到T - * F T。弹出T压入T F *。12$ E T F ** id $栈顶*匹配输入*。弹出*输入指针后移。13$ E T Fid $栈顶F查表 M[F, id] 得到F - id。弹出F压入id。14$ E T idid $栈顶id匹配输入id。弹出id输入指针后移。15$ E T$栈顶T查表 M[T, $] 得到T - ε。弹出T。16$ E$栈顶E查表 M[E, $] 得到E - ε。弹出E。17$$栈顶$匹配输入$。分析成功。实操心得在手动模拟时最容易出错的地方是逆序压栈。记住口诀“右部写出来从右往左压”。另外当应用A - ε产生式时操作就是简单地将A弹出栈不要压入任何东西。这个过程清晰地展示了最左推导每一步都是替换当前句型中最左边的非终结符。5. 常见问题与排查技巧实录即使理解了原理在实现或做题时还是会踩坑。下面是我总结的几个典型问题和解决思路。5.1 为什么我的FIRST/FOLLOW集算了几轮还不稳定这通常是因为文法中存在间接左递归或产生式右部以非终结符开头且该非终结符的FIRST集本身还在变化。排查技巧画一张依赖图。以非终结符为节点如果A的产生式右部开头是非终结符B则画一条边 A - B表示计算FIRST(A)需要先知道FIRST(B)。如果图中存在环就需要多轮迭代直到稳定。计算FOLLOW集时依赖更复杂需要FIRST和FOLLOW迭代轮数可能更多。务必手工多迭代两轮并用不同颜色的笔标记每一轮新增的元素直到连续两轮所有集合没有任何变化。5.2 构造预测分析表时什么情况下一个格子会有多条产生式这违反了LL(1)文法的定义通常根源在于文法本身。二义性经典例子是if-else的悬空else问题。文法无法决定else该匹配哪个if。公共左因子未提取例如A - αβ | αγ。对于输入前缀α表项M[A, a]其中a属于FIRST(α)就会冲突。解决方法提取左因子改为A - αAA - β | γ。左递归未消除包括直接左递归A - Aα和间接左递归。左递归会导致分析器陷入无限循环。消除方法是将A - Aα | β改写为A - βAA - αA | ε。FIRST集相交且含空对于某个非终结符A有两条产生式A - α和A - β如果 FIRST(α) ∩ FIRST(β) 非空就会冲突。更隐蔽的是如果 FIRST(α) 和 FIRST(β) 本身不相交但其中一个比如α能推出ε且 FIRST(β) ∩ FOLLOW(A) 非空那么对于FOLLOW(A)中的符号表项M[A, a]也会冲突因为既可以用A - β也可以用A - α推出空来匹配。因此LL(1)文法的严格条件是对于每个非终结符A的任何两个不同产生式其FIRST集不相交且如果其中一个能推出ε则另一个的FIRST集与FOLLOW(A)也不相交。5.3 模拟分析过程时遇到非终结符查表为空怎么办这是语法错误处理的核心。查表为空意味着在当前栈顶非终结符和当前输入符号的组合下预测分析表没有给出可用的产生式。程序应该进入错误处理例程。简单的错误恢复策略可以尝试“恐慌模式”恢复。即跳过输入符号直到遇到一个属于FOLLOW(栈顶非终结符)或FOLLOW(栈中下一个非终结符)的符号然后弹出栈顶非终结符认为它推导为空继续分析。这能保证分析器不会崩溃但可能掩盖后续错误。调试建议手动模拟时遇到空表项首先回查预测分析表构造是否正确再检查输入串是否书写正确比如运算符拼写错误。这是发现文法定义漏洞或输入错误的好机会。5.4 如何从零开始为一个简单语言设计LL(1)文法这是学习的终极目标。我的经验是先写直观文法不要一开始就考虑LL(1)。先用最自然的方式描述语言结构。比如表达式Expr - Expr Term | TermTerm - Term * Factor | FactorFactor - ( Expr ) | id。消除左递归上述文法有左递归直接应用公式消除。变成我们例题中的形式。提取左因子检查是否有形如A - αβ | αγ的产生式进行提取。验证LL(1)条件计算FIRST和FOLLOW集尝试构造预测分析表检查冲突。迭代调整如果发现冲突可能需要重新设计文法结构。有时需要引入新的非终结符来细化层次。这个过程很考验对语言结构的理解。最后我个人的体会是LL(1)分析就像学习骑自行车。原理和步骤FIRST/FOLLOW/预测表是自行车各个部件单独看都懂。但只有亲手计算一遍完整的例题再模拟一遍分析过程把部件组装起来并骑上一段路你才能真正掌握平衡理解各个部分是如何协同工作的。下次当你再看到id id * id这样的字符串时你眼里看到的就不再是字符而是一棵正在被栈和预测表共同构建的语法树。这种透过表象看到结构的能力就是学习编译原理最大的收获之一。
