语法分析核心考点精讲：FIRST/FOLLOW集与LL(1)、LR分析表构造指南

语法分析在整个编译原理课程里属于那种“一听就会一做就废”的章节。词法分析好歹还能靠正则表达式和有限自动机硬刚一波到了语法分析这儿上下文无关文法、FIRST集、FOLLOW集、LL(1)、LR(0)、SLR(1)这些概念一股脑砸过来课后习题更是变着花样让你构造分析表、写推导过程、判断文法类型。我当年学这块的时候课堂笔记抄得满满当当真做起作业来照样卡壳最后是靠着反复刷题、把经典题型的套路摸清楚才真正通透的。这篇文章不打算做成教材的复读机而是以课后习题为主线把语法分析的核心知识串成一条线。内容包括上下文无关文法的构建思路、自顶向下和自底向上两类主流分析方法的解题模板、FIRST/FOLLOW集的手算技巧、预测分析表与LR分析表的构造流程再结合我踩过的坑和常见考点做一次系统性梳理。不管你是正在被课后作业折磨的本科生还是准备考研、面试需要突击编译原理的同学这篇文章都能帮你少走点弯路。1. 语法分析在学什么先理清它是编译器的哪一环1.1 语法分析要解决的核心问题从编译流程来看词法分析负责把源代码字符串拆成一个个token比如关键字、标识符、运算符、数字常量这些。但拿到一串token之后编译器怎么知道这些token的组合是否符合语言的语法规则比如int a 3 4;是合法的C语言声明语句而int 3 a;就是一堆乱码。语法分析干的就是这件事按照语言的语法规则检查token序列的排列组合是否合法并在此基础上构建一棵语法树为后续的语义分析和中间代码生成打基础。换句话说词法分析回答的是“这个词是什么”语法分析回答的是“这些词按这个顺序排在一起成不成一句话”。如果你写过手工解析器比如用递归下降去解析JSON或者简单的数学表达式那你其实已经在做语法分析的事了只是当时可能没意识到这就是编译原理里的核心章节。1.2 为什么需要上下文无关文法小学语文课上学过句子有主谓宾结构可以用语法树来分析。编程语言也一样但比自然语言要严格得多。编译原理里用来描述程序语言语法结构的工具叫上下文无关文法Context-Free GrammarCFG它是比正则表达式更强的一种描述工具。正则表达式描述不了嵌套结构比如括号配对、if语句里再嵌套if语句这些结构用正则去匹配会非常痛苦甚至不可能实现。而上下文无关文法的产生式左部只有一个非终结符它天然支持递归定义所以能优雅地表达嵌套结构。比如经典的算术表达式就可以定义成E - E T | T T - T * F | F F - ( E ) | id这个文法通过非终结符E、T、F之间的递归和分层精准描述了加法和乘法的优先级差异。语法分析的核心工作之一就是给定一个文法判断一个输入串能不能由这个文法推导出来并给出推导过程。2. 从课后习题看核心概念推导、语法树与二义性2.1 推导过程最左推导与最右推导的实战记忆法课后习题里第一类常见题型是“给出文法写出某句子的推导过程”。要理解推导你得先分清两种方向从开始符号出发不断用产生式替换非终结符直到得到目标句子这叫推导反过来从句子出发不断归约回开始符号这叫归约。语法分析的本质就是在做推导或者归约。推导里最重要的概念是最左推导和最右推导。最左推导就是每次都替换最左边的非终结符最右推导则反过来。我当年记这两个概念的时候容易混后来找到了一个很笨但很有效的记忆方法“最左”和“最右”指的是每次被替换的那个非终结符的位置而不是替换出来的结果放在哪里。举个例子有文法S - A B A - a B - b从S出发做最左推导第一步替换S为AB此时最左非终结符是A于是把A替换成a得到aBB再替换成b得到ab。最右推导则是先替换最右边的B再从A推下去。考试里经常让你分别写出最左推导和最右推导并比较它们的异同核心考点就在这个“替换顺序”上。2.2 语法树的画法与二义性判断题的套路语法树是把推导过程图形化的结果根节点是开始符号叶子节点是终结符或者是句子中的词素内部节点是非终结符。画语法树的技巧是直接按产生式展开每一步推导对应一次替换树就长出来了。二义性文法是另一个高频考点。如果一个文法存在某个句子它有两棵不同的语法树等价地有两个不同的最左推导就说这个文法是二义性的。课后习题里最经典的例子就是E - E E | E * E | id这个文法描述加减乘除会出乱子因为字符串id id * id既可以被解析成(id id) * id也可以被解析成id (id * id)算术优先级直接乱了。判断二义性的解题方法有三个层次。第一层次是“看结构”产生式里同一个非终结符递归地出现在自己右边且没有通过分层把优先级分配开多半就有二义性风险。第二层次是“找句子”尝试构造一个句子画出两棵不同的语法树能画出来就直接证明二义性。第三层次是“带条件的判断”有些文法表面上看有歧义但实际上因为额外约束比如结合性声明而没有二义性这种题就要细心了。我在做这类题的时候养成了一个习惯每一个句子都先试最左推导再试最右推导如果在某个句子那里两条推导链不同就锁定了二义性证据。2.3 消除二义性的标准手法考试里如果让你消除二义性最标准的答案思路不是去改语法树而是改写文法。以E - E E | E * E | id为例消除二义性后应该变成E - E T | T T - T * F | F F - ( E ) | id核心手法是引入不同层次的非终结符。加减运算用E表示乘除运算用T表示原子表达式用F表示。推导时E会先“消耗”掉低优先级的再去处理高优先级的*这样乘法的优先级天然高于加法。结合性也是同理E - E T | T这种左递归写法让运算符天然左结合符合算术直觉。碰到“给出二义性文法要求改写为等价的无二义文法”的题目思路就是把优先级和结合性体现在文法层次上。3. 自顶向下分析LL(1)文法的判断与FIRST/FOLLOW集计算3.1 从递归下降到LL(1)为什么需要FIRST集和FOLLOW集自顶向下分析是从开始符号出发逐步推导直到匹配输入串。最简单的实现方式是递归下降每个非终结符对应一个递归函数根据输入token决定走哪条产生式。但问题来了如果文法有公共左因子比如A - ab | ac递归下降分析器看到a的时候不知道该选哪条路这就产生了回溯。更麻烦的是左递归比如E - E T这会让递归函数无限调用自己直接栈溢出。为了消除这些问题编译原理课程引入了LL(1)文法。LL(1)的含义是从左向右扫描输入串第一个L产生最左推导第二个L每一步最多向前看一个输入符号1。LL(1)文法要求对于任意一个非终结符通过查看下一个输入符号就能唯一确定该用哪条产生式。FIRST集和FOLLOW集就是为了判断这个“唯一性”而设计的工具。3.2 FIRST集的手算方法先找终结符再追非终结符FIRST集的定义是对于文法符号串αFIRST(α)是所有能从α推导出的串的第一个终结符的集合。如果α能推导出空串ε那么ε也属于FIRST(α)。手算FIRST集我总结了几个步骤。第一步对所有非终结符先把产生式右部以终结符开头的那些终结符直接加进FIRST集。第二步处理右部以非终结符开头的产生式如果产生式形如A - Bγ那么FIRST(B)里的全部终结符都属于FIRST(A)如果B能推导出ε还要继续看γ的FIRST集。第三步确定哪些非终结符能推导出ε这是最容易漏的地方要专门标记出来。举个例子。考虑文法S - A B A - a | ε B - b求FIRST(A)很简单就是{a, ε}。求FIRST(S)时看S - A BA的FIRST里有a所以a进FIRST(S)因为A可以推导出ε所以要接着看B的FIRST得到b。所以FIRST(S) {a, b}。注意这里b是通过“A推导出空串然后B推出b”这条路径进去的如果A不能推出εb就进不了FIRST(S)。3.3 FOLLOW集的手算方法盯紧产生式右部FOLLOW集的定义是对于非终结符AFOLLOW(A)是在所有句型中紧跟在A后面的终结符的集合。注意如果A是开始符号且出现在句型的最末尾那么输入结束标记$或#也算在FOLLOW集里。计算FOLLOW集有三个规则。规则一把$放进FOLLOW(S)S是开始符号。规则二如果有产生式A - αBβ那么FIRST(β)中除了ε之外的所有符号都要放进FOLLOW(B)。规则三如果有产生式A - αB或者A - αBβ且β能推导出ε那么FOLLOW(A)的全部符号都要放进FOLLOW(B)。第三条规则是初学者最容易漏的。它的逻辑是如果B后面没有东西了或者B后面那些东西可以被“吃掉”变成空串那么B后面实际能跟的符号就是A后面能跟的符号。我把这个过程叫作“FOLLOW传递”。做课后习题时我习惯先把所有产生式列成一排然后逐个看每个非终结符出现在产生式右部的哪个位置接着对“它后面有什么”做判断最后检查有没有需要向左边非终结符“继承FOLLOW”的情况。3.4 LL(1)判断条件与预测分析表构造判断一个文法是否是LL(1)文法核心条件有三条。第一条对于每个产生式A - α | β必须满足FIRST(α) ∩ FIRST(β)为空这就保证了同一非终结符的不同产生式不会因为第一个符号相同而产生冲突。第二条如果存在A - ε这样的产生式那么对于FIRST(A)和FOLLOW(A)必须有FIRST(A) ∩ FOLLOW(A)为空这是因为有空产生式时解析器有时要靠“看后面跟什么”来决定是否走空串分支。第三条一个文法要没有任何左递归和公共左因子。预测分析表是一个二维表格行是非终结符列是终结符包括$。表格里的每个格子存放一个产生式表示在遇到对应输入符号时该非终结符应该展开成什么。构造方法是对每个产生式A - α先求FIRST(α)把该产生式填到FIRST(α)中每个终结符对应的格子里如果FIRST(α)包含ε再把该产生式填到FOLLOW(A)中每个终结符对应的格子里。填完表之后如果任何一个格子里出现了多于一个的产生式就说明文法不是LL(1)的。这个表格直接决定了后续“预测分析程序”的走向课设实验里写的表驱动预测分析程序本质上就是照着这张表做跳转。4. 自底向上分析LR(0)、SLR(1)与冲突处理4.1 从移进-归约到句柄自底向上的直觉自底向上分析是另一种主流方法方向刚好反过来从输入串出发不断找到可以被归约的子串用产生式左部的非终结符替换它直到归约成开始符号。这个过程中每一步归约的“子串”叫句柄handle。如果能每次都准确找到句柄并归约分析就是正确的。移进-归约分析器的核心操作有两个移进就是读入下一个输入符号把它压入栈顶归约就是栈顶的某些符号匹配某个产生式的右部把它们弹出把产生式左部压入。这里有个经典陷阱怎么知道什么时候该移进、什么时候该归约盲目归约可能导致局部看起来合法、整体却推不回去。LR(k)分析器就是通过一张状态转移表和一个栈来自动完成这个决策过程的它每走一步都依据当前状态和输入符号查表决定动作。4.2 LR(0)项目集规范族的构建方法构建LR分析表的第一步是构造LR(0)项目集规范族。所谓LR(0)项目就是在产生式右部的某个位置加一个圆点表示“已经看到了圆点左边的部分还没看到右边的部分”。比如E - E T可以对应三个项目E - .E T、E - E. T、E - E .T、E - E T.其中点在不同位置。圆点在最右边表示这个产生式已经完整匹配了可以归约了这叫“归约项目”。构造项目集规范族的算法核心是一个“闭包”操作。当一个项目中圆点后面紧跟着一个非终结符B时要把所有以B为左部的产生式加进当前项目集并在它们最左边加个圆点也就是B - .γ这种形式。这个操作叫求闭包。接下来根据圆点后面的符号分门别类做状态转移圆点后面是终结符就按该终结符转移是非终结符就按该非终结符转移。反复做闭包和转移直到没有新状态产生最终就得到一整张LR(0)自动机。我初学的时候觉得这个流程很绕后来发现把它类比成NFA转DFA就好理解了每个项目集的闭包等价于ε-闭包转移则等价于读入符号后能到达的所有状态的集合。编译原理课程之所以让你学LR(0)自动机是为了后面构造SLR(1)分析表时你能真正理解“状态”是怎么来的而不是死记表格样式。4.3 SLR(1)与LR(1)的核心区别什么时候用FOLLOW集解决冲突LR(0)分析表有个很大的问题它在归约时不看输入符号只要某个项目集里有归约项目它就会盲目归约导致大量“移进-归约冲突”和“归约-归约冲突”。SLR(1)Simple LR的改进是当遇到冲突时利用FOLLOW集来排除可能性。具体的说如果项目集里有归约项目A - α.只有在当前输入符号属于FOLLOW(A)时才执行归约否则不归约。这样很多冲突就被消解了。但SLR(1)也有局限。有些文法即使在SLR(1)下冲突在LR(1)下却可以无冲突。LR(1)分析对每个项目额外附带了一个“展望符”表示归约时下一个输入符号允许是什么。这个展望符更精确所以LR(1)分析能力更强。代价是状态数量大得多通常会有几千个状态工程上不实用所以实际用的时候往往用LALR(1)Look-Ahead LR它是LR(1)的简化版状态数量与SLR(1)相近分析能力却接近LR(1)。Yacc和Bison这类语法分析器生成器底层用的其实就是LALR(1)算法。考试做题的优先级是先判断文法能不能用LR(0)直接搞定不行就试SLR(1)再不行就上LR(1)。课后习题一般只让你做到SLR(1)为止个别提高题才要求构造LR(1)分析表。构造LR(1)分析表前一定要先算FOLLOW集因为SLR(1)表里归约动作的选择完全依赖它——这是我当时踩过最大的坑FOLLOW集算错一个符号整张表全废。4.4 典型习题构造SLR(1)分析表的完整套路下面用经典文法做个完整示范。给定文法E - E T | T T - T * F | F F - ( E ) | id第一步先把文法拓广加一条E - E目的是让开始符号有一个唯一的接受状态。第二步求所有LR(0)项目集。第三步画出状态转换图。第四步在每个项目集里若圆点后是终结符则在该终结符对应的列填“移进到对应状态”若圆点后是非终结符则填“转移到对应状态”若出现归约项目A - α.则对FOLLOW(A)中的每个终结符所在的列填“用A - α归约”。第五步检查填出来的动作表ACTION和状态转移表GOTO有没有一个格子待多个动作有就是冲突要考虑换别的分析方法。这道题做完你会发现一个规律在含有F - ( E ).的项目集里归约项目要用到FOLLOW(F)而FOLLOW(F)中包含 * $ )这些终结符。有些符号同时还可能触发其他项目要求移进于是冲突就冒头了。真正理解SLR(1)冲突来源的地方恰恰就在这类题目上。5. 课后习题精讲四个高频题型手把手过一遍5.1 题型一给定文法求FIRST集和FOLLOW集这种题属于语法分析的基本功几乎每次考试都有。做的时候按部就班来先标注所有能推出ε的非终结符再算FIRST最后算FOLLOW。以文法S - a S e | B B - b B | ε为例。第一步看哪些非终结符能推出εB能推出εS可以通过S - B再B - ε推出ε所以S和B都能推出ε。第二步算FIRSTFIRST(B) {b, ε}FIRST(S) 包含a来自S - aSe、FIRST(B)里的b因为S能推出ε所以ε也属于FIRST(S)。所以FIRST(S) {a, b, ε}FIRST(B) {b, ε}。第三步算FOLLOW给FOLLOW(S)放入$看S - a S ee跟在S后面所以e进FOLLOW(S)看S - BB在末尾FOLLOW(S)的所有元素都要给FOLLOW(B)所以FOLLOW(B)至少包含$和e。另外FOLLOW(S)里还有a不对a出现在S后面吗没有a在S前面。所以FOLLOW(S) {$ , e}FOLLOW(B) {$ , e}。这类题做完要多检查一遍尤其注意“A在产生式右部末尾”的传递情况。我考前一晚上用十来道题专门练这个把每个符号的FIRST和FOLLOW都仔细推导一遍效果比抄十遍笔记好得多。5.2 题型二判断文法是否为LL(1)文法判断步骤是死的先消除左递归和公共左因子如果存在再计算FIRST集和FOLLOW集最后检查同一非终结符不同产生式的FIRST集是否相交以及存在ε产生式时FIRST和FOLLOW是否相交。有一道很经典的习题是这样的A - a B A A - a A | ε B - b这里A的产生式有a A和ε两条。FIRST(A) {a, ε}FOLLOW(A) FOLLOW(A)因为A在产生式末尾如果FOLLOW(A)里含有a就会产生冲突。考试时这个FOLLOW(A)怎么算要看其他产生式对A的引用。如果某个产生式是S - A a那么a就进了FOLLOW(A)于是FIRST(A) ∩ FOLLOW(A) 非空文法不是LL(1)。这个题极好地考察了“FIRST集与FOLLOW集不交集”这一条。5.3 题型三给定文法构造预测分析表构造预测分析表的核心环节是“面对非终结符和终结符的组合该选哪条产生式”。一旦FIRST和FOLLOW算对填表只是体力活。但如果某个格子出现两条以上产生式那就是LL(1)冲突你需要在答卷上明确指出这表示文法不具有LL(1)性质。我建议做题时先画一个空表行是非终结符列是所有终结符加$然后逐条产生式填。对于产生式A - α若FIRST(α)含终结符a则在格子(A, a)里填A - α若FIRST(α)含ε则在所有(A, b)且b属于FOLLOW(A) 的格子里填A - α。每填完一个产生式都要回头check一遍看有没有格子被填了多次。被填多次的地方就是解“用该文法构造预测分析器是否可行”这类题的关键证据。5.4 题型四LR分析过程中写出分析栈的变化这类题要求你手写输入串的LR分析过程通常给一个已经构造好的ACTION表和GOTO表让你模拟分析栈和输入串的变化。模拟时维护两个数据结构状态栈和符号栈有的教材合二为一。每一步查表如果ACTION[当前状态][当前输入符号]是“移进”就把输入符号和新的状态压栈如果是“归约”就按产生式右部长度弹出栈顶若干项查GOTO表把左部非终结符和新状态压栈如果是“接受”分析成功。有一次我做题做迷糊了把移进符号的顺序搞反了结果分析过程跟答案差了好几步。后来总结出一个小技巧每一步先把当前状态栈的栈顶和输入串的第一个符号单独写出来再考虑该查哪一格。这样不容易乱写字也快。模拟LR分析是考试中比较繁琐但拿分稳的题型练熟后基本是送分题。6. 复习笔记语法分析高频考点速查表6.1 必背考点清单下面这份清单是我当年期末复习时整理的覆盖了语法分析章节最常见的考点考前两天对着过一遍很有用。考点核心要点常见题型上下文无关文法定义四元组终结符、非终结符、产生式、开始符号选择题/判断题推导与归约最左推导、最右推导、句柄大题前几问语法树根为开始符号叶子为终结符画图题二义性存在两棵不同语法树的句子证明/改写题目FIRST集可能推导出的串的首终结符集合计算题FOLLOW集句型中紧跟某非终结符的终结符集合计算题LL(1)条件FIRST集不相交与FOLLOW集无交集判断题预测分析表行列分别为非终结符和终结符构造题LR(0)项目圆点位置决定项目类型构造题SLR(1)用FOLLOW集解决归约冲突构造/判断题LR(1)与LALR(1)展望符、能力与状态数权衡概念选择题6.2 最容易扣分的五个细节细节一忘记给开始符号的FOLLOW集放入$。这个错误非常隐蔽因为有时FOLLOW(S)本身就有内容你光顾着加终结符忘了输入结束标记。考试阅卷时这个$往往是一个扣分点。细节二求FIRST集时忽略空串影响。A - B C这条产生式里如果B能推出εFIRST(A)就还得并入FIRST(C)的内容。漏掉“B推空串进一步看后续符号”这一步答案就会少符号。细节三构造LR(0)项目集闭包时忘了把新的非终结符产生式带圆圈加进去。很多时候写了圆点后面的非终结符但没继续展开它的产生式项目集就不全后面的状态转移也跟着错。细节四SLR(1)的归约动作看FOLLOW集但FOLLOW集本身算错。FOLLOW集错一处ACTION表里归约列的符号就全偏了。所以我在做题时有个原则先单独用一小块地方算FOLLOW算完再回填到表里。细节五二义性文法消除后没有验证新文法和原文法描述的是同一种语言。有些改写虽然消了二义但把能接受的句子集合也改了这在语义上是错的。7. 常见问题与面试向考点7.1 复习时容易卡壳的几个点很多同学会纠结“LR(1)和LALR(1)到底要不要掌握到能手工构造的程度”。我的经验是为了考试重点掌握LR(0)和SLR(1)手工构造LR(1)分析表属于提高题为了工程和面试理解LALR(1)的动机就够。真让你在考场上构造LR(1)分析表状态数会爆炸时间根本不够。但概念题里会问它们之间的关系比如“为什么说LALR(1)是LR(1)的压缩版”“LALR(1)合并状态后可能引入什么冲突”这些要能讲清楚。还有同学经常会问“递归下降和LL(1)有什么关系”。递归下降是一种程序实现方法LL(1)是一种文法性质。理论上任何LL(1)文法都可以写一个不带回溯的递归下降分析程序反过来手写的递归下降分析器如果遇到需要回溯的地方可以看作是试图处理非LL(1)文法。实际工程里很多手写解析器会做一些预读和分支处理本质上就是在LL(1)基础上扩展。理解这个对应关系面试时被问到“你写过解析器吗”就不会发虚。7.2 面试高频问题与答题思路面试题里关于语法分析的提问往往不会太深但会结合工程实践。比如问写一个表达式解析器你会怎么处理运算符优先级这类题我建议从文法和递归下降两个层面回答。先给出分层文法Expr - Term (|-) Term、Term - Factor (*|/) Factor、Factor - number | ( Expr )然后说明用递归下降函数parseExpr、parseTerm、parseFactor分别对应这三层每个函数循环处理同优先级的运算符。这种回答既展示了编译原理功底又表明你真写过代码。问什么是左递归为什么需要消除从产生式A - A α说起指出其会导致自顶向下分析直接死循环。解决方案是改写为右递归形式A - β A、A - α A | ε并说明直接转成右递归后会产生左结合性问题必要时需要语义动作或中间表示来处理结合性。表达清楚“消除左递归是为了适配LL分析方法而LR类方法本身能处理左递归”这个对比基本就能拿到不错评价。问你了解语法分析器生成器吗可以从Yacc/Bison的用法谈起写文法规则用语义动作生成抽象语法树生成器内部处理LR/LALR分析。最好举一个真实的例子比如用Bison解析一个mini计算器或者解析配置文件。只要你能说清“规则由用户提供状态机由工具生成”这个分工面试官就知道你不是只背了概念。8. 实操心得与扩展从课后题到实验室再到工程语法分析的课后习题做完只是掌握了纸面上的套路。我印象里比较深的是第一次做词法分析实验和语法分析实验的衔接词法分析器输出token流语法分析器读入token流构建语法树。一开始我偷懒把词法分析的结果打印到文本文件语法分析再读这个文件后来发现直接通过管道传递更方便。这个看似工程上的小决策其实也体现了“模块间接口设计”的思路语法分析器不关心token是怎么来的只关心token的顺序对不对。如果你正在做一个完整实验项目比如用Java做一个C语言子集的编译器我建议语法树的数据结构提前设计好。每个节点至少要有节点类型、Token信息、子节点列表。用LL(1)做递归下降时节点构造几乎和产生式一一对应用Yacc/Bison生成解析器时每个归约动作里也要new一个节点。提前把节点定义写清楚后面做语义分析和中间代码生成时能少改很多代码。做实验还有一个容易被忽视的问题错误处理。教材里教你构造分析表都是假定输入是合法的但真实输入永远有错误。课堂上说的“恐慌模式”恢复策略在实验里非常好用当预测分析遇到表项为空时不断跳过输入符号直到遇到同步符号比如分号、右括号、$为止。同步符号的选择来自FOLLOW集这正好能把课上学到的FIRST/FOLLOW知识用起来。我个人的感受是语法分析是编译原理课程里承上启下的部分前面词法分析相对独立后面语义分析和代码生成都要建立在语法树之上。如果这块没学扎实后面的实验会越做越吃力。反过来一旦把FIRST集、FOLLOW集、预测分析表、LR自动机这些概念真正吃透了你会发现写解析器不再神秘无论是手写递归下降还是使用解析器生成器都能有自己的判断。希望这篇复习笔记和习题思路能帮你少走点弯路也欢迎你在评论区聊聊自己做题时的困惑。