又到期末复习季编译原理大概是计算机专业里最容易被“预习一下就直接上考场”的科目。它看起来全是抽象名词正规式、NFA、LL(1)、LR(0)、语法制导翻译、三地址码、活性分析……很多人一打开书就蒙了于是选择死记硬背结果拿到卷子发现该算的照样不会算。我带复习时反复强调一句话编译原理的期末考试题型高度固定翻来覆去就是词法分析的自动机构造、语法分析的LL/LR表、语法制导翻译和中间代码、运行环境、优化这几大块每一块都有非常固定的手算套路。这篇笔记就是把这条主线从头到尾捋一遍顺手标出最容易丢分的细节。适合正在突击期末的同学也适合准备考研复试、想快速把知识框架捡起来的人。1. 先建立主线六个阶段各自解决什么、产出什么编译原理零基础复习最忌讳一上来就背概念。你需要的是一张“流水线地图”每一步解决什么问题、输入是什么、输出是什么全串起来之后后面的题自然知道在考哪个环节。1.1 编译过程的“输入-算法-输出”三栏表编译器的整体结构可以拆成六个阶段。期末复习时每个阶段只需要抓住三件事输入、核心算法、输出。阶段输入核心算法输出词法分析源程序字符流正则表达式、NFA/DFA记号流token语法分析记号流LL(1)、LR(1)等语法分析树/推导树语义分析语法分析树属性文法、类型检查带标注的语法树、符号表中间代码生成标注后的语法树语法制导翻译三地址码、四元式优化中间代码基本块、DAG、循环优化优化后的中间代码目标代码生成中间代码寄存器分配、指令选择汇编代码或机器码这张表建议你手抄一遍贴在旁边。复习到哪一章先确认它对应的是表格里的哪一行。很多同学考试时看到“把下面语句翻译成四元式”不知道在考什么其实就是第三行到第四行之间的语法制导翻译。1.2 前端和后端复习时的分界点编译器内部还有一个常用的分界线前端和后端。前端包括词法分析、语法分析、语义分析、中间代码生成主要依赖的是形式语言理论和属性文法和具体机器无关。后端包括优化和目标代码生成需要涉及指令系统、寄存器、寻址方式等机器相关知识。期末考试如果你学校用的是国产教材或龙书风格绝大多数大题集中在前端。后端比如基本块划分、DAG优化、寄存器分配也会考但通常作为一道大题或几道小题出现权重不会超过前端。复习时间紧张时前端优先后端主攻那三种固定套路我会在第六章详细说。1.3 用一行赋值语句把流水线走一遍只看表格还是有点虚我用一行代码走一遍完整流程position initial rate * 60词法分析阶段这行字符流会被切分成记号标识符position、赋值号、标识符initial、加号、标识符rate、乘号*、数字常量60。语法分析阶段这些记号根据文法被组织成一棵表达式树能清楚地看出rate * 60先算然后和initial相加最后赋给position。语义分析阶段编译器会检查position是否已声明、initial和rate的类型是否匹配、60能不能和它们做加法。中间代码生成阶段这棵语法树会变成三地址码t1 rate * 60 t2 initial t1 position t2优化阶段可能会发现某些子表达式可复用或者临时变量可合并。目标代码生成阶段再把它映射成具体的汇编指令。你发现没有整个过程是一个“降维”过程从字符串到记号从记号到树从树到线性指令每一层都在去掉一些无关信息、保留结构信息。复习的时候脑子里有这条线做综合题就不容易卡壳。2. 词法分析正则表达式、自动机与两类必考计算词法分析这块期末出题特别“赏罚分明”会算的送分不会算的连蒙都不知道怎么蒙。主要考两类计算一类是正则表达式转NFA再转DFA另一类是DFA最小化。2.1 为什么先画NFA再转DFA有人会问既然最终程序实现的是DFA为什么不直接从正则表达式构造DFA因为从正则式直接构造DFA在逻辑上很绕而构造带ε转移的NFA有一套机械规则每个正则式都能用基本的子图拼出来并集就是两个子图并联加ε边连接就是串联闭包就是加一个回边。Thompson构造法本质上就是把正则式的“结构”变成“图的拓扑结构”。反过来说NFA的问题是不确定性同一个状态读同一个字符可能转移到多个状态没法直接写成查表程序。所以算法上要走两步先用Thompson构造法得到NFA再用子集构造法把NFA确定化为DFA。2.2 子集构造法的手算模板子集构造法的核心就两个操作ε-closure(T)从状态集合T出发只走ε边能到达的所有状态包含T自身。move(T, a)从状态集合T中任一状态读入字符a能到达的所有状态。然后从初始状态的ε闭包开始对每个输入符号计算move结果再求ε闭包得到新的DFA状态。反复执行直到没有新状态出现。写题的时候建议画一张表DFA状态、对a的转移、对b的转移、是否是终态。这样既清晰又不容易漏状态。我拿经典例子(a|b)*abb演示开头几步。用Thompson构造法得到的NFA状态编号不唯一我们重点看子集构造的节奏。记初始状态为0先算A ε-closure({0}) {0, 1, 2, 4, 7}从A读入a先move得到{3, 8}再求ε闭包得到{1, 2, 3, 4, 6, 7, 8}记为B。从A读入b先move得到{5}再求ε闭包得到{1, 2, 4, 5, 6, 7}记为C。接下来继续对B和C分别读a、b直到闭包稳定。最后含NFA终态10的DFA状态就是DFA终态。这里有一个常见的丢分点ε-closure({0})不是只算第0个状态而是要把从0能通过任意条ε边到达的状态全部算进去。很多同学少算了某个中间状态后面DFA直接错完。算完之后一定要检查一遍“起始状态自身有没有包含进去”。2.3 DFA最小化的标准三步DFA最小化其实就是合并“不可区分”的状态。期末标准答案是三步把所有状态分成两个组终态组和非终态组。对每组内部看读入每个输入符号后分别转移到哪个组。如果一个组内的两个状态对某个符号转移到不同组它们就可区分必须拆分。重复第二步直到所有组都不能再拆。每个组就是一个等价类合并成一个新状态。易错点往往不是算法难而是划分的起点错了。有人上来就按状态编号顺序乱分还有人把所有终态和非终态先不分开直接做划分后面越算越乱。另外最小化后的DFA要记得检查一下终态标识。合并后的组里只要有一个原终态新状态就是终态。漏标终态也经常被扣分。2.4 词法部分的概念复盘词法分析的小题也爱考几个概念。正规式、正规集、NFA、DFA四者关系要熟正规式描述正规集NFA和DFA识别正规集三者能力等价。这个结论看起来简单但选择题经常换个说法来迷惑你。还有词法分析器的输出是记号流不是单词本身也不做语法检查。它只负责识别不负责判断“这句话符不符合语法”后者是语法分析的事。3. 语法分析从First集到LR分析表的完整链路语法分析是期末复习的重头戏分值大、题型多。通常出题顺序是先让你求First集、Follow集再判断是不是LL(1)文法然后可能让你构造LR分析表或模拟分析过程。这整条链是连贯的必须一口气打通。3.1 First集和Follow集的计算顺序First集的定义不用多说关键在算法顺序。我习惯这样算对所有非终结符先看产生式右部的第一个符号。如果第一个符号是终结符直接加入First如果是非终结符把它自己的First集元素加入如果它还能推导出ε就继续看下一个符号。反复迭代直到所有First集都不再变化。Follow集要先算First集因为Follow集中会用到First。具体规则是把结束符$有的教材用#加入开始符号的Follow集。对形如A → αBβ的产生式把First(β)中除ε以外的所有符号加入Follow(B)。如果β能推导出ε那么Follow(A)中的全部符号也加入Follow(B)。看一个期末经典文法E → T E E → T E | ε T → F T T → * F T | ε F → ( E ) | id先求FirstFirst(F) { (, id } First(T) { (, id } First(E) { (, id } First(E) { , ε } First(T) { *, ε }这里要注意E → T E的First就是First(T)因为T不能推出ε。再求FollowFollow(E) { ), $ } Follow(E) { ), $ } Follow(T) { , ), $ } Follow(T) { , ), $ } Follow(F) { *, , ), $ }怎么核对以T为例E → T E让T后面紧跟E的First也就是又因为E能推出ε所以Follow(E)也就是{ ), $ }也要给T。这个“又因为”是考试扣分重灾区很多人只写了丢了后面两个。3.2 LL(1)判定中的隐藏条件LL(1)文法的判定大多数教材用SELECT集来定义同一个非终结符的任意两个候选式的SELECT集交集为空。有的学校还要求会用定义判断即每个产生式右部的First集合两两不相交且如果某个候选式能推出ε还需要First(A)与Follow(A)不相交。上面那个表达式文法E的两个候选式 T E和εSELECT集分别是{ }和Follow(E) { ), $ }交集为空T的两个候选式SELECT集是{ * }和{ , ), $ }交集也为空。所以它是LL(1)文法。预处理那块也有两个固定操作消除左递归和提取左公因子。记住一点只含有“直接左递归”的文法用改写公式即可例如A → Aα | β改成A → βA、A → αA | ε。间接左递归则需要先排序再逐个消除期末一般不会考太复杂但原理要知道。3.3 LR分析表构造一个手工可推完的小文法很多同学一看到LR分析表构造就放弃实际上期末考的LR文法通常都控制规模。我给你一个能完整推完的例子0. S → E 1. E → E T 2. E → T 3. T → id从初始项目S → .E出发求闭包得到I0I0 { S → .E, E → .E T, E → .T, T → .id }对E转移得到I1{ S → E., E → E. T }。注意I1里同时有“接受项目”S→E.和“移进符号”的项目E→E.T它们不构成冲突因为接受只发生在输入为$时。对T转移得到I2{ E → T. }。对id转移得到I3{ T → id. }。然后I1对转移得到I4{ E → E .T, T → .id }。I4对T转移得到I5{ E → E T. }。这样5个状态就构造完了。根据状态转移可以填出SLR分析表。注意规约时要看Follow比如I3里T → id.是规约项目只有当前输入是Follow(T)里的符号时才规约。Follow(T) { , $ }所以id遇到和$都按T → id规约。这句话就是“SLR”的核心用Follow集化解部分冲突。3.4 用分析表模拟一次移进-规约会画表还不够还得会查表模拟输入串的分析过程。输入id id分析栈和输入串的变化如下步骤1 栈: 0 输入: id id $ 动作: 移进 步骤2 栈: 0 id 3 输入: id $ 动作: 按 T → id 规约 步骤3 栈: 0 T 2 输入: id $ 动作: 按 E → T 规约 步骤4 栈: 0 E 1 输入: id $ 动作: 移进 步骤5 栈: 0 E 1 4 输入: id $ 动作: 移进 步骤6 栈: 0 E 1 4 id 3 输入: $ 动作: 按 T → id 规约 步骤7 栈: 0 E 1 4 T 5 输入: $ 动作: 按 E → E T 规约 步骤8 栈: 0 E 1 输入: $ 动作: 接受写这种题时一定要把“栈、输入串、动作”三列写清楚。状态栈和符号栈可以合并写但不要漏状态。动作列宁可多写也不要跳步因为老师是按步骤给分的。最后判断接受时还要看当前状态中是否有S → E.这个接受项目同时输入是$才算接受。3.5 文法分类与LR家族的能力边界期末小题还常考乔姆斯基文法分类和LR家族包含关系。四种文法0型文法短语结构文法能力最强1型文法上下文有关文法2型文法上下文无关文法3型文法正规文法能力最弱。编译器前端主要用2型和3型正规文法描述词法上下文无关文法描述语法结构。LR家族也要分清LR(0) ⊂ SLR ⊂ LALR ⊂ LR(1)能力从弱到强。LR(0)不看任何向前看符号冲突最多SLR用Follow集解决部分冲突LR(1)能力最强LALR是LR(1)的压缩版状态数目和SLR差不多但能力介于SLR和LR(1)之间。很多人误以为LALR和LR(1)完全等价严格说大多数教材认为它们识别同样的语言但LR(1)文法类更大LALR能力更弱。这个说法在不同教材里有细微差别复习时以你们老师课件为准。4. 语义分析与中间代码生成从属性到四元式语法分析告诉你“结构对不对”语义分析告诉你“意思合不合理”。期末这部分主要考属性文法和中间代码生成符号表也会出小题。4.1 综合属性与继承属性怎么区分综合属性是从子节点往父节点传递的属性在产生式左部的非终结符上求值。继承属性是从父节点或兄弟节点往子节点传递的属性。看两个例子E → E1 T { E.val : E1.val T.val }这里的E.val是综合属性因为它由右部E1.val和T.val计算而来。D → T id { id.type : T.type }这里id.type是继承属性类型信息从T传给id。考试时让你“指出哪些是综合属性、哪些是继承属性”你只要记住综合属性“自下而上”继承属性“自上而下”或“从左到右”。一个属性到底是综合还是继承不由它叫什么决定而是由它在语义规则里的位置决定。4.2 SDT动作在分析的哪个时刻执行语法制导翻译方案SDT就是在文法产生式中嵌入语义动作。做题时要搞清楚这些动作什么时候执行。自底向上分析时语义动作一般安排在产生式末尾也就是规约的时候执行。自顶向下分析时一个动作通常安排在该非终结符展开之前或之后执行。很多参考书会写“在合适的位置插入语义动作”复习时不必纠结太深只要会翻译语句就行。期末最常考的还是直接给出语义规则让你求某个输入串的属性值。比如L → En的规则是print(E.val)你会算35的输出是8就够了。4.3 表达式和if语句的中间代码翻译模板中间代码生成是有模板的背熟一个就能套用一片。算术表达式翻译的核心是临时变量分配从左到右每算一个子表达式就分配一个新的临时变量。例如a b * -c d三地址码t1 -c t2 b * t1 t3 t2 d a t3if语句和控制流的重点在跳转。看这个例子if (a b || c d) x y z;带短路求值的三地址码如下if a b goto L2 if c d goto L2 goto L3 L2: t1 y z x t1 L3:注意||的短路翻译左边为真就直接跳转去执行真分支不计算右边。四元式版本同样清晰(1) (j, a, b, L2) (2) (j, c, d, L2) (3) (j, -, -, L3) (4) (, y, z, t1) (5) (, t1, -, x) (6) (label, L3, -, -)很多同学写四元式漏掉第一条跳转或者把goto L3写成了goto L2这是致命的。建议每写一个控制流语句都对着模板检查一遍真出口在哪假出口在哪要不要无条件跳转。4.4 符号表的作用域与类型检查符号表常考的是作用域处理。语言通常有块结构内层可以重定义外层变量。符号表的组织方式一般用链表或哈希表加作用域栈。查找变量时遵循“最近嵌套规则”从当前作用域往外逐层找找到就返回找不到就报“未声明”。类型检查本质是把声明中的类型和表达式运算规则结合起来。比如float和int相加要做类型转换有些考试会让你写类型检查的语义规则本质还是在考综合属性。这块背两个典型规则考试时往里套即可。5. 运行环境与存储管理活动记录、参数传递的必考细节运行环境这一章偏“背”但是背了就能拿分性价比很高。5.1 活动记录里的字段每次函数调用系统要在运行时栈上分配一段空间叫活动记录。不同的教材字段和顺序略有不同但大致包括下面这些东西返回值实参控制链指向调用者的活动记录访问链用于访问外层作用域的变量保存的机器状态返回地址、寄存器值局部数据临时变量小题爱考“访问链和控制链的区别”。控制链管的是“谁调用了我”访问链管的是“我能访问到外层的哪些变量”。尤其是支持嵌套函数的语言访问链必须沿静态外层跳转而不能沿调用链跳转这个点经常出选择题。5.2 四种参数传递对比这一节期末必有一道题。四种参数传递方式传递方式本质swap(x, y)执行后x和y的值传值形参是实参值的拷贝x、y不变传引用形参是实参的别名/地址x、y交换传值结果进入时拷贝值返回时拷贝结果x、y交换一般情况传名每次使用时重新求值实参表达式视实参表达式而定传值和传引用最好区分。传结果要从两个方向记忆拷贝进、拷贝出。传名是最容易被忽略的它有点像宏替换形参每次出现都等价于实参表达式重新计算一遍。如果实参是简单变量x、y传名和传引用的结果一样但如果实参是a[i]而且函数里改了i传名的行为就会非常微妙。期末如果只考简单变量案例记住上面表格够用要考复杂案例一定把“每次使用时重新求值”这句话写上去。5.3 存储区划分与作用域的关系运行时存储可以粗略分成代码区、静态数据区、栈区、堆区。静态变量分配在静态数据区活动记录在栈上动态申请的内存走堆。静态作用域和动态作用域的区别也常考静态作用域看代码嵌套结构动态作用域看调用链。现代主流语言大多用静态作用域复习时能举出一个和它对比的例子即可。6. 优化与目标代码生成三种大题套路优化章节出题相对固定主要三种基本块划分、DAG优化、循环优化。目标代码生成有时候只考寄存器分配的几个概念。6.1 基本块划分先找入口语句基本块是“只能从块首进入、只能从块尾出去”的连续指令序列。划分算法三步找入口语句程序第一条语句条件转移或无条件转移的目标语句紧跟在转移语句后面的语句。每个入口语句到下一个入口语句之前不含下一个入口语句构成一个基本块。根据转移关系画流图每个基本块是节点条件跳转产生两条出边。做这题时最容易把“紧跟在转移后的语句”漏掉。一条条件转移后面那行即使没有被任何地方跳转过去它也是新基本块的入口。很多同学漏了这一步导致后续基本块之间的边画错。6.2 DAG构建与公共子表达式构造DAG时四元式里每个运算如、*对应一个节点变量名挂在节点上公共子表达式共享同一个节点。举个最简单的例子t1 a b t2 t1 c t3 a b t4 t3 * 2t1 a b和t3 a b右部完全相同DAG中共用一个节点。优化后t4直接用t1计算t3若后面不再被使用就可以删除。优化后的中间代码可以写成t1 a b t2 t1 c t4 t1 * 2这里背后是“公共子表达式删除”和“死代码删除”。考试时画DAG要标清叶子节点、运算节点和变量标签散乱地画几个节点是无法得满分的。6.3 循环优化三板斧循环优化常考三个手法代码外提把循环体内每次计算结果都不变的表达式移到循环前面。强度削减把乘法运算改成加法。比如循环变量i每轮加1原来有4 * i可以引入一个新变量t每轮t t 4代替每次乘法。归纳变量消除i和t同步变化如果t只用于控制循环或者提供给别的语句有时可以直接用t代替i把其中一个变量消掉。考试问“以下哪些优化属于循环优化”别犹豫答案就是这三板的变体。问“如何对给定循环做强度削减”要写出引入了哪个新变量、每轮怎么更新。6.4 目标代码生成的常考概念目标代码生成大题如果出通常考寄存器分配。经典方法是活跃变量分析加图染色先分析每个变量在哪些基本块中是活跃的活跃区间重叠的变量不能共用一个寄存器用图染色模型求最少寄存器数。期末一般不会让你完整做一遍图染色更多是考“某个变量的活跃区间”“这两个变量能否共用一个寄存器”这种小问。要是实在没时间复习后端优先级是基本块划分大于DAG大于循环优化寄存器分配看概念即可。7. 考前冲刺把时间花在高频题型上复习到最后比的不是你看了多少页书而是你掌握了多少种“拿分动作”。7.1 用往年试卷做题型权重热力图我建议每个同学都先做一张表格把近三年的期末试卷按题型列出来统计出题次数。你会发现几件事词法分析几乎必有NFA转DFA或最小化语法分析必有First/Follow和LR表构造语义分析必有“生成三地址码或四元式”运行环境必有“参数传递方式”优化必有“基本块划分或DAG”。这些就是第一优先级。剩下的时间再去看概念选择题文法分类、短语与句柄、二义性、活前缀、综合属性与继承属性、符号表作用域。这些内容零散但分值稳定适合考前两三天集中背。7.2 最后四周的复习节奏如果还有一个月节奏可以这样安排第一周过主线把第一章到第五章的例题亲手算一遍。只看不算是复习编译原理最大的坑尤其是First/Follow和LR分析表你以为看懂了一上手必然错。第二周主攻第六章优化和后端把基本块、DAG、循环优化的例题做熟。第三周做两到三套往年卷子按时间限制模拟。做完不对答案先自己找问题。第四周只看错题和背诵型概念。到考前一天把每个计算大题的主要步骤用一页纸写出来相当于给自己出一张“操作手册”。如果你只剩一周压缩成前三天过主线计算题第四、五天做两套卷子最后两天背概念和查漏补缺。时间再紧也至少要把LR分析表构造和中间代码生成这两块练出来它们分值最大且套路最稳定。7.3 考场书写规范与几个隐蔽的丢分点笔试踩过的坑都是血泪这里列一下First/Follow集计算必须写过程。哪怕结果对没有过程也可能被扣步骤分。结束符写法要看老师习惯有的教材用#有的用$。写之前翻一下课件错了会连锁影响Follow集。LR分析表要写“状态动作”两大部分移进、规约、接受、报错四个动作不能漏写。如果是SLR表规约动作要写明“按第几个产生式规约”。模拟分析串时状态栈和符号栈分不清没关系但动作列一定要写清楚“移进、规约、接受”。画DFA、语法树、DAG用尺子画线涂涂改改很容易让阅卷老师看错。写四元式时每一行标上行号跳转目标写清晰。goto L3和if ab goto L2不要混在一起。还有一个小技巧做计算题前先在草稿纸上写一个自己的“公式清单”比如子集构造三步、Follow集三条规则、基本块划分三个入口条件。考试时卡壳就扫一眼清单一般都能救回来。我自己复习编译原理时印象最深的一点这门课不是靠背而是靠“动手算”。哪怕你觉得自己思路全明白了不亲手推一遍First/Follow、不亲手画一张LR自动机考场上一定会卡壳。如果你只剩很少的时间也请保证每天手算两到三个小时。把这套主线捋顺之后你会发现整本教材其实一直在讲同一个故事字符串进来结构建出来含义算出来代码生成出来。把这条流水线装进脑子里期末就没那么可怕了。