期末复习的节奏一到编译原理永远是软件学院里“让人又爱又恨”的一门课。爱的是它逻辑链条完整、每一步都有章可循恨的是章与章之间环环相扣前面一个概念含糊了后面所有题全部开始飘。习题三恰好是用来“收尾”的一份材料它通常把词法分析到中间代码生成的内容串在一起难度比作业略高题型也更接近期末考试。这篇就拿它当主线把我备考时对重点题型的拆解、容易踩的坑、以及答题时的固定套路一次性捋清楚希望能帮正在刷题的你少走弯路。先说清楚这份复习思路适合谁如果你已经听完了课、但做题总是卡在某个环节比如FIRST集算错、LR(0)项目集画不完整、或者四元式顺序老搞反那这篇就是按“常见丢分点”来组织的。如果你是刚开始复习、还没形成整体框架建议先花20分钟把课本目录过一遍再回来对着这篇逐步推进。1. 复习重点与题型方向习题三应当怎么用1.1 习题三在全课程体系里的定位吉林大学软件学院的编译原理课程整体框架基本是龙书那一套词法分析、语法分析、语法制导翻译、中间代码生成、优化和目标代码生成。习题三所处的位置一般是在语法制导翻译和中间代码生成之后、代码优化之前这意味着它默认你已经掌握了前面所有基础。从这个角度讲习题三不只是一份“课后作业”更像是一座桥把前半程的概念性知识和后半程的工程实现衔接起来。很多同学做这套题时有个误区以为它是单独某一章的练习于是翻着书对着那一章的例题找相似题。实际上习题三的综合性很强一道大题可能同时考察词法分析的正规式转化、语法分析的LL(1)判断、以及中间代码的四元式生成。比如给定一个小型表达式文法先让你消除左递归、再构造预测分析表、最后基于语法制导定义输出三地址码——三个步骤对应三个不同的知识模块。这种综合题的答题逻辑是线性的前面某一步错了后面全部跟着错所以练习时必须强迫自己在每一步都写清楚推导依据不能只写结果。1.2 复习顺序的合理安排我的建议是不要按习题册上的题号顺序做而是按“知识链的依赖关系”来安排复习顺序。先复习词法分析把正规式、NFA、DFA、最小化这四步冶炼成一条流水线再复习语法分析重点放在LL(1)和LR(1)族的构造步骤然后是语法制导定义和翻译方案搞清楚两者之间的区别——前者是抽象的语义规则说明后者是具体的实现动作序列最后才是中间代码生成把前面所有内容落到四元式上。这个顺序好在哪它最大程度避免了“基础概念还没搞懂就强行做综合题”的挫败感。比如你如果没有把FIRST集和FOLLOW集的计算规则烂熟于心做预测分析表时就只能靠猜。如果将复习顺序按照知识依赖关系重新组织你会发现自己对每道题的理解加深了一整层因为你在动笔之前已经清楚这道题在考什么模块、需要动用哪些前置知识。2. 词法分析核心考点与解题套路的拆解2.1 从正规式到NFAThompson构造法词法分析这部分习题三最常见的考法是给出一个正规式让你先构造NFA、再确定化为DFA、最后最小化。正规式到NFA用的是Thompson构造法这个方法本身不复杂核心就是分情况处理三种基本运算连接、选择和闭包。以正规式a(b|c)*为例先为a构造一个基础NFA包含两个状态、一条标号为a的边。再为(b|c)构造两个并列的子NFA分别对应b和c通过一个ε边汇合到一个新的终止状态。对这个子NFA施加Kleene闭包运算增加新的开始状态和终止状态用ε边构成回环。最后将a的NFA与(b|c)*的NFA串接整体完成。这部分容易出错的地方在闭包运算的状态设计。很多人在构造X*时会忘记“可以跳过整个X直接到终止状态”这个选项导致最终NFA少了一条ε边。验证NFA是否正确的简单方法是检查空串ε是否被接受——闭包运算的结果永远能接受空串如果你的构造做不到这一点基本可以断定闭包部分画错了。2.2 子集构造法与DFA最小化NFA转DFA的核心是子集构造法subset construction核心思路就是把NFA状态集合的子集作为DFA的状态。计算每个子集时第一步求ε-闭包第二步根据输入符号求转移后的ε-闭包过程机械、结果确定。DFA最小化则需要注意划分法的正确执行顺序。先根据是否为接受状态画一条分界线然后对每个等价类反复检查对于某个输入符号a组内所有状态经a转移后是否落在同一个等价类中如果分布不一致该组就需要分裂。这里有一个很多人都会犯的细节错误比较状态是否等价时只检查当前分组内的目标状态却忘了目标状态也要在“同一个分组内”而不是“同样都是接受状态”就行。接受状态也可能因为后续转移不同而被进一步划分所以最小化不能停留在第一轮。另外最后别忘了把“不可达状态”删掉这在考试中是既送分又容易大意丢掉的小项。2.3 词法分析器实现中的关键点如果习题三让你写词法分析器的伪代码或模块设计通常不是要你写出一个能够处理所有情况的完整工业级代码而是考察以下几个工程要点超前搜索lookahead的必要性识别关键字和标识符时需要向前多读一个字符才能判断边界。最长匹配原则如果输入串可以匹配多个词素选择最长的那个。状态转换表与驱动代码的分离把分析逻辑做成通用的表驱动形式新加关键词时只需要修改表不需要修改代码。这三个点中考试最常考的是最长匹配原则。给出一段输入串和若干个正规式问你最终词法分析器返回的token序列是什么如果不使用最长匹配ifx会被错误识别成关键字if加标识符x而正确结果应该是标识符。答题时必须描述清楚分析器回退指针的行为。3. 语法分析中的重难点LL(1) 与 LR 系列3.1 消除左递归与提取左因子语法分析的大题第一问往往是“改写文法”。处理左递归时要注意直接左递归和间接左递归的处理方式不同。间接左递归需要先通过代入把所有非终结符之间的间接关系转化为直接左递归再进行消除很多同学只背了直接左递归的消除公式A - Aα | β变为A - βA和A - αA | ε遇到间接左递归就直接懵了。提取左因子则是对A - αβ1 | αβ2这样的情况引入新的非终结符进行提取。关键提醒提取左因子必须在完成消除左递归之后进行这两步不能颠倒因为消除左递归有时会产生新的公共左因子而提取左因子不会产生左递归。如果先把左因子提取了再消除左递归时可能还得重新提取。3.2 FIRST集与FOLLOW集的计算FIRST和FOLLOW是最容易因小失大的计算题。FIRST集计算的规则严格按照定义来终结符的FIRST集合就是自身非终结符的产生式右部如果以终结符开头则该终结符加入FIRST如果以非终结符开头则加入该非终结符的FIRST集如果某个非终结符可以推出ε则继续看产生式右部的下一个符号。FOLLOW集容易出错的地方有三处。第一开始符号的FOLLOW集必须包含$这个不能忘。第二产生式A - αBβ中B的FOLLOW集要加入FIRST(β)除去 ε 的所有元素如果β可以推导出 ε还要把FOLLOW(A)加入FOLLOW(B)。第三产生式A - αB中B在末尾那么FOLLOW(B)必须加入FOLLOW(A)的全部内容。这三处是递推关系需要反复迭代直到所有集合不再变化答题时不能迭代到一半就停下否则结果就不完整。3.3 LL(1) 预测分析表的构造与判断构造LL(1)分析表本质上是对每个产生式A - α为每个a ∈ FIRST(α)在表项M[A, a]填入该产生式如果α * ε还要对每个b ∈ FOLLOW(A)在M[A, b]填入该产生式。这里的易错点是判断“什么情况下填FOLLOW集”只有FIRST(α) 包含 ε 时才需要把FOLLOW(A)中的终结符填入。很多同学在α ε时还会填其他列或者在α不能推出 ε 时也填FOLLOW都错了。判断一个文法是否为LL(1)文法就看分析表中每个表项是否最多只有一个产生式。如果是则回答是LL(1)文法并可以据此构造递归下降分析器或表驱动预测分析器。3.4 LR(0) 项目集族、SLR(1) 分析表LR部分对大多数同学来说是最难啃的骨头但也是考试中区分度最大的题。构造LR(0)项目集族时要记住每个项目集I包含“项目”和“闭包”两层内容先把初始项目S - .S放进去然后求闭包——对于每个形如A - α.Bβ的项目把所有B - .γ项目都加入当前项目集并不断重复直到不再变化。然后根据每个项目集和文法符号计算GO函数得到完整的项目集族。之后判断是LR(0)还是SLR(1)的关键在于分析动作冲突的消除如果某个项目集里同时存在移进-归约冲突看冲突的终结符是否在相应非终结符的FOLLOW集中如果在SLR(1)无法解决不在则可以解决。类似地归约-归约冲突用FOLLOW集判断各个归约项目对应的产生式左部非终结符的FOLLOW集是否有交集。很多同学在构造SLR(1)分析表时忘记处理$列——接受动作acc只出现在S - S.这个项目所在的状态对其他归约项目要在左部非终结符FOLLOW集中的所有终结符包括$所在列填入rj。这个步骤遗漏率极高写完表格后建议花30秒整体扫一遍看是否有状态在$列上该填r却空着的情况。4. 语法制导翻译与中间代码生成4.1 语法制导定义 vs 翻译方案语法制导定义SDD是对文法产生式附加语义规则它是抽象的、不规定计算顺序的。翻译方案SDT则是在产生式右部中嵌入语义动作用花括号标出它是具象的、可执行的。考试时如果题目问“给出语法制导定义”只需要写清楚每个产生式的语义规则公式如果问“给出翻译方案”则要把动作嵌入到产生式的相应位置。这两者的区别从概念上就决定了答题规范。语法制导定义可以只有产生式和语义规则两列但翻译方案必须有动作嵌入的具体位置。要求给出SDT时你写个SDD上去哪怕语义规则完全正确也会因为形式不对被扣分。平时做题时就要养成“先看问什么再选择形式”的习惯。4.2 四元式与三地址代码的生成中间代码生成的大题基本围绕赋值语句id : expr和布尔表达式展开。用SDT生成三地址码时核心是引入临时变量。以a : b * c d为例先翻译b * ct1 : b * c再翻译t1 dt2 : t1 d最后赋值给aa : t2这里的细节在于“临时变量的编号顺序”——必须与语义动作的执行顺序一致。你不能先算加法再算乘法因为那样会产生错误的依赖关系。一个实用的检查方法是把生成的三地址码按顺序读一遍看每个临时变量是否在使用前一定被赋值如果在使用t2时t2还没出现那说明翻译顺序错了。布尔表达式的翻译相对更复杂一些因为它涉及回填backpatching。习题三如果涉及通常会给你一个带||和的布尔表达式让你列出代码并标注真/假链。回填的核心思想是先为跳转指令留下空白等目标地址确定后再回填。4.3 声明语句的翻译和过程调用声明语句的翻译考点集中在符号表和相对地址的计算。例如过程内声明若干变量要求你为每个变量分配相对地址偏移。这里需要区分静态分配和栈式分配静态分配用绝对地址栈式分配用相对地址offset且在过程调用时还需考虑活动记录activation record的布局。过程调用语句翻译成三地址码时需要先计算实参的值、压入参数区然后跳转到被调用过程的起始地址。这里容易漏掉的步骤是“保存返回地址”和“恢复调用者的运行环境”。有些教材把这部分纳入代码生成范围习题三往往作为加分项出现理解活动记录的结构比死记动作序列更重要。5. 代码优化与运行时环境容易被忽略的提分点5.1 基本块划分与DAG优化习题三的末尾经常会附带一道代码优化的小题常见形式是“把以下三地址码划分成基本块并对每个基本块应用DAG优化”。虽然分值不高但它考察的是整条知识链的完整性。基本块的划分规则是第一个三地址码语句是入口语句任何跳转语句的目标语句是入口语句跳转语句之后的第一个语句也是入口语句。从入口语句到下一条入口语句之间的连续语句属于同一个基本块。DAG优化需要为每个变量和运算建立节点。构建DAG时同一个操作的公共子表达式会合并为同一个节点局部变量在离开基本块后不再活跃时可以删除对它的赋值常量表达式可以在编译期间就计算好。这就是所谓“删除局部公共子表达式、删除无用赋值、常量折叠”三项优化。做DAG优化的一个关键要求是你必须保留对基本块出口处活跃变量的最终赋值不然优化就会把有用的语句也删掉。判断活跃变量需要用到数据流分析期末考试通常不会让你完整计算活跃变量集合而是预先给出哪些变量是活跃的你根据给出的信息做优化即可。5.2 寄存器分配与存储组织寄存器分配在本科编译原理期末中很少单独出大题但有可能出现在选择题或填空题中。最需要记住的是简单寄存器分配算法为每个在基本块中计算出的新值分配一个寄存器当寄存器不够时选择已分配寄存器中“下次使用最远”的变量进行溢出。这个策略在考试中用来分析一个具体基本块“需要多少个寄存器”非常有效。存储组织方面要清楚堆和栈的区别、静态区和动态区的区别。栈式存储中活动记录包含返回地址、静态链、动态链、参数、局部变量和临时变量偏移量的计算通常是从活动记录的某个基点如指向本活动记录的SP或FP进行加减。如果一个过程的局部变量和参数比较多考题可能要求你填写不同变量对应的偏移量这时画一个活动记录布局图就是最快也最稳妥的办法。5.3 从习题三反推期末出题偏好仔细观察习题三里优化题的分布可以发现它倾向于考察“能用手算验证”的优化比如DAG、基本块划分、活跃变量。像循环优化中的代码外提、强度削减这类题目手算复杂度高且容易出错一般不会作为期末大题出现。因此在复习优化章节时可以分配较多的时间在DAG构建其他优化只需要了解原理。6. 考前避坑指南与临场经验6.1 作业题与期末考试题的差异习题三里的题目风格整体比平时作业更接近期末考试但还是有所不同。平时作业允许你翻书、查笔记、慢慢推演期末考场时间紧张要求你迅速判断题型并调用对应的解题模板。平时做习题三时就要模拟考场节奏每道大题限时10到15分钟时间一到即使没做完也要停笔然后对照标准答案找薄弱环节。另外习题三偶尔会有一两道“陷阱题”表面上考A知识实际需要先转化为B知识才能求解。比如给出一个文法让你判断是不是LL(1)文法你可能需要先消除左递归再做判断因为该文法原本含有左递归根本就不是LL(1)文法的候选者。考试时若发现某题条件诡异多半是暗示你需要先做变换。6.2 常见扣分点与避免方法我将常见扣分点和对应的避免方法整理如下题目类型常见扣分点避免方法消除左递归忘记处理间接左递归先画依赖图标出所有间接关系再统一消除FIRST/FOLLOWFOLLOW集漏掉$或忘了顺推按固定步骤先算FIRST再算FOLLOW最后统一增补检查预测分析表有ε产生式时忘记填FOLLOW每填一个产生式前自查“FIRST(α)含不含ε”LR项目集闭包没有求完整每新增一个项目必须检查右部点号后是否为非终结符SLR分析表归约项目漏填FOLLOW列用已算好的FOLLOW集逐一对齐填表四元式生成临时变量编号顺序错按“先算深度更深的后算深度更浅的”规则产生新临时变量DAG优化删除活跃变量的赋值构建DAG前先确认基本块的活跃变量集合这张表是我复习到后期自己总结的也是我在刷题时反复出错的几个位置。如果你做题时也总是“差点意思”可以对照检查一下自己是不是踩在同一类坑上。6.3 考场时间分配与做题顺序如果期末试卷结构稳定一般会有选择填空、简答、计算大题和综合设计题四类。以100分钟为例我自己的分配方案是前20分钟解决所有选择和填空题不会的先跳过回头再补中间60分钟集中攻克计算大题优先做自己最有信心的题型比如FIRST/FOLLOW和预测分析表、四元式生成这些题型模板化程度高容易拿分最后20分钟用于综合设计题和补漏。这里特别想提醒一点不要在LR分析的某一小问上死磕超过15分钟。LR项目集的构造工作量很大一旦某一子集求错后续分析表全部报废性价比很低。遇到这种情况先把能拿到的步骤分拿到手比如前面构造的项目集、GO函数、状态的识别写清楚推导过程即使最后分析表填错了评卷时也会给一定的步骤分。作为过来人我的真实感受是编译原理期末复习拼的不是智商而是“熟练度”。习题三里的每一道题都是一个“套路”而这些套路一旦被拆解、练熟你会发现它们互相之间是贯通的——词法分析中的DFA最小化、语法分析中的SLR表构造、中间代码生成中的回填本质上都在做同一件事把自然语言描述的语法规则一步步变成计算机可以执行的动作序列。刷这一套题的时候如果能体会到这种“贯穿感”那期末复习就算是真正到位了。最后再分享一个小技巧做完每一道大题后不要直接对答案先给自己1分钟时间复述解题步骤——从题目条件出发到关键步骤再到最终结果。说得出来说明你真的掌握了说不出来那这个知识点就是你的盲区趁考前赶紧补。这个方法帮我考前至少发现了三个自以为会、其实不会的知识点希望你也能用上。祝考试顺利。