编译原理复习提纲：从词法分析到代码优化的流水线地图

如果让我用一个词概括编译原理这门课，我选“流水线”。2025年春季学期这门课结课后，我花了一周把全学期的笔记、作业、往年卷重新过了一遍，整理出这份核心提纲。初衷很简单：给复习备考的同学一份能直接照着用的地图，而不是又一本把所有细节都堆上去的教科书。这门课的知识量确实大，从正则表达式到DFA，从LL(1)到LALR，从属性文法到四元式，最后还要碰数据流分析和寄存器分配，任何一个环节掉链子，后面都会像多米诺骨牌一样跟着崩。但好消息是，编译原理非常适合结构化复习——每个阶段都有非常明确的输入、输出和标准算法，考点高度稳定，甚至可以说比操作系统和计算机网络更好押题。这份笔记适合正在学编译原理、准备期末或者补底层功底的读者，粗略算下来，按照这份提纲把例题过两遍，再刷三套卷子，基本盘就稳了。

1. 先建立全局地图：编译器就是一条逐级加工的流水线

1.1 一条语句从源码到目标代码的完整旅程

很多同学学编译原理容易陷进某个算法里出不来，比如在LR(1)项目集的构造上死磕了一下午，回头却不知道这个项目集在整个编译器里是干什么的。我建议第一件事不是背算法，而是把编译器的阶段划分刻在脑子里。最简单的划分是四个阶段：词法分析、语法分析、语义分析和中间代码生成、代码优化与目标代码生成。前三个阶段通常叫前端，负责把源代码“读懂”并翻译成一种与机器无关的中间表示；后端负责优化并生成目标机器的指令。

拿一条语句举例：position = initial + rate * 60进入编译器后，词法分析先把字符串切成记号流：标识符position、等号、标识符initial、加号、标识符rate、乘号、整数常量60。语法分析拿到记号流，按照文法把它组织成一棵语法树，树的内部节点是文法非终结符，叶子节点是终结符。语义分析在这棵树上做类型检查、作用域检查，并伴随着翻译动作，生成中间代码。最后后端把中间代码优化并映射成目标机器指令。这里我希望你记住一个关键点：编译器的每个阶段本质上都是一个“读入一种表示、输出另一种表示”的转换器，源程序的全部信息在每个阶段被逐步压缩和抽象。

1.2 用“厂房流水线”类比理解阶段耦合

可以把编译器想象成一条汽车装配流水线：词法分析是零件分拣——把散落在地上的零件（字符）按类型放进不同料箱（记号）；语法分析是骨架焊接——结构不对的零件组合到不了下一道工序；语义分析是质检和贴标签——给每个组件标上类型和作用域信息，不合规就退回；中间代码生成是给流水线拍了一张标准图纸；优化阶段是调整工序，减少无效动作；最后代码生成是真正的总装下线。这个类比的用处在于：一旦某个阶段出了问题，你要能判断问题出在哪道工序。比如看到“语法错误”提示，可能是词法阶段记号切错了，也可能是文法设计有问题；看到“类型不匹配”，问题基本确定在语义阶段。复习的时候我习惯拿一个真实编译器（比如GCC或者Clang）的命令行参数来对照：-E只做预处理，-S输出汇编，-c生成目标文件。你能直观感受到每个阶段确实存在，而且可以独立输出。

2. 词法分析：正则、NFA、DFA的推导套路与踩坑点

2.1 正则表达式是词法规则的语言，优先级别弄反

词法分析的核心是让计算机理解“什么样的字符序列是一个合法的记号”。最方便的描述工具是正则表达式。一个易错点：正则表达式里的三种基本运算——闭包*、连接、并|——优先级依次降低。a|bc*的意思是a或者b后面跟零个或多个c，而不是(a|b)c*。考试里经常拿这种式子考基本概念，一眼看错整个DFA就废了。另一个容易忽略的点是正则表达式只能描述正则语言，它描述不了“成对括号匹配”这类嵌套结构，这正是后面语法分析要引入上下文无关文法的根本原因。

词法规则里还有一个“最长匹配”原则，虽然不考推导，但理解它对做题很有帮助。比如输入是if8，词法分析不能只识别出if就停下来，而要继续读入8，把它们组合成一个标识符if8。如果输入是if后面紧跟空格，才识别为关键字if。很多同学在构造DFA时容易忽略这个策略，导致在“标识符 vs 关键字”的区分上懵圈。通常的做法是：把所有关键字单独列出来，词法分析器先识别标识符，再查关键字表，查得到就标记为关键字，查不到就是普通标识符。

2.2 从正则到最小DFA的三步走

词法分析大题基本固定：给你一个正则表达式，要求画出NFA，再确定化为DFA，最后最小化。这三步必须连贯熟练，任何一个环节卡住都拿不到分。第一步用Thompson构造法：基本正则表达式对应基本的NFA片段，然后通过ε转换把片段拼起来。ε在这时候的作用就是“无代价跳跃”，把各个部分的入口和出口连接在一起。

第二步用子集构造法把NFA转成DFA。核心是两个集合运算：ε-closure(状态集合)表示从集合中状态出发，只沿着ε边走能到达的全部状态；move(状态集合, 字符)表示从集合中状态出发，读入一个字符后能到达的状态集合。DFA的每个状态都是一个NFA状态集合，所以转换结果本质上是一张状态转移表。第三步用划分法最小化DFA：先把状态分成终态组和非终态组，然后反复检查同一组里的状态读入相同字符后是否落在同一个组，不在就拆开，直到所有组不能再拆。这样每组保留一个代表状态即可。

下面给一个非常典型的例子。识别带符号整数的正则表达式是(+|-|ε)[0-9]+。从NFA开始，构造过程大致是：开始状态S通过ε分三条支路——+、-、直接走数字；+和-之后都进入同一个中间状态，再通过ε进入数字循环；数字循环是一个自环[0-9]，最终态在接受一个或多个数字后到达。子集构造后的DFA状态转移表如下：

这个DFA本身已经是最简的，因为三个状态读入字符后的归属都不相同。如果题目给的是0(0|1)*01这类式子，最小化阶段就有文章可做了，通常要把终态组内部的差异慢慢拆出来。

2.3 词法分析最常见的三种失分方式

失分方式一：ε-closure漏算自己。ε-closure({S})必然包含S本身，因为不需要走任何边就能到达自己。很多人一上来就数ε边，把自己给忘了。失分方式二：NFA转DFA时，每个新DFA状态必须重新计算ε-closure，不能直接拿上一个状态的move结果当新状态。失分方式三：最小化时只看一步转移，没有把“经过一行字符后是否落在同一组”当作划分依据。划分离线条件是对组内所有状态、所有输入符号都检查一遍，只要有一个符号的转移目标不在同一组，就要拆分。

我复习时的经验是：把教材里所有涉及正则、NFA、DFA的例题全部亲手做一遍，而不是用眼睛看。这三步只要动手做十道以上的题，基本不会出错。做题时用铅笔在状态图上标组号，最小化过程的每一步都能看得清清楚楚。词法分析这一章是整门课里“投入产出比”最高的一块，花一天时间吃透，考试至少能锁住十五到二十分。

3. 语法分析的重头戏：LL(1)与LR家族

3.1 First集和Follow集的正确算法与陷阱

语法分析的目标是判定记号流是否符合文法。自上而下分析的代表是LL(1)，自底向上分析的代表是LR家族。无论哪个方向，先决条件都是会算First集和Follow集，这是每年必考的基础题，也是很多人的丢分点。First集的定义是：从某个文法符号出发，能够推导出的所有终结符串的第一个终结符集合。计算时要反复迭代到不动点。一个需要注意的坑：如果一个非终结符能推导出ε，那么ε要放进它的First集，但使用First集判断产生式时要把ε单独处理。

Follow集的定义是：在文法的所有句型中，紧跟在某个非终结符之后可能出现的终结符集合。计算规则有四条：第一，开始符号的Follow集一定包含结束符$；第二，如果产生式形式是A → αBβ，把First(β)中除ε以外的所有符号加入Follow(B)；第三，如果β能推导出ε，把Follow(A)加入Follow(B)；第四，如果产生式形式是A → αB，即B后面什么都没有，同样把Follow(A)加入Follow(B)。最容易错的是第三条，很多人只记得First(β)，忘了β → ε时要继承Follow(A)。

看一个标准例子。文法（已消除左递归）：

E → T E' E' → + T E' | ε T → F T' T' → * F T' | ε F → (E) | id

First集为：

First(E) = First(T) = First(F) = { ( , id } First(E') = { + , ε } First(T') = { * , ε }

Follow集为：

Follow(E) = { $ , ) } Follow(E') = { $ , ) } Follow(T) = { $ , ) , + } Follow(T') = { $ , ) , + } Follow(F) = { $ , ) , + , * }

这里Follow(T)为什么有+？因为产生式E' → + T E'中，T后面跟着E'，而First(E')里有+，所以+进Follow(T)。Follow(F)里的*来自T' → * F T'，*本身是跟在F后面的终结符。每次算完可以互相验证：一个非终结符的Follow集不应该包含它自己，除非文法有特殊设计，否则大概率算错了。

3.2 LL(1)判定与预测分析表构造

LL(1)的含义是：从左向右扫描输入，产生最左推导，每一步只需向前看一个符号。判断一个文法是否是LL(1)，核心看两条：第一，同一非终结符的任意两个不同产生式，它们的First集互不相交；第二，如果某个产生式能推导出ε，它的First集不能和该非终结符的Follow集相交。这两条只要有一条不满足，文法就不是LL(1)。左递归文法一定不是LL(1)，因为同一个非终结符的First集必然重叠，所以做题第一步永远是消除左递归、提取左因子。

构造预测分析表的算法也很固定：对每个产生式A → α，如果终结符a属于First(α)，就在表[A, a]位置填入这个产生式；如果α能推导出ε，则对Follow(A)里的每个终结符b，在[A, b]位置填入该产生式。表里同一个格子出现两个产生式，就说明文法有冲突，不是LL(1)。用上面的表达式文法，预测分析表关键位置长这样：

这个表填写的过程就是LL(1)分析的灵魂。真正分析时，只需要一个栈存文法符号、一个输入缓冲区存记号流，查表决定用哪个产生式展开。考卷上的预测分析过程题，本质上是在模拟栈和输入的匹配过程，只要表构造对了，过程题基本是送分题。

3.3 LR(0)、SLR(1)、LR(1)、LALR(1)一次理清

LR分析是自底向上分析，从输入串开始不断归约，最后归约回开始符号。它的核心数据结构是“项目”——在产生式右部的某个位置放一个圆点，表示当前分析进度。比如E → E · + T表示已经看到E，期望接下来看到+。LR(0)项目集规范族是基础，但通常不够用，因为会出现“移进-归约冲突”（一个项目说该移进，另一个项目说该归约）。

四种LR分析法的区别可以用一张表理清：

SLR(1)的做法是：当LR(0)项目集中出现移进-归约冲突时，只有当当前输入符a属于Follow(A)时，才执行归约，否则移进。这能解决一部分冲突，但解决不了的场景依然存在。比如文法S → L = R | R、L → * R | id、R → L，SLR(1)会在某个项目集里出现冲突，因为Follow(L)和Follow(R)有重叠。LR(1)给每个项目增加一个向前看符号，归约时必须满足当前输入符号等于该项目的向前看符号，冲突瞬间被精确区分。但LR(1)的项目集会爆炸式增长，所以LALR(1)把“核心相同、向前看符号不同”的项目合并，在显著缩小分析表的同时，分析能力已经覆盖绝大多数程序设计语言的文法。YY中的LALR(1)文法冲突则用优先级和结合性声明来解决，考试里如果考到，通常只需要你判断冲突类型，并说明用优先级如何消解。

3.4 表驱动分析和冲突处理

LR分析表分两部分：ACTION表以“状态+终结符”为索引，GOTO表以“状态+非终结符”为索引。分析时维护一个状态栈和一个符号栈（其实就是状态栈隐含了符号栈），每次读入一个输入符号查ACTION表：表中是s开头的动作就移进，是r开头的动作就按第几条产生式归约，是acc就接受，空就报错。这一套流程考得非常多，但本身不复杂，复杂的是构造那张表。

造表时的冲突处理是高频考点。移进-归约冲突的经典场景是表达式文法中运算符优先级和结合性没有声明清楚。比如E → E + E这种文法，遇到+后面的输入也是+时，既可以把E+E归约成E，也可以继续移进+。如果是左结合的+，应该选择归约；如果是右结合的赋值运算符=，应该选择移进。考试中如果给出一个冲突状态，通常要根据运算符的优先级和结合性给出处理方案。归约-归约冲突则一般出现在两个非终结符有相同右部的场景，比如A → id和B → id同时可归约，需要通过向前看符号判断哪个更合适。我复习时的经验是：把LR(0)项目集规范族的构造练到不用翻书就能推，SLR(1)和LR(1)的差别自然就能体会出来。

4. 语义分析与中间代码：四元式翻译的拿分模板

4.1 属性文法考什么：综合属性与继承属性

语义分析阶段要回答“这段代码什么意思”。最通用的形式化工具是属性文法——在上下文无关文法的基础上，给每个文法符号挂上若干属性，属性之间用语义规则关联。综合属性的计算方向是“自下而上”的，子节点的属性先算出来，父节点的属性依赖子节点；继承属性则是“自上而下”的，父节点先有值，子节点从父节点继承。经典例子是表达式求值：每个表达式节点的“值”属性由子表达式节点的值运算得到，这是综合属性。类型检查的例子也常考：E → E1 + E2要求E1和E2的类型都是int，则E.type = int，否则报错。

这里有一个复习重点：S属性的SDD（语法制导定义）可以直接用自底向上的分析器实现，因为所有属性都是综合属性，在归约时就能计算。L属性的SDD则适合在自顶向下分析中实现，继承属性在展开产生式时传递。考试通常不会让你实现整个分析器，而是给一小段文法加语义规则，让你画出某棵语法树的属性计算过程。这种题唯一的技巧是搞清楚计算的先后顺序：综合属性的计算必须在所有子节点分析完成后进行，所以画依赖图时箭头方向要画对，依赖图中出现环就说明属性规则定义有误。

4.2 中间代码与四元式的通用翻译模板

中间代码有很多形式：三地址码、四元式、三元式、间接三元式、后缀式等。考试范围通常是四元式，因为它的结构最规整：(op, arg1, arg2, result)。四元式的优点是每个运算只包含一个操作符和至多两个操作数，非常适合描述“每条指令只做一件事”的风格。翻译的核心是“开临时变量”，比如表达式a + b * c翻译成四元式：

(*, b, c, t1) (+, a, t1, t2) (=, t2, _, a)

临时变量t1、t2按顺序编号，不可复用。这一小段几乎覆盖了所有赋值语句翻译的套路。数组元素访问稍微复杂一点，比如A[i] = x需要根据数组首地址和元素宽度计算实际地址，通常用(*, i, 4, t1)这类四元式计算偏移，再用(=, x, _, A[t1])表示赋值。考试中如果给了一个二维数组，题目会提供行列数和存储方式，牢牢抓住“地址 = 首地址 + 行号 × 每行宽度 + 列号 × 元素宽度”就行。

控制流语句的翻译是另一个必考模板。if (a > b) S1 else S2可以翻译成：

(j>, a, b, L1) (j, _, _, L2) L1: S1的四元式序列 (j, _, _, Lnext) L2: S2的四元式序列 Lnext: 后续代码

while (cond) S的翻译模板稍有不同：条件不满足时跳出循环，条件满足时执行循环体再跳回条件判断的开头。标号L1、L2通常由课堂规定或题目要求决定，没有统一标准，但跳转目标必须与标号一致。

4.3 布尔表达式翻译与回填技术

布尔表达式a < b or c < d的直接翻译是产生一组带跳转的四元式，而不是先算出布尔值再判断。这样做的原因是短路计算——or左边为真时右边不必再算。翻译时，每个布尔表达式会附带两个标号：真出口和假出口。问题在于，生成四元式时，两个出口的跳转目标可能还没生成，这就引出了回填技术。回填的意思是：先把跳转指令的目标字段空着，记下一个待回填地址列表，等目标标号确定后再回头填入。

这个考点看起来抽象，但考题形式很固定：给一段带嵌套if和while的代码，要求翻译成四元式并回填标号。解题步骤一般是先给每个基本块分配标号，然后从前到后扫描，遇到条件跳转就生成带空缺目标的四元式并记录跳转列表，遇到标号确定的地方就把该列表中所有四元式的目标字段填上。我自己做题习惯是先写出每条语句对应的四元式骨架，再用箭头把跳转目标连一遍，最后才写标号，这样不容易漏跳转。考试时最怕的不是不会回填，而是临时变量编号和标号编号混在一起导致后面全乱，建议编号用不同前缀区分，比如t1、L1、L2，一眼就能看出类型。

5. 代码优化与目标代码生成：常考题型与基本盘

5.1 基本块、流图与DAG优化

代码优化的对象通常是中间代码。第一步是划分基本块：找入口语句——代码的第一条语句、跳转目标语句、跳转指令后面的第一条语句。每个基本块内部是顺序执行的直线代码，没有入口和出口分支。基本块之间用流图连接，节点是基本块，边代表控制转移。这个划分过程几乎年年考，把它练熟之后，后面的优化才能展开。

DAG（有向无环图）优化是代码优化章节里性价比最高的部分，因为它本质上是个“合并同类项”的算法。构建DAG时，每个变量和常量对应一个叶子节点，每个运算对应一个内部节点。如果两个运算的操作符相同、操作数相同，新运算可以复用已有节点，这就是公共子表达式消除。看经典例子：

a = b + c b = a - d c = b + c d = a - d

构建DAG后会发现，第二条和第四条语句都是a - d，可以共享同一个减法节点。优化后的结果是：

t = a - d b = t c = t + c d = t

第一条a = b + c不会被删除吗？注意看，优化前d = a - d中的a是第一条语句的结果，优化后第一条既然没有被后续使用，有些题目会要求你也可以删除它。这种题就是考你对DAG节点的“活跃性”有没有概念：一个节点如果不再被后续引用，就可以不生成对应代码。我在做这类题时的策略是先把原始DAG画全，再标记哪些变量在基本块出口处仍是活跃的，然后从叶子往上扫描可复用的运算节点，最后按拓扑序生成中间代码。

5.2 数据流分析考到什么程度

数据流分析是优化的重要支撑。常考的分析包括到达定值、活跃变量、可用表达式。到达定值分析的方程是：

in[B] = ∪ out[P]（P是B的所有前驱基本块） out[B] = gen[B] ∪ (in[B] - kill[B])

其中gen[B]是基本块内部新产生的定值，kill[B]是整个程序中可能被基本块内语句杀死的定值集合。这个方程看起来抽象，但考的通常是给定一个小程序，让你写出每个基本块的gen、kill、in、out，并判断某条定值是否能到达某条语句。同样热门的是活跃变量分析：一个变量如果在某条语句之后、下一次定值之前还可能被读取，它就是活跃的。活跃变量分析的方向是从后往前传播，方程恰好是到达定值的镜像。

老实说，这部分如果出大题通常是中等难度，不会让你证明某个不动点定理，而是考你方程能否用对。我把四个数据流分析（到达定值、活跃变量、可用表达式、很忙表达式）列了一张横向对比表：分析对象、传递方向、初始值、gen和kill各自是什么。考前把这张表背下来，再做两道例题，基本就过关了。

5.3 寄存器分配只需要掌握思路

目标代码生成阶段最典型的优化问题是寄存器分配，常用方法是图着色。基本思想是：变量在同一个时刻是活跃的，就不能分配同一个寄存器，把它们连一条冲突边；建完冲突图后，用K种颜色给图着色，相邻节点颜色不同。K通常等于目标机可用寄存器数，如果图是K可着色的，分配方案就存在。这个考点很少要求完整执行图着色算法，更多是考你：给定一个活跃区间列表，判断变量之间是否冲突，或者在一个简单冲突图上手算一组合法分配。

剩下的目标代码生成内容，比如指令选择，更多的是一种工程权衡。考试一般只要求理解思路：给中间代码选择合适的机器指令，如果目标机器有复杂寻址方式，可以把几条四元式合并成一条汇编指令。我复习这一章的心得是不要陷入细节，抓住两个主线——优化前先找基本块，优化时先做DAG简化，其余内容以概念题准备为主。只要基本块划分和DAG优化两大题不失手，代码优化章节的分数就到手大半。

6. 考前回顾：我的复习顺序与最容易失分的八个细节

6.1 按题型分配时间的复习顺序

我个人不太建议按教材章节顺序从头到尾刷，更推荐按题型从高性价比到低性价比推进。第一优先永远是词法分析大题的“三步走”，这是基础中的基础，也是后面所有阶段的输入格式来源。第二优先是语法分析：First/Follow集、预测分析表构造、LR分析表构造或LALR合并，这些是考试大题的重灾区，占分最多。第三优先是四元式翻译，因为它套路固定，默写模板就能拿分。第四优先是代码优化里的基本块划分和DAG优化。最后的碎片时间可以留给属性文法、数据流方程、运行时环境、寄存器分配这些概念题和简答题。

按这个顺序，如果复习时间只剩三天，第一天拿下词法加语法，第二天拿下翻译加优化，第三天刷往年卷并整理错题，基本可以覆盖百分之八十五以上的考点。如果时间充足，再把教材例子重新推导一遍，效果会更好。我不建议直接刷题而不看教材，因为编译原理的算法步骤容错率极低，一个概念理解偏差会导致整个项目集构造错误，必须回到教材把算法定义读准确。

6.2 八个容易丢分的细节清单

第一个细节：ε是空串，不是空集。First集中能包含ε，但Follow集一定不能包含ε，如果算出ε出现在Follow集里，一定是算法用错了。第二个细节：消除左递归只处理直接左递归还不够，间接左递归（比如S → A a、A → S b）也要通过代入消除。第三个细节：构造预测分析表时，产生式A → ε不是不填表，而是填在Follow(A)对应的所有终结符格子中。第四个细节：LR(0)项目集规范族中，闭包运算要不断加入新的A → ·α项目，直到没有新项目为止，漏掉一个闭包项目会导致后面一系列状态错误。第五个细节：SLR(1)归约动作的判定条件是“当前输入符在Follow(A)中”，不要和LR(1)的“当前输入符恰好等于该项目的前瞻符号”混为一谈。第六个细节：四元式翻译时，临时变量编号不能重复使用，但控制流标号通常也要单独编号，不要在同一个题目里让编号体系互相冲突。第七个细节：基本块的入口语句集合不能忘了“跳转指令之后的第一条语句”，很多人只找跳转目标，漏了顺序执行的分支入口。第八个细节：DAG优化后生成代码时，如果某个中间节点在当前基本块之后不再活跃，可以不再生成它的赋值指令。这个条件经常被忽略。

把这八个细节做成一张小卡片，考前过一遍，能避免很多低级失分。我整理这份笔记的最终体会是：编译原理不是一门靠死记硬背的课，但只要把每条流水线的接口和算法步骤梳理清楚，它就是一门可以稳定拿高分的课。最后再分享一个我自己一直在用的方法——每次学完一个阶段，用白纸默写该阶段的输入、输出、核心数据结构、标准算法四要素，默写不出来就回去翻书，直到能完整画出来为止。这个方法帮我从第一次月考的七十分提升到了期末九十分以上，你也可以试试。