又到期末复习季，编译原理大概是计算机专业里最容易被“预习一下就直接上考场”的科目。它看起来全是抽象名词，正规式、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先求First：
First(F) = { (, id } First(T) = { (, id } First(E) = { (, id } First(E') = { +, ε } First(T') = { *, ε }这里要注意E → T E'的First就是First(T)，因为T不能推出ε。再求Follow：
Follow(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出发，求闭包得到I0：
I0 = { 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)，你会算3+5的输出是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 a<b goto L2不要混在一起。
还有一个小技巧：做计算题前先在草稿纸上写一个自己的“公式清单”，比如子集构造三步、Follow集三条规则、基本块划分三个入口条件。考试时卡壳就扫一眼清单，一般都能救回来。
我自己复习编译原理时印象最深的一点：这门课不是靠背，而是靠“动手算”。哪怕你觉得自己思路全明白了，不亲手推一遍First/Follow、不亲手画一张LR自动机，考场上一定会卡壳。如果你只剩很少的时间，也请保证每天手算两到三个小时。把这套主线捋顺之后，你会发现整本教材其实一直在讲同一个故事：字符串进来，结构建出来，含义算出来，代码生成出来。把这条流水线装进脑子里，期末就没那么可怕了。
