1. 为什么“编译原理”这门课总让人感觉学了个寂寞如果你问一个计算机专业的学生哪门课最让人头皮发麻“编译原理”大概率能排进前三。我见过太多人期末周抱着龙书啃了两周考完试第二天就把LL(1)分析表怎么画忘得一干二净。等到工作面试被问到“词法分析和语法分析的区别”脑子里只剩下“好像有个自动机”这种模糊印象。这个现象背后其实有个很现实的原因大多数人是把编译原理当成一门“理论课”在背而不是当成一个“工程项目”在理解。你背下了FIRST集和FOLLOW集的求法但不知道它到底在解决什么问题你记住了LR分析器的状态转移表但没想过为什么需要这么复杂的设计。结果就是知识点像散落的珠子串不起来。这篇复习提纲我想换个思路来写。不按教科书的章节顺序平铺直叙而是从“一个编译器到底要干什么”这个最朴素的问题出发把词法分析、语法分析、语义分析、中间代码生成、优化、目标代码生成这条主线串起来。每个环节我会说清楚三件事它要解决什么问题、核心方法是什么、考试和面试里最容易在哪里翻车。适合谁来读如果你是正在准备期末考试的在校生这篇提纲可以帮你把零散的知识点重新组织成一条逻辑链如果你是准备面试的求职者这里面的核心概念和常见追问角度能帮你把“背过的知识”变成“能讲清楚的东西”如果你只是对编译器好奇想搞明白从源代码到可执行文件之间到底发生了什么那这篇内容也能给你一个不绕弯子的入门路径。需要说明的是编译原理涉及的内容非常广一篇文章不可能覆盖所有细节。我的策略是抓住主干——那些考试必考、面试常问、实际工作中真正影响你理解力的核心概念把它们的来龙去脉讲透。至于一些偏门的高级话题比如属性文法的高级应用、复杂的代码优化算法我会点到为止给出进一步学习的方向。2. 从源代码到机器码先把编译器的整体骨架搭起来2.1 编译器到底在做什么一个翻译流水线的类比你可以把编译器想象成一个翻译团队任务是把一本用“高级语言”写成的书翻译成“机器语言”版本。这个团队不是一个人从头翻到尾而是分成好几道工序每道工序只负责一件事做完就交给下一道。第一道工序是词法分析负责把连续的字符流切成一个个有意义的“词”Token。就像翻译时先要把句子拆成单词识别出哪些是名词、哪些是动词。第二道工序是语法分析负责检查这些词能不能组成合法的句子比如“我吃饭”是合法的“饭吃我”虽然每个词都认识但结构不对。第三道工序是语义分析负责检查句子的意思是否合理比如“我把石头吃下去了”语法没问题但语义上需要进一步处理类型检查、作用域检查等。再往后是中间代码生成相当于先把外文翻译成一种中间语言比如世界语方便后续统一处理。然后是代码优化把翻译出来的内容润色得更简洁高效。最后是目标代码生成把中间语言转换成特定机器能执行的指令。这个流水线的设计思想非常重要每个阶段只关心自己的输入和输出不关心其他阶段怎么实现。词法分析器不需要知道语法分析器怎么用它的输出语法分析器也不需要知道词法分析器内部是怎么实现的。这种“高内聚、低耦合”的设计是编译器能够处理复杂语言特性的基础。考试里经常考的一道题是给出一个编译器的各个阶段问某个错误会在哪个阶段被发现。比如“变量未声明”是语义分析阶段发现的“括号不匹配”是语法分析阶段发现的“非法字符”是词法分析阶段发现的。搞清楚每个阶段的职责边界这类题就不会丢分。2.2 前端与后端的分界线为什么中间代码这么重要编译器通常被分为“前端”和“后端”两部分。前端负责理解源语言包括词法分析、语法分析、语义分析和中间代码生成后端负责生成目标代码包括代码优化和目标代码生成。中间代码就是前后端的接口。为什么要设计中间代码这一层直接从前端跳到目标代码不行吗行但代价很大。假设你要支持三种源语言比如C、Java、Python和三种目标架构比如x86、ARM、MIPS如果没有中间代码你需要写3×39个编译器。有了中间代码你只需要写3个前端每种语言一个和3个后端每种架构一个总共6个模块。这就是中间代码的“解耦”价值。常见的中间代码形式有三地址码、四元式、三元式、间接三元式等。考试里最常考的是四元式因为它结构清晰方便用表格表示。一个四元式包含四个部分操作符、第一个操作数、第二个操作数、结果。比如a b c的四元式是(, b, c, a)。这里有个容易混淆的点四元式和三元式的区别。三元式不保存结果变量名而是用指令的位置索引来引用结果。比如(, b, c)的结果用“第1条三元式”来表示。四元式则显式保存结果变量所以更直观但也更占空间。考试里如果让你把表达式翻译成四元式或三元式一定要看清楚题目要求的是哪种。2.3 符号表贯穿始终的“户口本”符号表是编译过程中一个非常关键的数据结构但很多人在复习时容易忽略它。你可以把符号表理解成编译器的“户口本”里面记录了每个标识符变量名、函数名、类型名等的各种属性名字、类型、作用域、存储位置、是否已定义、是否已使用等等。符号表贯穿编译的几乎所有阶段。词法分析器识别出一个标识符后会把它交给符号表管理模块语法分析器在构建语法树时需要查询符号表来确认某个名字是否已声明语义分析器需要往符号表里填入类型信息代码生成阶段需要从符号表里读取变量的存储地址。符号表的实现方式有很多种常见的有线性表、二叉搜索树、哈希表。哈希表因为查找效率高平均O(1)在实际编译器中用得最多。但考试里更常考的是符号表的组织方式特别是如何处理作用域。比如嵌套作用域的实现通常用栈式符号表进入一个作用域时压入一个新表退出时弹出。查找时从栈顶往下找找到第一个匹配的就停止。这里有个经典的考试陷阱同名变量在不同作用域中的处理。比如在C语言里内层作用域可以定义一个和外层同名的变量此时内层变量会“遮蔽”外层变量。符号表需要能够正确处理这种情况通常的做法是在符号表项里记录作用域层级查找时优先返回最内层的匹配项。3. 词法分析把字符流切成有意义的词3.1 正则表达式与有限自动机词法分析的两把武器词法分析器的核心任务是识别出源程序中的一个个Token。比如对于代码int a 10;词法分析器需要输出关键字int、标识符a、赋值号、整数常量10、分号;。怎么描述“什么是标识符”“什么是整数常量”这类规则答案是正则表达式。比如标识符可以定义为“以字母或下划线开头后跟零个或多个字母、数字或下划线”写成正则表达式就是[a-zA-Z_][a-zA-Z0-9_]*。整数常量可以定义为[0-9]。但正则表达式只是“描述”真正要“识别”还需要有限自动机。有限自动机分为两种非确定有限自动机NFA和确定有限自动机DFA。NFA的特点是对于同一个输入可能有多个下一个状态甚至可以不读入任何字符就跳转ε-转移。DFA的特点是对于每个状态和每个输入字符最多只有一个下一个状态。实际编译器里用的是DFA因为DFA的识别过程是确定的不需要回溯效率高。但从正则表达式到DFA通常要经过“正则表达式→NFA→DFA→最小化DFA”这个流程。考试里经常考的就是这个转换过程。3.2 从正则表达式到DFA三步走的转换流程第一步是正则表达式转NFA。这里用的是Thompson构造法核心思想是把正则表达式的每个基本元素字符、连接、选择、闭包都对应到一个小的NFA片段然后把这些片段组合起来。比如a|b对应的NFA是从一个开始状态出发分别经过a和b到达两个不同的状态再汇合到一个接受状态。第二步是NFA转DFA用的是子集构造法。核心思想是DFA的每个状态对应NFA的一个状态集合。从NFA的起始状态集合出发对于每个输入字符计算能到达的所有NFA状态的集合这个集合就是DFA的一个新状态。重复这个过程直到不再产生新的状态集合。第三步是DFA最小化用的是Hopcroft算法或划分法。核心思想是把DFA的状态划分成若干等价类等价类内的状态对于任何输入串都产生相同的接受/拒绝行为。然后把每个等价类合并成一个状态。这三步里考试最常考的是第二步也就是子集构造法。因为这一步的计算量最大也最容易出错。我见过很多人在考场上算着算着就乱了根本原因是没有把NFA的状态集合写清楚。我的建议是先用表格列出NFA的所有状态和转移然后逐步构造DFA的状态集合每算出一个新集合就编号最后画出DFA的状态转移图。这个过程虽然繁琐但只要按部就班就不会出错。3.3 词法分析器的实操细节缓冲区与回退理论讲完了说说实际实现里的两个关键细节输入缓冲和回退。输入缓冲是为了减少对磁盘或内存的频繁读取。常见的方案是双缓冲区把输入分成两个半区当一个半区读完时从输入源读取下一块数据填充这个半区同时继续处理另一个半区。这样读取和处理可以并行进行。回退是因为词法分析器有时候需要“多看几个字符”才能确定当前Token的边界。比如遇到时需要看下一个字符是不是如果是那Token是如果不是那Token是并且需要把多读的那个字符“退回”到输入流里。实现回退的常见做法是用一个指针记录当前读取位置需要回退时把指针往回移动。这里有个容易忽略的坑回退的字符数不能超过已读取的字符数。如果词法分析器在文件开头就尝试回退会导致指针越界。实际实现里通常会在缓冲区里保留一个“哨兵”字符或者用额外的变量记录已回退的次数。考试里关于词法分析的题目除了自动机转换还常考Token的识别顺序。比如关键字和标识符的识别通常是把关键字放在优先匹配的位置因为关键字也是字母序列如果不优先匹配int可能会被识别成标识符。这个优先级的处理在DFA里体现为接受状态的优先级在代码里体现为匹配规则的顺序。4. 语法分析从Token流到语法树4.1 上下文无关文法语法分析的基石语法分析的核心任务是判断一个Token序列是否符合语言的语法规则并构建出语法树或抽象语法树。描述语法规则的工具是上下文无关文法CFG。一个CFG由四部分组成终结符集合、非终结符集合、产生式集合、开始符号。比如一个简单的算术表达式文法可以写成E → E T | T T → T * F | F F → ( E ) | id这个文法里E、T、F是非终结符、*、(、)、id是终结符E是开始符号。CFG的一个重要概念是推导从开始符号出发不断用产生式的右部替换左部直到得到一个全是终结符的串。推导分为最左推导和最右推导。最左推导每次替换最左边的非终结符最右推导每次替换最右边的非终结符。这两种推导分别对应自顶向下和自底向上两种语法分析策略。考试里经常考的是文法的二义性。如果一个句子有两棵不同的语法树那这个文法就是二义的。二义性会导致语法分析器无法确定唯一的语法结构所以实际编程语言的文法通常要求是无二义的。消除二义性的常见方法有引入优先级和结合性规则、重写文法等。4.2 自顶向下分析递归下降与LL(1)自顶向下分析是从开始符号出发尝试推导出输入的Token序列。最直观的实现方式是递归下降分析为每个非终结符写一个函数函数内部根据当前Token决定用哪个产生式然后递归调用其他非终结符对应的函数。递归下降分析的问题是如果文法有左递归比如E → E T递归下降会陷入无限递归。解决办法是消除左递归把左递归改成右递归。比如E → E T | T可以改写成E → T EE → T E | ε。另一个问题是回溯如果当前选择的产生式不对需要回退到之前的状态重新尝试。为了避免回溯引入了LL(1)文法。LL(1)的意思是从左到右扫描输入产生最左推导只需要看1个Token就能确定用哪个产生式。LL(1)文法的判断需要计算FIRST集和FOLLOW集。FIRST集是某个符号串能推导出的所有可能的开头终结符的集合。FOLLOW集是某个非终结符后面可能紧跟的终结符的集合。计算这两个集合是考试的重点也是容易出错的地方。我总结了一个计算FIRST集的口诀看产生式右部第一个符号是终结符就直接加入第一个符号是非终结符就加入它的FIRST集去掉ε如果第一个符号能推出ε就继续看第二个符号以此类推。FOLLOW集的计算稍微复杂一些看产生式右部对于每个非终结符它后面的符号的FIRST集去掉ε加入它的FOLLOW集如果它后面没有符号或者后面的符号能推出ε就把产生式左部的FOLLOW集加入它的FOLLOW集。4.3 自底向上分析LR分析器的家族谱系自底向上分析是从输入的Token序列出发尝试归约到开始符号。最强大的自底向上分析方法是LR分析它能够处理几乎所有上下文无关文法。LR分析器的核心是一个状态栈和一个分析表。分析表分为ACTION表和GOTO表。ACTION表决定当前状态下遇到某个Token时应该做什么移进、归约、接受、报错GOTO表决定归约后应该跳转到哪个状态。LR分析器有很多变种LR(0)、SLR(1)、LR(1)、LALR(1)。它们的区别在于分析表的构造方法和能处理的文法范围。LR(0)最简单但能处理的文法最少LR(1)最强大但分析表的状态数最多LALR(1)是折中方案状态数和SLR(1)差不多但能处理的文法比SLR(1)多。实际编译器里用得最多的是LALR(1)比如Yacc和Bison。考试里最常考的是LR(0)和SLR(1)的分析表构造。构造LR(0)分析表的关键是计算项目集规范族。项目就是在产生式右部加一个点表示当前分析到的位置。比如E → E · T表示已经分析了E接下来期待。项目集规范族的构造需要用到闭包和转移两个操作。闭包操作是如果项目集里有A → α · B β那所有B → · γ形式的项目也要加入这个集合。转移操作是对于项目集里的每个项目如果点后面是符号X就把点往后移一位得到新项目所有这样的新项目组成转移后的项目集。SLR(1)在LR(0)的基础上用FOLLOW集来解决归约-移进冲突。具体来说如果某个状态里既有归约项目A → α ·又有移进项目B → β · a γ那只有当a在FOLLOW(A)里时才用归约动作否则用移进动作。这里有个我踩过的坑FOLLOW集的计算一定要仔细特别是对于开始符号要记得把结束符$加入它的FOLLOW集。我见过有人在考场上忘了这一步导致整个分析表都错了。5. 语义分析与中间代码让程序“有意义”5.1 语义分析的核心任务类型检查与作用域管理语法分析只检查程序的结构是否正确不检查含义是否合理。比如int a hello;在语法上没问题但语义上类型不匹配。语义分析的任务就是发现这类错误。语义分析的核心任务包括类型检查、作用域检查、控制流检查、唯一性检查等。其中最重要的是类型检查。类型检查需要维护一个类型系统记录每个表达式的类型并检查操作符和操作数是否匹配。类型检查通常用语法制导翻译来实现。语法制导翻译的核心思想是为每个产生式关联一些语义动作在语法分析的过程中执行这些动作。语义动作可以计算表达式的类型、生成中间代码、更新符号表等。语法制导翻译有两种形式S-属性定义和L-属性定义。S-属性定义只使用综合属性可以在自底向上分析的过程中计算。L-属性定义可以使用继承属性但要求继承属性只依赖于父节点和左边的兄弟节点可以在自顶向下分析的过程中计算。考试里经常考的是语法制导翻译方案的编写。比如给一个简单的表达式文法让你写出计算表达式值的语义动作。这类题目的关键是搞清楚每个属性的含义和计算顺序。综合属性是从子节点往父节点传继承属性是从父节点往子节点传。5.2 中间代码的常见形式三地址码与四元式中间代码是介于源语言和目标语言之间的一种表示形式。它的特点是比源语言更接近机器但又不依赖于具体的机器架构。常见的中间代码形式有三地址码、四元式、三元式、间接三元式、静态单赋值形式SSA等。三地址码是最常用的一种中间代码形式。它的特点是每条指令最多有三个操作数形式通常是x y op z。三地址码可以表示算术运算、赋值、条件跳转、无条件跳转、函数调用等。四元式是三地址码的一种具体实现方式用四个字段表示一条指令操作符、第一个操作数、第二个操作数、结果。比如a b c的四元式是(, b, c, a)。四元式的优点是结构统一方便用数组或表格存储。三元式和四元式类似但不保存结果变量名而是用指令的位置来引用结果。比如(, b, c)的结果用“第1条三元式”来表示。三元式的优点是节省空间缺点是当指令位置发生变化时所有引用都需要更新。间接三元式是为了解决三元式的这个问题而设计的。它用一个额外的指针数组来记录三元式的执行顺序这样三元式本身的位置可以不变只需要修改指针数组即可。考试里经常考的是把表达式或控制语句翻译成四元式。比如while (a b) { a a 1; }需要翻译成一系列四元式包括条件判断、跳转、赋值等。这类题目的关键是搞清楚控制流的转移逻辑特别是跳转指令的目标地址。5.3 控制语句的翻译布尔表达式的短路计算控制语句如if、while、for的翻译核心是布尔表达式的翻译。布尔表达式通常需要支持短路计算比如a b如果a为假就不需要计算b了。短路计算的实现方式是为布尔表达式生成跳转代码而不是直接计算出一个布尔值。比如a b可以翻译成如果a为假跳转到Lfalse否则计算b如果b为假跳转到Lfalse否则跳转到Ltrue。这种翻译方式的关键是回填。因为在生成跳转指令时目标地址可能还不知道需要先留空等目标地址确定后再填回去。回填技术是中间代码生成中的一个重要技巧考试里也经常考。我总结了一个回填的口诀先建链表存空缺目标确定再回填。具体来说对于每个需要回填的跳转指令把它加入一个链表当目标地址确定后遍历链表把目标地址填入每条指令。6. 代码优化与目标代码生成让程序跑得更快6.1 代码优化的常见手段局部优化与全局优化代码优化的目标是在不改变程序语义的前提下提高程序的运行效率减少时间或减少程序的空间占用。优化分为局部优化和全局优化。局部优化只在一个基本块内进行全局优化跨越多个基本块。基本块是一段顺序执行的代码只有一个入口和一个出口。基本块的划分是优化的基础。划分方法是先找出所有的入口语句第一条语句、跳转目标、跳转的下一条语句然后从每个入口语句开始直到遇到下一个入口语句或跳转语句为止就是一个基本块。常见的局部优化包括常量折叠在编译时计算常量表达式的值、常量传播把变量替换成已知的常量、公共子表达式消除避免重复计算相同的表达式、死代码消除删除永远不会执行的代码。常见的全局优化包括循环优化代码外提、强度削弱、删除归纳变量、全局公共子表达式消除、全局常量传播等。考试里经常考的是基本块的划分和局部优化。比如给一段代码让你划分基本块然后做常量折叠和公共子表达式消除。这类题目的关键是仔细追踪每个变量的值不要漏掉任何一次赋值。6.2 目标代码生成的关键问题寄存器分配与指令选择目标代码生成是把中间代码转换成特定机器的汇编代码或机器码。这个阶段的两个核心问题是指令选择和寄存器分配。指令选择是为每个中间代码操作选择合适的机器指令。比如a b c可能对应ADD R1, R2, R3这样的指令。指令选择需要考虑机器的指令集特点比如是否支持内存操作数、是否有乘加指令等。寄存器分配是决定哪些变量放在寄存器里、哪些变量放在内存里。寄存器分配的目标是尽量减少访问内存的次数因为寄存器的访问速度比内存快得多。寄存器分配是一个NP难问题实际编译器里通常用启发式算法比如图着色算法。考试里关于目标代码生成的题目相对较少但寄存器分配的基本概念还是需要掌握的。比如什么是寄存器描述符、什么是地址描述符、如何生成高效的代码等。6.3 一个完整的编译流程示例从源码到汇编为了把前面的内容串起来我们来看一个完整的例子。假设有这样一段C语言代码int main() { int a 10; int b 20; int c a b; return c; }词法分析阶段识别出int、main、(、)、{、a、、10、;等Token。语法分析阶段构建出语法树确认函数定义、变量声明、赋值语句、返回语句的结构都正确。语义分析阶段检查类型是否匹配int和int相加得到int检查变量是否已声明。中间代码生成阶段生成三地址码a 10 b 20 c a b return c代码优化阶段可能会做常量折叠把c a b优化成c 30。目标代码生成阶段生成x86汇编mov eax, 10 mov ebx, 20 add eax, ebx ret这个例子虽然简单但完整展示了编译器的各个阶段。考试里的大题通常就是这种综合题要求你写出某个阶段的输出。我的建议是先把整体流程在脑子里过一遍再动手写具体内容这样不容易漏掉步骤。7. 复习策略与考场避坑指南7.1 知识点优先级排序哪些必须掌握哪些可以放一放编译原理的内容很多复习时间有限的情况下需要分清主次。根据我的经验下面这些知识点是必须掌握的词法分析正则表达式转NFA、NFA转DFA、DFA最小化语法分析FIRST集和FOLLOW集的计算、LL(1)分析表的构造、LR(0)和SLR(1)分析表的构造语义分析语法制导翻译的基本概念、类型检查的基本方法中间代码四元式的生成、控制语句的翻译、回填技术代码优化基本块的划分、局部优化的常见手段下面这些知识点可以适当放一放如果时间不够属性文法的高级应用复杂的全局优化算法特定机器的指令选择和寄存器分配的细节7.2 常见计算题的易错点与检查方法编译原理考试里有很多计算题比如求FIRST集、FOLLOW集、构造分析表等。这些题目最容易出错的地方是细节遗漏。我总结了一个检查清单FIRST集是否考虑了ε是否处理了所有产生式FOLLOW集是否加入了开始符号的$是否处理了产生式右部末尾的非终结符LL(1)分析表是否处理了冲突是否所有非终结符都有对应的表项LR(0)项目集闭包操作是否完整转移操作是否遗漏了某些符号SLR(1)分析表归约动作是否只填在FOLLOW集里考场上做完题后建议用反向验证的方法检查随便找一个输入串按照你构造的分析表走一遍看看能不能正确接受或拒绝。如果走不通说明分析表有问题。7.3 从考试到实践编译原理到底有什么用最后说点实在的。很多人觉得编译原理学了没用工作中又不会真的去写编译器。但我的体会是编译原理教给你的是一种系统化的思维方式。词法分析和语法分析里的自动机理论在文本处理、协议解析、正则表达式引擎等场景里直接用到。语义分析里的类型系统和作用域管理在静态代码分析工具、IDE的代码提示功能里用到。中间代码和优化里的数据流分析在程序性能调优、代码混淆、逆向工程里用到。更重要的是编译原理让你理解“从高层抽象到低层实现”的完整链路。这种理解力在你学习新的编程语言、新的框架、新的系统时会帮你更快地抓住本质。我在实际工作中遇到过很多次这样的情况同事对着一个复杂的配置解析问题发愁我一看这不就是个简单的词法分析加语法分析吗用有限自动机的思路一拆解问题就清晰了。这种“降维打击”的能力就是编译原理给你的。复习的时候不要只盯着考试。试着把每个知识点和实际场景联系起来你会发现这门课其实挺有意思的。