编译原理期末速成：词法语法分析与LR闭包笔记

1. 开篇：这门课为什么让人头皮发麻，又该怎么速成

编译原理期末速成笔记，说白了就是我考这门课之前攒下来的一整套复习思路。如果你现在打开课本发现满页都是自动机、文法、FIRST集、项目集闭包这些东西，脑子里一片空白，那这篇东西就是写给你的。它不打算把你培养成写编译器的人，目标很直接：在有限的时间里把考试要考的东西拎清楚，知道哪些是必考、哪些是套路题、哪些看一眼就能拿分，同时把几个核心概念真正搞懂，而不是背下来第二天就忘。

先说说这门课为什么难。它难在抽象。操作系统你还能想象成管理进程和内存，计算机网络你能对应到插网线、发数据包，可编译原理一上来就是"字符串集合""状态转移""推导树"，全是纸面上的符号游戏。很多人卡住不是因为不聪明，而是没找到一个把符号和实际意义对应起来的抓手。我的经验是，你得先建立起"编译器就是一条流水线"的画面感，每个阶段负责一道加工工序，后面所有细节都往这条流水线上挂，这样零散的知识点才会连成串。

适合谁看这篇笔记：一是这学期正在上编译原理、马上要期末的人；二是想临时抱佛脚但不想考太差的人；三是准备面试被问到"词法分析和语法分析的区别""LR和LL哪个更强"这类问题、想快速把知识捡回来的人。热词里提到的词法分析实验、第三版答案、哈工大课件、面试题，本质上是同一批知识的不同使用场景，我都会照顾到。

我特意把复习顺序做了调整：不是按课本章节从前往后啃，而是按"分值密度"和"上手难度"重新排。词法分析最机械、最容易速成，先拿下；语法分析是大头，要花最多时间；语法制导翻译和中间代码属于理解了就好拿分；最后的优化和代码生成分值相对分散，抓典型例题即可。下面按这个顺序展开，每一块我都会告诉你为什么这么学、坑在哪里、考试怎么出。

2. 先把编译器的全局地图画出来

2.1 六个阶段到底各干什么

编译器处理一个源程序，粗略走六个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。速成阶段你不需要背每个阶段的完整定义，但一定要能用一句话说清"输入是什么、输出是什么"。

• 词法分析：把字符流切成一个个有意义的记号（Token），比如int、x、=、10。
• 语法分析：把 Token 序列组织成语法树，判断符不符合文法。
• 语义分析：做类型检查、作用域检查，语法对不代表意思对，int + string就是在这里被拦下来的。
• 中间代码生成：把语法树翻译成一种和机器无关的表示，常见的是三地址码。
• 代码优化：在不改变程序语义的前提下让中间代码跑得更快、占得更少。
• 目标代码生成：翻译成具体机器的汇编或机器码，还要分配寄存器。

这张图为什么重要？因为考试特别喜欢考"某个错误在哪个阶段被发现"。比如括号不匹配是语法错误，变量没声明是语义错误，除零这种运行期才炸的不算编译期错误。你把六阶段在心里排成一条线，这类题基本白送。

2.2 用分值分布决定复习优先级

我复盘过好几份不同学校的真题，分值大概长这样，你可以照着调整精力：

看到没，词法和语法加起来就过半了，这两块是绝对的主战场。很多人一上来就死磕 LR(1) 项目集，结果最基础的 Thompson 构造法都没练熟，这是典型的用力用错地方。我建议你先花一天把词法分析的所有题型刷一遍，拿到稳稳的基础分，再回头啃语法分析。

注意：不同教材的章节顺序和术语略有差异，比如有的书把"语义分析"和"中间代码生成"合在一起讲，复习时以你老师划的重点为准，别被不同版本术语绕晕。

很多同学问：为什么不直接从难的开始？因为速成最怕挫败感。先做几道能快速做对的题，把手感和信心建立起来，后面啃硬骨头才扛得住。这个顺序其实是我踩过坑之后改的——第一次复习我是按课本从词法啃到尾，结果卡在 LR 分析表那里就再没翻过后面几章，最后中间代码那部分直接空着交卷。

3. 词法分析：有限自动机是绕不过去的坎

3.1 正则表达式到 NFA，Thompson 构造法是标准套路

词法分析的核心任务，说白了就是"给你一个规则，判断一串字符符不符合这个规则"。规则用正则表达式描述，实现用有限自动机。考试最常考的就是三种转换：正则表达式转 NFA、NFA 转 DFA、DFA 最小化。这三个就是一条流水线，练熟了基本都能拿分。

先说正则转 NFA，标准方法叫Thompson 构造法。它的思路特别朴素：把复杂的正则拆成最基本的几块，每块单独构造一个小自动机，再用 ε 边拼起来。

• 单个字符a：两个状态，中间一条标a的边。
• 连接rs：先构造r和s的 NFA，把r的接受状态和s的起始状态用 ε 边连起来。
• 选择r|s：新建一个起始状态和一个接受状态，起始状态用 ε 边分别指向r、s的起始状态，r、s的接受状态再用 ε 边指向新的接受状态。
• 闭包r*：r的接受状态用 ε 边回到自己的起始状态，同时新增起始和接受状态做进出。

听起来绕，其实你只要记住一句话：每个基本块都是"一进一出"，拼接时首尾用 ε 相连，分叉和循环也全靠 ε。考试里画出正确结构比追求状态数最少更重要，没人会因为多画两个状态扣分。

3.2 NFA 转 DFA，子集构造法的两个核心操作

NFA 是非确定性的，一个状态读一个字符可能跳到多个状态，机器没法直接执行，所以要转成确定的 DFA。方法是子集构造法，核心就两个操作：

• ε-闭包（ε-closure）：从一个状态集合出发，只走 ε 边能到达的所有状态的集合。注意起始状态本身也算在内。
• move 操作：从一个状态集合出发，读一个字符a能到达的状态集合。

算法流程：从起始状态的 ε-闭包开始，对每个可能的输入字符做 move 再取闭包，得到新状态；反复直到没有新状态产生。每个 DFA 状态对应原 NFA 的一个状态子集。

我给你一个最容易出错的地方：ε-闭包要反复取到不动为止。有些人只闭包了一层，漏掉链式 ε 转移，结果整个 DFA 都是错的。我的做法是画状态集时随手标注，边算边核对，宁可慢一点。

还有一个细节值得说：DFA 里的死状态（空集）要不要画？严格来说可以省，但很多参考答案会画出来，因为省掉之后某些转移就没地方标了。考试时如果老师给的模板有死状态，你就跟着画；没有就省掉，别自己加戏。

3.3 DFA 最小化，分割法一步步来

最小化就是把等价的状态合并。标准方法是分割法（划分法）：

1. 先把所有状态分成两组——接受状态一组、非接受状态一组。
2. 对每组，检查组内状态读同一个字符后会不会落到不同的组。会，就把这组再拆开。
3. 重复第 2 步，直到所有组都不能再拆。
4. 每个最终组取一个代表状态，重新画转移。

关键名词叫可区分：两个状态如果读某个字符串后一个接受一个不接受，它们就不同。最小化的本质上就是不断找出可区分的状态对，把不可区分的合并。

我建议你拿一道标准题反复手算三遍，直到能闭着眼睛走完流程。因为分割法的步骤是死的，会了就是一劳永逸的送分题，不会就是每次都栽。

3.4 词法分析实验怎么写代码

热词里反复出现"词法分析实验"，说明很多人卡在写代码上。实验一般要求你手写一个词法分析器，输入一段源代码，输出 Token 序列。常见做法有两个：

一是直接用状态转移法手写while循环加switch，适合词法规则不复杂的情况。核心结构是维护一个当前字符指针，根据第一个字符判断进入哪类 Token 的处理分支，读完再回退或前进。二是用DFA 表格驱动，把最小化后的 DFA 存成二维表，代码只负责查表，结构更干净，也更符合课本套路。

# DFA 表格驱动的词法分析骨架 def lexer(src): tokens = [] i = 0 while i < len(src): c = src[i] if c.isspace(): i += 1 elif c.isalpha(): j = i while j < len(src) and (src[j].isalnum() or src[j] == '_'): j += 1 tokens.append(('ID', src[i:j])) i = j elif c.isdigit(): j = i while j < len(src) and src[j].isdigit(): j += 1 tokens.append(('NUM', src[i:j])) i = j else: tokens.append(('SYM', c)) i += 1 return tokens

这段是手写简化版，真正实验里最容易被抓的问题有三个：标识符和关键字的区分（先按标识符读，再查关键字表）、多字符运算符的贪心匹配（>=不能拆成>和=）、注释和空白的跳过。这三点老师基本必查，写实验前先在纸上把状态图画清楚，比对着代码改要快得多。

提示：实验报告的给分往往和"你画的自动机是否和代码一致"挂钩。代码能跑但图对不上，分数也不好拿，别偷懒。

4. 语法分析：LL 和 LR 两条路怎么选怎么记

4.1 文法、推导、规约这三个基础概念

语法分析之前，先把几个词分清，不然做题时会一直懵。

**上下文无关文法（CFG）**由四部分组成：非终结符、终结符、产生式、起始符号。它比正则表达式强，能描述嵌套结构，比如括号匹配、嵌套 if，这些正则搞不定。

推导是从起始符号出发，不断用产生式替换非终结符，一步步得到句子。最左推导每次替换最左边的非终结符，最右推导每次替换最右边的。规约是推导的逆过程，从句子往回推。

还有一个高频考点：二义性文法。如果一个句子对应两棵不同的语法树，这个文法就有二义性。经典的例子是E → E + E | E * E | id，id + id * id能画出两种树。消除二义性通常靠引入优先级和结合性的层次，把文法改写成：

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

这个改写后的文法就是后面所有 LL、LR 例题的常客，你务必把它背熟，最好能默写出它的语法树。

4.2 自上而下分析：LL(1) 的三板斧

自上而下分析从起始符号往句子推，代表是LL(1)，第一个 L 表示从左到右扫描输入，第二个 L 表示最左推导，1 表示每次向前看一个符号。

LL(1) 要解决两个拦路虎：左递归和回溯。

左递归就是产生式形如A → Aα，直接这么写会死循环。消除办法是改成右递归：

A → Aα | β 改成 A → βA' A' → αA' | ε

提取左公因子是为了避免回溯。如果两个产生式开头一样，比如A → αβ | αγ，就提出来：

A → αA' A' → β | γ

然后就是 LL(1) 的核心计算：FIRST 集和FOLLOW 集。

• FIRST(α)：α 能推导出的所有可能的开头终结符集合。如果 α 能推出空串 ε，那 ε 也在里面。
• FOLLOW(A)：在所有句型里，紧跟在非终结符 A 后面的终结符集合。起始符号的 FOLLOW 里一定有个结束符$。

拿经典文法练手：

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

算出来是：

有了这两张表，就能构造预测分析表：对每条产生式A → α，把 α 填进表里A行、FIRST(α)列的格子；如果 α 能推 ε，就再填到FOLLOW(A)的列。一个格子如果填了两条产生式，就产生冲突，说明这个文法不是 LL(1)。

提示：考试里判断"是不是 LL(1)"几乎必考，判据就是预测分析表有没有多重入口。你算完表扫一眼冲突格子就行，不用逐条推导。

4.3 自下而上分析：LR 家族四兄弟

自下而上分析从句子往起始符号归约，代表是LR 分析，它的家族有点大，很多人被 LR(0)、SLR(1)、LR(1)、LALR(1) 绕晕。我用一句话帮你区分：

• LR(0)：最弱，只看当前状态，不看向前看符号。
• SLR(1)：在 LR(0) 基础上，用FOLLOW 集来化解冲突。
• LR(1)：每个项目带一个向前看符号，能力强但状态多。
• LALR(1)：把 LR(1) 里"同心"的项目集合并，能力介于 SLR 和 LR(1) 之间，实际编译器最爱用。

LR 分析的核心工具是项目，也就是在产生式右边某个位置点一个点，表示"我已经读到哪了"。比如A → α·β表示 α 已经匹配，接下来期待 β。然后通过**闭包（closure）**和GOTO 函数构造 LR(0) 项目集规范族，再填分析表。

分析表分两张：ACTION 表管终结符，GOTO 表管非终结符。填表规则按项目类别来：

• 移进项目A → α·aβ：在 ACTION 里填s+ 目标状态。
• 规约项目A → α·：一般填r+ 产生式编号。
• 接受项目S' → S·：填 acc。

冲突主要两种：移进-规约冲突和规约-规约冲突。SLR 的化解办法是看 FOLLOW 集，LR(1) 则靠向前看符号。我在 LR 这一块踩得最惨的坑，是闭包计算不完整——构造项目集时，点在非终结符前面就要把这个非终结符的所有产生式加进来，很多人漏了这一步，导致整张表全错。

举个龙书里的经典例子，这个文法在 SLR 里会出现移进-规约冲突：

S → L = R | R L → * R | id R → L

处理它的过程几乎每年都会以不同形式出现在考卷里，值得你专门花时间手推一遍。

4.4 一张表看懂 LL 和 LR 的取舍

速成建议：LL(1) 一定要会算表和判断冲突，这是稳拿分；LR 至少要能画出项目集和填 ACTION 表。如果你时间实在不够，LALR 的合并过程可以只记住"同心项目集合并、向前看符号取并集"这个结论，做到看懂题不至于全空。

5. 语法制导翻译和中间代码，理解比背更重要

5.1 属性文法：S 属性和 L 属性

语法分析解决"对不对"，语义分析解决"什么意思"。**语法制导定义（SDD）**给每条产生式挂上属性和计算规则，属性分两类：

• 综合属性：由子节点的属性算出来，自下而上传播，比如表达式E → E1 + T里E.val = E1.val + T.val。
• 继承属性：由父节点或兄弟节点算出来，自上而下传播，典型场景是类型信息往下传。

只含综合属性的叫S 属性定义，可以在自下而上分析时顺手算完，实现简单。既含继承属性、又满足"沿语法树从左到右计算"约束的叫L 属性定义。考试常考"判断某个 SDD 是不是 L 属性""画带注释的语法树"，你只要抓住"继承属性不能依赖右边的兄弟节点"这条就能判断。

5.2 三地址码和四元式

中间代码最常见的表示是三地址码，每条指令最多三个操作数，形式像x = y op z。它比语法树更适合做优化和代码生成。表达a = b + c * d会翻译成：

t1 = c * d t2 = b + t1 a = t2

考试里翻译成四元式最规范，四元式是(op, arg1, arg2, result)。上面三行对应：

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

控制语句的翻译是高频考点。while、if都会用到**回填（backpatching）**技术，因为跳转目标地址一开始不知道，先留空，等确定后再填。理解回填的关键是记住三个辅助函数：makelist建链、merge合并链、backpatch回填。这三兄弟配合起来，才能把布尔表达式的短路求值翻译对。

5.3 优化：基本块、流图和 DAG

基本块是一段顺序执行、只有一个入口一个出口的代码。流图把基本块用有向边连起来，表示控制流。优化分局部优化和全局优化，速成阶段重点抓局部优化。

局部优化里最常考的是DAG（有向无环图）。把基本块里的每条语句建成节点，相同的子表达式合并成同一个节点，就能自动消除公共子表达式。画 DAG 的要诀：变量赋值时，这个变量指向对应节点；遇到已有节点就直接复用，不要新建。

除了公共子表达式消除，还有常量合并、死代码消除、复写传播这些。一个实用判断：如果一条计算的结果从来没被用过，删掉它不改变程序语义，这就是死代码。考试让你"对某基本块做优化"，基本就是让你画 DAG 再读一遍。

6. 冲刺阶段的时间分配和题型打法

6.1 三天版复习排期

如果离考试只剩几天，我建议这么排：

• 第 1 天：词法分析全题型（正则转 NFA、NFA 转 DFA、DFA 最小化），练到能独立完成。同时过一遍概念简答。
• 第 2 天：语法分析主力攻坚。上午 LL(1) 算 FIRST/FOLLOW 和预测分析表，下午 LR(0)/SLR 项目集和分析表。晚上把语法制导翻译的典型例题看懂。
• 第 3 天：中间代码、四元式、回填、DAG 优化各刷几道，然后整套真题掐时间做一遍。

这个排期的逻辑是"先易后难、难的重投入、最后查漏"。千万别把最难的 LR(1) 放在最后一天啃，那只会让你崩溃。

6.2 高频题型清单

我整理了一下最常出现的题型，你照着刷：

6.3 面试题其实和期末是一套东西

热词里有人搜"编译原理面试题"，我顺带说一句：面试问的编译原理，深度往往不如期末笔试卷，但更爱问原理性理解。常见问题比如"词法分析和语法分析的区别"（一个处理字符到 Token，一个处理 Token 到语法树）、"为什么用中间代码"（便于优化和跨平台）、"LL 和 LR 谁更强"（LR 能处理的文法集合更大，但构造复杂）。

一个反直觉的点：面试官很少让你现场手推 LR 分析表，却经常问"你了解过哪些编译器""正则表达式引擎的原理"。这类问题答好了加分很多，所以别把知识只用在考试上，理解到位了面试是顺带的事。

7. 踩坑实录：这些错误我替你试过了

复习和考试里最容易栽的地方，我都踩过，整理成一个速查表给你：

再分享几条课本上不会写的实操心得。

第一，画图比写字快。NFA、DFA、语法树、DAG 全都画出来，比纯文字描述清楚十倍，改错也方便。我考试时习惯先在草稿纸上画草稿，确认无误再誊抄到答题卡。

第二，先算小文法再套大文法。遇到复杂文法别硬上，先拿最简单的一条产生式走一遍流程，确认方法记住了再处理整题。很多人是方法没记牢就冲进大题，结果步骤全乱。

第三，符号命名保持统一。临时变量用 t1、t2、t3 递增，状态用 0、1、2 编号，不要一会儿 A 一会儿 S0，自己都会看花眼。这个习惯看着小，实际能省不少粗心分。

第四，真题至少做两套。不同学校的出题风格差别很大，有的偏爱 LR 大计算，有的爱考概念简答。做两套你就能摸到老师的口味，复习也能针对性收口。

注意：速成不等于什么都不懂。像 FIRST/FOLLOW、闭包这些核心概念，理解之后记一辈子；纯靠背的话，换个文法就懵了。时间再紧，也要给理解留出空间。

说个我自己的教训收尾。我第一次考这门课，死活想不通 LR 项目集为什么要做闭包，硬背步骤，结果题目换个文法我就全错。第二次我花了一个晚上专门画项目集、逐条对照，突然就通了——闭包其实就是"我现在期待看到 A，那 A 能怎么展开，我全列出来备用"。想通这一句之后，LR 那一片题再没丢过分。所以编译原理这门课，速成的关键不是背得多快，而是找到那几个让你"啊，原来是这个意思"的瞬间。把词法那三个转换、LL 的 FIRST/FOLLOW、LR 的闭包这三关过了，期末基本就稳了。