简介面向哈工大编译原理期末复习的完整版资料覆盖编译系统结构、语言及其文法、词法分析、语法分析、语义分析、中间代码生成、目标代码生成与代码优化等全部核心模块适合期末系统梳理与查漏补缺。内容按课堂知识体系展开从串、字母表、文法定义与分类到正则表达式、有穷自动机DFA/NFA、分析树、三地址码与四元式、寄存器分配等关键难点均有清晰归纳同时结合典型编译流程串讲各个阶段便于快速对照教材巩固理解。对DFA与NFA的关系、子集构造法、中间表示转换等易混淆点也做了对比整理帮助加深记忆。包体为一份PDF文档大小31.14MB完整度高、层次分明可打印或电子阅读。目前已有2311人学习下载是准备期末考试的实用参考资料。1. 为什么哈工大编译原理期末复习要抓全局一份完整版复习笔记的用法期末周拿到这份《哈工大编译原理期末复习完整版涵盖编译原理所有内容》时多数人的第一反应是“先背概念再刷题”。实际上编译原理这门课的知识结构是链式的词法产出的记号送给语法语法产出的分析树送给语义语义动作驱动中间代码生成最后才是目标代码。哪个环节断了后面的题都做不动。这份复习文档的价值在于把整条链按章节收拢适合两类人一类是临近考试需要快速建立知识框架的另一类是实验做到一半、理论课没跟上回头补洞的。需要先说明一点文档资料不带可执行代码但它能把实验题和定理对应上这是拆这份资源时最值得留意的部分。2. 词法与语法分析从正规式到 DFA、LL(1) 与 LR 的判定闭环对绝大多数期末卷来说词法分析和语法分析加起来能占四成以上的分值。复习这一章的重心不是记住“什么是正则表达式”而是能把一条正规式手工转成最小化 DFA并能在 LL(1) 和 LR 两个方向上都做出正确的判断。这一部分主要有三个落点。2.1 词法分析正规式转 DFA 的五步操作实验第一关词法分析在实验里通常对应一个用 Java 写的词法分析器。你输入一段源码文本它输出一串 token。期末笔试不会让你写完整代码但一定考正规式到 DFA 的构造。常见做法是三步走先用 Thompson 构造法把正规式转成 NFA再用子集构造法把 NFA 确定化为 DFA最后对 DFA 做最小化。三步缺一分值就丢。以正规式a(b|c)*为例转化过程的核心动作可以列成一张表。步骤动作要检查的点1拆成基本子表达式画出 a 与 (bc)* 的拼接2为每个子表达式引入新的开始和接受状态状态编号别跳后面子集构造要引用3用子集构造法从 NFA 的开始状态做 ε-闭包任何一个 NFA 状态都不能漏4对每个输入符号计算转移并得到新子集DFA 状态数量可能膨胀属正常现象5删除不可达状态并合并等价状态最小化之前先看终态与非终态分组做完这五步得到的 DFA 就能直接用于识别a开头、后面任意多个b或c的串。这里有个笔试高频坑a(b|c)*与ab*c*并不等价前者接受ac后者不接受。复习文档里如果只列正规式不列等价关系建议你自己补上一组反例这是选择题和判断题的常见素材也是实验里词法分析器状态表设计错了才会暴露出来的问题。2.2 语法分析上LL(1) 的 First/Follow 集计算与预测分析表LL(1) 是自顶向下分析的代表考点集中在 First 集、Follow 集和预测分析表的构造。很多同学背了定义就上考场结果连 Follow 集里要不要加结束符都拿不准。我一般建议按固定顺序算先算每个产生式右部的 First 集再算非终结符的 First 集最后从开始符号出发算 Follow 集。计算 Follow 集有一个容易被忽略的点产生式A → αBβ中如果 β 可以推出空串那么 Follow(B) 要并入 Follow(A)。这个规则在多个产生式右部都出现同一非终结符时最容易漏。可以用下面这张表的顺序自查。序号计算对象动作常见错误1终结符与非终结符的 First终结符的 First 是自身非终结符看产生式右部开头忘了处理右部为空的产生式2Follow(开始符号)初始化加入结束符忘加结束符3A→αBβ 形式Follow(B) 加入 First(β) 去掉空串把 First(β) 原样加入4β 可推空或 A→αBFollow(B) 加入 Follow(A)不检查 β 是否可推空算完 First 和 Follow预测分析表就是逐格填动作对产生式A → α把α的 First 集中每个终结符填入表项对应位置如果α可推空再把 Follow(A) 中每个终结符填入。表里一格出现两个不同产生式就是存在冲突意味着该文法不是 LL(1)。2.3 语法分析下LR 项目集规范族、SLR 与 LR(1) 的冲突消解LR 分析是自底向上的代表期末题里常见的是给你一个文法要求构造 LR(0) 项目集规范族判断是 SLR(1) 还是 LR(1)并解释冲突来源。这部分在《哈工大编译原理期末复习完整版》里给了不少例题但很多人只看了结果没看“为什么这个状态有两个规约项”。构造项目集规范族时闭包函数是核心如果项目集中有一个形如A → α·Bβ的项目就把所有B → ·γ的项目加入。移进-规约冲突的消解要分层次判断LR(0) 遇到冲突就失败SLR(1) 用 Follow 集做规约判定LR(1) 则要看向前看符号。三者的差异考试几乎年年出用一张对比表可以快速记住。类型判定符号冲突处理能力分析表规模LR(0)不看遇到移进/规约冲突即失败最小SLR(1)Follow 集能解决部分移进/规约冲突较小LR(1)向前看符号几乎所有上下文无关文法最大LALR(1)向前看符号合并接近 LR(1)状态少很多中等这里要注意SLR(1) 能处理的文法换成 LR(1) 一定能处理但 LALR(1) 在某些文法上反而会产生新的规约-规约冲突。复习时如果不理解这一点实验里用工具生成分析器时碰到 shift/reduce 冲突警告就会无从下手。文档里那些带星号的例题建议逐个手推一遍项目集再对照结果这比反复读概念有效得多。2.4 复习文档怎么对着看把例题映射到实验题很多拿到这份文档的同学问该从哪一页开始。我的习惯是倒着用先翻到实验相关的题目看学校实验平台要求了什么然后从文档里找对应的理论例题。比如实验要求手写递归下降分析器就重点复习 First/Follow 和 LL(1)实验要求生成 LALR 分析器就把重心放到 LR 项目集和冲突消解上。这不是哈工大特有的问题像广州大学这些同样开设编译原理实验的学校学生拿到文档后也是这么倒着用的。文档里的例题和许多教材的课后习题是能对上的比如王生原《编译原理第3版》第三章的习题做答案对照时正好互补。但注意一点文档例题都是纸面推演和实际跑通一个分析器之间有至少半天的动手差距。这一步别跳过。3. 语义分析与符号表语法制导翻译的挂接方式和实验写法语法分析器在产出分析树之后下一步就是把语义规则挂上去。笔试里“语义分析”通常考语法制导定义、翻译模式、符号表三项。实验里则是你真正要把属性存进结构体、在分析方法中传参的部分。热搜词里的“编译原理符号表”占了很大比例说明这是期末高频痛点。3.1 语法制导定义综合属性与继承属性的求值顺序语法制导定义是给每个产生式配上语义规则。综合属性由子节点推导出来自底向上求值继承属性从父节点或兄弟节点传下来按依赖图求值。期末考试最常见的形式是给你一个产生式和属性规则叫你判断哪些是综合属性、哪些是继承属性或者叫你画依赖图。先看判定方式如果一个属性在产生式左部非终结符上且由右部符号的属性算出来它就是综合属性如果一个属性在右部符号上且依赖左部或右部更靠左的符号它就是继承属性。S 属性的语法制导定义只需综合属性可以在自底向上分析时顺便完成L 属性的定义则要求继承属性只继承左兄弟。实验里设计表达式求值时用的基本都是综合属性——每个节点的值由子节点计算后上传逻辑最直白。关于求值顺序我一般用“依赖图排序”的思路把每个属性画成节点一条边从被依赖的属性指向依赖它的属性然后做拓扑排序。如果图中出现环说明文法或规则设计有问题。这条规则在文档里是“判定合法性”的标准动作做题时请先画图再回答一步不能省。3.2 符号表作用域、类型与重载的组织方式符号表的考点集中在组织结构和作用域处理。常见实现是哈希表加链地址法——键是名字值是类型、作用域、偏移地址等信息的集合。作用域嵌套时一般用多层符号表或一张带作用域链的表。多层符号表的进出时机很关键进入一个块时压入新表退出时弹出。查找名字从当前表往上层逐层找保证内层变量可以遮蔽外层变量。笔试里常考“某个名字在第几层被绑定”这种题只要画好作用域栈就不会错。还有一种变体是重载——同名函数按参数个数和类型区分。此时符号表里同一个名字会对应多条记录查找时要把参数列表一并匹配。文档在这块如果有数据结构定义建议自己照着敲一遍并在调试器里观察插入过程。我带的实验里很多同学栽在重载上只按名字查表不比较参数列表结果两个同名函数永远命中第一个。3.3 实验视角语义动作加在哪个产生式上属性栈怎么同步写实验时最常见的问题是“语义动作不知道往哪放”。以表达式E → E T为例正确做法是把这个产生式的语义动作放在右部末尾先把E和T的值取出来做加法存回E的综合属性。如果你把动作放在后面此时右部的T还没被分析属性值拿不到程序一跑就崩。这种问题不会在笔试里出现但实验调试时会让你怀疑人生。另一个实验高频点是属性栈。自底向上分析器里有一个与分析栈并行的属性栈移进一个终结符时压入它的属性归约时用属性栈顶的几个值做计算然后弹出并压入新值。这个机制如果没理解用 Java 写翻译器时很容易出现“属性栈不同步”——归约完属性没更新。这种问题调试起来很像是玄学其实只需同时打印分析栈和属性栈逐条看哪一步错位比单步跟踪快得多。4. 中间代码与运行时环境从三地址码到目标代码生成的一条链中间代码生成和代码生成这两章在期末考卷里所占比例不低但记忆难度很高。原因在于三地址码、回填、基本块优化、活动记录这些概念彼此纠缠。用一条主线能串起来词法语法分析出结构语义动作生成中间代码优化对中间代码做变换最终代码生成把中间代码映射到寄存器与指令。4.1 三地址码与回填控制流转移的地址拼接三地址码是期末笔试的必考项。考法通常是给一段条件分支或循环语句要求写出三地址码序列。写之前先约定地址编号每个四元式占一个编号。生成跳转指令时目标地址一开始可能还不知道用到的是回填技术——先记下待回填的跳转指令位置等目标地址确定后再把地址写进去。布尔表达式的回填有一套固定流程。短路语义决定它的三地址码是一串条件跳转和无条件跳转具体写的时候注意真值出口和假值出口分别回填到哪个四元式。很多同学在这里丢分原因是把两个出口的位置弄反了。你可以用下面这张表检验。表达式结构生成的跳转回填时机与运算两个条件都满足条件不满足直接跳假出口满足则继续在后续判断完成后再回填或运算至少一个条件满足条件满足直接跳真出口不满足继续在后续判断完成后再回填循环条件条件满足进入循环体不满足跳出循环体结束后回填循环入口注意回填表里存的是“待回填的四元式编号和要填的出口类型”不是直接存地址。实验里如果用 Java 实现这个表通常是一个存整数编号的栈。4.2 基本块划分与优化哪些优化笔试必考、哪些实验不用做把三地址码划分成基本块规则很简单遇到入口语句就开启新基本块比如转移的目标语句、转移语句的下一条语句。然后对每个基本块做流图。优化的考点固定在常量传播、公共子表达式删除、死代码删除和 DAG 重写这几类。公共子表达式删除在纸面推演时最容易漏的是“中间有赋值语句打断”。比如a x y之后如果x被重新赋值后面再出现x y就不是公共子表达式了。DAG 优化的做法是为每个基本块建图节点代表运算发现重复运算时直接复用已有节点。笔试里叫你“用 DAG 优化以下三地址码”的题按“先建图再导出新语句”的顺序做结果能保持稳定不至于漏优化项。与实验的关联是大多数学校的课程实验不要求做优化但要求能输出合理的三地址码和基本块划分。所以复习时把文中的优化例题手推一遍足够不用为了实验去背优化算法代码。4.3 运行时存储静态链、动态链与活动记录运行时环境考察的是过程调用的存储布局。活动记录里保存返回地址、局部变量、临时变量、调用者的活动记录指针等。笔试容易出“画出某次递归调用后的活动记录链”这类题。先想清楚静态链和动态链的区别——动态链是调用链指向调用者的活动记录静态链指向定义该过程的词法外层的过程活动记录作用是访问外层局部变量。嵌套过程语言的变量访问规则是先沿静态链找到对应层的过程活动记录再按变量在该层活动记录里的偏移地址取值。考试题目里经常给出嵌套层次和偏移量问你某个变量最终落在哪个位置。只要按“层次差等于沿静态链次数”这个公式算就不会错。显示表是静态链的优化形态用一张表直接跳转到指定层理解原理即可笔试很少深入。4.4 简单代码生成寄存器描述和地址描述怎么用代码生成算法考的是寄存器分配常用方法是“寄存器描述加地址描述”。寄存器描述记录每个寄存器当前保存了哪个变量的值地址描述记录每个变量的值现在存放在哪些寄存器或内存单元中。生成赋值语句时先从寄存器里找两个操作数的现存位置选一个寄存器存放结果再更新两个描述表。这里有个考点什么时候需要把寄存器里的值写回内存。当寄存器被分配用于新用途、或过程调用前必须保护寄存器中的变量时就要生成存数指令。笔试中要求“给出代码生成序列并说明每一步的寄存器状态”你可以用两列表格记录每一步前后的状态这种题按格式写完整就能拿全分。5. 期末复习避坑指南五类高频翻车点与排查顺序这一章写的是我拆这份文档和带实验时反复遇到的翻车场景。如果你时间有限直接从这一章的排查顺序开始看再回头补前面的理论。5.1 First/Follow 集算错LL(1) 判定全盘崩现象预测分析表填到一半发现表格里同一个位置出现两条产生式你以为是文法不是 LL(1)但对照答案却发现自己是 Follow 集算错才导致的假冲突。原因计算 Follow 集时漏了“产生式右部末尾的非终结符要继承左部的 Follow 集”这条传递规则。具体来说A → αB或A → αBβ且 β 能推出空串时Follow(B) 必须并入 Follow(A)这一步常常被漏。解决把每个非终结符的 Follow 集源头都标出来分两轮计算。第一轮只处理直接规则第二轮处理所有传递。这样能保证每个 Follow 元素都有迹可循。从那以后我每次做题都会把 Follow 集的推导路径写在旁边不写不往下走。5.2 LR 项目集规范族状态合并错分析表推不下去现象状态 5 和状态 6 看起来项目完全相同你直接合并成一个状态结果后面的转移函数全部错位分析表怎么填都填不满。原因合并状态时忽略了对向前看符号的差异。LALR(1) 可以合并同心项目集但 LR(1) 不可以而 LR(0) 根本没有向前看符号的概念。不同分析表构造法的合并规则完全不同。解决动手构造前先写明用的是 LR(0)、SLR(1) 还是 LR(1)。LR(1) 的状态必须包含完整向前看符号不能只比较产生式部分。如果你用的是文档中的例题建议把所有状态写完后统一检查一遍每个项目对的一致性再做任何合并。5.3 属性求值顺序写反中间代码动作对不上现象在实验里给E → E1 E2加语义动作动作写在刚读入后就执行结果E2的值还不在属性栈上算出来的结果永远少一个操作数。原因自底向上分析中一个产生式右部全部符号归约完成后整个右部的属性才会齐。动作放在右部中间就会访问到尚未压栈的属性。解决把语义动作放在产生式末尾。如果实验允许也可以使用产生式中间插入动作的扩展写法但必须明确此时右部已分析的符号数量和属性栈深度。调试时打印属性栈深度一眼就能看出动作位置是否合理。5.4 符号表作用域混乱同名变量遮蔽识别不出来现象代码块里声明了int x外层也有int x实验输出里内层赋值总是写到外层的地址上。原因符号表插入时没有按作用域分层。常见做法是只用一张哈希表插入时直接覆盖同名字段导致内层声明把外层记录顶掉。解决改用分层符号表结构。每进入一个作用域就压入一个新层查找从当前层向父层遍历。做实验时我一般在进入块和退出块处打印当前符号表快照对照快照很容易看出哪个变量被错误覆盖。5.5 只背概念不做题实验和考试题脱节现象文档从头到尾读了一遍理论题都会一到综合题或实验课就不知道从哪下手。原因编译原理的知识是链路式的单独记忆每个概念无法形成解题路径。综合题通常需要你一次性完成“文法到分析表再到中间代码”这条流水线只看不做根本建立不起串联能力。解决给自己限时 60 分钟从文档里挑一道综合题从产生式推导到三地址码输出全程手写一遍。写不出来就回查对应章节然后换一道题再来。这一招在期末前两天比什么都管用因为复习到这时候已经没有后悔药了。6. 把知识收口成答题套路用一套四步走做完一道综合大题期末卷子的压轴题基本是综合题形态给定一个小型文法要求完成语法分析、语义分析和中间代码生成。这类题的分值通常在 15 到 20 分之间也是拉开差距的地方。如果你能把下面这套四步走练成固定习惯考场上几乎不用思考就能按顺序往下写。第一步标出文法中的终结符、非终结符与开始符号画出产生式编号。这一步的作用是防止后面引用产生式时写错编号尤其是在 LR 分析表里每个规约动作都对应一个产生式编号编号错一整道题就废了。第二步判断分析方式。题目如果不限定单看文法结构如果每一个非终结符的候选首符集两两不相交优先用 LL(1) 路线先算 First/Follow 再构造预测分析表如果文法有明显左递归或需要处理优先级直接走 LR 路线构造项目集规范族。这一步是全局路径选择比埋头计算更重要。第三步按所选路线完成分析表构造并在同一张表上用箭头标出每个入口的语义动作。比如归约E → E T时属性栈弹出两个操作数计算相加后压回。这一步要求把语法制导定义和分析表同步推演不能分开做。第四步用一个小输入串完整走一遍带语义动作的分析过程。例如输入35*2从初始状态开始逐步写上当前状态栈、符号栈、属性栈和已生成的三地址码。这四列对应写全整个过程是否一致一目了然。提示考场上如果时间快到了优先保证 First/Follow 集和分析表的正确性中间代码部分写到可读即可。属性栈不同步这种问题在纸面上看不出来但分析表错了就是硬扣分。这套四步走的思路来自我经历过的一次教训有一年期末我跳过综合题直接刷选择填空结果压轴题让我从文法开始重新推演当场乱了阵脚。从那以后我每次复习编译原理都会强制先完整走一遍综合大题再回头补细节。这次拆《哈工大编译原理期末复习完整版涵盖编译原理所有内容》这份文档我也按这个顺序用了一遍发现最值钱的不是那些结论而是结论背后的推导过程。如果你手头还没有这份完整版建议拿到后从第 5 章和第 6 章倒着用起先把综合题打通再回头补推导细节希望这份拆解能帮你在复习时少走一点弯路。本文还有配套的精品资源点击获取
简介面向哈工大编译原理期末复习的完整版资料覆盖编译系统结构、语言及其文法、词法分析、语法分析、语义分析、中间代码生成、目标代码生成与代码优化等全部核心模块适合期末系统梳理与查漏补缺。内容按课堂知识体系展开从串、字母表、文法定义与分类到正则表达式、有穷自动机DFA/NFA、分析树、三地址码与四元式、寄存器分配等关键难点均有清晰归纳同时结合典型编译流程串讲各个阶段便于快速对照教材巩固理解。对DFA与NFA的关系、子集构造法、中间表示转换等易混淆点也做了对比整理帮助加深记忆。包体为一份PDF文档大小31.14MB完整度高、层次分明可打印或电子阅读。目前已有2311人学习下载是准备期末考试的实用参考资料。1. 为什么哈工大编译原理期末复习要抓全局一份完整版复习笔记的用法期末周拿到这份《哈工大编译原理期末复习完整版涵盖编译原理所有内容》时多数人的第一反应是“先背概念再刷题”。实际上编译原理这门课的知识结构是链式的词法产出的记号送给语法语法产出的分析树送给语义语义动作驱动中间代码生成最后才是目标代码。哪个环节断了后面的题都做不动。这份复习文档的价值在于把整条链按章节收拢适合两类人一类是临近考试需要快速建立知识框架的另一类是实验做到一半、理论课没跟上回头补洞的。需要先说明一点文档资料不带可执行代码但它能把实验题和定理对应上这是拆这份资源时最值得留意的部分。2. 词法与语法分析从正规式到 DFA、LL(1) 与 LR 的判定闭环对绝大多数期末卷来说词法分析和语法分析加起来能占四成以上的分值。复习这一章的重心不是记住“什么是正则表达式”而是能把一条正规式手工转成最小化 DFA并能在 LL(1) 和 LR 两个方向上都做出正确的判断。这一部分主要有三个落点。2.1 词法分析正规式转 DFA 的五步操作实验第一关词法分析在实验里通常对应一个用 Java 写的词法分析器。你输入一段源码文本它输出一串 token。期末笔试不会让你写完整代码但一定考正规式到 DFA 的构造。常见做法是三步走先用 Thompson 构造法把正规式转成 NFA再用子集构造法把 NFA 确定化为 DFA最后对 DFA 做最小化。三步缺一分值就丢。以正规式a(b|c)*为例转化过程的核心动作可以列成一张表。步骤动作要检查的点1拆成基本子表达式画出 a 与 (bc)* 的拼接2为每个子表达式引入新的开始和接受状态状态编号别跳后面子集构造要引用3用子集构造法从 NFA 的开始状态做 ε-闭包任何一个 NFA 状态都不能漏4对每个输入符号计算转移并得到新子集DFA 状态数量可能膨胀属正常现象5删除不可达状态并合并等价状态最小化之前先看终态与非终态分组做完这五步得到的 DFA 就能直接用于识别a开头、后面任意多个b或c的串。这里有个笔试高频坑a(b|c)*与ab*c*并不等价前者接受ac后者不接受。复习文档里如果只列正规式不列等价关系建议你自己补上一组反例这是选择题和判断题的常见素材也是实验里词法分析器状态表设计错了才会暴露出来的问题。2.2 语法分析上LL(1) 的 First/Follow 集计算与预测分析表LL(1) 是自顶向下分析的代表考点集中在 First 集、Follow 集和预测分析表的构造。很多同学背了定义就上考场结果连 Follow 集里要不要加结束符都拿不准。我一般建议按固定顺序算先算每个产生式右部的 First 集再算非终结符的 First 集最后从开始符号出发算 Follow 集。计算 Follow 集有一个容易被忽略的点产生式A → αBβ中如果 β 可以推出空串那么 Follow(B) 要并入 Follow(A)。这个规则在多个产生式右部都出现同一非终结符时最容易漏。可以用下面这张表的顺序自查。序号计算对象动作常见错误1终结符与非终结符的 First终结符的 First 是自身非终结符看产生式右部开头忘了处理右部为空的产生式2Follow(开始符号)初始化加入结束符忘加结束符3A→αBβ 形式Follow(B) 加入 First(β) 去掉空串把 First(β) 原样加入4β 可推空或 A→αBFollow(B) 加入 Follow(A)不检查 β 是否可推空算完 First 和 Follow预测分析表就是逐格填动作对产生式A → α把α的 First 集中每个终结符填入表项对应位置如果α可推空再把 Follow(A) 中每个终结符填入。表里一格出现两个不同产生式就是存在冲突意味着该文法不是 LL(1)。2.3 语法分析下LR 项目集规范族、SLR 与 LR(1) 的冲突消解LR 分析是自底向上的代表期末题里常见的是给你一个文法要求构造 LR(0) 项目集规范族判断是 SLR(1) 还是 LR(1)并解释冲突来源。这部分在《哈工大编译原理期末复习完整版》里给了不少例题但很多人只看了结果没看“为什么这个状态有两个规约项”。构造项目集规范族时闭包函数是核心如果项目集中有一个形如A → α·Bβ的项目就把所有B → ·γ的项目加入。移进-规约冲突的消解要分层次判断LR(0) 遇到冲突就失败SLR(1) 用 Follow 集做规约判定LR(1) 则要看向前看符号。三者的差异考试几乎年年出用一张对比表可以快速记住。类型判定符号冲突处理能力分析表规模LR(0)不看遇到移进/规约冲突即失败最小SLR(1)Follow 集能解决部分移进/规约冲突较小LR(1)向前看符号几乎所有上下文无关文法最大LALR(1)向前看符号合并接近 LR(1)状态少很多中等这里要注意SLR(1) 能处理的文法换成 LR(1) 一定能处理但 LALR(1) 在某些文法上反而会产生新的规约-规约冲突。复习时如果不理解这一点实验里用工具生成分析器时碰到 shift/reduce 冲突警告就会无从下手。文档里那些带星号的例题建议逐个手推一遍项目集再对照结果这比反复读概念有效得多。2.4 复习文档怎么对着看把例题映射到实验题很多拿到这份文档的同学问该从哪一页开始。我的习惯是倒着用先翻到实验相关的题目看学校实验平台要求了什么然后从文档里找对应的理论例题。比如实验要求手写递归下降分析器就重点复习 First/Follow 和 LL(1)实验要求生成 LALR 分析器就把重心放到 LR 项目集和冲突消解上。这不是哈工大特有的问题像广州大学这些同样开设编译原理实验的学校学生拿到文档后也是这么倒着用的。文档里的例题和许多教材的课后习题是能对上的比如王生原《编译原理第3版》第三章的习题做答案对照时正好互补。但注意一点文档例题都是纸面推演和实际跑通一个分析器之间有至少半天的动手差距。这一步别跳过。3. 语义分析与符号表语法制导翻译的挂接方式和实验写法语法分析器在产出分析树之后下一步就是把语义规则挂上去。笔试里“语义分析”通常考语法制导定义、翻译模式、符号表三项。实验里则是你真正要把属性存进结构体、在分析方法中传参的部分。热搜词里的“编译原理符号表”占了很大比例说明这是期末高频痛点。3.1 语法制导定义综合属性与继承属性的求值顺序语法制导定义是给每个产生式配上语义规则。综合属性由子节点推导出来自底向上求值继承属性从父节点或兄弟节点传下来按依赖图求值。期末考试最常见的形式是给你一个产生式和属性规则叫你判断哪些是综合属性、哪些是继承属性或者叫你画依赖图。先看判定方式如果一个属性在产生式左部非终结符上且由右部符号的属性算出来它就是综合属性如果一个属性在右部符号上且依赖左部或右部更靠左的符号它就是继承属性。S 属性的语法制导定义只需综合属性可以在自底向上分析时顺便完成L 属性的定义则要求继承属性只继承左兄弟。实验里设计表达式求值时用的基本都是综合属性——每个节点的值由子节点计算后上传逻辑最直白。关于求值顺序我一般用“依赖图排序”的思路把每个属性画成节点一条边从被依赖的属性指向依赖它的属性然后做拓扑排序。如果图中出现环说明文法或规则设计有问题。这条规则在文档里是“判定合法性”的标准动作做题时请先画图再回答一步不能省。3.2 符号表作用域、类型与重载的组织方式符号表的考点集中在组织结构和作用域处理。常见实现是哈希表加链地址法——键是名字值是类型、作用域、偏移地址等信息的集合。作用域嵌套时一般用多层符号表或一张带作用域链的表。多层符号表的进出时机很关键进入一个块时压入新表退出时弹出。查找名字从当前表往上层逐层找保证内层变量可以遮蔽外层变量。笔试里常考“某个名字在第几层被绑定”这种题只要画好作用域栈就不会错。还有一种变体是重载——同名函数按参数个数和类型区分。此时符号表里同一个名字会对应多条记录查找时要把参数列表一并匹配。文档在这块如果有数据结构定义建议自己照着敲一遍并在调试器里观察插入过程。我带的实验里很多同学栽在重载上只按名字查表不比较参数列表结果两个同名函数永远命中第一个。3.3 实验视角语义动作加在哪个产生式上属性栈怎么同步写实验时最常见的问题是“语义动作不知道往哪放”。以表达式E → E T为例正确做法是把这个产生式的语义动作放在右部末尾先把E和T的值取出来做加法存回E的综合属性。如果你把动作放在后面此时右部的T还没被分析属性值拿不到程序一跑就崩。这种问题不会在笔试里出现但实验调试时会让你怀疑人生。另一个实验高频点是属性栈。自底向上分析器里有一个与分析栈并行的属性栈移进一个终结符时压入它的属性归约时用属性栈顶的几个值做计算然后弹出并压入新值。这个机制如果没理解用 Java 写翻译器时很容易出现“属性栈不同步”——归约完属性没更新。这种问题调试起来很像是玄学其实只需同时打印分析栈和属性栈逐条看哪一步错位比单步跟踪快得多。4. 中间代码与运行时环境从三地址码到目标代码生成的一条链中间代码生成和代码生成这两章在期末考卷里所占比例不低但记忆难度很高。原因在于三地址码、回填、基本块优化、活动记录这些概念彼此纠缠。用一条主线能串起来词法语法分析出结构语义动作生成中间代码优化对中间代码做变换最终代码生成把中间代码映射到寄存器与指令。4.1 三地址码与回填控制流转移的地址拼接三地址码是期末笔试的必考项。考法通常是给一段条件分支或循环语句要求写出三地址码序列。写之前先约定地址编号每个四元式占一个编号。生成跳转指令时目标地址一开始可能还不知道用到的是回填技术——先记下待回填的跳转指令位置等目标地址确定后再把地址写进去。布尔表达式的回填有一套固定流程。短路语义决定它的三地址码是一串条件跳转和无条件跳转具体写的时候注意真值出口和假值出口分别回填到哪个四元式。很多同学在这里丢分原因是把两个出口的位置弄反了。你可以用下面这张表检验。表达式结构生成的跳转回填时机与运算两个条件都满足条件不满足直接跳假出口满足则继续在后续判断完成后再回填或运算至少一个条件满足条件满足直接跳真出口不满足继续在后续判断完成后再回填循环条件条件满足进入循环体不满足跳出循环体结束后回填循环入口注意回填表里存的是“待回填的四元式编号和要填的出口类型”不是直接存地址。实验里如果用 Java 实现这个表通常是一个存整数编号的栈。4.2 基本块划分与优化哪些优化笔试必考、哪些实验不用做把三地址码划分成基本块规则很简单遇到入口语句就开启新基本块比如转移的目标语句、转移语句的下一条语句。然后对每个基本块做流图。优化的考点固定在常量传播、公共子表达式删除、死代码删除和 DAG 重写这几类。公共子表达式删除在纸面推演时最容易漏的是“中间有赋值语句打断”。比如a x y之后如果x被重新赋值后面再出现x y就不是公共子表达式了。DAG 优化的做法是为每个基本块建图节点代表运算发现重复运算时直接复用已有节点。笔试里叫你“用 DAG 优化以下三地址码”的题按“先建图再导出新语句”的顺序做结果能保持稳定不至于漏优化项。与实验的关联是大多数学校的课程实验不要求做优化但要求能输出合理的三地址码和基本块划分。所以复习时把文中的优化例题手推一遍足够不用为了实验去背优化算法代码。4.3 运行时存储静态链、动态链与活动记录运行时环境考察的是过程调用的存储布局。活动记录里保存返回地址、局部变量、临时变量、调用者的活动记录指针等。笔试容易出“画出某次递归调用后的活动记录链”这类题。先想清楚静态链和动态链的区别——动态链是调用链指向调用者的活动记录静态链指向定义该过程的词法外层的过程活动记录作用是访问外层局部变量。嵌套过程语言的变量访问规则是先沿静态链找到对应层的过程活动记录再按变量在该层活动记录里的偏移地址取值。考试题目里经常给出嵌套层次和偏移量问你某个变量最终落在哪个位置。只要按“层次差等于沿静态链次数”这个公式算就不会错。显示表是静态链的优化形态用一张表直接跳转到指定层理解原理即可笔试很少深入。4.4 简单代码生成寄存器描述和地址描述怎么用代码生成算法考的是寄存器分配常用方法是“寄存器描述加地址描述”。寄存器描述记录每个寄存器当前保存了哪个变量的值地址描述记录每个变量的值现在存放在哪些寄存器或内存单元中。生成赋值语句时先从寄存器里找两个操作数的现存位置选一个寄存器存放结果再更新两个描述表。这里有个考点什么时候需要把寄存器里的值写回内存。当寄存器被分配用于新用途、或过程调用前必须保护寄存器中的变量时就要生成存数指令。笔试中要求“给出代码生成序列并说明每一步的寄存器状态”你可以用两列表格记录每一步前后的状态这种题按格式写完整就能拿全分。5. 期末复习避坑指南五类高频翻车点与排查顺序这一章写的是我拆这份文档和带实验时反复遇到的翻车场景。如果你时间有限直接从这一章的排查顺序开始看再回头补前面的理论。5.1 First/Follow 集算错LL(1) 判定全盘崩现象预测分析表填到一半发现表格里同一个位置出现两条产生式你以为是文法不是 LL(1)但对照答案却发现自己是 Follow 集算错才导致的假冲突。原因计算 Follow 集时漏了“产生式右部末尾的非终结符要继承左部的 Follow 集”这条传递规则。具体来说A → αB或A → αBβ且 β 能推出空串时Follow(B) 必须并入 Follow(A)这一步常常被漏。解决把每个非终结符的 Follow 集源头都标出来分两轮计算。第一轮只处理直接规则第二轮处理所有传递。这样能保证每个 Follow 元素都有迹可循。从那以后我每次做题都会把 Follow 集的推导路径写在旁边不写不往下走。5.2 LR 项目集规范族状态合并错分析表推不下去现象状态 5 和状态 6 看起来项目完全相同你直接合并成一个状态结果后面的转移函数全部错位分析表怎么填都填不满。原因合并状态时忽略了对向前看符号的差异。LALR(1) 可以合并同心项目集但 LR(1) 不可以而 LR(0) 根本没有向前看符号的概念。不同分析表构造法的合并规则完全不同。解决动手构造前先写明用的是 LR(0)、SLR(1) 还是 LR(1)。LR(1) 的状态必须包含完整向前看符号不能只比较产生式部分。如果你用的是文档中的例题建议把所有状态写完后统一检查一遍每个项目对的一致性再做任何合并。5.3 属性求值顺序写反中间代码动作对不上现象在实验里给E → E1 E2加语义动作动作写在刚读入后就执行结果E2的值还不在属性栈上算出来的结果永远少一个操作数。原因自底向上分析中一个产生式右部全部符号归约完成后整个右部的属性才会齐。动作放在右部中间就会访问到尚未压栈的属性。解决把语义动作放在产生式末尾。如果实验允许也可以使用产生式中间插入动作的扩展写法但必须明确此时右部已分析的符号数量和属性栈深度。调试时打印属性栈深度一眼就能看出动作位置是否合理。5.4 符号表作用域混乱同名变量遮蔽识别不出来现象代码块里声明了int x外层也有int x实验输出里内层赋值总是写到外层的地址上。原因符号表插入时没有按作用域分层。常见做法是只用一张哈希表插入时直接覆盖同名字段导致内层声明把外层记录顶掉。解决改用分层符号表结构。每进入一个作用域就压入一个新层查找从当前层向父层遍历。做实验时我一般在进入块和退出块处打印当前符号表快照对照快照很容易看出哪个变量被错误覆盖。5.5 只背概念不做题实验和考试题脱节现象文档从头到尾读了一遍理论题都会一到综合题或实验课就不知道从哪下手。原因编译原理的知识是链路式的单独记忆每个概念无法形成解题路径。综合题通常需要你一次性完成“文法到分析表再到中间代码”这条流水线只看不做根本建立不起串联能力。解决给自己限时 60 分钟从文档里挑一道综合题从产生式推导到三地址码输出全程手写一遍。写不出来就回查对应章节然后换一道题再来。这一招在期末前两天比什么都管用因为复习到这时候已经没有后悔药了。6. 把知识收口成答题套路用一套四步走做完一道综合大题期末卷子的压轴题基本是综合题形态给定一个小型文法要求完成语法分析、语义分析和中间代码生成。这类题的分值通常在 15 到 20 分之间也是拉开差距的地方。如果你能把下面这套四步走练成固定习惯考场上几乎不用思考就能按顺序往下写。第一步标出文法中的终结符、非终结符与开始符号画出产生式编号。这一步的作用是防止后面引用产生式时写错编号尤其是在 LR 分析表里每个规约动作都对应一个产生式编号编号错一整道题就废了。第二步判断分析方式。题目如果不限定单看文法结构如果每一个非终结符的候选首符集两两不相交优先用 LL(1) 路线先算 First/Follow 再构造预测分析表如果文法有明显左递归或需要处理优先级直接走 LR 路线构造项目集规范族。这一步是全局路径选择比埋头计算更重要。第三步按所选路线完成分析表构造并在同一张表上用箭头标出每个入口的语义动作。比如归约E → E T时属性栈弹出两个操作数计算相加后压回。这一步要求把语法制导定义和分析表同步推演不能分开做。第四步用一个小输入串完整走一遍带语义动作的分析过程。例如输入35*2从初始状态开始逐步写上当前状态栈、符号栈、属性栈和已生成的三地址码。这四列对应写全整个过程是否一致一目了然。提示考场上如果时间快到了优先保证 First/Follow 集和分析表的正确性中间代码部分写到可读即可。属性栈不同步这种问题在纸面上看不出来但分析表错了就是硬扣分。这套四步走的思路来自我经历过的一次教训有一年期末我跳过综合题直接刷选择填空结果压轴题让我从文法开始重新推演当场乱了阵脚。从那以后我每次复习编译原理都会强制先完整走一遍综合大题再回头补细节。这次拆《哈工大编译原理期末复习完整版涵盖编译原理所有内容》这份文档我也按这个顺序用了一遍发现最值钱的不是那些结论而是结论背后的推导过程。如果你手头还没有这份完整版建议拿到后从第 5 章和第 6 章倒着用起先把综合题打通再回头补推导细节希望这份拆解能帮你在复习时少走一点弯路。本文还有配套的精品资源点击获取
