1. 为什么“编译原理”值得你花时间啃下来
如果你正在准备期末、考研复试，或者单纯想补一补计算机基础里最硬的那块骨头，那“编译原理复习提纲”这个标题背后要解决的事情就很明确了：把一门公认难啃的课，拆成能理解、能背、能做题、能讲清楚的模块。我见过太多同学，教材翻了三遍，词法分析勉强能画个DFA，一到语法分析就开始怀疑人生，到了语义分析和代码生成直接放弃治疗。问题不在于智商，而在于复习路径错了——编译原理不是靠“读”能读会的，它需要你按“前端—中端—后端”的流水线去拆，按“概念—算法—手算—代码”四层去练。
这篇内容适合三类人：第一类是要应付考试的学生，需要一份能直接照着走的复习路线；第二类是想真正搞懂编译器怎么工作的人，需要把零散知识点串成一条线；第三类是已经工作但想回头补基础的人，需要知道哪些知识在实际工程里真的有用。我会把整个复习过程拆成设计思路、核心细节、实操推演和问题排查四个大块，每一块都给出可以直接抄作业的步骤和手算示例。你不需要先看完一本六百页的教材再回来，跟着这条线走，边看边在纸上画，效果比干读强十倍。
先给一个整体判断：编译原理的复习，核心就五件事——正则与有限自动机、上下文无关文法与语法分析、语法制导翻译与中间代码、运行时环境与符号表、代码优化与目标代码生成。这五件事对应编译器的五个阶段，也对应考试里百分之九十的考点。把这五块吃透，剩下的边角知识都是它们的组合和变形。
2. 复习提纲的整体设计与模块拆解
2.1 按编译器流水线组织，而不是按教材章节
很多人复习编译原理喜欢按教材目录走，第一章引论、第二章词法、第三章语法……这样走最大的问题是：你学到语法分析时，已经把词法忘了一半，学到语义分析时，前面两章全糊了。我的建议是按数据流动的方向组织复习，因为编译器本身就是一个流水线：源代码进去，经过词法分析变成记号流，经过语法分析变成语法树，经过语义分析变成带注解的树，经过中间代码生成变成三地址码，最后经过优化和目标代码生成变成汇编。
你复习的时候也应该这样：先建立“输入是什么、输出是什么、中间经过哪些变换”的框架，再往每个环节里填细节。比如词法分析的输入是字符流，输出是记号流，核心工具是正则表达式和有限自动机；语法分析的输入是记号流，输出是语法树，核心工具是上下文无关文法和下推自动机。这样你每复习一块，都知道它在整个流水线里的位置，不会迷失。
2.2 每个模块按“概念—算法—手算—代码”四层推进
光有框架还不够，编译原理的难点在于它既有理论又有工程。我的经验是每个模块都要过四层：
- 概念层：这个阶段要解决什么问题？为什么需要它？比如为什么词法分析要用正则而不用上下文无关文法？因为正则足够表达记号的结构，而且可以用有限自动机高效识别，没必要上更重的工具。
- 算法层：核心算法是什么？比如子集构造法、LL(1)分析表的构造、LR(1)项目集的闭包运算、算符优先关系表的构造。这些算法必须能默写出来。
- 手算层：给你一个具体的小文法或正则表达式，你能不能在纸上一步步算出DFA、分析表、语法树？这一层是考试的重灾区，也是检验你是否真懂的唯一标准。
- 代码层：如果让你用代码实现一个简化版，你会怎么写？比如用状态机实现词法分析器，用递归下降实现语法分析。这一层不一定要写完整编译器，但至少要把核心数据结构想清楚。
2.3 重点模块的优先级排序
时间有限的情况下，不是所有内容都同等重要。根据我自己的复习和带人经验，优先级大致是这样的：
| 优先级 | 模块 | 理由 |
|---|---|---|
| 最高 | 语法分析（LL、LR） | 考试分值最大，算法最复杂，最容易拉开差距 |
| 最高 | 语法制导翻译与中间代码 | 连接前端和后端的桥梁，大题常考 |
| 高 | 词法分析与有限自动机 | 基础中的基础，DFA最小化常考 |
| 高 | 运行时环境与符号表 | 概念多但难度不大，背了就有分 |
| 中 | 代码优化 | 考点相对固定，掌握常见优化即可 |
| 中 | 目标代码生成 | 如果考纲包含就重点看基本块和活跃变量分析 |
| 低 | 编译器前端工具（如Lex/Yacc原理） | 了解即可，除非明确考 |
这个排序不是绝对的，如果你的考纲明确说代码优化占三十分，那当然要调整。但大多数情况下，语法分析和语法制导翻译是绝对的核心。
2.4 复习节奏建议
我试过的最有效的节奏是“三轮法”：
第一轮用两周左右，把五个模块的概念和算法过一遍，不追求全懂，但要求知道每个模块在干什么、核心算法叫什么。第二轮用一周，专门做手算题，把历年真题里出现的DFA构造、LL(1)分析表、LR项目集、语法树、三地址码全部手算一遍。第三轮用三到五天，查漏补缺，把错题和容易混淆的概念集中突破，比如LL和LR的区别、SLR和LALR的区别、语法制导定义和翻译方案的区别。
注意：不要在第一轮就死磕难题，那样会严重拖慢进度。先把框架搭起来，再填肉。
3. 核心细节解析与手算实操要点
3.1 词法分析：从正则表达式到最小DFA的完整手算流程
词法分析的核心就一句话：用正则表达式描述记号的模式，用有限自动机识别这些模式。考试里最常见的题型是：给你一个正则表达式或一组记号描述，让你构造NFA，再转成DFA，最后最小化。
我拿一个典型例子走一遍。假设要识别标识符和整数，规则是：标识符以字母或下划线开头，后跟字母、数字或下划线；整数是数字序列。对应的正则表达式可以写成：
id = [a-zA-Z_][a-zA-Z0-9_]* num = [0-9]+第一步，构造NFA。对于id，可以画成：起始状态经过字母或下划线到状态A，状态A经过字母、数字或下划线回到状态A，状态A是接受状态。对于num类似。然后把两个NFA用ε转移连到一个新的起始状态，形成合并的NFA。
第二步，子集构造法转DFA。核心操作是计算ε闭包和move集合。具体做法是：从起始状态的ε闭包开始，对每个输入符号计算move后的ε闭包，得到新状态。重复直到没有新状态产生。这一步最容易出错的地方是忘记计算ε闭包，或者把move和闭包的顺序搞反。记住：先move，再求ε闭包。
第三步，DFA最小化。用划分法：先把状态分成接受状态和非接受状态两组，然后不断细分，直到每组内所有状态对同一输入都转移到同一组。最后每组选一个代表，画出最小DFA。
手算的时候，我建议用表格来跟踪子集构造过程，列是输入符号，行是状态子集。这样不容易漏。最小化的时候，用一张表记录每对状态是否可区分，从接受/非接受对开始标记，然后迭代。
实操心得：子集构造法得到的DFA状态数可能很多，但考试通常只要求你构造出来，不要求最小化。如果题目明确说“最小化”，那一定要做，因为最小化后的DFA才是唯一的。
3.2 语法分析：LL(1)与LR的对比与手算要点
语法分析是编译原理的重头戏，也是复习时最花时间的部分。核心就两大类：自顶向下的LL分析和自底向上的LR分析。
LL(1)分析的关键是构造FIRST集、FOLLOW集和预测分析表。手算步骤：
- 对每个非终结符求FIRST集。规则是：如果X是终结符，FIRST(X)={X}；如果X→ε，把ε加入FIRST(X)；如果X→Y1Y2...Yk，把FIRST(Y1)中非ε的元素加入，如果Y1能推出ε，继续看Y2，以此类推。
- 求FOLLOW集。起始符号的FOLLOW包含结束符$。对于产生式A→αBβ，把FIRST(β)中非ε的元素加入FOLLOW(B)；如果β能推出ε，把FOLLOW(A)加入FOLLOW(B)。
- 构造预测分析表。对每个产生式A→α，对FIRST(α)中每个终结符a，把A→α填入M[A,a]；如果α能推出ε，对FOLLOW(A)中每个终结符b，把A→α填入M[A,b]。
- 检查是否有冲突。如果同一个格子有多个产生式，就不是LL(1)文法。
LR分析更复杂，但考试里常见的是SLR(1)和LALR(1)。手算步骤：
- 构造增广文法，加入S'→S。
- 构造LR(0)项目集规范族。从I0=closure({S'→·S})开始，对每个项目集和每个文法符号计算goto，直到没有新项目集。
- 对SLR(1)，用FOLLOW集解决归约冲突：如果项目A→α·在状态I中，对FOLLOW(A)中每个符号a，填action[I,a]=reduce A→α。
- 对LALR(1)，需要合并同心项目集，用向前看符号解决冲突。
LL和LR的区别是考试常考的概念题。简单说：LL是自顶向下、从左到右扫描、最左推导；LR是自底向上、从左到右扫描、最右推导的逆过程。LL(1)文法一定是LR(1)文法，反之不然。LL分析器用手写递归下降或预测分析表实现，LR分析器用驱动表加栈实现。
注意：LR项目集构造时，closure和goto的定义一定要记牢。closure(I)是把所有·后面是非终结符的项目，把该非终结符的产生式加进来，点在最左边。goto(I,X)是把I中所有·后面是X的项目，把点移过X，然后求closure。
3.3 语法制导翻译：从语法树到三地址码
语法制导翻译是连接语法分析和中间代码生成的桥梁。核心概念是语法制导定义（SDD）和语法制导翻译方案（SDT）。SDD是带属性和语义规则的上下文无关文法，SDT是嵌入了语义动作的产生式。
属性分两类：综合属性是自底向上传递的，继承属性是自顶向下或从左到右传递的。考试里最常见的是用SDD计算表达式的值、构造语法树、生成三地址码。
我拿一个典型例子：表达式a+b*c的三地址码生成。假设用SDD，每个非终结符有一个综合属性code表示生成的代码，还有一个addr表示存放结果的临时变量或变量名。对于产生式E→E1+T，语义规则可以是：
E.addr = new_temp() E.code = E1.code || T.code || gen(E.addr '=' E1.addr '+' T.addr)手算的时候，从语法树底部往上，每一步生成一条三地址码。比如a+b*c，先算b*c得到t1，再算a+t1得到t2。最终三地址码序列是：
t1 = b * c t2 = a + t1如果是控制流语句，比如if-else和while，需要用回填技术。核心思想是先生成跳转指令但目标地址留空，等目标确定后再填回去。考试里常考的是布尔表达式的翻译和回填算法。
实操心得：三地址码的格式要统一，常见的是
x = y op z、x = op y、x = y、goto L、if x relop y goto L。写的时候注意临时变量的编号不要重复，回填的时候注意链表操作。
3.4 运行时环境与符号表：概念多但容易拿分
运行时环境这块，核心概念包括：活动记录、控制栈、访问链、显示表、参数传递方式、堆和栈的管理。考试里常考的是活动记录的布局和访问链的建立。
活动记录通常包含：返回地址、动态链（指向调用者的活动记录）、访问链（指向定义该过程的直接外层过程的活动记录）、参数、局部变量、临时变量。访问链的建立规则是：如果被调用过程的嵌套深度比调用者深1，访问链指向调用者的活动记录；如果深更多，沿着调用者的访问链往上走相应步数。
符号表的核心是作用域管理。常见实现是栈式符号表：进入作用域时压入新表，退出时弹出。每个表项包含名字、类型、存储位置等信息。考试里常考的是符号表的操作和名字解析规则。
注意：访问链和动态链的区别是常考点。动态链指向调用者，用于返回；访问链指向定义外层，用于访问非局部变量。别搞混。
4. 完整实操推演：从一个小文法到三地址码
4.1 选定一个覆盖多阶段的小文法
为了把前面几块串起来，我选一个简单但覆盖多个阶段的文法。假设我们要处理赋值语句和算术表达式，文法如下：
S → id = E E → E + T | T T → T * F | F F → ( E ) | id | num这个文法足够小，手算不累，但又覆盖了词法、语法、语法制导翻译三个环节。我带你从词法开始，一路走到三地址码。
4.2 词法分析：识别id、num和运算符
对输入x = a + b * 3，词法分析输出记号流：
<id, x> <assign, => <id, a> <plus, +> <id, b> <times, *> <num, 3>手算的时候，你只需要按正则规则逐个扫描字符，遇到字母开始收集标识符，遇到数字收集整数，遇到运算符直接返回对应记号。注意最长匹配原则：比如==要识别成等于而不是两个赋值。
4.3 语法分析：构造语法树
用LL(1)或LR分析这个记号流，得到语法树。以x = a + b * 3为例，语法树大致是：
S / | \ id = E /|\ E + T | /|\ T T * F | | | F F num | | id id手算语法树的时候，从起始符号开始，按产生式展开，遇到终结符就和输入记号匹配。LL是自顶向下展开，LR是自底向上归约。两种方法得到的语法树是一样的。
4.4 语法制导翻译：生成三地址码
给每个非终结符定义综合属性addr和code。对于F → num，F.addr = num.lexeme，F.code为空。对于F → id类似。对于T → T1 * F，生成T.addr = new_temp()，T.code = T1.code || F.code || gen(T.addr '=' T1.addr '*' F.addr)。对于E → E1 + T类似。
从语法树底部往上算：
F → id(a)：addr = aF → id(b)：addr = bF → num(3)：addr = 3T → F(b)：addr = bT → T * F：t1 = b * 3，T.addr = t1E → T(a)：addr = aE → E + T：t2 = a + t1，E.addr = t2S → id = E：x = t2
最终三地址码：
t1 = b * 3 t2 = a + t1 x = t24.5 代码优化：窥孔优化与常量折叠
如果b和3都是常量，可以在编译期直接算出t1 = 6，这就是常量折叠。如果t2只被使用一次，可以把t2替换掉，得到：
t1 = b * 3 x = a + t1再进一步，如果t1也只使用一次，可以合并成x = a + b * 3。这就是窥孔优化的基本思想：在局部窗口内寻找可以改进的模式。
实操心得：手算三地址码的时候，临时变量的编号要连续，不要跳号。回填的时候，用链表把需要回填的指令串起来，目标确定后遍历链表填入。
5. 常见问题与排查技巧实录
5.1 概念混淆类问题速查
| 问题 | 常见混淆 | 正确理解 |
|---|---|---|
| LL和LR的区别 | 以为只是方向不同 | LL是自顶向下最左推导，LR是自底向上最右归约 |
| SLR和LALR的区别 | 以为LALR更强大 | LALR合并了同心项目集，可能引入归约-归约冲突，但比SLR精确 |
| 综合属性和继承属性 | 以为继承属性就是自顶向下 | 继承属性可以从父节点、兄弟节点或自身传递，不一定是自顶向下 |
| 语法制导定义和翻译方案 | 以为是一回事 | SDD是声明式的，SDT是命令式的，SDT可以控制求值顺序 |
| 活动记录和符号表 | 以为是一回事 | 活动记录是运行时栈帧，符号表是编译时数据结构 |
5.2 手算出错的高频点
子集构造法忘记ε闭包：这是最常见的错误。记住，每次move之后必须求ε闭包，否则得到的DFA不完整。
FIRST集和FOLLOW集搞混：FIRST是“能推出什么开头”，FOLLOW是“后面能跟什么”。求FOLLOW时，只有产生式右边某个非终结符后面可能为空时，才把左边的FOLLOW加进去。
LR项目集closure算错：closure(I)中，如果项目A→α·Bβ，且B是非终结符，那么把所有B→·γ加进来。注意点在最左边，不要漏掉任何产生式。
三地址码临时变量重复：每次生成新临时变量时，编号要递增。如果手动编号，建议用t1、t2、t3这样顺序编，不要跳。
回填链表操作错误：回填时，把需要回填的指令的跳转目标字段串成链表，目标确定后遍历链表填入。注意链表头指针的保存和更新。
5.3 复习时间不够时的取舍策略
如果离考试只剩三天，我建议这样取舍：
- 第一天：语法分析。把LL(1)分析表和SLR分析表的构造手算三遍，确保能独立完成。
- 第二天：语法制导翻译和三地址码。把表达式和控制流的翻译各手算两遍。
- 第三天：词法分析和运行时环境。DFA构造和最小化各做两题，活动记录和访问链背熟。
代码优化和目标代码生成如果时间不够，只看基本概念和常见优化名称，不深究算法细节。
注意：不要试图在最后一天背所有算法，那样只会什么都记不住。抓住分值最大的模块，确保能拿到的分不丢。
5.4 从考试到工程的延伸
如果你不是为了考试，而是想真正理解编译器，那复习完之后可以尝试写一个简化版的编译器。我建议从表达式计算器开始：支持加减乘除和括号，用递归下降做语法分析，直接生成三地址码并解释执行。这个项目不大，但能让你把词法、语法、语法制导翻译串起来。写完之后再扩展变量、赋值、if和while，你就有了一个微型语言的编译器前端。
实际工程里，编译原理的知识用得最多的地方是：解析配置文件、实现领域特定语言、写代码生成工具、做静态分析。比如你写一个JSON解析器，词法分析和语法分析的思想直接能用；你写一个模板引擎，语法制导翻译的思路能帮你设计得更好。
我个人在实际操作中的体会是：编译原理最难的不是算法本身，而是把算法和具体问题对应起来。你看到一个文法，要能判断它是不是LL(1)，是不是LR(1)，该用哪种分析方法。这种判断力只能通过大量手算来培养。我当年复习的时候，把教材上的例题全部手算了一遍，又把历年真题手算了一遍，才算真正入门。后来工作中遇到需要解析自定义格式的场景，那些手算经验直接派上了用场。
最后再分享一个小技巧：复习的时候准备一张A4纸，把五个模块的核心算法和易错点写成一页纸的速查表。考前只看这张纸，比翻书效率高得多。这张纸的内容应该包括：子集构造法的步骤、FIRST和FOLLOW的求法、LL(1)分析表构造、LR(0)项目集构造、SLR和LALR的区别、三地址码的格式、回填算法、活动记录布局、访问链建立规则。把这些浓缩到一页纸上，你就真正掌握了编译原理的骨架。
