简介《哈工大编译原理期末复习》是一份面向高校计算机专业学生与编译原理初学者的完整期末复习资料针对哈工大课程考核重点与难点进行系统梳理可帮助读者在考前快速搭建知识框架、查漏补缺。内容以PDF文档形式打包整理共1个文件压缩包大小31.14MB覆盖编译系统整体结构、语言与文法、词法分析、语法分析、语义分析、中间代码生成、目标代码生成及代码优化等全部核心模块。具体知识点包括DFA与NFA的构造与转换、正则表达式与有穷自动机的关系、文法分类、CFG分析树、三地址码与四元式等并配有章节式复习要点与图示适合按模块分块学习。截至目前已有2311人学习下载尤其适合考前冲刺、系统回顾编译原理知识体系的学习者使用。1. 编译原理期末复习为什么背定义的人最容易翻车编译原理这门课期末复习最容易翻车的地方不是知识点多而是脑子里只有孤立定义。文法、推导、句柄、活前缀、属性文法、三地址码……单看每个词都眼熟一拿到综合大题就不知道第几步该画图、第几步该填表。这篇复习笔记按编译器从词法分析到目标代码生成的完整流水线来组织把每段的输入输出讲清再配上期末最高频的构造题步骤和常见坑。适合正在备考期末的本科生也适合考研复试前想快速捡起编译基础的人。先摆一句话这课能拿到分的题90%落在你能不能闭卷画出状态图、填出分析表、写出四元式。2. 词法分析复习正则式、自动机和扫描器的三条主线词法分析在期末试卷里占的分量不算最大但它是最“机械”——也是最容易拿满分的部分。所有考题都绕着同一条链子转给定正则式构造 NFA再把 NFA 确定化成 DFA最后做最小化。这条链子走顺了你已经把词法分析的大题拿下一多半。2.1 正则式转 NFAThompson 构造法与四步检查词法分析第一个高频大题是“给定正则式构造等价的 NFA”多数教材要求用 Thompson 构造法。原因不只是考试词法工具 flex 内部做的就是这件事先生成 NFA 再确定化成 DFA。所以这道题不掌握后面的子集构造和最小化也做不下去。Thompson 的核心规则很简单每个基本字符 a 构成一个只有两个状态的子 NFA开始状态有一条 a 边到接受状态。然后按三种组合方式拼接。连接 R1R2 时把 R1 的接受态用 ε 边连到 R2 的开始态选择 R1|R2 时新增一个开始态和接受态用 ε 边把两条分支接进去闭包 R* 时在 R 外面套两个状态加一条从新开始态进 R 的 ε 边再加一条从 R 的接受态回到 R 开始态的 ε 边同时留一条直接跳过 R 的 ε 边。运算Thompson 构造动作单个字符 as0 --a-- s1连接 r1r2r1 的接受态 --ε-- r2 的开始态选择 r1|r2新增起点用 ε 分入 r1、r2两终点用 ε 并入新增终点闭包 r*新增起点进 rr 终点回 r 起点另加 ε 直通新终点画完 NFA 之后别急着去确定化先做四步检查每个基本字符是否都有独立的开始态和接受态选择的两条分支是否都用 ε 边并回同一个终点闭包的回头边是否落在闭包子 NFA 的开始态上从总开始状态沿空串能不能走到接受状态。最后一条很多人漏ε 边画少一条NFA 接收的语言就错了后面全白做。我一般用a(b|c)*这个式子练手先做 a 和 b、c 两个原子再做选择最后包星号。练两遍之后(a|b)*abb就不会在状态编号上纠结了。这种构造题状态编号不唯一只要连接关系对阅卷都放行。2.2 子集构造与最小化DFA 状态表填到哪一步才算完由 NFA 到 DFA 的子集构造法是期末另一道白给分题关键动作只有三步先算初始状态集合即 NFA 初态的 ε-closure然后对每个尚未处理的状态集合逐个字符求 move 之后再求一次 ε-closure得到后继状态集合最后新集合就是新状态重复上一步直到没有新集合出现。这里最容易丢分的是“每走一步都要重新闭包”。不少同学只做 move 不重新闭包结果少算一整类字符。可以把 ε-closure 理解成“站在当前状态不读任何字符能到达的所有地方”。每算一个新集合立刻给它编号并补一行表格这样边算边扩表不会漏状态。最小化用分划法就够了先把所有状态按“接受态 / 非接受态”分成两组然后检查每组内各状态读入每个字符后落到哪个组如果同一组内两个状态读同一个字符落到的组不同就把它们拆开反复拆到不能再拆为止。给你一个验证数据正则式(a|b)*abb的最小 DFA 恰好是 5 个状态。你画完自检一下abb、aabb、ababb、babb 应该全部被接受abab 应该被拒绝。如果你画出 6 个以上状态先检查是不是把 ε 闭包里的临时状态当成独立状态了。如果课程要求按 Hopcroft 算法写期末答题用分划法也能得到同样结果阅卷通常认可。2.3 手写扫描器还是 flex实验课给期末考喂了什么分实验课用 flex 生成器写词法分析很快但期末手写题不允许用工具。最好的走法是实验能 flex 就 flex但你至少要亲手手写一次极简扫描器。方式适合场景期末相关度手写状态转换表 / 命令式扫描理解词法原理高期末常考flex / lex快速生成复杂词法规则实验高期末低JavaCC 等一批工具词法和语法一起生成实验参考下面这段是手写扫描器最核心的骨架识别标识符、整数和赋值号关键逻辑就这么几行int next_token() { while (isspace(ch)) ch getchar(); // 跳过空白 if (isalpha(ch)) { // 标识符或关键字开头 char buf[64]; int i 0; while (isalnum(ch)) { buf[i] ch; ch getchar(); } buf[i] \0; return is_keyword(buf) ? KEYWORD : IDENT; } if (isdigit(ch)) { // 无符号整数 int val 0; while (isdigit(ch)) { val val * 10 ch - 0; ch getchar(); } return NUM; } if (ch ) { // 区分赋值号和相等判断 ch getchar(); return (ch ) ? EQ : ASSIGN; } return ERROR; }这段代码体现的是最长匹配原则。比如读入必须读到时再往后看一眼不能读一个字符就立刻返回否则会被拆成两个 token。代码里的ch getchar()配合后面的判断就是“往前多看一位”的典型实现。用 Java 写实现也很常见语言不影响原理核心是一样的 token 定义和状态转移。实验课对期末最大的反哺就在这你手写一遍这个骨架之后期末考试里“识别标识符、整数、关系运算符”这类题基本就是默写。如果你只用了 flex 而没手写过考前一定要补一次哪怕只写这个极简版也足够帮你理解状态表是怎么来的。3. 语法分析复习LL 与 LR 家族的构造题都在考同一件事语法分析是期末复习的重头戏。题型说白了只有两簇自顶向下LL、递归下降和自底向上LR、SLR、LALR。两簇的公分母是集合计算——FIRST、FOLLOW。所有语法分析题不管表面问法是什么最终都会落到“集合算对没有、表格填对没有”这两件事上。3.1 FIRST、FOLLOW 与 FIRSTVT先把集合算对后面全是顺的所有 LL(1) 题都从求 FIRST 和 FOLLOW 开始。求 FIRST 的迭代做法对每个产生式右部从左往右看遇到终结符直接加入 FIRST遇到非终结符 X把 FIRST(X) 去掉 ε 后加入如果 X 能推出 ε 就继续看下一个符号直到某个符号确定不能为空就停下如果产生式本身是 A→ε就把 ε 加入 FIRST(A)。整个循环重复到所有集合不再变大为止。求 FOLLOW 的迭代做法更集中两条规则对产生式 A→αBβ把 FIRST(β) 去掉 ε 后加入 FOLLOW(B)如果 β 能推出 ε或者 β 根本不存在就把 FOLLOW(A) 整体加入 FOLLOW(B)。同样重复到不再变化。拿期末考试出场率最高的经典表达式文法来练E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id求完之后你得到两组集合非终结符FIRSTFOLLOWE{(, id}{), #}E{, ε}{), #}T{(, id}{, ), #}T{*, ε}{, ), #}F{(, id}{*, , ), #}核对方法有一条所有非终结符的 FOLLOW 最终都该通过开始符号染上 #。如果你算完发现某个能出现在句子末尾的非终结符 FOLLOW 里没有 #十有八九是漏了“若 β 可空则并入 FOLLOW(A)”这一步。有些同学到处找清华大学出版社第三版第二章答案对着背其实自己按迭代法算一遍比背答案可靠得多。3.2 LL(1) 判定与预测分析表消除左递归后别忘了验证LL(1) 的大题通常两问判断是不是 LL(1)构造预测分析表。判定条件三条同一非终结符的各个右部 FIRST 集两两不相交若某个右部可空则 ε 属于 FIRST(A) 时FOLLOW(A) 与其它右部的 FIRST 集不相交文法本身没有左递归和公共左因子。消除直接左递归的公式只有一个A→Aα|β 变成 A→βAA→αA|ε。注意这只对直接左递归有效间接左递归要先排序再逐步代入具体的坑放到后面避坑章节再展开。填预测分析表也只有两步。第一步对每个产生式 A→α把所有终结符 a∈FIRST(α) 的位置 M[A,a] 填入这个产生式。第二步如果 ε∈FIRST(α)那么对所有 b∈FOLLOW(A)把产生式填入 M[A,b]。填表时还带出另一重功能填入过程中如果你发现某个格子有两个产生式说明文法不是 LL(1)。继续用上面那个经典文法预测分析表应该长这样非终结符填入位置产生式Eid、 (E→TEEE→TEE)、#E→εTid、 (T→FTT*T→*FTT、)、#T→εFidF→idF(F→(E)拿到一张空白表你直接按这两步往里填判定的活顺便就干完了。考试时可以在一张表上同时完成两问省时间还能互相印证。3.3 LR 家族对比从 LR(0) 到 LALR 的状态数与冲突差异LR 分析家族是期末最劝退的一块但它也就围着两个概念转项目集规范族和冲突消解。构造 LR(0) 自动机的步骤是给文法加一个增广产生式 S→S初始项目集是 S→·S 的闭包对每个项目集中的每个文法符号做 goto生成新项目集重复到最后不再有新项目集为止。闭包的规则一句话点号后面是非终结符 B就把 B 的全部产生式以 B→·γ 的形式加进当前项目集循环到不能再加。这句几乎是每年必考要么填空要么选择。LR 家族四个成员的区别期末最爱考的就是这张对比分析器项目集形式状态数规模冲突消解方式LR(0)不带向前看最小不额外消解SLR(1)LR(0) 项目集 FOLLOW与 LR(0) 相同用 FOLLOW 集判断是否归约LR(1)每个项目带向前看符号最大常翻倍向前看符号精确判定LALR(1)合并 LR(1) 同心项目集与 LR(0) 同量级合并可能产生归约-归约冲突关于 LR(1) 闭包有一个必须背下来的结论对项目 [A→α·Bβ, a] 做闭包时新增项目 [B→·γ, b] 的向前看符号 b 来自 FIRST(βa)。这里 a 是当前项目的向前看符号不是固定的 #很多人在这里丢分。LALR 还有一条高频结论合并同心项目集不可能产生新的移进-归约冲突但可能产生新的归约-归约冲突。理由是移进动作由项目核心决定向前看符号只参与归约判断。这条结论在选择填空里出现率极高。3.4 递归下降代码题背下骨架比临场推理快十倍递归下降和 LL(1) 预测分析表是同一件事的两种表达。每个非终结符对应一个函数每个产生式对应一段 if 分支。期末如果考手写代码题基本就是让你补全下面这种骨架void E() { T(); E_prime(); } void E_prime() { if (lookahead ) { match(); T(); E_prime(); } // 没有匹配到 就直接返回相当于选择 ε 产生式 }配套的 match 函数长这样void match(int token) { if (lookahead token) { lookahead next_token(); // 读入下一个 token } else { error(unexpected token); } }函数名就是非终结符if 分支就是该非终结符的一个候选产生式函数自然返回等于选择了 ε 产生式。这跟预测分析表 M[A,a] 的格子是一一对应的。实验课如果让你写表达式计算器把语义动作直接塞进E_prime函数的match()之后——在匹配完时立刻生成一条三地址码——语法分析和中间代码生成就一起练完了。注意 error() 至少要打印当前行号。很多同学写递归下降不写错误处理遇到非法输入就一直递归到栈爆掉也查不出原因。留个行号输出问题定位快十倍。4. 语义分析、中间代码与优化从属性文法到四元式怎么连语法分析拿到的是“这句话合不合语法”语义分析回答的是“这句话是什么意思”。期末考到这一章题型从画图变成了写属性、填符号表、翻译三地址码。这块内容表面琐碎实际上有一条链子属性文法把类型、值等信息挂到语法树上语义动作把语法树变成三地址码符号表和运行时存储为变量和过程调用提供地址基础。4.1 综合属性与继承属性依赖图能帮你避开赋值顺序的坑属性文法里最常考的就是判断属性类型。综合属性的特点是只需看子节点和自己的属性就能算出来。继承属性正好相反必须从父节点、兄弟节点或者更外层环境传入。判断技巧是反过来问这个属性能不能只从语法树的子树内部得到能就是综合的不能就是继承的。最经典的例子是D → T id。T.type 是综合属性它从 T 子节点的词法值综合而来而 id.type 是继承属性它从左边兄弟 T.type 继承。数组元素的偏移量也是典型继承属性——不知道数组声明里的每维长度你根本算不出某个元素在内存里的位置。如果考到求值顺序用依赖图最稳。每个属性画成一个节点每条属性计算规则画一条有向边属性之间如果有依赖关系就从被依赖者指向依赖者。图建完之后做一次拓扑排序排序结果就是安全的求值顺序。只凭感觉“先子后父”应对综合属性没问题但一掺进继承属性就容易顺序颠倒。4.2 三地址码与回填声明翻译和数组下标按统一模板写三地址码是期末手写题的大头常见形式有四元式、三元式和间接三元式。考试最常写四元式把 操作符、左操作数、右操作数、结果 四个字段一次性写出来。指令类型不多一张表能收住类别形式说明赋值x y op z / x y二元运算与复制数组x y[i] / x[i] y下标访问与写回跳转goto L无条件转移条件跳转if x relop y goto L关系比较后转移过程调用param x / call f / return参数传递、调用、返回while (a b) a a 1;的标准翻译长这样(1) if a b goto (3) (2) goto (5) (3) t1 a 1 (4) a t1 (5) goto (1)你能看到第 (2) 行跳到 (5) 是为了绕过循环体第 (5) 行跳回 (1) 是回到循环判断。翻译过程中目标地址不是一开始就能确定的需要先留空、等知道跳哪了再回头填这就是回填。期末考里最常见的问法就是“补全跳转目标”。数组下标翻译也常考x a[i][j]假设每行 n 个元素、每个元素 w 字节翻译结果应该是t1 i * n t1 t1 j t2 t1 * w t3 a_base t2 x t3多维度数组的地址计算公式就是行优先的线性化先算行偏移再算列偏移最后乘元素宽度。第一次写会容易漏了乘宽度那步考前一晚值得单独过一遍。4.3 符号表与运行时存储一张活动记录图能串起半章考点符号表这一节期末经常以画结构的形式出题给你一段嵌套的 C 或 Pascal 风格程序要求画出符号表以及作用域链。基本规则是查符号从内层往外层找内层作用域里可以重新定义外层同名变量符号表条目要有名字、类型、作用域指针和存储偏移量。运行时存储里最实用的考点是活动记录布局。每个函数调用都会在栈上压入一个活动记录典型布局从栈底到栈顶是这样区域作用返回地址调用点下一指令动态链调用者的栈帧指针参数区实参值局部变量区函数内部变量临时变量区编译期生成的中间量考试常挖的坑是问返回地址在局部变量的哪一侧或者问动态链指向谁。动态链永远指向调用者的活动记录底部不是指向栈底。如果课程讲过嵌套过程这里还会补一个访问链或 display 表的概念——访问链指向定义该过程的词法外层过程的最新活动记录一句话带过即可。4.4 优化与目标代码生成期末常考的六种优化识别特征优化部分期末以选择、填空为主认得出就够了。最常出现的六种优化常量折叠、常量传播、复写传播、死代码删除、公共子表达式消除、循环不变式外提。每种都有一个识别特征常量折叠是2*3直接写成6常量传播是把恒为常量的变量替换成常量复写传播是xy之后遇到 x 直接用 y死代码删除是删掉结果不被任何语句使用的计算公共子表达式消除是两次ab只算一次循环不变式外提是把循环体内不随迭代变化的运算搬到循环前。如果考大题多半给你一个基本块要你画 DAG 图。DAG 的构造要点叶子是变量和常量内部节点是运算符两个相同运算节点值相同且子节点顺序相同就可以合并。一张 DAG 画完公共子表达式消除和死代码删除的答案就同时出来了。5. 期末复习避坑五个高频失分点的现象与排查以下五个坑是我每年都会被问一遍的高频失分点每条都按“现象、原因、解决”写清楚。考前对照排查比自己闷头刷题效率高得多。5.1 求 FOLLOW 时漏掉可空符号的传递现象算经典文法E→TE、E→TE|ε这类题最后得出 FOLLOW(T){)}丢了#和)的传递整道 LL(1) 判断题的 FOLLOW 全错。原因只执行了“把 FIRST(E) 去掉 ε 加入 FOLLOW(T)”这一步没有继续判断 E 可空时还要把 FOLLOW(E) 整体并入 FOLLOW(T)。解决求 FOLLOW 时严格按两条规则操作。右部形如 A→αBβ 时先做 FIRST(β)-{ε}再检查 β 能否推出 ε如果能就追加 FOLLOW(A) 整体并入 FOLLOW(B)。每次扫完所有产生式之后循环一遍集合不再变化才停手。检查答案时用前面那张经典表达式的表对着核少一个符号都能立刻发现。5.2 消除间接左递归只做了一半现象给定文法S→Aa|b、A→Sc|d有人直接把 S 或 A 套用消除直接左递归的公式结果越消越乱。原因S 通过 A 间接左递归即 S⇒Aa⇒Sca直接套公式时根本没有直接左递归可消必须先代入再处理。解决按三步走。第一步给非终结符排个序第二步把间接左递归变成直接左递归具体到这个例子把 S 的产生式代入 AA → Sc|d A → (Aa|b)c|d A → Ac|bc|d此时 A 有了直接左递归。第三步套公式A → bcA | dA A → cA | ε最后把新 A 代回 S 的产生式S → bcAa | dAa | b试卷上如果给了多个非终结符互相间接左递归先编号再从头到尾代入一步都不能跳。5.3 LR 项目集规范族画到一半就停手现象画 LR(0) 自动机时画了三四个项目集觉得“剩下的看起来差不多”结果 GOTO 表少了转移边后面 SLR 分析表跟着错。原因closure 没有做彻底。点号后面是非终结符 BB 的所有产生式都必须加进来而且要一直加到不能再加。很多人只展开了一层少加了一个产生式状态就少了一个。解决采用“表格法”代替凭感觉画图。把每个项目集编号单独登记三列当前状态编号、输入符号、跳转目标编号。每个状态都先把闭包算完整再对每一个文法符号做 goto所有结果先写进表里最后再根据这张表去画自动机。表里任何一格填了重复目标编号说明状态合并有问题一眼就能抓到。5.4 递归下降的 lookahead 与 match 顺序写反现象递归下降函数跑起来死循环或者把明明合法的输入判成语法错误。原因常见写法是先lookahead next_token()再调用 match等于跳过了当前 token 的判断。正确的 match 必须“先比后读”比较的是当前 lookahead读完新 token 后更新 lookahead。写反了第一次判断就拿不到正确输入。解决统一按这个模式写函数开头只检查全局变量 lookahead匹配成功后才更新 lookahead任何分支都不写“先读 token 再判断”。调试时在 error() 里打印当前 lookahead 和行号马上能看出是读过头还是判断漏了分支。5.5 三地址码回填时目标标号不统一现象翻译 while 或 if-else 时goto 的目标写到别的地方去或者同一个标号被两段代码复用翻译结果逻辑错乱。原因手写标号时靠眼睛记边翻边编前后不一致。代码一长编号就乱了。解决用一个计数器维护标号每生成一个 Lx 就自增同时按语句模板翻译。while 语句的模板是固定的L1: 条件跳转 L2 goto L3 L2: 循环体 goto L1 L3: 出口if-else 也有固定模板。考试时先写模板、再填内容标号就不会乱。填空或补全题里看到不完整的跳转先把模板框架列出来再对号入座正确率明显更高。6. 考前两周的验证方法把整条流水线画成一幅图考前两周最该做的事是把知识从“名词解释”改成“带输入输出的处理过程”。我自己的习惯是找一张 A4 白纸从上到下画一条完整流水线源程序字符流 → token 流 → 语法树 → 带属性的语法树 → 三地址码 → 优化后的中间代码 → 目标代码。每段中间在右侧写一行这个阶段最常考的题型。阶段输入输出对应期末题型词法分析源程序字符流token 流自动机、状态表、手写扫描器语法分析token 流语法树LL(1)、LR、递归下降语义分析语法树属性树、符号表属性文法、类型检查中间代码生成属性树三地址码四元式、回填、数组寻址优化三地址码优化后的代码公共子表达式、DAG目标代码生成中间代码目标指令寄存器分配、伪汇编画完之后用五个问题来自检能否十分钟内不看书求出一个给定文法的 FIRST/FOLLOW能否闭卷画出(a|b)*abb对应的五状态 DFA 并标出终态能否说清 SLR、LR(1)、LALR 的状态数关系和冲突差异能否把while(ab) aa1写成标准四元式并说明回填位置能否手写出一个表达式文法的递归下降骨架并带错误处理。五个问题里任何一个答不上来就回到对应章节重做一两道大题而不是去背名词解释。有一次我考前画这条流水线在“中间代码生成”处卡住了——发现自己从来没把符号表里的偏移量和三地址码的下标翻译连起来。第二天专门把数组元素寻址算了一遍结果那年的实验题恰好考到这一段。这个习惯后来保持到了工作里接手一个编译器项目时第一件事就是先画出全流程的输入输出而不是急着翻代码。考前再把这张图过一遍比翻十遍笔记都有用。希望帮到你。本文还有配套的精品资源点击获取