编译原理期末复习指南：从词法分析到LR语法分析核心考点

1. 期末复习编译原理的整体思路与取舍1.1 先搞清楚这门课到底在讲什么编译原理这门课很多人一上来就被正则表达式、NFA、DFA、FIRST集、FOLLOW集、LR项目集规范族这些名词砸懵然后开始按章节顺序硬啃结果啃到语法分析就放弃了。我当年也是这么栽过一次后来才想明白问题出在哪——不是内容难而是没建立全局地图就开始钻细节。编译器本质就是一条流水线源代码进来经过词法分析切成一个个单词符号Token再由语法分析组装成语法树接着语义分析检查类型和含义然后生成中间代码做优化最后输出目标代码。整门课就是围绕这条流水线展开的。你复习的时候脑子里要始终挂着这条线每学一个知识点都问自己它在流水线的哪一环解决什么问题。这样一来零散的知识点就有了归属记忆负担会小很多。期末考试的题型其实高度固定无非就是几类给正则表达式构造NFA和DFA、求FIRST和FOLLOW集、构造LL(1)分析表、构造LR项目集规范族和SLR/LALR分析表、写语法制导翻译、生成三地址码、做基本块优化。把这些题型的套路吃透及格甚至拿高分并不难。这份笔记就是按这个思路组织的直接对着考点去补而不是从头到尾重新学一遍。1.2 时间有限时该怎么排优先级期末周时间紧必须做取舍。我的建议是按“性价比”排序而不是按教材章节顺序。优先级最高的是词法分析和语法分析这两块几乎必考而且题型固定、套路清晰投入产出比极高。词法分析的核心就是正则到NFA到DFA再到最小化这一条链练熟三五道题就能形成肌肉记忆。语法分析的重点是LL(1)和LR系列尤其是FIRST/FOLLOW集的求法和LR项目集的构造这两块一定要动手画表光看是看不会的。优先级中等的是语法制导翻译和中间代码生成。这两块理解了属性传递的方向、三地址码的写法基本就能拿分但需要一点练习量来熟悉。优先级相对较低的是代码优化和目标代码生成期末考得相对少把基本块划分、流图、常量折叠、公共子表达式消除、死代码消除这几个概念搞清楚即可深入的部分可以放到考后。至于教材市面上的编译原理教材原理大同小异重点章节集中在词法、语法、语义这几部分。第三版的习题答案网上流传很广做完课后题对答案能快速定位自己哪里理解偏了。有些高校的课件讲义整理得很清楚尤其是词法分析和语法分析部分的例题推导过程比教材更直白可以拿来当速查手册用。1.3 复习节奏怎么安排我实际用下来比较有效的节奏是这样的第一天集中攻词法分析把正则、NFA、DFA、最小化的转换流程完整走一遍手写至少五道题第二天攻语法分析的上半场也就是上下文无关文法、推导、语法树、二义性、FIRST/FOLLOW集、LL(1)分析表第三天攻LR系列重点搞懂LR(0)、SLR(1)、LR(1)、LALR(1)的区别和项目集规范族的构造第四天处理语法制导翻译和中间代码第五天刷历年真题和课后题查漏补缺。这个节奏的前提是你已经上过课、有基本印象只是需要系统梳理。如果你是零基础速成那前两天要压缩到一天把词法和语法分析的骨架先搭起来剩下的靠刷题倒逼理解。别指望一次全懂先会用套路解题再回头补原理这是期末速成最现实的路径。提示复习时准备一张A4纸把编译流水线的六个阶段画出来每复习完一块就在对应位置补关键词。考前一天只看这张纸比翻书有效得多。2. 词法分析从正则到DFA的手把手推演2.1 词法分析到底在干什么词法分析的任务用一句话说就是把一串字符流切分成有意义的单词符号并给每个单词打上类别标签。比如int a 10;这行代码词法分析器要输出int是关键字a是标识符是赋值运算符10是整数字面量;是分号。每个单词用一个二元组表示通常是种别码属性值。为什么要有这一步因为语法分析器不想处理一个个字符它需要的是有结构的单词。词法分析相当于把原始文本“预处理”成语法分析能吃的输入。它需要用到的理论工具就是正规文法、正则表达式和有限自动机。这三者是等价的一个正则表达式可以描述一类单词的模式然后转换成NFA再确定化成DFA最后用DFA写代码或直接用工具生成词法分析器。考试里最常考的就是这条转换链。给定一个正则表达式或者一段单词描述让你构造NFA再确定化为DFA最后最小化。这个过程有固定算法练熟了就是送分题。2.2 正则表达式到NFAThompson构造法Thompson构造法的核心思想是递归地把正则表达式的每个基本操作连接、选择、闭包转换成一个带ε边的NFA片段然后组合起来。基本规则有三条记住这三条就能应付绝大多数题。对于单个字符a构造两个状态一条标记为a的边。对于连接rs把r的接受状态和s的开始状态用ε边连起来。对于选择r|s新建一个开始状态和一个接受状态分别用ε边连到r和s的开始状态r和s的接受状态再用ε边连到新的接受状态。对于闭包r*新建开始和接受状态用ε边绕过去同时从r的接受状态加ε边回到r的开始状态形成循环。我当年做这类题老出错后来发现是漏了ε边。Thompson构造法的一个特点就是大量使用ε边你不要嫌它丑先把结构搭对后面的确定化会自动处理掉这些ε边。练习时建议先写出正则表达式的语法树再自底向上构造这样不容易乱。2.3 NFA确定化为DFA子集构造法子集构造法是词法分析里最考验耐心的部分但步骤非常机械。核心概念是ε-闭包从一个状态出发只经过ε边能到达的所有状态的集合。算法从NFA的开始状态的ε-闭包出发作为DFA的开始状态然后对每个状态集合和每个输入符号计算移动后的ε-闭包得到新的状态集合直到不再产生新集合为止。具体操作时我习惯画一张表行是DFA的状态也就是NFA的状态集合列是输入符号。每一格填move和ε-闭包的结果。填完后凡是包含NFA接受状态的DFA状态都标记为接受状态。这里有个容易踩的坑ε-闭包要反复求到不动点不能只求一层。比如状态集合里有多个状态每个状态经过ε边可能到达新的状态新状态又可能有ε边要把这些都算进去。考试时如果算漏了后面的DFA就是错的整题连锁崩盘。我的办法是先把NFA里所有的ε边单独列出来每次求闭包时对照着查避免遗漏。2.4 DFA最小化Hopcroft算法思路确定化得到的DFA往往状态冗余最小化就是合并等价状态。两个状态等价的条件是对任意输入串它们要么都到达接受状态要么都到达非接受状态。算法是先把状态分成接受状态组和非接受状态组然后不断细分直到每组内的状态对所有输入符号都转移到相同的组。实操时用一张划分表初始划分是{接受状态集合非接受状态集合}然后检查每个组内的状态在某个输入符号下是否转移到不同的组如果是就拆分。反复直到稳定。最后每个组选一个代表画出最小DFA。期末考最小化的概率不算特别高但一旦考到往往是压轴的小题。记住一句话先分终态和非终态再逐步细分。这句话能帮你记住整个算法的主干。2.5 词法分析实验怎么快速搞定如果课程有词法分析实验用Java写一个简单的手写词法分析器是最省事的方案。思路很简单读入源文件字符串维护一个指针跳过空白和注释然后根据当前字符判断是标识符/关键字、数字、运算符还是界符。标识符和关键字的处理是先读入连续的字母数字下划线再去关键字表里查查到就是关键字查不到就是标识符。数字要处理整数和小数遇到小数点继续读。运算符要处理单字符和双字符的情况比如和要区分通常是多读一个字符再看。实验报告里通常要求给出单词种别码表、状态转换图、核心代码和测试结果。状态转换图直接用前面的DFA思想画出来就行核心代码重点是那个主循环和几个判断分支。测试用例记得覆盖关键字、标识符、各种数字、多字符运算符和注释这样报告看起来才完整。注意写实验时不要一上来就追求支持所有语法先把基本单词识别跑通再逐步加。我见过太多人卡在注释处理和字符串字面量上结果主体功能都没做完。3. 语法分析自上而下与自下而上的两条路线3.1 上下文无关文法与语法树基础语法分析的理论基础是上下文无关文法也就是CFG。一个文法由四部分组成终结符集合、非终结符集合、产生式集合和开始符号。推导就是从开始符号出发不断用产生式的右部替换左部的非终结符最终得到一串终结符。最左推导每次替换最左边的非终结符最右推导每次替换最右边的。语法树是把推导过程可视化的工具。每个内部节点是非终结符叶子节点是终结符。最左推导和最右推导对应同一棵语法树只是展开顺序不同。如果一个句子对应两棵不同的语法树这个文法就是二义的。二义性在编程语言里是要避免的因为它导致同一个程序有多种解释编译器无法确定该生成哪种代码。期末常考的是给一个文法和一个句子判断它是否属于该文法画出语法树或者给一个二义文法要求改写消除二义性。消除二义性的常用手段是引入新的非终结符来规定优先级和结合性比如表达式文法里用多个层次的非终结符来区分加减和乘除的优先级。3.2 FIRST集和FOLLOW集手算不翻车的方法FIRST集和FOLLOW集是LL(1)分析的基础也是每年必考的内容。FIRST(A)是A能推导出的所有可能的开头终结符的集合。如果A能推导出ε那ε也在FIRST(A)里。求FIRST集的规则如果X是终结符FIRST(X){X}。如果X是非终结符且有产生式X→Y1Y2...Yk先把Y1的FIRST集去掉ε加入FIRST(X)如果Y1能推出ε就继续看Y2依次类推。如果所有Yi都能推出ε那ε也加入FIRST(X)。FOLLOW(A)是可能在A后面出现的终结符的集合。开始符号的FOLLOW里放结束符#。求FOLLOW时看每条产生式如果A在右部它后面的符号串的FIRST集去掉ε加入FOLLOW(A)。如果A后面没有符号或者后面所有符号都能推出ε那产生式左部的FOLLOW集加入FOLLOW(A)。我算这个的习惯是先把所有能推出ε的非终结符标出来然后逐个产生式扫先算FIRST再算FOLLOW因为FOLLOW的计算依赖FIRST。考试时最容易出错的是漏掉“后面的符号能推出ε”这种情况比如产生式A → B C DB能推出ε那么C的FIRST也要加入A的FOLLOW。这种细节要反复检查。3.3 LL(1)分析表的构造与预测分析LL(1)是自上而下分析的代表名字的含义是从左到右扫描输入、产生最左推导、每次向前看一个符号。它的要求是每个非终结符的产生式右部的FIRST集两两不相交如果某个产生式能推出ε那FIRST集和FOLLOW集也不能相交。构造分析表的规则很直接对每条产生式A→α如果终结符a在FIRST(α)里就把A→α填进M[A,a]。如果ε在FIRST(α)里那对FOLLOW(A)里的每个终结符b把A→α填进M[A,b]。填完后如果某一格有多个产生式说明不是LL(1)文法。预测分析的过程就是维护一个栈初始放#和开始符号。每次看栈顶符号和当前输入符号如果栈顶是终结符就匹配并弹出如果是非终结符就查表展开把产生式右部逆序压栈。这个模拟过程考试常考给你输入串让你写出每步的栈、输入和动作。做这类题时画三列表格最清晰千万别心算容易乱。预测分析表还有一种构造方式是先消除左递归、提取左公因子这是把一个非LL(1)文法改造成LL(1)的标准手段。消除左递归的公式要背熟A → Aα | β改成A → βA和A → αA | ε。提取左公因子是把公共前缀提出来。这两步几乎是固定套路考试遇到改造文法直接套。3.4 LR系列自下而上分析的四种形态LR分析是自下而上分析的主角也是期末的难点。它的核心是识别活前缀通过项目集规范族和移进-归约动作来完成分析。LR分析器有一个状态栈根据栈顶状态和当前输入查动作表决定是移进还是归约。LR(0)项目是产生式右部某个位置加一个点表示已经匹配到哪里。项目集规范族的构造从增广文法的开始项目出发求闭包然后对每个文法符号求转移。闭包的规则是如果项目里点的后面是非终结符B那B的所有产生式对应的项目都要加进来。转移就是点向后移一位。LR(0)的问题是归约不看输入符号容易冲突。SLR(1)的改进是归约时看FOLLOW集只有当前输入符号在FOLLOW(左部)里才归约。LR(1)进一步加强每个项目带一个向前看符号归约时精确匹配。LALR(1)是在LR(1)基础上合并同心项目集压缩状态数同时保持大部分分析能力。这四者的关系和区别是高频考点。记一张表就够了LR(0)最弱SLR(1)看FOLLOWLR(1)看具体向前看符LALR(1)合并同心项。冲突处理原则是移进优先于归约避免悬空else这类问题。提示画LR项目集规范族时每个项目集编号转移用箭头标注文法符号。归约项目要标出来分析表里归约动作填在对应的向前看符号列下。这一步千万别省考试写清楚过程才能拿过程分。4. 语法制导翻译与语义分析4.1 属性文法S属性和L属性语法制导翻译是语法分析的延伸核心思想是给文法符号配属性用语义规则描述如何计算这些属性。属性分两类综合属性和继承属性。综合属性由子节点计算传给父节点继承属性由父节点或兄弟节点计算传下来。S属性文法只用综合属性可以在自下而上分析时顺便计算处理起来简单。L属性文法允许继承属性但要求继承属性只依赖父节点和左边的兄弟节点这样可以一次遍历完成计算。判断一个文法是S属性还是L属性是常考的选择题或简答题记住这两个定义就能判断。属性计算的过程就是给语法树的每个节点填属性值。考试通常给一段语法制导定义和一个表达式让你画出带属性的语法树或者写出每步的属性计算过程。做这种题的关键是分清每个属性的依赖关系先算没有依赖的再逐层往上算不要跳步。4.2 中间代码生成三地址码和四元式中间代码是编译器的“通用语言”与具体机器无关方便做优化和移植。最常见的形式是三地址码每条指令最多三个操作数形如x y op z。还有四元式用(运算符, 操作数1, 操作数2, 结果)表示更规整适合程序处理。生成三地址码的过程通常配合语法制导翻译。比如表达式a b * c按优先级先算b * c得到临时变量 t1再算a t1得到 t2。控制流语句的翻译要复杂一些if-else 要用标号和跳转指令while 要用条件跳转和回跳。考试里常考的是给一个语句或程序段写出对应的三地址码或四元式序列。这个没有捷径就是多练掌握表达式、赋值、if、while、for 这几种结构的翻译模板。我建议把每种结构的标准翻译模式记下来考试时直接套能省很多时间。4.3 语义检查都在查什么语义分析阶段主要做类型检查和符号表管理。类型检查确保运算符的操作数类型匹配比如不能把整数和结构体相加。符号表记录每个标识符的类型、作用域、存储位置等信息供后续阶段查询。期末对这块的考查相对浅通常就是填符号表或者判断类型错误。符号表的关键是作用域的处理进入一个块就压一层离开就弹一层。类型检查的关键是类型相容规则比如隐式类型转换什么时候允许、什么时候报错。这些概念性的内容理解即可不用花太多时间。5. 代码优化与目标代码生成5.1 基本块与流图优化的基础结构代码优化前要先划分基本块。基本块是一段顺序执行、只有一个入口和一个出口的代码序列。划分方法是遇到跳转目标、跳转语句的下一条、或者条件跳转的下一条就切开。每个基本块内部不会跳进跳出。把基本块用有向边连起来就是流图边表示控制流的转移。流图是很多优化的分析基础比如循环识别、活跃变量分析都要基于流图。期末常考的是给一段三地址码让你划分基本块并画出流图。这个按规则切就行注意跳转语句是基本块的结尾跳转目标要单独成块。5.2 常见优化技术速览局部优化里最常考的是常量折叠、常量传播、公共子表达式消除和死代码消除。常量折叠是把编译期能算出的表达式直接算出来比如x 2 3直接变成x 5。常量传播是把已知的常量值代入后续使用。公共子表达式消除是如果两个表达式算的是同一个值第二个直接用第一个的结果。死代码消除是删掉永远不会被执行或结果永远不会被使用的代码。循环优化里有代码外提、强度削弱和删除归纳变量。代码外提是把循环内不变的表达式移到循环外避免重复计算。强度削弱是把乘法换成加法比如i * 4换成每次加4。删除归纳变量是去掉只用来控制循环的变量。考试里通常给一段代码让你指出可以做的优化并写出优化后的代码。做这种题时先划分基本块再逐块找可优化的点最后检查循环层面的优化。把这几类优化记熟基本就能应对。5.3 目标代码生成要点目标代码生成是把中间代码翻译成汇编或机器码核心问题是寄存器分配和指令选择。寄存器数量有限多个变量争用寄存器时就要决定谁留在寄存器、谁溢出到内存。常见策略是图着色法把冲突的变量连成边用最少的颜色着色颜色数对应寄存器数。期末对这块的考查通常停留在概念层面比如问寄存器分配的常用算法、指令选择的原则。把基本概念和流程记住即可不用深入算法细节。6. 期末高频题型与面试题盘点6.1 期末大题的基本套路梳理下来期末大题基本跑不出这几个模板第一题通常是词法给正则或单词描述要求构造DFA第二题是文法题给文法求FIRST/FOLLOW、判断LL(1)或构造分析表第三题是LR构造项目集规范族和分析表第四题是语法制导翻译或中间代码生成第五题可能涉及优化。每道题的解法都是固定的把每类题的步骤背熟、练熟考试时就是套模板加细心。过程分很重要。DFA要画出状态转换图分析表要画完整表格项目集要编号标注转移三地址码要按顺序写。就算最后结果有小错过程写清楚也能拿到大部分分数。我见过有人直接写答案不写过程结果错一个符号就全扣很亏。6.2 面试题里的编译原理考点如果是准备面试编译原理的考查点更偏概念和理解而不是手算。高频问题包括编译的各个阶段都做了什么、词法分析和语法分析的区别、解释器和编译器的区别、LL和LR的区别、什么是语法糖、JIT编译的原理、Java的编译过程等。有个常见问题是“为什么Java是编译和解释结合的”——Java源码先编译成字节码再由JVM解释执行或JIT编译成本地代码。理解这个流程就能串联起前端编译、中间表示、后端优化这些概念。回答这类问题时先讲整体流程再讲关键环节最后点出设计动机逻辑就完整了。6.3 复习时的自测清单考前一天用这份清单快速过一遍正则到NFA的三条规则记住了吗子集构造法会不会漏ε闭包最小化的划分流程清楚吗FIRST和FOLLOW的计算规则有没有遗漏“能推出ε”的情况LL(1)分析表的填充规则记牢了吗LR项目集闭包和转移会不会画SLR和LR(1)的区别说得清吗三地址码的几种控制结构模板记住了吗常见优化技术举得出例子吗。这九个问题都能答上来基本就稳了。7. 常见问题与避坑实录7.1 词法分析最容易翻车的三个点第一个坑是ε闭包求不全。解决办法是每次求闭包时把新加入的状态再检查一遍ε边直到集合不再变化。第二个坑是NFA的接受状态处理。Thompson构造法里闭包和选择操作都会新建接受状态原来的接受状态就不再是接受了这点容易搞混。第三个坑是最小化时分不清哪些状态可以合并。记住等价的条件是“对任意输入串行为一致”实操中用划分法逐步细分就行不要凭感觉合并。7.2 语法分析的高频错误FIRST和FOLLOW集的错误大多来自对ε的处理。一个符号串X1X2...Xn的FIRST集要依次看每个Xi只有当前面所有符号都能推出ε时才继续看下一个。FOLLOW集里如果A后面跟着的符号串能推出ε那产生式左部的FOLLOW也要加进来。这两条规则一定要刻在脑子里。LR项目集构造的错误主要是闭包和转移没搞清。闭包是把点后面是非终结符的所有产生式加进来转移是点向后移一位。构造时先写初始项目集求闭包再对每个文法符号求转移得到新项目集后再求闭包。整个过程耐心画别跳步。7.3 实操层面的经验做三地址码题时先给每个临时变量编号按表达式树自底向上生成逻辑最清晰。做优化题时先划分基本块画流图再逐块找优化点最后看循环。做预测分析模拟时画栈、输入、动作三列一步步来别贪快。考场上时间分配也很关键。词法和FIRST/FOLLOW这类题要快给LR和翻译题留足时间。如果某道题卡住超过十分钟先跳过做后面的回头再啃。很多时候后面的题做着做着前面的思路就通了。这份笔记覆盖的是期末最高频的考点和最容易踩的坑。真正上考场前把每类题手写一遍比看十遍都管用。编译原理不难难的是没找到那条主线。抓住流水线这条线把每个阶段的输入输出和核心算法串起来你会发现它其实是一门逻辑很漂亮的课。