1. 开篇这门课为什么让人头皮发麻又该怎么速成编译原理期末速成笔记说白了就是我考这门课之前攒下来的一整套复习思路。如果你现在打开课本发现满页都是自动机、文法、FIRST集、项目集闭包这些东西脑子里一片空白那这篇东西就是写给你的。它不打算把你培养成写编译器的人目标很直接在有限的时间里把考试要考的东西拎清楚知道哪些是必考、哪些是套路题、哪些看一眼就能拿分同时把几个核心概念真正搞懂而不是背下来第二天就忘。先说说这门课为什么难。它难在抽象。操作系统你还能想象成管理进程和内存计算机网络你能对应到插网线、发数据包可编译原理一上来就是字符串集合状态转移推导树全是纸面上的符号游戏。很多人卡住不是因为不聪明而是没找到一个把符号和实际意义对应起来的抓手。我的经验是你得先建立起编译器就是一条流水线的画面感每个阶段负责一道加工工序后面所有细节都往这条流水线上挂这样零散的知识点才会连成串。适合谁看这篇笔记一是这学期正在上编译原理、马上要期末的人二是想临时抱佛脚但不想考太差的人三是准备面试被问到词法分析和语法分析的区别LR和LL哪个更强这类问题、想快速把知识捡回来的人。热词里提到的词法分析实验、第三版答案、哈工大课件、面试题本质上是同一批知识的不同使用场景我都会照顾到。我特意把复习顺序做了调整不是按课本章节从前往后啃而是按分值密度和上手难度重新排。词法分析最机械、最容易速成先拿下语法分析是大头要花最多时间语法制导翻译和中间代码属于理解了就好拿分最后的优化和代码生成分值相对分散抓典型例题即可。下面按这个顺序展开每一块我都会告诉你为什么这么学、坑在哪里、考试怎么出。2. 先把编译器的全局地图画出来2.1 六个阶段到底各干什么编译器处理一个源程序粗略走六个阶段词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。速成阶段你不需要背每个阶段的完整定义但一定要能用一句话说清输入是什么、输出是什么。词法分析把字符流切成一个个有意义的记号Token比如int、x、、10。语法分析把 Token 序列组织成语法树判断符不符合文法。语义分析做类型检查、作用域检查语法对不代表意思对int string就是在这里被拦下来的。中间代码生成把语法树翻译成一种和机器无关的表示常见的是三地址码。代码优化在不改变程序语义的前提下让中间代码跑得更快、占得更少。目标代码生成翻译成具体机器的汇编或机器码还要分配寄存器。这张图为什么重要因为考试特别喜欢考某个错误在哪个阶段被发现。比如括号不匹配是语法错误变量没声明是语义错误除零这种运行期才炸的不算编译期错误。你把六阶段在心里排成一条线这类题基本白送。2.2 用分值分布决定复习优先级我复盘过好几份不同学校的真题分值大概长这样你可以照着调整精力知识模块典型占比速成难度建议投入词法分析NFA/DFA15%~20%低优先拿下语法分析LL/LR30%~40%高主力攻坚语法制导翻译10%~15%中理解为主中间代码与优化15%~20%中抓典型题概念与简答10%~15%低考前突击看到没词法和语法加起来就过半了这两块是绝对的主战场。很多人一上来就死磕 LR(1) 项目集结果最基础的 Thompson 构造法都没练熟这是典型的用力用错地方。我建议你先花一天把词法分析的所有题型刷一遍拿到稳稳的基础分再回头啃语法分析。注意不同教材的章节顺序和术语略有差异比如有的书把语义分析和中间代码生成合在一起讲复习时以你老师划的重点为准别被不同版本术语绕晕。很多同学问为什么不直接从难的开始因为速成最怕挫败感。先做几道能快速做对的题把手感和信心建立起来后面啃硬骨头才扛得住。这个顺序其实是我踩过坑之后改的——第一次复习我是按课本从词法啃到尾结果卡在 LR 分析表那里就再没翻过后面几章最后中间代码那部分直接空着交卷。3. 词法分析有限自动机是绕不过去的坎3.1 正则表达式到 NFAThompson 构造法是标准套路词法分析的核心任务说白了就是给你一个规则判断一串字符符不符合这个规则。规则用正则表达式描述实现用有限自动机。考试最常考的就是三种转换正则表达式转 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 最小化分割法一步步来最小化就是把等价的状态合并。标准方法是分割法划分法先把所有状态分成两组——接受状态一组、非接受状态一组。对每组检查组内状态读同一个字符后会不会落到不同的组。会就把这组再拆开。重复第 2 步直到所有组都不能再拆。每个最终组取一个代表状态重新画转移。关键名词叫可区分两个状态如果读某个字符串后一个接受一个不接受它们就不同。最小化的本质上就是不断找出可区分的状态对把不可区分的合并。我建议你拿一道标准题反复手算三遍直到能闭着眼睛走完流程。因为分割法的步骤是死的会了就是一劳永逸的送分题不会就是每次都栽。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 | idid 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算出来是非终结符FIRSTFOLLOWE( , id$ , )E , ε$ , )T( , id , ) , $T* , ε , ) , $F( , 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(1)/LALR分析方向自上而下最左推导自下而上最右推导逆序构造难度低算 FIRST/FOLLOW高构造项目集文法能力弱强冲突处理消除左递归用向前看符号实际应用手写递归下降自动生成工具速成建议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 高频题型清单我整理了一下最常出现的题型你照着刷题型出没频率拿分要点正则转 NFA极高Thompson 构造别漏 ε 边NFA 转 DFA极高子集构造闭包算全DFA 最小化高分割法注意可区分消除左递归/提左公因子高公式套用检查完整性求 FIRST/FOLLOW极高起始符号含 $构造 LL(1) 表并判冲突极高冲突 非 LL(1)构造 LR 项目集高闭包 GOTO三地址码/四元式高临时变量编号别乱布尔表达式回填中短路求值分清 and/orDAG 局部优化中相同子表达式合并6.3 面试题其实和期末是一套东西热词里有人搜编译原理面试题我顺带说一句面试问的编译原理深度往往不如期末笔试卷但更爱问原理性理解。常见问题比如词法分析和语法分析的区别一个处理字符到 Token一个处理 Token 到语法树、为什么用中间代码便于优化和跨平台、LL 和 LR 谁更强LR 能处理的文法集合更大但构造复杂。一个反直觉的点面试官很少让你现场手推 LR 分析表却经常问你了解过哪些编译器正则表达式引擎的原理。这类问题答好了加分很多所以别把知识只用在考试上理解到位了面试是顺带的事。7. 踩坑实录这些错误我替你试过了复习和考试里最容易栽的地方我都踩过整理成一个速查表给你现象原因解决办法DFA 状态数总是对不上ε-闭包只取了一层闭包要算到不动LL(1) 表到处是冲突忘了提左公因子先消左递归再提公因子FIRST 集把 ε 漏了没考虑可空非终结符能推 ε 的都要带上FOLLOW 集忘了 $起始符号特殊起始符号 FOLLOW 必含 $LR 表规约位置全错闭包没展开完整点在非终结符前要展开全部产生式四元式临时变量重复编号没递增用一个全局计数器回填链断开makelist/merge 用混链头链尾要分清再分享几条课本上不会写的实操心得。第一画图比写字快。NFA、DFA、语法树、DAG 全都画出来比纯文字描述清楚十倍改错也方便。我考试时习惯先在草稿纸上画草稿确认无误再誊抄到答题卡。第二先算小文法再套大文法。遇到复杂文法别硬上先拿最简单的一条产生式走一遍流程确认方法记住了再处理整题。很多人是方法没记牢就冲进大题结果步骤全乱。第三符号命名保持统一。临时变量用 t1、t2、t3 递增状态用 0、1、2 编号不要一会儿 A 一会儿 S0自己都会看花眼。这个习惯看着小实际能省不少粗心分。第四真题至少做两套。不同学校的出题风格差别很大有的偏爱 LR 大计算有的爱考概念简答。做两套你就能摸到老师的口味复习也能针对性收口。注意速成不等于什么都不懂。像 FIRST/FOLLOW、闭包这些核心概念理解之后记一辈子纯靠背的话换个文法就懵了。时间再紧也要给理解留出空间。说个我自己的教训收尾。我第一次考这门课死活想不通 LR 项目集为什么要做闭包硬背步骤结果题目换个文法我就全错。第二次我花了一个晚上专门画项目集、逐条对照突然就通了——闭包其实就是我现在期待看到 A那 A 能怎么展开我全列出来备用。想通这一句之后LR 那一片题再没丢过分。所以编译原理这门课速成的关键不是背得多快而是找到那几个让你啊原来是这个意思的瞬间。把词法那三个转换、LL 的 FIRST/FOLLOW、LR 的闭包这三关过了期末基本就稳了。 编译原理期末速成：词法语法分析与LR闭包笔记
1. 开篇这门课为什么让人头皮发麻又该怎么速成编译原理期末速成笔记说白了就是我考这门课之前攒下来的一整套复习思路。如果你现在打开课本发现满页都是自动机、文法、FIRST集、项目集闭包这些东西脑子里一片空白那这篇东西就是写给你的。它不打算把你培养成写编译器的人目标很直接在有限的时间里把考试要考的东西拎清楚知道哪些是必考、哪些是套路题、哪些看一眼就能拿分同时把几个核心概念真正搞懂而不是背下来第二天就忘。先说说这门课为什么难。它难在抽象。操作系统你还能想象成管理进程和内存计算机网络你能对应到插网线、发数据包可编译原理一上来就是字符串集合状态转移推导树全是纸面上的符号游戏。很多人卡住不是因为不聪明而是没找到一个把符号和实际意义对应起来的抓手。我的经验是你得先建立起编译器就是一条流水线的画面感每个阶段负责一道加工工序后面所有细节都往这条流水线上挂这样零散的知识点才会连成串。适合谁看这篇笔记一是这学期正在上编译原理、马上要期末的人二是想临时抱佛脚但不想考太差的人三是准备面试被问到词法分析和语法分析的区别LR和LL哪个更强这类问题、想快速把知识捡回来的人。热词里提到的词法分析实验、第三版答案、哈工大课件、面试题本质上是同一批知识的不同使用场景我都会照顾到。我特意把复习顺序做了调整不是按课本章节从前往后啃而是按分值密度和上手难度重新排。词法分析最机械、最容易速成先拿下语法分析是大头要花最多时间语法制导翻译和中间代码属于理解了就好拿分最后的优化和代码生成分值相对分散抓典型例题即可。下面按这个顺序展开每一块我都会告诉你为什么这么学、坑在哪里、考试怎么出。2. 先把编译器的全局地图画出来2.1 六个阶段到底各干什么编译器处理一个源程序粗略走六个阶段词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。速成阶段你不需要背每个阶段的完整定义但一定要能用一句话说清输入是什么、输出是什么。词法分析把字符流切成一个个有意义的记号Token比如int、x、、10。语法分析把 Token 序列组织成语法树判断符不符合文法。语义分析做类型检查、作用域检查语法对不代表意思对int string就是在这里被拦下来的。中间代码生成把语法树翻译成一种和机器无关的表示常见的是三地址码。代码优化在不改变程序语义的前提下让中间代码跑得更快、占得更少。目标代码生成翻译成具体机器的汇编或机器码还要分配寄存器。这张图为什么重要因为考试特别喜欢考某个错误在哪个阶段被发现。比如括号不匹配是语法错误变量没声明是语义错误除零这种运行期才炸的不算编译期错误。你把六阶段在心里排成一条线这类题基本白送。2.2 用分值分布决定复习优先级我复盘过好几份不同学校的真题分值大概长这样你可以照着调整精力知识模块典型占比速成难度建议投入词法分析NFA/DFA15%~20%低优先拿下语法分析LL/LR30%~40%高主力攻坚语法制导翻译10%~15%中理解为主中间代码与优化15%~20%中抓典型题概念与简答10%~15%低考前突击看到没词法和语法加起来就过半了这两块是绝对的主战场。很多人一上来就死磕 LR(1) 项目集结果最基础的 Thompson 构造法都没练熟这是典型的用力用错地方。我建议你先花一天把词法分析的所有题型刷一遍拿到稳稳的基础分再回头啃语法分析。注意不同教材的章节顺序和术语略有差异比如有的书把语义分析和中间代码生成合在一起讲复习时以你老师划的重点为准别被不同版本术语绕晕。很多同学问为什么不直接从难的开始因为速成最怕挫败感。先做几道能快速做对的题把手感和信心建立起来后面啃硬骨头才扛得住。这个顺序其实是我踩过坑之后改的——第一次复习我是按课本从词法啃到尾结果卡在 LR 分析表那里就再没翻过后面几章最后中间代码那部分直接空着交卷。3. 词法分析有限自动机是绕不过去的坎3.1 正则表达式到 NFAThompson 构造法是标准套路词法分析的核心任务说白了就是给你一个规则判断一串字符符不符合这个规则。规则用正则表达式描述实现用有限自动机。考试最常考的就是三种转换正则表达式转 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 最小化分割法一步步来最小化就是把等价的状态合并。标准方法是分割法划分法先把所有状态分成两组——接受状态一组、非接受状态一组。对每组检查组内状态读同一个字符后会不会落到不同的组。会就把这组再拆开。重复第 2 步直到所有组都不能再拆。每个最终组取一个代表状态重新画转移。关键名词叫可区分两个状态如果读某个字符串后一个接受一个不接受它们就不同。最小化的本质上就是不断找出可区分的状态对把不可区分的合并。我建议你拿一道标准题反复手算三遍直到能闭着眼睛走完流程。因为分割法的步骤是死的会了就是一劳永逸的送分题不会就是每次都栽。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 | idid 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算出来是非终结符FIRSTFOLLOWE( , id$ , )E , ε$ , )T( , id , ) , $T* , ε , ) , $F( , 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(1)/LALR分析方向自上而下最左推导自下而上最右推导逆序构造难度低算 FIRST/FOLLOW高构造项目集文法能力弱强冲突处理消除左递归用向前看符号实际应用手写递归下降自动生成工具速成建议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 高频题型清单我整理了一下最常出现的题型你照着刷题型出没频率拿分要点正则转 NFA极高Thompson 构造别漏 ε 边NFA 转 DFA极高子集构造闭包算全DFA 最小化高分割法注意可区分消除左递归/提左公因子高公式套用检查完整性求 FIRST/FOLLOW极高起始符号含 $构造 LL(1) 表并判冲突极高冲突 非 LL(1)构造 LR 项目集高闭包 GOTO三地址码/四元式高临时变量编号别乱布尔表达式回填中短路求值分清 and/orDAG 局部优化中相同子表达式合并6.3 面试题其实和期末是一套东西热词里有人搜编译原理面试题我顺带说一句面试问的编译原理深度往往不如期末笔试卷但更爱问原理性理解。常见问题比如词法分析和语法分析的区别一个处理字符到 Token一个处理 Token 到语法树、为什么用中间代码便于优化和跨平台、LL 和 LR 谁更强LR 能处理的文法集合更大但构造复杂。一个反直觉的点面试官很少让你现场手推 LR 分析表却经常问你了解过哪些编译器正则表达式引擎的原理。这类问题答好了加分很多所以别把知识只用在考试上理解到位了面试是顺带的事。7. 踩坑实录这些错误我替你试过了复习和考试里最容易栽的地方我都踩过整理成一个速查表给你现象原因解决办法DFA 状态数总是对不上ε-闭包只取了一层闭包要算到不动LL(1) 表到处是冲突忘了提左公因子先消左递归再提公因子FIRST 集把 ε 漏了没考虑可空非终结符能推 ε 的都要带上FOLLOW 集忘了 $起始符号特殊起始符号 FOLLOW 必含 $LR 表规约位置全错闭包没展开完整点在非终结符前要展开全部产生式四元式临时变量重复编号没递增用一个全局计数器回填链断开makelist/merge 用混链头链尾要分清再分享几条课本上不会写的实操心得。第一画图比写字快。NFA、DFA、语法树、DAG 全都画出来比纯文字描述清楚十倍改错也方便。我考试时习惯先在草稿纸上画草稿确认无误再誊抄到答题卡。第二先算小文法再套大文法。遇到复杂文法别硬上先拿最简单的一条产生式走一遍流程确认方法记住了再处理整题。很多人是方法没记牢就冲进大题结果步骤全乱。第三符号命名保持统一。临时变量用 t1、t2、t3 递增状态用 0、1、2 编号不要一会儿 A 一会儿 S0自己都会看花眼。这个习惯看着小实际能省不少粗心分。第四真题至少做两套。不同学校的出题风格差别很大有的偏爱 LR 大计算有的爱考概念简答。做两套你就能摸到老师的口味复习也能针对性收口。注意速成不等于什么都不懂。像 FIRST/FOLLOW、闭包这些核心概念理解之后记一辈子纯靠背的话换个文法就懵了。时间再紧也要给理解留出空间。说个我自己的教训收尾。我第一次考这门课死活想不通 LR 项目集为什么要做闭包硬背步骤结果题目换个文法我就全错。第二次我花了一个晚上专门画项目集、逐条对照突然就通了——闭包其实就是我现在期待看到 A那 A 能怎么展开我全列出来备用。想通这一句之后LR 那一片题再没丢过分。所以编译原理这门课速成的关键不是背得多快而是找到那几个让你啊原来是这个意思的瞬间。把词法那三个转换、LL 的 FIRST/FOLLOW、LR 的闭包这三关过了期末基本就稳了。