编译原理核心考点全梳理：从词法分析到代码生成复习指南

说实话，每次期末或者考研复习到《编译原理》这门课，很多人的第一反应就是“头大”。我曾经也是这么过来的：上课听的好像是人话，一做题发现题目认识我、我不认识题目；概念背了一堆，真正拿到文法构造分析表的时候，又从第一步开始卡壳。后面读研做编译器相关的东西、再回头准备面试，才慢慢把整门课的骨架给拎明白——编译原理之所以难，不是因为知识点本身有多高深，而是“概念多、层次多、每层还相互依赖”，没把框架搭起来之前，学多少细节都像散沙。

这一篇总结，我不打算像教材那样按章节平铺直叙，而是直接站在复习和考试的角度，把《编译原理》里的核心知识点、高频考点、实验常见套路以及面试常问方向全部串起来。无论你是在准备期末、考研复试，还是想在下一次技术面试里把“编译原理”变成自己的加分项，这篇都能帮你少走弯路。下面我们直接开整。

1. 先搭框架：编译原理到底在学什么

1.1 编译器的七个阶段

任何一本教材开头都会讲，编译器不是一步到位的，而是像一条流水线，把高级语言程序“翻译”成目标机器代码。经典划分一般是五个阶段加两个辅助环节：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成，以及贯穿全程的符号表管理和错误处理。很多学校会把中间代码生成和语义分析合并讲，但核心逻辑是一样的。

这里面最形象的理解方式就是“传话游戏”：词法分析相当于把一长串字符切成一个个有意义的单词（token），比如关键字、标识符、运算符；语法分析相当于判断这些单词按照文法规则排成的句子对不对，比如“主谓宾”顺序对不对；语义分析则检查这句话有没有逻辑问题，比如主谓是否一致、变量是否声明了。后面的中间代码生成和优化，则是把一句通过检查的话，翻译成更精炼、更贴近实际表达的说法。

1.2 三套核心考点之间的依赖关系

考试最常见的题型分布，其实是围绕三块：词法分析、语法分析、语义分析与中间代码生成。这三块之间有严格的依赖关系：

• 词法分析输出token流，这是语法分析的输入；
• 语法分析输出语法树/推导过程，这是语义分析的基础；
• 语义分析基于语法树做类型检查、作用域检查，再生成中间表示。

所以复习的时候，千万别跳着学。很多人学语法分析的时候 LR 项集构造看不懂，回头发现是词法阶段对“终结符/非终结符”的理解不够牢固；学语法制导翻译的时候看不懂属性文法的继承属性，又回头发现是不清楚语法树的父子、兄弟关系。

1.3 复习顺序与资料怎么选

如果时间紧张，我的建议是三轮走：

1. 第一轮：按教材顺序过一遍，重点看词法、语法、语义三章，代码优化和代码生成可以先放低优先；
2. 第二轮：以历年真题和课后习题为主，做错的地方回书本找对应小节，把概念彻底搞明白；
3. 第三轮：回归框架和易错题，用“能否看着目录回忆起章节重点”来检验掌握程度。

资料方面，不用贪多。经典教材一两本就够，配套的“XXX第三版答案”可以拿来对课后题，但别迷信答案。公开渠道能找到的哈工大、吉林大学等学校的课件讲义，质量都比较高，适合用来补齐笔记里缺失的图例和推导步骤。

2. 词法分析：看着简单，考点一点不少

2.1 从正则式到NFA再到DFA

词法分析的核心任务，是用正则表达式描述单词结构，再把它转成有限自动机来识别。考试里几乎必考的一条主线是：正则式 → NFA → DFA → 最小化DFA。

为什么不能直接用正则式识别？因为正则式是一种“描述工具”，程序跑起来没法直接拿它去匹配。为什么先转 NFA 而不是直接构造 DFA？因为从正则式直接构造 DFA 的规则非常繁琐，带着 ε 转移的 NFA 更容易机械地构造出来。NFA 转 DFA 用的是子集构造法，核心思想是把 NFA 的“某组状态集合”合并成 DFA 的一个状态，这样把不确定性去掉。

举个最小化的例子，很多同学容易忘记：DFA 最小化的本质是不断划分状态集合，从“非终态/终态”出发，看两个状态在某个输入符号下是否到达同一组内的状态，如果不能保持等价就拆开。注意，如果两个终态在所有输入下都到达等价状态，它们才能合并。一个很常见的陷阱是“一看状态长得像就合并”，结果把有区别的状态合在了一起，导致识别的语言发生变化。

2.2 词法分析实验的完整思路

热词里“词法分析实验”出现频率很高，我猜测很多学校会要求实现一个简易词法分析器。我自己当年踩过不少坑，给你梳理一个通用框架：

1. 定义 token 类型枚举：关键字、标识符、整数常量、浮点数常量、运算符、界符、字符串等；
2. 读入源程序字符流，写一个nextChar()函数和一个“回退一个字符”的函数，这是很多人的忽略点；
3. 按字符逐个扫描，遇到字母开头就进入标识符/关键字识别状态，遇到数字就进入数字识别状态，遇到运算符要考虑“单字符还是双字符”（例如=和==）；
4. 遇到空白符跳过，遇到无法匹配的字符报“非法字符”错误。

这里最大的坑是“超前读一个字符”之后忘记回退。比如读到一个<=，你读完=之后程序已经往前读了一个字符，如果不把多读的字符回退，下一个 token 的开头就丢了。很多同学调试半天，最后发现是这个小问题导致 token 流错位。

2.3 常见选择题陷阱

词法分析的选择题虽然不难，但坑很多，我整理几个高频出题点：

• 正则表达式无法描述的语言：典型的例子是“成对括号”“a^n b^n”这类需要计数的语言，只能用上下文无关文法描述；
• 词法分析器输出的是什么：不是字符流，也不是语法树，而是token流，每个 token 一般由(类别, 属性值)二元组表示；
• 正规式、NFA、DFA三者等价：它们描述的语言集合完全一致，区别只在识别效率；
• DFA识别过程中状态是否确定：DFA 每个状态在同一输入符号下最多有一个后继，NFA 则可能有多个，这是最根本的区别。

3. 语法分析：编译原理的硬骨头

3.1 文法与推导

语法分析这章，是《编译原理》里分量最重、也是最容易挂人的一章。首先要理解文法的形式化定义：一个文法G = (V_N, V_T, P, S)，分别代表非终结符集合、终结符集合、产生式集合、开始符号。

考试里有个经典考点是“最左推导 vs 最右推导（规范推导）”。最左推导就是每一次替换最左边的非终结符，最右推导就是替换最右边的非终结符。如果一个句子存在两棵不同的语法树（或者等价地说，有两种不同的最左推导/最右推导），这个文法是二义性的。常见的二义性例子包括“悬空 else”问题，以及表达式文法E -> E + E | E * E | (E) | id。

二义性好消息是：可以改写文法来消除，比如表达式文法改成E -> E + T | T, T -> T * F | F, F -> (E) | id。坏消息是：有些语言根本不存在无二义文法，这个在理论上叫“固有二义性语言”，考试一般不深入，但选择题偶尔会提。

3.2 LL(1)：First集、Follow集、预测分析表

LL(1) 是自顶向下分析的代表。第一个 L 表示从左到右扫描输入，第二个 L 表示产生最左推导，1 表示向前看一个输入符号。

要构造预测分析表，必须先算FIRST集和FOLLOW集。很多人背了定义还是会算错，我说说我的心得：

• FIRST(X)：可以从 X 推导出的所有终结符开头的集合。如果 X 能推出空串 ε，ε 也要加入 FIRST；
• FOLLOW(A)：在所有句型中，紧跟在 A 后面的终结符集合。注意$（输入结束符）一定在开始符号的 FOLLOW 集中；
• 构造预测分析表的核心规则：对每一个产生式A -> α，把FIRST(α)中的所有终结符填入M[A, 该终结符]；如果 α 能推导出 ε，再把FOLLOW(A)中的所有终结符填入M[A, 该终结符]。

为了判断一个文法是不是 LL(1)，需要检查预测分析表中每个格子是否最多只有一个产生式。只要有一个格子出现两个及以上产生式，就说明有冲突，文法不是 LL(1)。这里有个高频主观题：为什么需要 FIRST 和 FOLLOW 两个集合？答案是：当我们试图用A -> α展开时，要看当前输入符号是否在 FIRST(α) 中；但如果 α 能推导出 ε，我们就得看当前输入符号是否可能是 A 后面会出现的符号，也就是 FOLLOW(A)。

3.3 LR 分析家族

LR 分析是自底向上的方法，也是考试公认的难点。它的优点很明显：能处理几乎所有程序设计语言的语法结构，而且比 LL 更强大。LR 分析的核心是LR(0) 项集、GOTO 函数和ACTION 表。

复习时请记住这条演进路线：

考试最常考的是 SLR(1) 的构造流程。我的建议是“三步走”：

1. 写出增广文法S' -> S，方便识别接受状态；
2. 构造 LR(0) 项集族，就是不断求 closure 和 goto；
3. 依据项集族填 ACTION 表和 GOTO 表，其中归约动作要检查“当前输入符是否在 FOLLOW(A) 中”。

最容易出问题的点有两处。一是closure计算时，新加入的产生式也要继续求 closure，直到不再增加新项目为止；二是移进-归约冲突和归约-归约冲突的判断。SLR 的思路是：每个归约项目A -> α·只在输入符号属于 FOLLOW(A) 时才执行归约，如果这个符号同时也要求移进另一个项目，就产生了冲突。

很多教材还会补充：LR(1) 比 SLR(1) 强在哪里？核心在于 LR(1) 使用了“更精确”的向前看符号，而不是笼统的 FOLLOW 集。这一点面试里偶尔也会被追问到，值得理解而不是死背。

3.4 语法分析实验建议

很多学校第二个实验是用递归下降或 LL(1) 实现一个计算器或简易语言分析器。以我经验，递归下降最容易实现的坑是“左递归”。比如E -> E + T这种写法，会让递归下降分析陷入无限递归，因为函数parseE()一进来又调用parseE()。解决办法就是消除左递归，把左递归文法改写成右递归，再用循环处理同一层级的运算。

做实验时优先建议按“词法分析器 + 预测分析表（或递归下降）+ 语法树打印”三层结构走，每层设计好接口，后面接语义分析会舒服很多。

4. 语义分析与中间代码：从“识别”到“翻译”

4.1 属性文法与语法制导翻译

语法分析只回答“句子对不对”，而语义分析回答“这句话什么意思”。在编译原理里，语义通常用属性文法来描述，也就是在文法产生式上附加语义规则。

属性分为两种：综合属性和继承属性。简单记忆：综合属性是“自底向上”计算的，子节点的信息向父节点传递；继承属性是“自顶向下”或“从左到右”传递的，父节点或左侧兄弟的信息传给子节点。考试常考 S-属性文法（只含综合属性）和 L-属性文法（继承属性只沿从左到右方向传播），以及它们分别适合哪种分析：S-属性文法适合自底向上的 LR 分析，L-属性文法适合自顶向下的 LL 分析。

4.2 三地址码与回填

中间代码的形式有好几种：三地址码、四元式、三元式、逆波兰表示、DAG 等。考试最常考的是三地址码和四元式，比如赋值、算术运算、逻辑运算、跳转等，一条条列出来。

三个地址的“地址”不一定非得是变量名，也可以是临时变量，比如t1 = a + b，t2 = t1 * c。为什么编译器不直接生成目标代码？中间表示让“与机器无关的优化”成为可能，而且一个前端可以对接多个后端，这是分阶段设计带来的巨大工程收益。

回填技术是语义分析里的经典考点。跳转指令（比如if a < b goto L）在生成时，目标地址可能还没确定，所以先留空，等真正知道目标后再“回头填地址”。考试里常考布尔表达式的回填翻译，比如a < b or c < d如何翻译成跳转指令，并用 true/false 链表处理回填。

4.3 符号表与作用域

符号表管理贯穿整个编译过程，考试容易出简答或设计题。符号表要存什么？名字、类型、作用域信息、存储位置信息等。作用域的处理方式常见两种：一种是单张符号表 + 嵌套栈，进入一个作用域压栈，退出时弹栈；另一种是多张符号表，每层作用域一张，用指针连接。

这里我想强调一个个人认为很重要的点：符号表不只服务于语义分析，代码生成阶段分配存储空间的时候也要查符号表。所以符号表结构设计得好不好，直接影响编译器的后续扩展。

5. 运行时环境与代码生成

5.1 存储分配与活动记录

虽然很多学校把这章划为“了解”，但个别题目还是会出。运行时存储分配的三种策略：静态分配、栈式分配、堆式分配。

• 静态分配适合编译期间就可以确定大小和生命周期的对象（比如全局变量）；
• 栈式分配支持过程的递归调用，每次调用压入一个活动记录；
• 堆式分配用于动态申请内存的对象。

活动记录（activation record）通常包括返回地址、动态链/静态链、参数、局部变量、临时变量等。过程调用的约定（谁负责保存寄存器、参数怎么传）就是调用约定，这也是“编译原理 + 操作系统/体系结构”交叉出题的地方。

5.2 代码优化基础

代码优化在大纲里分量不小，期末考一般考概念和简单的块内优化。先把范围缩小：

• 基本块划分：入口语句和出口语句之间的直线代码段；
• 基本块内优化：删除公共子表达式、删除无用代码、复写传播、代数化简；
• 循环优化：代码外提、强度削减、删除归纳变量。

DAG（有向无环图）是表示基本块内优化的重要工具。用 DAG 对基本块重建中间代码，可以自动完成公共子表达式的删除，还能发现哪些变量在后续没有被使用，从而删除无用赋值。

这里说一个考点：为什么循环优化对性能影响大？因为程序 90% 以上的时间花在循环里，把循环内不变的运算提到循环外，收益非常明显。这在面试里讲 JIT 或解释器优化时也能用上，是很好的加分素材。

5.3 目标代码生成要点

目标代码生成通常只考概念，比如指令选择、寄存器分配。寄存器分配最经典的算法是图着色：把变量当作图的顶点，两个变量在同一时刻都活跃则连边，然后给图着色，颜色数不超过寄存器数，颜色就是寄存器编号。这个思想不难，但面试里经常出现“如果寄存器不够用怎么办”的追问，答案是溢出到内存，这会引入额外的存取开销。

对复习来说，这一章不追求手算大量题目，但要把术语理解透，能和前面的中间代码表示串起来。

6. 实验、复习与面试通用指南

6.1 词法+语法实验的验收关键

如果你正在被实验折磨，我给你一个“验收清单”式的思路：

1. 程序要能支持常见错误提示，比如非法字符、缺少分号、括号不匹配。很多实验的扣分点其实在“错误处理”，而不在“正常路径”；
2. 输出格式要符合要求，比如 token 行号、列号、类别和属性值。输出格式不统一，测试脚本跑不过，代码写得再好也白搭；
3. 测试用例要覆盖边界：空文件、连续多个空格、运算符连写（如a<=b==c）、字符串中含关键字等；
4. 设计上尽量把“词法分析器”做成一个独立模块，后续接语法分析的时候只用拿 token 流，不用再改。

6.2 面试高频题清单

如果“编译原理面试题”是你的搜索目标，那我把最常见的几类题列出来：

• 什么是编译器？和解释器的区别？
• 词法分析和语法分析的区别，举个例子；
• 如何消除左递归？为什么要消除左递归？
• LL(1) 和 LR(1) 的区别，各自优缺点；
• 什么是语法制导翻译？（ SDT / SDD）
• 介绍一下内存分配中的活动记录；
• JVM 或者 V8 里的热点代码优化，和编译原理有没有关系？
• 简述 AOT 编译和 JIT 编译的区别。

这些问题不要求你背答案，能用“流程 + 例子 + 优缺点”的结构讲清楚就行。比如问 JIT，你就可以从“中间表示 → 运行时热点检测 → 编译为机器码 → 优化”来展开，这就是编译器前端和后端知识的实际应用。

6.3 考前一周冲刺安排

最后说点实操性强的复习方法。如果离考试还有一周，我建议不要再重新翻教材，而是按这套节奏来：

1. 前 2 天：把词法分析和语法分析的课后题做一遍，重点做 FIRST/FOLLOW 集、LR 项集构造、预测分析表；
2. 中间 3 天：主攻语义分析和中间代码，特别是属性文法、三地址码翻译、回填；
3. 最后 2 天：过选择题和易错概念清单，再做一两套真题/模拟题，控制时间。

做题时遇到不会的，比起直接看答案，更好的方式是“倒回去找例题”，教材例题的步骤往往比答案更完整。很多人靠背答案过了考试，但一到实验或者面试就露馅，那是因为没有真正理解“为什么要这样算”。

我自己当年复习到 LALR(1) 的时候差点破防，后来发现一个特别管用的土办法：拿两个同心项集并排写在一起，看它们向前看符号的区别，多手推几遍之后，LALR 的想法自然就记住了。这种“亲手推导一遍”的方法，比看十遍课件都有效。

这篇总结把《编译原理》从框架到细节、从考试到实验、从面试到复习规划都串了一遍。如果你还有哪个模块觉得没讲透，大概率是你还没“动手算过”那一部分。找张白纸，从词法分析的最小化 DFA 开始，再到语法分析的 LR 项集，一题一题手推过去，这门课的基本盘就稳了。