预测分析表的构造与实现详解)
1. 从“猜”语法到“算”语法为什么我们需要预测分析表在编译原理的实践里语法分析器的工作本质上就是拿着源代码的字符串去匹配我们预先定义好的语法规则。这个过程有点像拿着一个复杂的乐谱去判断一段旋律是否符合它的结构。最直观、最笨的办法就是“猜”——遇到一个语法成分我尝试用所有可能的规则去匹配它这条路走不通就退回来换另一条也就是所谓的“回溯”。这种方法在理论上是万能的但效率极低想象一下一个大型项目几万行代码每个地方都去猜和回溯编译时间会变得无法接受。所以我们需要一种“确定性”的分析方法让语法分析器在每一步都明确地知道该用哪一条规则没有歧义绝不回头。LL(1)文法及其核心工具——预测分析表就是为了实现这个目标而生的。它把“猜”的过程提前变成了“算”的过程。在真正开始分析源代码之前我们就通过计算生成一张表格预测分析表。这张表告诉分析器当栈顶是某个非终结符并且当前输入符号是某个特定终结符时你应该毫不犹豫地选择应用哪一条产生式。这就像给分析器配备了一张精确的“决策地图”。分析器不再是摸着石头过河而是按图索骥每一步都走得坚定而准确。这也是“预测分析”这个名字的由来——我们能够预测下一步的动作。理解并亲手构造出这张表是掌握自顶向下语法分析技术的关键一步它连接了抽象的文法理论和具体的分析器实现。今天我们就来彻底拆解这个过程让你不仅能看懂课本上的例子更能自己动手为任何给定的LL(1)文法构造出那张神奇的预测分析表。2. 构造预测分析表前的三大核心计算FIRST、FOLLOW与SELECT预测分析表不是凭空想象出来的它的每一个单元格的填充都依赖于对文法规则的精确计算。这些计算围绕三个核心集合展开FIRST集、FOLLOW集以及由它们衍生出的SELECT集。可以说吃透了这三个集合构造预测分析表就成功了一大半。2.1 FIRST集一个符号串所有可能的“开头”是什么FIRST(α) 的定义是由符号串 α 推导出的所有终结符号串的第一个终结符所构成的集合。如果 α 可以推导出空串 ε那么 ε 也属于 FIRST(α)。计算规则务必按顺序迭代计算直至不再变化对于终结符 aFIRST(a) { a }。这是基础。对于非终结符 A查看其所有产生式 A - β如果存在产生式 A - ε则将 ε 加入 FIRST(A)。对于产生式 A - X1 X2 ... Xk将 FIRST(X1) 中除 ε 外的所有元素加入 FIRST(A)。如果 ε ∈ FIRST(X1)则继续将 FIRST(X2) 中除 ε 外的所有元素加入 FIRST(A)。以此类推如果对于所有 1 ≤ i ≤ k都有 ε ∈ FIRST(Xi)则将 ε 加入 FIRST(A)。这意味着整个右部都能推出空。对于符号串 α X1 X2 ... XnFIRST(α) 初始化为 FIRST(X1)如果X1不能推出ε则计算结束。如果 ε ∈ FIRST(X1)则将 FIRST(X2) 中除 ε 外的元素加入 FIRST(α)。重复此过程如果所有 Xi 的 FIRST 集都包含 ε则将 ε 加入 FIRST(α)。举个例子假设有文法E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id我们计算 FIRST(F)F - ( E )右部第一个符号是终结符(所以 FIRST(() {(}。因此(∈ FIRST(F)。F - id右部第一个符号是终结符id所以id∈ FIRST(F)。没有其他产生式。因此FIRST(F) {(,id}。接着计算 FIRST(T’)T’ - * F T’右部第一个符号是终结符*所以*∈ FIRST(T’)。T’ - ε根据规则将 ε 加入 FIRST(T’)。因此FIRST(T’) {*, ε }。2.2 FOLLOW集一个非终结符后面可能跟着什么FOLLOW(A) 的定义是在所有规范句型可以理解为推导过程中出现的句型中紧跟在非终结符 A之后的终结符的集合。如果 A 可能是某个句型的最后一个符号那么句子结束符$也属于 FOLLOW(A)。$在这里代表输入串的结束。计算规则从开始符号S开始迭代计算对于开始符号 S将$加入 FOLLOW(S)。因为S是开头它后面就是输入结束。如果存在产生式 B - α A β其中β是非空串将FIRST(β) 中除 ε 外的所有元素加入 FOLLOW(A)。因为A后面紧跟着ββ的第一个终结符就是可能跟在A后面的东西。如果存在产生式 B - α A或者存在产生式 B - α A β 且 ε ∈ FIRST(β)即β可以推出空将FOLLOW(B) 的全部元素加入 FOLLOW(A)。这是因为如果A后面啥也没有或者后面的β能变成空那么A后面能出现的东西其实就是产生式左部B后面能出现的东西。这是FOLLOW集计算中最关键也最容易出错的一条规则它体现了“继承”关系。继续上面的例子计算 FOLLOW(E)规则1E是开始符号所以$∈ FOLLOW(E)。寻找形如... E ...的产生式在 F - ( E ) 中E后面跟着终结符)。根据规则2将 FIRST()) {)} 加入 FOLLOW(E)。所以)∈ FOLLOW(E)。没有其他产生式右部包含E了。因此FOLLOW(E) {),$}。再计算一个复杂的FOLLOW(E’)E’ 不是开始符号规则1不适用。寻找形如... E ...的产生式在 E - T E’ 中E’ 出现在产生式尾部。根据规则3情况 B - α A将 FOLLOW(E) 的所有元素加入 FOLLOW(E’)。所以),$∈ FOLLOW(E’)。在 E’ - T E’ 中E’ 也出现在产生式尾部。根据规则3将 FOLLOW(E’) 加入 FOLLOW(E’)这看起来是递归的但在迭代计算中我们是在不断更新集合。初始时 FOLLOW(E’) 为空在上一轮我们从E那里得到了),$。在这一轮由于E’ - T E’ 右部最后的符号是E’自己我们需要将 FOLLOW(E’)当前已有的加入 FOLLOW(E’)这不会增加新元素。因此FOLLOW(E’) {),$}。这里可以看到E’ 的 FOLLOW 集继承了 E 的 FOLLOW 集。2.3 SELECT集为每一条产生式划定“生效范围”SELECT集是连接产生式和预测分析表的直接桥梁。对于一条产生式 A - αSELECT(A - α) 指明了在什么情况下我们应该选择使用这条产生式进行推导。计算规则如果ε ∉ FIRST(α)那么 SELECT(A - α) FIRST(α)。为什么如果α推不出空那么选择这条产生式后我们期望立刻看到α的第一个终结符。所以当输入符号属于FIRST(α)时就选它。如果ε ∈ FIRST(α)那么 SELECT(A - α) (FIRST(α) - {ε}) ∪ FOLLOW(A)。为什么如果α能推出空那么选择这条产生式后A可能被替换为空串。此时A后面必须跟的东西即FOLLOW(A)就应该出现在当前的输入中。所以选择范围是FIRST(α)里除了ε以外的部分加上A后面可能跟的所有符号。计算上面文法的 SELECT 集SELECT(E - T E’):α T E’。我们需要 FIRST(T E’)。FIRST(T) FIRST(F) {(,id} (因为 T - F T’且F推不出ε)。FIRST(T E’) FIRST(T) {(,id}且 ε 不在其中。所以SELECT(E - T E’) {(,id}。SELECT(E’ - T E’):α T E’。FIRST() {}不含 ε。所以SELECT(E’ - T E’) {}。SELECT(E’ - ε):α ε。FIRST(ε) { ε }。因此适用第二条规则SELECT(E’ - ε) (FIRST(ε) - {ε}) ∪ FOLLOW(E’) ∅ ∪ {),$} {),$}。这一点至关重要当E’面临输入符号是)或$时它应该选择 ε 产生式将自身“消失”。注意SELECT集的计算是构造预测分析表的核心必须保证对每条文法产生式都计算正确任何错误都会直接导致分析表错误进而使分析器无法工作或产生错误结果。3. 预测分析表的构建算法与实例演练有了SELECT集构建预测分析表就变成了一个按部就班的填表过程。预测分析表M是一个二维表格行索引是非终结符列索引是终结符包括结束符$。构建算法对文法 G 的每个产生式 A - α执行第2步。对 SELECT(A - α) 中的每一个终结符 a注意SELECT集里可能包含$但不包含 ε在表M[A, a]中填入该产生式A - α。如果 SELECT(A - α) 中包含$则在表M[A, $]中填入 A - α。将所有未定义的M[A, a]标记为“错误”通常用空白或“error”表示。一个必须遵守的关键原则对于每个非终结符 A 和每个输入符号 aM[A, a]中最多只能有一条产生式。如果根据上述算法发现需要向同一个单元格填入两条或以上不同的产生式那么该文法不是 LL(1) 文法。这是判断文法是否为 LL(1) 的充要条件。让我们用之前的表达式文法完整演练一遍文法E - T E’E’ - T E’E’ - εT - F T’T’ - * F T’T’ - εF - ( E )F - id我们需要的终结符集合是,*,(,),id,$。 非终结符集合是E,E’,T,T’,F。首先列出所有SELECT集基于前面的计算SELECT(1): {(,id}SELECT(2): {}SELECT(3): {),$}SELECT(4): {(,id} (计算同E因为 T - F T’FIRST(F) {(,id})SELECT(5): {*}SELECT(6): {,),$} (FOLLOW(T’) FOLLOW(T) {,),$})SELECT(7): {(}SELECT(8): {id}现在初始化一个空白表格然后根据SELECT集填充非终结符id*()$EE - T E’E - T E’E’E’ - T E’E’ - εE’ - εTT - F T’T - F T’T’T’ - εT’ - *F T’T’ - εT’ - εFF - idF - ( E )填表过程解读行 ESELECT(E - T E’) 包含id和(所以在E行id和(列填入E - T E’。行 E’SELECT(E’ - T E’) 包含所以在列填入。SELECT(E’ - ε) 包含)和$所以在对应列填入。行 TSELECT(T - F T’) 包含id和(填入。行 T’SELECT(T’ - *F T’) 包含*填入。SELECT(T’ - ε) 包含,),$来自FOLLOW(T’)在对应三列填入。这里请注意T’行列填入的是ε产生式而不是*产生式。这意味着当栈顶是T’输入是时分析器知道乘法部分已经结束应该将T’弹出用ε替换。行 FSELECT(F - id) 包含idSELECT(F - ( E )) 包含(分别填入。检查表格每个单元格至多只有一个条目没有冲突。因此该文法是 LL(1) 文法这张表就是其预测分析表。4. 常见陷阱、冲突分析与文法改造思路在实际构造过程中很容易踩坑。最大的坑莫过于发现表格的同一个单元格里需要填入两条不同的产生式即发生了FIRST-FIRST 冲突或FIRST-FOLLOW 冲突。4.1 冲突类型与诊断FIRST-FIRST 冲突现象同一个非终结符的两条产生式它们的 SELECT 集有交集且这个交集来自各自的 FIRST 集部分。例子S - aB | aC。FIRST(aB) {a} FIRST(aC) {a}。SELECT集交集为 {a}。当输入是a时分析器无法决定用哪条规则。本质文法存在公共左因子。分析器看到第一个符号a后不知道后面跟着的是B还是C。FIRST-FOLLOW 冲突现象一条产生式的 SELECT 集因其能推出空包含了 FOLLOW(A)与另一条产生式的 SELECT 集来自其 FIRST 集有交集。例子S - Aa | ε且A - b | ε。计算 FOLLOW(S) 包含$FIRST(Aa) 包含b。那么 SELECT(S - Aa) 包含bSELECT(S - ε) 包含$。如果 FOLLOW(S) 也包含b这可能在更复杂的文法中发生那么当输入是b时分析器就不知道应该用S - Aa还是S - ε。本质文法存在左递归或不合理的空产生式导致一个非终结符在某种上下文下既可推出空又可推出以某个符号开头的串让分析器无法决策。4.2 文法改造消除左递归与提取左因子如果文法不是 LL(1) 的我们通常尝试通过改造使其满足 LL(1) 条件。核心是两大技术1. 消除直接左递归将形如A - Aα | β的规则其中β不以A开头改写为A - β A A - α A | ε这引入了新的非终结符A‘将左递归转化为了右递归。右递归是 LL(1) 分析器可以处理的。2. 提取左因子将形如A - αβ1 | αβ2 | ... | αβn | γ的规则其中γ不以α开头改写为A - α A | γ A - β1 | β2 | ... | βn这推迟了决策点等分析器消耗掉公共前缀α之后再根据后续输入在A‘处决定选择哪个β。改造实战假设有文法S - aS | a这显然不是 LL(1) 的因为两条产生式有公共左因子a。提取左因子公共部分是a剩余部分分别是S和ε。改写为S - a S‘S‘ - S | ε。但此时S‘的产生式又包含了左递归S‘ - S因为S可以推出以a开头的东西。我们需要继续处理。实际上这个简单文法等价于S - aS | a它描述的语言是a。一个更直接的 LL(1) 改写是S - a S‘S‘ - a S‘ | ε。这样SELECT(S - a S‘) {a} SELECT(S‘ - a S‘) {a} SELECT(S‘ - ε) FOLLOW(S‘) {$}没有冲突。重要提示并非所有文法都能改造为 LL(1) 文法。有些语言特性如某些自然语言结构或复杂的编程语言结构天生就无法用 LL(1) 文法描述。此时就需要使用更强大的分析技术如 LR(1) 分析。LL(1) 文法的能力是上下文无关文法的一个真子集。5. 从分析表到分析器驱动程序的实现逻辑构造出预测分析表后实现一个预测分析器就非常直观了。分析器通常包含一个栈、一个输入缓冲区和那张预测分析表 M。算法流程伪代码描述初始化栈将结束符$和文法开始符号S依次压入栈底$在最底下。将输入串 append$后放入输入缓冲区指针指向第一个输入符号。令X为栈顶符号a为当前输入符号。循环执行以下步骤直到接受或报错 a. 如果X a ‘$‘则分析成功接受输入串。 b. 如果X a且X是终结符但不是$则匹配成功。将X弹出栈输入指针前移一位。转到步骤4。 c. 如果X是非终结符查表M[X, a]。 i. 如果M[X, a]中是一条产生式X - Y1 Y2 ... Yk则弹出栈顶X然后将Yk, ..., Y2, Y1逆序压入栈中保证Y1在栈顶。输出或记录使用了该产生式。 ii. 如果M[X, a]中是X - ε则简单地将X弹出栈。 iii. 如果M[X, a]是空错误条目则调用错误处理例程。用之前的表格分析输入串id id * id栈初始为$ EE在栈顶 输入为id id * id $步骤栈 (栈顶在右)输入 (剩余部分)动作 (查表 M[栈顶 当前输入])1$ Eid id * id $M[E, id] E - T E‘。弹出E逆序压入 T E‘。栈变为$ E‘ T2$ E‘ Tid id * id $M[T, id] T - F T‘。弹出T压入 T‘ F。栈变为$ E‘ T‘ F3$ E‘ T‘ Fid id * id $M[F, id] F - id。弹出F压入 id。栈变为$ E‘ T‘ id4$ E‘ T‘ idid id * id $栈顶id匹配输入id。弹出id消耗输入id。栈变为$ E‘ T‘输入指向5$ E‘ T‘ id * id $M[T‘, ] T‘ - ε。弹出 T‘。栈变为$ E‘6$ E‘ id * id $M[E‘, ] E‘ - T E‘。弹出E‘压入 E‘ T 。注意顺序先压入E‘再T最后这样在栈顶。栈变为$ E‘ T 7$ E‘ T id * id $栈顶匹配输入。弹出消耗输入。栈变为$ E‘ T输入指向id8$ E‘ Tid * id $M[T, id] T - F T‘。弹出T压入 T‘ F。栈变为$ E‘ T‘ F9$ E‘ T‘ Fid * id $M[F, id] F - id。弹出F压入 id。栈变为$ E‘ T‘ id10$ E‘ T‘ idid * id $匹配id。弹出id消耗输入id。栈变为$ E‘ T‘输入指向*11$ E‘ T‘* id $M[T‘, *] T‘ - * F T‘。弹出T‘压入 T‘ F *。栈变为$ E‘ T‘ F *12$ E‘ T‘ F ** id $匹配*。弹出*消耗输入*。栈变为$ E‘ T‘ F输入指向id13$ E‘ T‘ Fid $M[F, id] F - id。弹出F压入 id。栈变为$ E‘ T‘ id14$ E‘ T‘ idid $匹配id。弹出id消耗输入id。栈变为$ E‘ T‘输入指向$15$ E‘ T‘$M[T‘, $] T‘ - ε。弹出 T‘。栈变为$ E‘16$ E‘$M[E‘, $] E‘ - ε。弹出 E‘。栈变为$17$$栈顶$匹配输入$分析成功。通过这个过程你可以清晰地看到预测分析表是如何精确地指导每一步操作的。栈的变化轨迹其实就是最左推导的逆过程。6. 工程实践中的考量与优化技巧在真实的编译器项目中构造和使用预测分析表并非总是像课本例子那样标准。这里分享一些从实践中学到的经验和技巧。1. 表驱动 vs 递归下降预测分析表是“表驱动”分析器的核心。但在实际中更常见的LL(1)分析器实现方式是递归下降。两者在逻辑上完全等价。表驱动通用性强算法固定只需更换分析表即可分析不同文法。但查表、栈操作有一定开销。递归下降为每个非终结符编写一个对应的递归函数。函数体根据当前输入符号通过预读一个token即“lookahead”决定调用哪个子函数或直接匹配终结符。这本质上就是把预测分析表“硬编码”成了if-else或switch-case语句。如何选择对于语法结构复杂、产生式多的语言如Java、C手写递归下降代码会非常冗长且容易出错通常使用工具如ANTLR生成。对于语法简单的小语言如配置文件解析器、DSL手写递归下降非常直观和高效。表驱动则更多用于教学和原理演示。2. 错误恢复与恐慌模式上面的算法在遇到表项为空时直接报错。真正的编译器需要更强的健壮性尝试从错误中恢复继续分析以发现更多错误。一种简单的策略是“恐慌模式”当M[X, a]出错时跳过输入符号a直到遇到一个属于FOLLOW(X)或同步集合通常设计为FIRST集合的扩展的符号。然后将栈顶的非终结符X弹出尝试继续分析。这允许分析器在遇到一个局部语法错误后能同步到下一个可继续分析的点而不是直接崩溃。3. 优化分析表存储对于大型文法预测分析表可能非常稀疏很多空单元格。直接使用二维数组浪费空间。可以采用压缩存储链表法为每个非终结符维护一个链表链表中存储 (终结符, 产生式指针) 对。查表时遍历链表。哈希表法为每个非终结符建立一个哈希表键是终结符值是产生式。这些优化在递归下降中自然不存在因为“查表”变成了代码分支。4. 处理“悬空else”等经典二义性某些文法结构如 if-then-else天生带有二义性。文法Stmt - if (Expr) Stmt | if (Expr) Stmt else Stmt | ...就不是 LL(1) 的因为当输入是else时不知道应该将其归为当前 if 的 else还是留给更外层的 if。解决方案文法改造。通常强制规定else与最近未匹配的if配对。这可以通过定义两种语句MatchedStmt(配对的) 和UnmatchedStmt(未配对的) 来实现从而消除二义性使其满足 LL(1)。这也是为什么大多数编程语言语法说明中会专门定义这一条。理解预测分析表的构造不仅仅是完成一道课后习题。它让你透彻地看到一个确定的、高效的自顶向下分析器其灵魂就在于那张通过严谨计算得来的、毫无歧义的决策表。下次当你手写一个递归下降解析器时不妨在脑海里先为你的文法画一画 FIRST、FOLLOW 和 SELECT 集心里构建出那张隐形的“表”你的代码逻辑会清晰得多。
