LL(1)预测分析表：从文法规则到确定性语法解析的实践指南

1. 项目概述从“语法”到“代码”的桥梁在编译器的世界里语法分析器就像一位严格的语法老师它需要检查我们写的程序代码是否符合编程语言预先定义好的“语法规则”。而LL(1)文法及其预测分析表就是这位老师手中最经典、最高效的一本“判题手册”。我最初接触这个概念时也觉得它充满了各种抽象的集合和公式但真正动手实现几次之后才发现它的精妙之处在于它将一个看似复杂的语法匹配问题转化为了一个确定性的查表决策过程。简单来说LL(1)预测分析表是一个二维表格。表的行对应文法的所有非终结符可以理解为语法结构单元比如“语句”、“表达式”列对应所有终结符可以理解为具体的单词比如if,id,,;以及一个特殊的结束符$。表格里的每个单元格告诉语法分析器当栈顶是某个非终结符并且当前输入单词是某个终结符时应该选择使用哪一条文法规则进行推导或者报错或者直接匹配掉。所谓LL(1)指的是分析时从左(L)向右扫描输入串构建最左(L)推导并且每一步只向前查看1个(1)输入符号就能做出决定。这种确定性的背后正是预测分析表在支撑。对于学习编译原理的同学或者任何想深入理解“代码如何被理解”的开发者掌握LL(1)预测分析表的构造不仅仅是应付考试。它能帮你真正厘清上下文无关文法的核心矛盾——如何消除二义性和左递归如何让语法变得“可预测”。在实践层面许多简单的领域特定语言DSL解析器、配置文件读取工具其核心思想都源于此。接下来我将以一个完整的、可运行的例子带你一步步拆解构造预测分析表的每一个环节并分享那些只有动手做过才会知道的“坑”和技巧。2. 核心概念与前置准备理解四大基石在动手画表之前我们必须先打好四个基础。它们就像是建造房子的四块基石缺一不可。很多同学觉得构造过程繁琐往往是因为对这几个概念的理解还浮在表面。2.1 文法规则的标准化表示我们通常使用扩展的巴科斯范式EBNF来表示文法。为了构造预测分析表我们需要一个更标准的形式。以一个简单的算术表达式文法为例它可能最初被写成E - E T | T T - T * F | F F - ( E ) | id但请注意这个文法存在左递归E - E T这会导致自顶向下的分析器陷入无限循环是LL(1)分析的大忌。因此构造预测分析表的第一步往往是文法改造。我们需要消除左递归和提取左公因子。改造后的等价文法可能如下1. E - T E 2. E - T E | ε 3. T - F T 4. T - * F T | ε 5. F - ( E ) | id这里引入了E和T这样的新非终结符来处理递归并使用ε表示空串。这是后续所有计算的基础务必保证文法是已经消除了左递归且尽可能提取了左公因子的。我们的后续步骤都将基于这个改造后的文法进行。2.2 FIRST集决定“开头能是什么”FIRST(α)集的定义是由非终结符或符号串α推导出的所有可能串的第一个终结符的集合。如果α可以推导出空串ε那么ε也属于FIRST(α)。计算规则是递推的如果X是终结符则FIRST(X) {X}。如果X是非终结符且存在产生式X - Y1 Y2 ... Yk。将FIRST(Y1)中所有非ε的符号加入FIRST(X)。如果FIRST(Y1)包含ε则继续查看FIRST(Y2)将其非ε符号加入以此类推。如果所有FIRST(Yi)都包含ε则将ε加入FIRST(X)。对于符号串X1 X2 ... Xn其FIRST集的计算类似从FIRST(X1)开始加入如果含ε则继续加入FIRST(X2)的非ε符号直至某个FIRST(Xi)不含ε或处理完所有符号。实操心得计算时建议画一张依赖图。从那些产生式右部以终结符开头的非终结符开始算起它们的FIRST集是立刻可知的。然后像“剥洋葱”一样逐步计算出依赖它们的其他非终结符的FIRST集。手动计算时最容易出错的地方是ε传递。一定要反复检查当右部某个符号能推出ε时是否继续检查了它后面的符号。以我们的文法为例FIRST(F) { (, id }由规则5直接得出FIRST(T) { *, ε }由规则4直接得出计算FIRST(T)规则3为T - F T。FIRST(F) { (, id }且不含ε所以FIRST(T) FIRST(F) { (, id }。计算FIRST(E) { , ε }。计算FIRST(E)规则1为E - T E。FIRST(T) { (, id }不含ε所以FIRST(E) FIRST(T) { (, id }。2.3 FOLLOW集决定“后面能接什么”FOLLOW(A)集的定义是在所有可能出现的句型中紧跟在非终结符A后面的终结符的集合。如果A可以是某个句型的最右符号那么输入结束符$也属于FOLLOW(A)。计算规则需要迭代至不再变化对于文法的开始符号S将$加入FOLLOW(S)。如果存在产生式A - α B βB是非终结符则将FIRST(β)中所有非ε的符号加入FOLLOW(B)。如果存在产生式A - α B或者A - α B β且FIRST(β)包含ε即β可以推出空则将FOLLOW(A)中的所有符号加入FOLLOW(B)。注意事项FOLLOW集的计算是一个迭代过程因为规则3会产生传递依赖。通常需要列一张表多轮计算直到所有集合不再扩大。这是最考验耐心和细心的步骤。继续我们的例子开始符号为E初始化FOLLOW(E) { $ }。看规则5F - ( E )这里是A - ( E )即α(, BE, β)。根据规则2应将FIRST()) { ) }加入FOLLOW(E)。所以FOLLOW(E) { $, ) }。看规则1E - T EAE, αε, BT, βE。规则2FIRST(E) { , ε }将非ε符号加入FOLLOW(T)。所以FOLLOW(T) { }。规则3因为FIRST(E)包含ε所以还要将FOLLOW(E)加入FOLLOW(T)。FOLLOW(T) { , $, ) }。看规则2E - T EAE, α, BT, βE。规则2将FIRST(E)的非ε符号加入FOLLOW(T)已存在。规则3FIRST(E)含ε将FOLLOW(E)加入FOLLOW(T)。但FOLLOW(E)目前未知先记录这个依赖关系。看规则2E - ε不产生FOLLOW集。看规则3T - F TAT, αε, BF, βT。规则2FIRST(T) { *, ε }将*加入FOLLOW(F)。FOLLOW(F) { * }。规则3FIRST(T)含ε将FOLLOW(T)加入FOLLOW(F)。所以FOLLOW(F) { *, , $, ) }。看规则4T - * F TAT, α*, BF, βT。规则2将FIRST(T)的非ε符号*加入FOLLOW(F)已存在。规则3FIRST(T)含ε将FOLLOW(T)加入FOLLOW(F)。记录依赖。看规则4T - ε无贡献。现在处理依赖由步骤4我们需要FOLLOW(E)。寻找所有A - ... E的规则规则1E - T E根据规则3β为空将FOLLOW(E)加入FOLLOW(E)。所以FOLLOW(E) { $, ) }。规则2E - T E根据规则3β为空这里β实际上是E自身但FIRST(E)含ε所以也满足条件将FOLLOW(E)加入FOLLOW(E)这是自引用不产生新元素。 因此FOLLOW(E) { $, ) }。将FOLLOW(E)代入步骤4的依赖FOLLOW(T)增加{ $, ) }但均已存在。FOLLOW(T)最终为{ , $, ) }。由步骤7我们需要FOLLOW(T)。寻找A - ... T规则3T - F T根据规则3将FOLLOW(T)加入FOLLOW(T)。所以FOLLOW(T) { , $, ) }。规则4T - * F T自引用不产生新元素。将FOLLOW(T)代入步骤7的依赖FOLLOW(F)增加{ , $, ) }但*已存在,$,)是新加入的。检查步骤6我们通过规则3已经将FOLLOW(T)加入了FOLLOW(F)而FOLLOW(T)正是{ , $, ) }。所以这里实际上已经添加过了。最终FOLLOW(F) { *, , $, ) }。经过多轮迭代我们得到FIRST(E) { (, id }FIRST(E) { , ε }FIRST(T) { (, id }FIRST(T) { *, ε }FIRST(F) { (, id }FOLLOW(E) { $, ) }FOLLOW(E) { $, ) }FOLLOW(T) { , $, ) }FOLLOW(T) { , $, ) }FOLLOW(F) { *, , $, ) }常见问题FOLLOW集计算混乱。一个有效的检查方法是FOLLOW集里的符号一定是终结符或$。FOLLOW集永远不会包含ε。计算时务必用笔和纸清晰地列出每一轮每个集合的变化直到连续两轮完全一致为止。2.4 SELECT集为每一条规则贴上“触发条件”标签有了FIRST和FOLLOW我们就可以定义SELECT集它直接决定了预测分析表的内容。对于文法的每一条产生式A - α其SELECT集计算如下如果ε不在FIRST(α)中那么SELECT(A - α) FIRST(α)。如果ε在FIRST(α)中那么SELECT(A - α) (FIRST(α) - {ε}) ∪ FOLLOW(A)。直观理解SELECT集回答了“在什么情况下我应该选择使用这条产生式”如果α不能推出空那么只要当前输入符号是α能推导出的开头符号之一就选它。如果α能推出空那么除了那些开头符号当当前输入符号正好是可以跟在A后面的符号时选择这条产生式相当于用空串ε来匹配直接消耗掉A也是合法的。计算我们文法每条规则的SELECT集SELECT(E - T E)FIRST(T E) FIRST(T) { (, id }不含ε。所以SELECT { (, id }。SELECT(E - T E)FIRST( T E) { }不含ε。所以SELECT { }。SELECT(E - ε)FIRST(ε) { ε }含ε。所以SELECT (FIRST(ε)-{ε}) ∪ FOLLOW(E) ∅ ∪ { $, ) } { $, ) }。SELECT(T - F T)FIRST(F T) FIRST(F) { (, id }不含ε。所以SELECT { (, id }。SELECT(T - * F T)FIRST(* F T) { * }不含ε。所以SELECT { * }。SELECT(T - ε)FIRST(ε) { ε }含ε。所以SELECT (FIRST(ε)-{ε}) ∪ FOLLOW(T) ∅ ∪ { , $, ) } { , $, ) }。SELECT(F - ( E ))FIRST(( E )) { ( }不含ε。所以SELECT { ( }。SELECT(F - id)FIRST(id) { id }不含ε。所以SELECT { id }。踩坑提醒计算SELECT(A-ε)时务必使用FOLLOW(A)而不是想当然地认为空产生式可以匹配任何符号。它只能匹配那些可以合法出现在A后面的符号。3. 预测分析表的构造算法与手工实现有了SELECT集构造预测分析表就变成了一个“填格子”的机械过程但其中依然有细节需要注意。3.1 算法步骤详解预测分析表M是一个二维表行索引是非终结符列索引是终结符包括结束符$。初始化表格M将所有单元格置为“错误”或空白。对文法G的每一条产生式A - α进行以下操作 a. 对于SELECT(A - α)集合中的每一个终结符a注意SELECT集里只包含终结符和$不包含ε在表M[A, a]中填入这条产生式A - α。 b. 如果SELECT(A - α)中包含$那么在表M[A, $]中填入这条产生式A - α。如果完成上述步骤后表中任何一个单元格仍然有超过一条产生式则说明该文法不是LL(1)文法。可能的原因包括文法存在二义性、未消除左递归、或未提取左公因子。3.2 手工填表示例基于我们刚才计算的SELECT集我们来填充表格。终结符集合为{ id, , *, (, ), $ }。非终结符集合为{ E, E, T, T, F }。我们按非终结符一行行来填行 E:SELECT(E - T E) { (, id }所以在(列和id列填入E - T E。行 E:SELECT(E - T E) { }在列填入E - T E。SELECT(E - ε) { $, ) }在$列和)列填入E - ε。行 T:SELECT(T - F T) { (, id }在(列和id列填入T - F T。行 T:SELECT(T - * F T) { * }在*列填入T - * F T。SELECT(T - ε) { , $, ) }在、$、)列填入T - ε。行 F:SELECT(F - ( E )) { ( }在(列填入F - ( E )。SELECT(F - id) { id }在id列填入F - id。将结果整理成表格如下非终结符id*()$EE-T EE-T EEE-T EE-εE-εTT-F TT-F TTT-εT-*F TT-εT-εFF-idF-( E )表格解读当分析栈顶是E当前输入符号是id或(时分析器就应用规则E - T E即用T E替换栈顶的E。当栈顶是E输入符号是时应用E - T E如果输入是)或$则应用E - ε即直接将E弹出栈不消耗输入符号。3.3 关键检查确认文法是LL(1)构造完表格后必须检查每个单元格至多只有一个条目。我们的表格满足这个条件因此该文法是LL(1)文法。如果一个单元格出现了两个或以上的产生式例如对于非终结符A和输入符号a既有A-α又有A-β那么分析器在面对(A, a)时就无法确定选择哪条规则这就是冲突。冲突的根源在于两条产生式的SELECT集有交集。实操心得手工构造时最容易在填SELECT集包含FOLLOW(A)的那些产生式通常是A-ε时出错或遗漏。务必对照FOLLOW集逐一核对。另外表格的列终结符一定要列全包括文法中出现的所有终结符和$避免遗漏导致后续分析出错。4. 基于预测分析表的语法分析过程表构造好了我们来看看分析器如何利用它来工作。语法分析器通常需要一个分析栈和一个输入缓冲区。初始时栈底为$栈顶为文法的开始符号E在栈顶。输入缓冲区中存放着待分析的符号串末尾附加一个$。分析过程遵循以下算法将$和开始符号依次压入分析栈。令X为当前栈顶符号a为当前输入指针所指的符号。循环执行以下步骤直到接受或报错 a. 如果X a $则分析成功接受输入串。 b. 如果X是一个终结符 - 如果X a则匹配成功。将X弹出栈输入指针前移一位。 - 如果X ! a则匹配失败报错。 c. 如果X是一个非终结符 - 查预测分析表M。如果M[X, a]中有一条产生式X - Y1 Y2 ... Yk则 i. 将X弹出栈。 ii. 将Yk, ..., Y2, Y1逆序压入栈中以保证Y1在栈顶。 - 如果M[X, a]为空则报错。4.1 实例分析解析id id * id我们来一步步模拟分析输入串id id * id后跟$的过程。步骤分析栈 (栈顶在右)剩余输入串动作说明0$ Eid id * id $初始状态1$ E Tid id * id $栈顶E输入id查表M[E, id]为E - T E。弹出E逆序压入T E。2$ E T Fid id * id $栈顶T输入id查表M[T, id]为T - F T。弹出T逆序压入F T。3$ E T idid id * id $栈顶F输入id查表M[F, id]为F - id。弹出F逆序压入id。4$ E T id * id $栈顶id是终结符与输入id匹配。弹出id输入指针后移。5$ E id * id $栈顶T输入查表M[T, ]为T - ε。弹出T压入空即不压入任何东西。6$ E T id * id $栈顶E输入查表M[E, ]为E - T E。弹出E逆序压入 T E。注意是终结符也被压入了栈。7$ E Tid * id $栈顶是终结符与输入匹配。弹出输入指针后移。8$ E T Fid * id $栈顶T输入id查表M[T, id]为T - F T。弹出T逆序压入F T。9$ E T idid * id $栈顶F输入id查表M[F, id]为F - id。弹出F逆序压入id。10$ E T* id $栈顶id匹配输入id。弹出id输入指针后移。11$ E T F ** id $栈顶T输入*查表M[T, *]为T - * F T。弹出T逆序压入* F T。12$ E T Fid $栈顶*匹配输入*。弹出*输入指针后移。13$ E T idid $栈顶F输入id查表M[F, id]为F - id。弹出F逆序压入id。14$ E T$栈顶id匹配输入id。弹出id输入指针后移。15$ E$栈顶T输入$查表M[T, $]为T - ε。弹出T。16$$栈顶E输入$查表M[E, $]为E - ε。弹出E。17栈空输入空栈顶$输入$匹配成功分析结束。过程解读这个过程清晰地展示了预测分析的“预测”特性。分析器从不“回头看”它只根据当前的栈顶符号和下一个输入符号通过查表唯一确定下一步的动作用哪条规则展开或者进行匹配。栈的变化记录了推导的过程最左推导的逆过程而输入的消耗是严格从左到右的。4.2 算法实现要点如果你想用代码实现这个分析器核心数据结构就是那个预测分析表M。可以用字典嵌套字典Map非终结符, Map终结符, 产生式或者二维数组来实现。栈可以用一个简单的列表或数组来模拟。代码片段示意Python风格# 预测分析表 M 这里用字典表示 M[non_terminal][terminal] production M { E: {id: [T, E\], (: [T, E\]}, E\: {: [, T, E\], ): [ε], $: [ε]}, # ... 其他行类似 } def parse(input_string): stack [$, E] # 初始化栈 input_tokens input_string.split() [$] # 假设输入是分词后的列表 ip 0 # 输入指针 while stack: X stack[-1] # 栈顶 a input_tokens[ip] if ip len(input_tokens) else $ if X $ and a $: print(Accept!) return True elif X in terminals: # X是终结符 if X a: stack.pop() ip 1 print(fMatch: {X}) else: print(fError: expecting {X}, found {a}) return False else: # X是非终结符 if a in M.get(X, {}): production M[X][a] stack.pop() if production ! [ε]: # 空产生式不压栈 # 逆序压栈 for symbol in reversed(production): stack.append(symbol) print(fApply: {X} - { .join(production)}) else: print(fError: no production for M[{X}, {a}]) return False return False注意事项在实际编程实现中需要小心处理ε产生式。它意味着直接从栈中弹出对应的非终结符而不压入任何新符号。另外输入串的预处理词法分析也很重要需要将源代码转换成终结符单词序列。5. 常见问题、冲突排查与文法改造理论很美好但实际中我们遇到的文法常常不是标准的LL(1)文法。构造预测分析表时出现冲突一个单元格有多条产生式是家常便饭。这时就需要我们化身“文法医生”进行诊断和改造。5.1 冲突类型与原因分析FIRST-FIRST冲突现象同一个非终结符的两条产生式它们的SELECT集因为FIRST集有交集而发生冲突。典型例子if语句文法。Stmt - if ( Exp ) Stmt | if ( Exp ) Stmt else Stmt对于非终结符Stmt当输入符号是if时两条产生式的FIRST集都是{ if }导致M[Stmt, if]有两条规则无法选择。解决方法提取左公因子。将共同前缀if ( Exp ) Stmt提取出来。Stmt - if ( Exp ) Stmt Stmt Stmt - else Stmt | ε这样看到if时只有一条路可走。至于后面是else还是其他由新的Stmt来处理。FIRST-FOLLOW冲突或ε冲突现象一条产生式的SELECT集含FOLLOW(A)与另一条产生式的SELECT集含FIRST(α)有交集。典型例子悬空else问题就是这种冲突。在上面的改造后的文法中Stmt有两条产生式Stmt - else Stmt和Stmt - ε。计算SELECT(Stmt - else Stmt) { else }SELECT(Stmt - ε) FOLLOW(Stmt)。我们需要计算FOLLOW(Stmt)它可能包含else吗这取决于文法其他部分。在某些设计中如果FOLLOW(Stmt)包含了else就会冲突。实际上经典的悬空else文法就是非LL(1)的需要额外规则如“最近匹配原则”来解决。解决方法这种冲突有时难以通过文法改写消除它可能揭示了文法的二义性。需要审视语言设计本身或者接受一个非LL(1)的文法在分析器中加入特殊的冲突解决规则。左递归引起的冲突现象直接或间接左递归的文法会导致FIRST集计算出现循环依赖并且预测分析表会在对应位置出现多条规则本质也是FIRST集重叠。典型例子本文开头未改造的表达式文法E - E T | T。FIRST(E)的计算会陷入循环。解决方法消除左递归。有标准算法直接左递归对于形如A - Aα | β的规则可改写为A - βA和A - αA | ε。间接左递归需要通过代入和排序来消除过程稍复杂但有固定套路。5.2 文法改造实战技巧1. 先消除左递归再提取左公因子这个顺序很重要。如果先提公因子可能会引入新的左递归或者让消除左递归的过程变复杂。2. 提取左公因子要彻底有时公因子不止一个符号。例如A - a b c X - a b c Y公因子是a b c需要一直提取到不同为止。改写为A - a b c A A - X | Y3. 关注ε产生式带来的影响引入ε产生式是消除左递归和提取公因子的常见结果但它会扩大FOLLOW集增加冲突风险。在改造后务必重新计算FIRST和FOLLOW集验证LL(1)性质。4. 并非所有文法都能改造成LL(1)有些文法天生就是二义性的如悬空else无法改造成LL(1)文法。对于这类文法要么使用更强大的分析技术如LR分析要么在LL分析框架内制定额外的、非文法规定的冲突解决策略。排查清单当你的预测分析表出现冲突时按以下步骤排查确认原文法是否已消除所有左递归包括间接的。确认是否对所有可能的地方进行了左公因子提取。重新、仔细地计算一遍FIRST集和FOLLOW集确保没有计算错误。特别注意ε的传递。检查冲突单元格对应的产生式分析冲突类型看是否有可能通过进一步改写解决。如果确认无法改写为LL(1)考虑这是否是语言设计必须的二义性并决定是否采用其他分析算法。6. 从理论到实践预测分析表的代码生成与应用理解了手工构造过程后我们可以尝试用程序来自动完成它。这不仅能加深理解也是构建真正语法分析器生成器如ANTLR早期版本的基础的核心步骤。6.1 自动化构造的核心逻辑程序构造预测分析表的核心就是实现我们之前讨论的算法数据结构定义定义文法规则非终结符、产生式体、终结符集合。计算FIRST集实现一个函数对于任意符号串能计算出其FIRST集。这里需要处理ε传递通常用一个字典来缓存非终结符的FIRST集采用迭代或递归直到集合不再变化。计算FOLLOW集这是最复杂的部分。需要初始化FOLLOW集开始符号加$然后反复扫描所有产生式应用规则2和规则3直到所有集合稳定。通常需要多轮循环。计算SELECT集遍历每一条产生式A-α根据FIRST(α)是否含ε计算其SELECT集。填充分析表遍历每一条产生式及其SELECT集将产生式填入表M[A, a]a是SELECT集中的终结符。如果发生重复填入则报告文法非LL(1)并指出冲突位置。编程细节提示在计算FIRST集时对于符号串α X1X2...Xn需要顺序处理。如果某个Xi的FIRST集不含ε则计算结束如果所有都含ε则最终FIRST(α)包含ε。计算FOLLOW集时建议使用一个changed标志位在一轮扫描中只要任何一个FOLLOW集扩大了就将changed设为True然后进行下一轮扫描直到某一轮没有任何集合发生变化。SELECT集的计算依赖于FIRST和FOLLOW所以必须在这两者都计算完成后进行。6.2 在真实编译器项目中的定位在一个完整的编译器前端中预测分析表通常是语法分析器生成器如早期基于LL(*)的ANTLR工具的输出之一或者由开发者手动编写对于小型DSL。分析表本身会被硬编码在分析器代码中或者作为一个可查询的数据结构。对于学习而言手动实现一遍这个构造过程其价值远超死记硬背公式。你会深刻理解文法设计的重要性一个糟糕的文法会给分析带来多少麻烦。确定性与效率LL(1)分析是确定性的、线性的时间复杂度O(n)这得益于预测分析表提供的O(1)时间复杂度的决策。错误的精准定位当输入符号与栈顶符号不匹配且预测分析表对应项为空时分析器可以立即报错并给出“期望的符号集合”即该非终结符对应的SELECT集的并集这对于生成友好的语法错误信息至关重要。6.3 扩展与局限性LL(1)文法只是上下文无关文法的一个子集。它的强大约束无二义性、无左递归、无回溯保证了分析的高效但也限制了其表达能力。许多实用的编程语言文法都不是严格的LL(1)。因此实践中发展出了LL(k)分析向前查看k个符号以解决更多冲突但分析表会指数级膨胀。递归下降分析手工编写分析函数每个非终结符对应一个函数。通过函数调用栈实现分析栈可以在函数内部嵌入任意代码来处理一些简单的冲突如if-else比通用的LL(1)分析器更灵活是许多工业级编译器如GCC、Clang的早期C/C前端的选择。ANTLR等工具它们使用LL(*)算法允许在规则中嵌入语义谓词和无限前瞻极大地扩展了LL系列分析的能力。尽管有这些更强大的工具LL(1)及其预测分析表仍然是编译原理教学中最核心的内容之一。它清晰地揭示了自顶向下分析的本质是理解更复杂分析技术如LR分析的绝佳阶梯。当你下次看到一段代码被解析成抽象语法树时可以想想也许就有一个看不见的预测分析表正在驱动着这个理解过程。