1. 项目概述从“天书”到“施工图”如果你尝试过手写一个简单的解释器或编译器大概率会在语法分析这一步卡住。面对一堆用巴科斯范式BNF定义的语法规则你可能会感到无从下手——这些规则就像一份抽象的“设计蓝图”告诉你最终的程序结构应该长什么样但没告诉你具体该怎么一步步把它“建造”出来。而预测分析表Predictive Parsing Table就是这份蓝图转化而成的、可被计算机直接执行的“施工进度表”。它明确地指示了语法分析器当你在分析源代码的某个位置并且看到下一个输入符号token时应该选择应用哪一条语法规则或者直接报错。这次要聊的就是如何为一种特殊的文法——LL(1)文法来构造这张至关重要的预测分析表。LL(1)是自顶向下语法分析家族中最经典、最实用的一员。第一个“L”表示从左Left向右扫描输入串第二个“L”表示产生最左Leftmost推导而“(1)”则表示只需要向前查看一个输入符号就能做出决策。这种“一眼定乾坤”的特性使得基于它的分析器效率极高结构清晰。许多实际语言如Pascal、早期C的声明部分的子集以及大量配置文件、模板语言的语法都设计或可以改造成LL(1)文法。构造预测分析表的核心在于精确计算三个集合FIRST集、FOLLOW集和SELECT集。这个过程有点像给文法规则做“体检”和“建档”确保每一条规则在每一种可能的上下文下都有唯一且明确的“出场时机”。很多同学在理论学习时觉得公式抽象一旦动手实现就漏洞百出。我将结合具体的例子把每一步的计算逻辑、常见的思维陷阱以及调试技巧掰开揉碎让你不仅能看懂更能自己动手构造出正确的分析表。2. 核心概念与前置知识拆解在动手“施工”前我们必须彻底理解“建筑材料”和“设计规范”。LL(1)文法及其预测分析表的构造建立在几个相互关联的核心概念之上。理解它们之间的关系比死记硬背公式重要得多。2.1 文法的形式化定义与LL(1)的约束一个上下文无关文法G通常定义为四元组 (V, T, P, S)。V是非终结符集合T是终结符集合P是产生式规则集合S是开始符号。例如一个简单的算术表达式文法可能包含V {E, T, F}T {, *, (, ), id}S EP:E - E T | TT - T * F | FF - ( E ) | id但请注意上面这个文法不是LL(1)文法因为它存在左递归E - E T和公共左因子。LL(1)文法首先要求消除左递归并可能需要进行左因子提取这是构造预测分析表的前提。一个改造后的、可能是LL(1)的文法如下E - T EE - T E | εT - F TT - * F T | εF - ( E ) | idLL(1)文法的核心约束是对于文法的每一个非终结符A它的任何两个不同的产生式 A - α 和 A - β都必须满足SELECT(A - α) ∩ SELECT(A - β) ∅。也就是说面对同一个非终结符A和当前输入符号绝不能有两条以上的规则可供选择否则分析器就会“迷茫”。SELECT集的计算正是FIRST集和FOLLOW集的组合运用。2.2 FIRST集规则能推导出的“开头”是什么FIRST(α) 被定义为能从符号串 α 推导出的所有终结符号串的开头终结符的集合。如果 α 可以推导出空串 ε那么 ε 也在 FIRST(α) 中。计算规则牢记于心终结符FIRST(a) {a}其中a是终结符。非终结符对于 A - X1 X2 ... Xn将 FIRST(X1) 中除了 ε 以外的所有元素加入 FIRST(A)。如果 ε ∈ FIRST(X1)则继续将 FIRST(X2) 中除 ε 外的元素加入 FIRST(A)。以此类推如果对于所有 i (1≤i≤n)都有 ε ∈ FIRST(Xi)则将 ε 加入 FIRST(A)。符号串FIRST(X1X2...Xn) 的计算方式与非终结符规则中的右部类似。关键难点与易错点ε 的处理ε 代表空串它的存在意味着这条路径可能“消失”。在计算时必须判断当前符号能否推出 ε以决定是否要继续看下一个符号。一个常见的技巧是预先计算哪些非终结符是“可空的”能推出 ε。迭代计算由于产生式相互关联FIRST集的计算通常需要多轮迭代直到所有集合不再变化为止。手工计算时建议画一张表格逐轮更新避免遗漏。以改造后的文法为例计算 FIRST(F)F - ( E )右部以终结符(开头所以 FIRST(F) 首先包含(。F - id右部以终结符id开头所以 FIRST(F) 也包含id。没有其他产生式且这两个产生式右部第一个符号都不是 ε 或非终结符能推出 ε因此计算结束。FIRST(F) { (, id }。2.3 FOLLOW集非终结符后面可能跟着什么FOLLOW(A) 被定义为在所有可能出现的句型中紧跟在非终结符A之后的终结符的集合。如果A可以是某个句型的最后一个符号那么句子结束符$也在 FOLLOW(A) 中。计算规则结合例子理解对于开始符号S将$加入 FOLLOW(S)。如果存在产生式 B - α A β那么将FIRST(β) 中除 ε 外的所有元素加入 FOLLOW(A)。如果存在产生式 B - α A或者 B - α A β 且 β 能推出 ε即 ε ∈ FIRST(β)那么将FOLLOW(B) 的所有元素加入 FOLLOW(A)。关键难点与易错点规则3的传递性这是最容易出错的地方。FOLLOW集的传播是“链式”的。例如A在B的后面B在C的后面那么FOLLOW(C)会影响FOLLOW(B)进而影响FOLLOW(A)。手工计算时必须反复迭代直到所有FOLLOW集稳定。$的加入只有开始符号的FOLLOW集初始包含$其他非终结符的$只能通过规则3传递得到。接上例计算 FOLLOW(E)找到所有E出现的位置E - T E。这里E在最后。应用规则3将 FOLLOW(E) 加入 FOLLOW(E)。E - T E。这里E在最后。应用规则3将 FOLLOW(E) 加入 FOLLOW(E)这看起来是自引用但注意规则说的是将产生式左部非终结符的FOLLOW集加入其右部末尾非终结符的FOLLOW集。这里是 E - ... E所以是将 FOLLOW(E)左部加入 FOLLOW(E)右部这是一个恒等式在本轮计算中不提供新信息但需要注意在迭代算法中处理。因此FOLLOW(E) 首先依赖于 FOLLOW(E)。而E是开始符号FOLLOW(E) 初始包含$。另外从 F - ( E ) 可知)在E的后面所以 FOLLOW(E) 也包含)。所以 FOLLOW(E) { ), $ }。根据规则3这些也被加入到 FOLLOW(E) 中。FOLLOW(E) { ), $ }。2.4 SELECT集为每一条规则划定“责任区”SELECT(A - α) 是选择使用产生式 A - α 时当前输入符号必须满足的条件集合。它是连接FIRST和FOLLOW并最终填充预测分析表的桥梁。计算公式如果 ε不属于FIRST(α)那么 SELECT(A - α) FIRST(α)。如果 ε属于FIRST(α)那么 SELECT(A - α) (FIRST(α) \ {ε}) ∪ FOLLOW(A)。直观理解一条规则能被选用要么是当前输入符号正好是该规则能推导出的第一个终结符对应第一种情况要么是该规则能推导出空ε此时我们“跳过”这个A那么当前输入符号就必须是允许跟在A后面的符号对应第二种情况。对于产生式 E - εFIRST(ε) {ε}。因此SELECT(E - ε) (FIRST(ε) \ {ε}) ∪ FOLLOW(E) ∅ ∪ { ), $ } { ), $ }。 这意味着当分析器处理非终结符E且看到输入符号是)或$时就应该选用 E - ε 这条产生式即“什么都不做”匹配空串。3. 预测分析表构造的完整流程与实操掌握了三个核心集合我们就可以开始绘制最终的“施工图”——预测分析表了。这张表是一个二维矩阵行索引是非终结符列索引是终结符包括结束符$。表格内的单元格 M[A, a] 存放着当栈顶是非终结符A且当前输入符号是a时分析器应采取的动作要么是应用某条产生式将A弹出将产生式右部符号逆序压栈要么是报错。3.1 逐步计算以经典表达式文法为例我们使用这个已消除左递归的表达式文法作为贯穿始终的例子E - T EE - T EE - εT - F TT - * F TT - εF - ( E )F - id步骤一计算所有非终结符和产生式右部的FIRST集我们先计算单个符号的FIRST再计算串的。基本终结符FIRST(){}, FIRST(*){*}, FIRST((){(}, FIRST()){)}, FIRST(id){id}FIRST(F)来自产生式7和8。FIRST(() ∪ FIRST(id) { (, id }FIRST(T)来自产生式5和6。FIRST(*) ∪ {ε} { *, ε }FIRST(T)来自产生式4。FIRST(F) { (, id } 因为F不能推出ε所以只看FIRST(F)即可FIRST(E)来自产生式2和3。FIRST() ∪ {ε} { , ε }FIRST(E)来自产生式1。FIRST(T) { (, id }对于产生式右部符号串FIRST(T E) FIRST(T) { (, id } 因为T不能推出εFIRST( T E) FIRST() { }FIRST(F T) FIRST(F) { (, id }FIRST(* F T) FIRST(*) { * }FIRST(( E )) FIRST(() { ( }FIRST(id) { id }步骤二计算所有非终结符的FOLLOW集初始化FOLLOW(E) { $ } E是开始符号 我们需要迭代计算直到所有集合不变。第一轮迭代规则 E - T E:β E。将 FIRST(E) 中除 ε 外的元素加入 FOLLOW(T)。FIRST(E){, ε}所以将加入 FOLLOW(T)。因为E在最后所以将 FOLLOW(E) 加入 FOLLOW(E)。FOLLOW(E)目前是{$}所以将$加入FOLLOW(E)。规则 E - T E:β E。将 FIRST(E) 中除 ε 外的元素加入 FOLLOW(T)。同上加入。重复无新元素E在最后将 FOLLOW(E) 加入 FOLLOW(E)。自引用本轮忽略规则 T - F T:β T。将 FIRST(T) 中除 ε 外的元素加入 FOLLOW(F)。FIRST(T){*, ε}所以将*加入FOLLOW(F)。T在最后将 FOLLOW(T) 加入 FOLLOW(T)。FOLLOW(T)目前是{}所以将加入FOLLOW(T)。规则 T - * F T:β T。将 FIRST(T) 中除 ε 外的元素加入 FOLLOW(F)。加入*。重复T在最后将 FOLLOW(T) 加入 FOLLOW(T)。自引用规则 F - ( E ):这里 A Eα (, β )。根据规则 B - α A β将 FIRST(β) 中除 ε 外的元素加入 FOLLOW(A)。FIRST()) { ) }所以将)加入FOLLOW(E)。第一轮结束后FOLLOW(E) { ), $ }FOLLOW(E) { $ } 从E传来FOLLOW(T) { }FOLLOW(T) { }FOLLOW(F) { * }第二轮迭代基于第一轮结果重新扫描规则规则 E - T EE在最后将 FOLLOW(E) 加入 FOLLOW(E)。FOLLOW(E)现在是{), $}所以FOLLOW(E)增加)。现在 FOLLOW(E) { ), $ }。规则 T - F TT在最后将 FOLLOW(T) 加入 FOLLOW(T)。FOLLOW(T)是{}已存在。规则 F - ( E )已处理。检查其他规则没有新的FOLLOW元素加入。第二轮后集合已稳定。最终FOLLOW(E) { ), $ }FOLLOW(E) { ), $ }FOLLOW(T) { , ), $ }? 等等这里需要检查。T后面可能跟什么在E - T E中T后面是E。E能推出 ε所以当E为空时T后面就跟E后面可能的东西即FOLLOW(E)。另外在E - T E中T后面也是E同理。因此FOLLOW(T) 应该包含 FOLLOW(E)因为E可空和 FOLLOW(E)因为E可空且E是上层让我们严格用规则推导从E - T Eβ E。FIRST(E) {, ε}。将加入 FOLLOW(T)。另外因为 ε ∈ FIRST(E)所以将 FOLLOW(E) 加入 FOLLOW(T)。FOLLOW(E){), $}。所以 FOLLOW(T) 目前有 {, ), $}。从E - T Eβ E。同样将加入 FOLLOW(T)重复且因为 ε ∈ FIRST(E)将 FOLLOW(E) 加入 FOLLOW(T)。FOLLOW(E){), $}。这没有增加新元素。所以FOLLOW(T) { , ), $ }。FOLLOW(T)从T - F TT在最后所以 FOLLOW(T) FOLLOW(T) { , ), $ }。FOLLOW(F)从T - F Tβ T。FIRST(T){*, ε}。将*加入 FOLLOW(F)。因为 ε ∈ FIRST(T)所以将 FOLLOW(T) 加入 FOLLOW(F)。FOLLOW(T){, ), $}。所以FOLLOW(F) { *, , ), $ }。步骤三计算每条产生式的SELECT集SELECT(1. E - T E) FIRST(T E) { (, id }SELECT(2. E - T E) FIRST( T E) { }SELECT(3. E - ε) (FIRST(ε){ε}) ∪ FOLLOW(E) ∅ ∪ { ), $ } { ), $ }SELECT(4. T - F T) FIRST(F T) { (, id }SELECT(5. T - * F T) FIRST(* F T) { * }SELECT(6. T - ε) (FIRST(ε){ε}) ∪ FOLLOW(T) ∅ ∪ { , ), $ } { , ), $ }SELECT(7. F - ( E )) FIRST(( E )) { ( }SELECT(8. F - id) FIRST(id) { id }步骤四填充预测分析表表的行非终结符 {E, E, T, T, F} 表的列终结符 {, *, (, ), id, $}根据SELECT集填充SELECT(E - T E) { (, id }在行E列(和id的格子填入E - T ESELECT(E - T E) { }在行E列的格子填入E - T ESELECT(E - ε) { ), $ }在行E列)和$的格子填入E - εSELECT(T - F T) { (, id }在行T列(和id的格子填入T - F TSELECT(T - * F T) { * }在行T列*的格子填入T - * F TSELECT(T - ε) { , ), $ }在行T列、)、$的格子填入T - εSELECT(F - ( E )) { ( }在行F列(的格子填入F - ( E )SELECT(F - id) { id }在行F列id的格子填入F - id所有其他空白格子均表示“错误”即分析器在该状态下遇到该输入符号应报错。最终得到的预测分析表如下非终结符*()id$EE - T EE - T EEE - T EE - εE - εTT - F TT - F TTT - εT - * F TT - εT - εFF - ( E )F - id3.2 算法实现要点与代码思路手工计算用于理解原理在实际编译器实现中我们需要用算法来实现这个过程。以下是核心步骤的伪代码思路计算FIRST集的算法迭代不动点算法初始化对于所有终结符aFIRST(a) {a}对于所有非终结符AFIRST(A) ∅。 重复执行以下步骤直到所有FIRST集不再变化 对于每一条产生式 A - X1 X2 ... Xk 将 FIRST(X1) 中除 ε 外的所有元素加入 FIRST(A)。 i 1 while (i k-1 且 ε ∈ FIRST(Xi)) // 当前符号能推出空 将 FIRST(X_{i1}) 中除 ε 外的所有元素加入 FIRST(A)。 i if (i k 且 ε ∈ FIRST(Xk)) // 所有符号都能推出空 将 ε 加入 FIRST(A)。对于符号串 α Y1 Y2 ... Yn计算其FIRST集的过程类似可以封装为一个函数getFirstOfString(α)。计算FOLLOW集的算法初始化FOLLOW(S) {$}其他非终结符的FOLLOW集为 ∅。 重复执行以下步骤直到所有FOLLOW集不再变化 对于每一条产生式 A - B1 B2 ... Bm for i 1 to m: if Bi 是一个非终结符 // 规则2: Bi后面有东西 if i m: first_of_beta getFirstOfString(B_{i1} ... Bm) 将 first_of_beta 中除 ε 外的所有元素加入 FOLLOW(Bi)。 // 规则3: Bi后面的串能推出空 if ε ∈ first_of_beta: 将 FOLLOW(A) 中的所有元素加入 FOLLOW(Bi)。 else: // i m, Bi在产生式末尾 // 规则3: Bi在末尾 将 FOLLOW(A) 中的所有元素加入 FOLLOW(Bi)。构造分析表初始化表M所有条目为空表示错误。 对于每一条产生式 A - α 计算 first_alpha getFirstOfString(α)。 对于 first_alpha 中的每一个终结符 a除了 ε 将产生式 A - α 填入表项 M[A, a]。 if ε ∈ first_alpha 对于 FOLLOW(A) 中的每一个终结符 b包括 $ 将产生式 A - α 填入表项 M[A, b]。完成填充后检查表中每个格子是否最多只有一个产生式。如果有格子包含多于一个产生式则该文法不是LL(1)文法。4. 常见陷阱、疑难排查与实战技巧理论是完美的但实践起来总会遇到各种边界情况和意想不到的错误。下面是我在学习和教学过程中总结的几个高频“坑点”和应对策略。4.1 典型错误案例深度剖析案例一FOLLOW集计算中的“传递性”遗漏这是最常见的错误。考虑一个片段S - A B B - ε A - a计算FOLLOW(A)。很多人只看到S - A B认为B不是ε所以只把FIRST(B)加入FOLLOW(A)。但这里B能推出ε因此除了FIRST(B)可能为空或包含其他符号还必须将FOLLOW(S)加入FOLLOW(A)。如果漏了这一步在计算SELECT(A - a)时如果FIRST(a)不含ε可能没问题但如果A有ε产生式SELECT集就会算错导致分析表错误或误判文法为非LL(1)。 排查技巧在手工计算FOLLOW集时每应用一次规则都要立刻追问“这个β后面的符号串能推出ε吗”如果能一定要把FOLLOW(左部)加进来。画一个依赖图可以帮助理解箭头从A指向B表示FOLLOW(A)依赖于FOLLOW(B)。计算时需要按照依赖顺序或迭代到底。案例二SELECT集计算时对ε产生式的处理混淆对于产生式A - ε它的SELECT集是FOLLOW(A)而不是{FIRST(ε)}也不是空集。这一点必须牢记。混淆的后果是分析表在该填A - ε的地方会留空导致分析器在应该接受空串的时候报错。 记忆口诀“空产生式看后面”SELECT(A-ε) FOLLOW(A)。案例三误判LL(1)文法有时计算出的预测分析表存在冲突一个格子有两条产生式。除了计算错误这往往意味着原文法确实不是LL(1)的。常见原因未消除左递归这是硬性要求必须首先消除。存在公共左因子未提取例如A - αβ | αγ当输入符号属于FIRST(α)时无法决定选哪条。必须提取左因子A - αA,A - β | γ。文法固有歧义某些语言结构如悬空else问题对应的文法本身就是歧义的无法改造成LL(1)。这时可能需要借助其他机制如优先级和结合性规则来辅助分析。 诊断流程首先检查计算过程尤其是FIRST和FOLLOW集中ε的传递处理。确认无误后如果冲突仍在则说明需要重构文法。可以尝试更彻底的左因子提取或者思考是否能用不同的语法结构来描述同一语言。4.2 手工计算与程序调试的实用技巧手工计算“三步检查法”FIRST集检查对于每个非终结符确保其FIRST集包含了其所有产生式右部可能推导出的第一个终结符。特别检查那些右部以非终结符开头的产生式是否因为该非终结符能推出ε而继续向后看。FOLLOW集检查重点关注开始符号是否有$、产生式末尾的非终结符是否继承了左部的FOLLOW、以及前面有能推出ε的串的非终结符是否也继承了左部的FOLLOW。可以用几个简单的句子进行验证例如“在...的后面可能跟着...”。SELECT集与表冲突检查填充完分析表后逐行检查每个非终结符对应的行。对于每个终结符列想象分析器处于该非终结符在栈顶、输入指针指向该终结符的情景思考是否有且只有一条产生式是合理的。如果有两条回溯检查它们的SELECT集计算。编程实现调试建议如果你在编写构造预测分析表的程序输出中间结果将每一步计算出的FIRST集、FOLLOW集以清晰格式打印出来。与手工计算的结果对比。可视化分析表将最终的分析表输出为Markdown或HTML表格直观检查冲突点。设计测试用例使用小型但典型的LL(1)文法如上面的表达式文法作为测试输入。再使用一些已知的非LL(1)文法验证程序是否能正确检测出冲突。注意数据结构FIRST和FOLLOW集通常用Set集合数据结构存储注意处理ε。预测分析表可以用二维字典或列表实现。4.3 从预测分析表到实际分析器构造出预测分析表只是第一步它定义了分析器的“决策逻辑”。一个完整的预测分析程序表驱动还需要一个栈和一个输入缓冲区。其工作流程如下初始化栈压入开始符号S和结束符$。初始化输入缓冲区放入待分析的词法单元序列末尾加上$。令栈顶符号为X当前输入符号为a。循环执行如果 X a $分析成功结束。如果 X a 且 X 是终结符但不是$则匹配成功弹出X输入指针后移。如果 X 是非终结符查表 M[X, a]。如果表项为空报错“语法错误在输入a处期望是...”可以根据FOLLOW(X)给出建议。如果表项是产生式 X - Y1 Y2 ... Yk则弹出X然后将 Yk, ..., Y2, Y1逆序压入栈中保证最左推导。同时可以输出或记录使用的产生式这就是推导过程。重复步骤4。这个算法清晰地将文法的控制逻辑在分析表中与分析器的执行机制栈操作分离开是编译器设计中“关注点分离”的一个优美范例。理解LL(1)文法与预测分析表的构造是打开语法分析大门的关键一步。它训练了一种严谨的、基于形式化规则的计算思维。虽然现代编译器生成器如ANTLR通常使用更强大的LL(*)或LR算法但LL(1)的原理依然是坚实的基础。下次当你看到一段语法定义时不妨在脑海里试着计算一下它的FIRST和FOLLOW集看看它是否“听话”到足以用一张简单的表格来描述。这个过程本身就是对语言设计深刻性的洞察。