简介面向哈工大编译原理课程期末备考这份完整版复习资料系统覆盖编译系统结构、语言及其文法、词法分析、语法分析、语义分析、中间代码生成、目标代码生成与代码优化等全部模块适合需要系统梳理考点、快速建立知识框架的本科生及自学者。内容以课件式笔记呈现既包含串与字母表、文法定义G(VT,VN,P,S)、CFG分析树等基础概念也详解DFA与NFA的识别原理、四元式/三元式/间接三元式等中间代码表示并针对目标代码生成中的寄存器分配和代码优化方法做了归纳总结。文件类型为PDF文档全包共1个文件大小31.14MB便于在手机、平板等多端离线研读。已有2311人学习下载资料按编译流程顺序组织从绪论到优化环环相扣可直接用于期末冲刺、复习提纲对照及查漏补缺。1. 编译原理期末复习为什么越翻书越慌以及这篇笔记的用法编译原理这门课期末翻车率常年稳居计算机专业课前列。平时代码能写、算法能背一到考试就被 FIRST、FOLLOW、LR(1) 项目集规范族这些名字搞得怀疑人生。原因很简单这门课的知识点不是线性排列的词法、语法、语义、中间代码、优化五块内容各自成体系又互相依赖按目录一章章看看到后面早就忘了前面。这篇笔记就是给期末复习用的完整版梳理把编译原理的所有核心内容压缩成一条可执行的复习主线——先通读建立骨架再分模块手算验证最后用自检清单查漏。适合正在备考、想要快速找回手感的人也适合想系统过一遍重点的读者按章节顺序看即可。2. 先搭知识骨架从词法到目标代码的全流程考点地图2.1 编译过程的六个阶段考试对应什么题型编译过程可以拆成词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成六个阶段外加贯穿始终的符号表管理和错误处理。期末题面上选择题和填空题最爱考“某个功能属于哪一阶段”“符号表在何时被写入和查询”大题则集中在词法分析、语法分析和中间代码生成上。要建立的第一条主线是把六个阶段串成一个管道源程序先进词法分析被切成一个个 tokentoken 流交给语法分析按文法规则生成语法树或推导序列。语法树接着进语义分析做类型检查和作用域绑定然后翻译成中间代码。中间代码做优化最后映射到目标机器的指令。复习时不要把六个阶段当独立章节背而是按数据流的顺序过每个阶段输入什么、输出什么、用什么数据结构、可能报什么错。比如词法分析的错误是“非法字符”语法分析报“语法错误”语义分析报“类型不匹配”错误出现的阶段也是常考选择题。2.2 语义分析与中间代码生成考点其实很有规律语义分析的核心是属性文法和语法制导翻译。考试里常见的题型有两种一种给一个文法要求你写出每个产生式对应的语义动作另一种是给定一个表达式转换成三地址码或四元式。这部分拿分的关键是区分两类属性综合属性自底向上传递继承属性自顶向下传递二者决定语义动作写在产生式的什么位置。中间代码的常见形式有三地址码、四元式、三元式、间接三元式其中四元式是期末最爱考的格式结构是 (op, arg1, arg2, result)。赋值语句、算术表达式、布尔表达式、数组引用和控制流语句都有各自的翻译模板复习时最好把常见语句的翻译模板列成一张速查表赋值语句如何处理数组下标的偏移布尔表达式如何用回填技术处理跳转地址。符号表在这一阶段的作用要重点理解编译器的各阶段都在查表和填表。符号表常见的组织方式是分层的散列表每个作用域一层进入作用域时压栈退出时弹出。期末考题常给一段 C 语言风格的代码问你某个变量在某个位置查到的类型是多少这种题考的就是作用域遮蔽规则。2.3 代码优化与目标代码生成期末常考的三个方向代码优化分局部优化和全局优化。局部优化在基本块内进行基本块是满足“只有一个入口、一个出口中间不含跳转”的连续语句序列常用 DAG有向无环图来消除公共子表达式和死代码。全局优化以循环优化为主包括代码外提、强度削减、删除归纳变量期末考题里给一段中间代码让你指出哪些可以外提、哪些可以削减。目标代码生成涉及指令选择、寄存器分配和指令调度。寄存器分配有寄存器分配图和图着色算法但期末考试通常不会要求完整实现更多是让你理解分配冲突的基本思路。这部分复习到位即可不用深挖除非你们老师明确画了大题范围。2.4 按分值排复习优先级哪些必须手算哪些理解为主把六阶段按“期末投资回报率”排序我的建议是语法分析优先词法分析次之语义分析和中间代码并列第三优化和目标代码最后。语法分析分值最重大题几乎必考而且需要大量手算练习词法分析分值中等但套路最固定练熟 Thompson 构造法、子集构造法、DFA 最小化三步就能覆盖大部分考点语义分析与中间代码适合用模板记忆优化只在选择题和简答题中出现。优先级安排好后再做一轮“输入条件”排查先确认课堂笔记和 PPT 覆盖了哪些深度期末是开卷还是闭卷有没有往届题可以参考。闭卷考试的话FIRST、FOLLOW 集的计算步骤、LR 分析表的构造流程这类硬功夫必须闭着眼能写出来。3. 词法分析正则、NFA/DFA 与最小化的手算套路3.1 从正则到 NFAThompson 构造法的完整示例词法分析的复习主线是正则表达式是单词的描述工具NFA 是识别器DFA 是效率更高的识别器最小化后的 DFA 是可以直接写进词法分析器的最终形态。考试要求你亲手完成这个转换链条的每一步。Thompson 构造法把每个正则表达式递归地拆成 NFA单个字符构造两个状态连接、选择、闭包各有固定的拼装模板。以正则表达式a(b|c)*为例手工构造时先画b|c再对它做闭包最后和a连接。每一步有个核心约定每个 NFA 片段只有一个开始状态和一个接受状态拼装时靠 ε 跳转连接。写复习笔记时我会把 NFA 画成一张状态表而非图形这样考试时不会画错。状态表里每一行是一个状态号ε、a、b、c 各占一列格子填跳转去往的状态集合。闭包状态的处理是初学者最容易丢分的地方闭包记号对应的是“从当前状态可以经 ε 多次跳转到达的所有状态”。3.2 子集构造法与 DFA 最小化闭包运算是命门子集构造法把一个 NFA 转成 DFA核心操作是两个集合运算求 ε-闭包从某状态出发经任意条 ε 边能到的所有状态和求 move读入一个字符后能到的状态集合再求闭包。手工做题时我建议用“队列表”格式来写第一列是 DFA 状态名第二列是它对应的 NFA 状态子集后几列是读入各字符后的迁移结果。以刚才的 NFA 继续初始状态的 ε-闭包是 DFA 的初态然后逐个字符求迁移发现新子集就新增 DFA 状态重复到没有新状态出现。每步都用“子集计算→闭包→去重”三件套不要跳步跳步等于给检查老师送分。DFA 最小化用的是等价类划分法。初始按接受状态和非接受状态分成两组然后反复细化若某组内两个状态读同一字符后落入不同组就把它们拆开。问自己一个问题接受状态集合里所有状态都真的等价吗如果两个状态后面跟的字符不同它们在将来能被接受的可能性就是不同的必须拆开。最小化的结果通常是一个更紧凑的状态表对应最简自动机。3.3 词法分析器的代码骨架用 DFA 驱动识别 token复习时能手写一个迷你词法分析器考场上的原理题会很有底气。核心思路用状态表驱动识别循环每读一个字符就根据当前状态和输入字符查表跳转记录最近一次处于接受状态的时机遇到死路时回退并输出 token。下面这个 Python 版骨架足够展示这个机制# DFA 驱动的词法分析器示意状态表用字典表示 # 状态表键状态名值dict字符 - 下一状态 # 接受状态集合记录哪些状态能结束一个合法 token statetable { S0: {a: S1, b: DEAD}, S1: {a: S1, b: S2}, S2: {a: ACC, b: DEAD} } accepting {S1, S2, ACC} def next_token(text, pos, start_stateS0): state start_state last_accept, last_accept_pos None, pos i pos while i len(text): ch text[i] key (state, ch) if state not in statetable or ch not in statetable[state]: break state statetable[state][ch] i 1 if state in accepting: # 记录最近一次合法终点 last_accept, last_accept_pos state, i if last_accept is None: return None, pos, 非法字符 # 回退并切出 token典型实现是返回 (词素, 终点) return text[pos:last_accept_pos], last_accept_pos, None这个骨架体现了词法分析器的两个关键约定最长匹配和回退。每次状态合法都要更新last_accept读到死路时回退到最近一个接受位置这样能保证关键字和标识符这类最长匹配场景不会切错。识别完成后可以按最终状态或关键字表区分 token 类别这也是“查表”工作的雏形。3.4 词法分析容易丢分的三个理解偏差第一个偏差把正则里的闭包和编程语言里的闭包混淆。这里的*表示零次或多次不是捕获外部变量。第二个偏差忽略最长匹配原则。if和ifx同时出现时DFA 必须多读一个字符才能决定是关键字还是标识符。第三个偏差把 NFA 的 ε 边理解成“无输入”而不是“可选的空跳转”导致闭包计算漏状态。这三个偏差每年都有人踩复习时自己用笔推一遍例子比看十遍书印象深。4. 语法分析LL(1) 与 LR 家族的构建步骤和高分要点4.1 动手前先做文法等价变换消除左递归与提取左公因子语法分析的大题第一步往往不是构建表而是把文法改写成适合分析的格式。对 LL(1) 来说文法不能有左递归不能有左公因子。消除立即左递归用的是改写公式A - Aα | β改写成A - βAA - αA | ε。提取左公因子则是把A - αβ1 | αβ2变成A - αAA - β1 | β2。改写时要特别注意 ε 串引入后的连锁影响。比如消除左递归后新增的A - ε会影响 FIRST 集和 FOLLOW 集的计算后面算 LL(1) 表时就必须考虑空串是否能够推导出来。这一步是后面所有计算的地基地基歪了整套分析表都错。很多同学做题时喜欢直接跳进 FIRST 集计算忽略文法的等价变换。我的习惯是先盯着文法看十秒钟问自己——这个文法有左递归吗有公共前缀吗如果有先改写再动手否则大概率算到一半发现表里冲突一堆回头重改更浪费时间。4.2 FIRST、FOLLOW 与预测分析表的完整计算流程LL(1) 分析表的构造公式不复杂对每个产生式A - α把FIRST(α)中每个终结符 a 都填进M[A, a]如果α能推导出 ε再把FOLLOW(A)中每个终结符 b 填进M[A, b]。难点在于 FIRST 和 FOLLOW 的迭代计算不能漏。FIRST 集按文法定义递归展开终结符的 FIRST 就是自己非终结符要看它的产生式右部首符FOLLOW 集比 FIRST 更抽象它遵循三条规则开始符号的 FOLLOW 包含结束符$产生式A - αBβ中 B 的 FOLLOW 包含FIRST(β)β 可为空产生式A - αB中 B 的 FOLLOW 包含FOLLOW(A)。举个最常考的文法E - E T | T消完左递归后变成E - T E、E - T E | ε。算 FOLLOW 时最隐蔽的点是E - ε让FOLLOW(T)从E那里继承了FOLLOW(E)。也就是说 FOLLOW 的迭代往往需要算到两轮以上第一轮和最后一轮结果不一致很正常迭代到集合不再变化为止才算完。4.3 LR 分析LR(0)、SLR(1)、LR(1) 自动机构造路线LR 分析比 LL 难在状态更多、抽象程度更高复习时把三个变体放在一起对比会清晰很多。LR(0) 只看点的位置SLR(1) 用 FOLLOW 集消除归约冲突LR(1) 带向前看符号。它们的共同基础是 LR(0) 项目集规范族每个项目是一条产生式里加点表示分析进度闭包运算要反复把点后非终结符的所有产生式加进来。做项目集规范族时我习惯用“项目集编号 转移字符 目标项目集”的表格来画自动机。遇到归约项目A - α.和移进项目B - β.aγ同时出现就是经典的移进-归约冲突。SLR(1) 的做法是用 FOLLOW(A) 和当前输入符号做区分输入符号在 FOLLOW(A) 里才归约否则移进。如果 FOLLOW(A) 里也存在那个移进符号冲突消不掉就得升级到 LR(1)用更精确的向前看符号来区分。考试中如果给了 LR(1) 自动机通常考的是向前看符号的传播规则。核心就一句归约项目的向前看符号来自产生式被调用处的 FOLLOW而不是被归约者的 FOLLOW具体计算要看同一项目集中更早项目展开时传过来的符号。做例题时把每个项目的向前看符号来源标出来比直接背规则更有效。4.4 冲突消解与判卷的评分思路LR 分析表的构造过程会暴露文法的固有局限性。遇到移进-归约冲突先看看是不是 FOLLOW 集算错了——这是最高频的错误排除后考虑用人称约定的优先级和结合性来消解。比如表达式中乘号优先级高于加号时就规定遇到冲突优先移进这样乘号会“先入栈先归约”自然形成更紧密的结合。评分上语法分析大题通常是分步骤给分文法改写正确给一部分FIRST/FOLLOW 各项对一项给一项分分析表填写按格子给分。这意味着即使最终表没画完只要中间步骤正确也能拿不少分。所以答题时不要跳步每步都写在卷面上这是最朴素的得分策略。4.5 递归下降分析适合作为代码题的拿分方案如果期末考试里有代码大题——要求手写一个小型语法分析器——递归下降分析是优先考虑的解法。它本质上就是把每个非终结符写成一个函数用函数调用栈模拟语法树的下降过程。消除左递归后的文法可以对应每个产生式写一个 if 分支遇到终结符就调匹配函数遇到非终结符就递归调用。写递归下降时注意处理回溯和错误恢复。回溯可以通过在每个分支前保存输入位置实现发现分支不匹配就恢复到保存点。错误恢复是加分项设计一个error()函数输出报错位置并同步若干 token 继续读很多考试只要求识别合法串但错误处理能力能体现对语法分析的理解深度。5. 编译原理期末复习的五个高频翻车点与排查方法5.1 FIRST 与 FOLLOW 里混进空串导致全盘算错现象算出来的 FIRST 集是“非终结符集合”里面混进了εFOLLOW 集里也出现ε后面填表时把 ε 当成了输入符号。原因对“序列的 FIRST”和“单个非终结符的 FIRST”没做区分。FIRST(αβ)只有在α可以推出空串时才会包含FIRST(β)而FOLLOW集合定义里就不可能包含 ε。解决把集合计算分三步写清楚——先算每个符号的 FIRST再根据规则迭代算 FOLLOW最后标出哪些非终结符能推出 ε。填 LL(1) 表时手工核对ε是否真的出现在“展望位置”而不是出现在“遇到输入符号”的位置。5.2 LR 项目集里漏掉闭包运算后续状态全线出错现象手画 LR(0) 自动机时某个状态只列了初始项目没有把点的后续非终结符的全部产生式加进来。结果后面所有迁移边都少分析的移进归约动作也对不上。原因每次生成一个新项目集状态时必须对点后为终结符的全部产生式做一次闭包运算而且闭包引入的新项目可能再次触发新的闭包需要循环操作。漏闭包往往是只做了一遍就停了。解决闭包运算画圈直到集合不再变化。检查作业时对每个项目集状态回看一遍点后的非终结符是否已经包含了该非终结符的全部产生式。如果某个产生式你没写说明闭包没闭到底。5.3 语法制导翻译里把综合属性和继承属性用反了现象写语义动作时在产生式右部符号的语义栈上取了一个它没有的属性或者把子表达式的类型属性放到了父节点计算顺序里导致依赖循环。原因综合属性用于自底向上传递结果如表达式类型、地址继承属性用于自顶向下传递上下文如声明部分的类型信息。两者用反会让依赖图出现环。解决做题前先画一棵带属性标注的语法树用箭头把依赖关系画出来。箭头只朝上就是纯综合属性S-属性定义有向下箭头就是继承属性。检查时看每个属性的依赖值是否在所属结点的子树范围内。5.4 符号表作用域处理只填不删查表全错现象模拟器执行一段嵌套作用域代码时外层作用域中查到了一个内层的局部变量名而且不报错。原因作用域栈的实现里内层变量插入后没有在退出作用域时删除散列表链路上留下了脏数据。许多考试题目专门考这一点因为题目所给代码的内层变量恰好与外层同名。解决处理符号表时用一个作用域栈进入块时压入新一层退出时整层弹出销毁。查表时从栈顶往下逐层搜。手工做题时给每个变量标注其所属作用域编号遇到同名变量按“最近原则”查找。5.5 局部优化与全局优化分不清论述题翻车现象简答题里让你分析某段循环代码的优化方法你写了“DAG 消除公共子表达式”并说这是全局优化实际 DAG 作用范围是基本块内属于局部优化。原因术语层级混乱。局部优化范围是基本块内部全局优化范围跨越基本块循环优化属于全局优化的一种针对结构。解决记一张对应表基本块内——DAG、删除死代码、代数恒等式循环上——代码外提、强度削减、归纳变量删除。答题时先说范围再说手段能显著减少表述歧义。平时刷题可以把每种优化方法标好作用域临考时就不会答串。6. 冲刺阶段用一张自检清单验证复习有没有漏洞考前两三天不建议再看新题我习惯用一张自检清单把所有核心能力过一遍。这张清单按“能否不翻笔记手算出来”来设计能达到哪一档心里就有底。模块自检项验证方式词法分析正则转 NFA 再转 DFA 再最小化拿三个不同正则各练一遍卡壳处标红语法分析消除左递归、算 FIRST/FOLLOW、构造 LL(1) 表给出新文法20 分钟内独立完成全流程语法分析LR(0) 项目集规范族、SLR 分析表至少独立完成一个文法的完整自动机语义分析四元式翻译、回填技术把if-else和while语句翻译成中间代码符号表作用域栈的插入删除逻辑用嵌套代码手写查表过程优化区分局部/全局/循环优化给一段中间代码标注可用优化点这张表还有一个连带作用它本身就是知识地图能告诉你哪里还没复习到位。某个项目卡住说明对应模块的大题很危险立即回到对应章节做两道题再回来。另外一个值得坚持的习惯是“限时手算”。期末考语法分析大题时时间压力会让平时没卡过壳的人也出 bug。我当年就是把近十年真题的分析表构造题全部按考试时限重算了一遍每道题都要求自己在草稿纸上写出完整状态表和查询过程。算到第三张以后闭包运算和 FOLLOW 迭代的速度明显上来了考场上那种“算到一半忘记项目集闭包”的慌乱感也消失了。等到清单全勾完再有时间就去把每章名词解释过一遍比如“语法制导翻译”“回填”“基本块”这些术语考前背熟能防简答题没话说。我的教训是考前不要沉迷刷偏题怪题把这份清单逐项过掉比再多做三套模拟题都稳。希望帮到你。本文还有配套的精品资源点击获取 编译原理期末复习：词法分析到语法分析的核心考点与手算套路
简介面向哈工大编译原理课程期末备考这份完整版复习资料系统覆盖编译系统结构、语言及其文法、词法分析、语法分析、语义分析、中间代码生成、目标代码生成与代码优化等全部模块适合需要系统梳理考点、快速建立知识框架的本科生及自学者。内容以课件式笔记呈现既包含串与字母表、文法定义G(VT,VN,P,S)、CFG分析树等基础概念也详解DFA与NFA的识别原理、四元式/三元式/间接三元式等中间代码表示并针对目标代码生成中的寄存器分配和代码优化方法做了归纳总结。文件类型为PDF文档全包共1个文件大小31.14MB便于在手机、平板等多端离线研读。已有2311人学习下载资料按编译流程顺序组织从绪论到优化环环相扣可直接用于期末冲刺、复习提纲对照及查漏补缺。1. 编译原理期末复习为什么越翻书越慌以及这篇笔记的用法编译原理这门课期末翻车率常年稳居计算机专业课前列。平时代码能写、算法能背一到考试就被 FIRST、FOLLOW、LR(1) 项目集规范族这些名字搞得怀疑人生。原因很简单这门课的知识点不是线性排列的词法、语法、语义、中间代码、优化五块内容各自成体系又互相依赖按目录一章章看看到后面早就忘了前面。这篇笔记就是给期末复习用的完整版梳理把编译原理的所有核心内容压缩成一条可执行的复习主线——先通读建立骨架再分模块手算验证最后用自检清单查漏。适合正在备考、想要快速找回手感的人也适合想系统过一遍重点的读者按章节顺序看即可。2. 先搭知识骨架从词法到目标代码的全流程考点地图2.1 编译过程的六个阶段考试对应什么题型编译过程可以拆成词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成六个阶段外加贯穿始终的符号表管理和错误处理。期末题面上选择题和填空题最爱考“某个功能属于哪一阶段”“符号表在何时被写入和查询”大题则集中在词法分析、语法分析和中间代码生成上。要建立的第一条主线是把六个阶段串成一个管道源程序先进词法分析被切成一个个 tokentoken 流交给语法分析按文法规则生成语法树或推导序列。语法树接着进语义分析做类型检查和作用域绑定然后翻译成中间代码。中间代码做优化最后映射到目标机器的指令。复习时不要把六个阶段当独立章节背而是按数据流的顺序过每个阶段输入什么、输出什么、用什么数据结构、可能报什么错。比如词法分析的错误是“非法字符”语法分析报“语法错误”语义分析报“类型不匹配”错误出现的阶段也是常考选择题。2.2 语义分析与中间代码生成考点其实很有规律语义分析的核心是属性文法和语法制导翻译。考试里常见的题型有两种一种给一个文法要求你写出每个产生式对应的语义动作另一种是给定一个表达式转换成三地址码或四元式。这部分拿分的关键是区分两类属性综合属性自底向上传递继承属性自顶向下传递二者决定语义动作写在产生式的什么位置。中间代码的常见形式有三地址码、四元式、三元式、间接三元式其中四元式是期末最爱考的格式结构是 (op, arg1, arg2, result)。赋值语句、算术表达式、布尔表达式、数组引用和控制流语句都有各自的翻译模板复习时最好把常见语句的翻译模板列成一张速查表赋值语句如何处理数组下标的偏移布尔表达式如何用回填技术处理跳转地址。符号表在这一阶段的作用要重点理解编译器的各阶段都在查表和填表。符号表常见的组织方式是分层的散列表每个作用域一层进入作用域时压栈退出时弹出。期末考题常给一段 C 语言风格的代码问你某个变量在某个位置查到的类型是多少这种题考的就是作用域遮蔽规则。2.3 代码优化与目标代码生成期末常考的三个方向代码优化分局部优化和全局优化。局部优化在基本块内进行基本块是满足“只有一个入口、一个出口中间不含跳转”的连续语句序列常用 DAG有向无环图来消除公共子表达式和死代码。全局优化以循环优化为主包括代码外提、强度削减、删除归纳变量期末考题里给一段中间代码让你指出哪些可以外提、哪些可以削减。目标代码生成涉及指令选择、寄存器分配和指令调度。寄存器分配有寄存器分配图和图着色算法但期末考试通常不会要求完整实现更多是让你理解分配冲突的基本思路。这部分复习到位即可不用深挖除非你们老师明确画了大题范围。2.4 按分值排复习优先级哪些必须手算哪些理解为主把六阶段按“期末投资回报率”排序我的建议是语法分析优先词法分析次之语义分析和中间代码并列第三优化和目标代码最后。语法分析分值最重大题几乎必考而且需要大量手算练习词法分析分值中等但套路最固定练熟 Thompson 构造法、子集构造法、DFA 最小化三步就能覆盖大部分考点语义分析与中间代码适合用模板记忆优化只在选择题和简答题中出现。优先级安排好后再做一轮“输入条件”排查先确认课堂笔记和 PPT 覆盖了哪些深度期末是开卷还是闭卷有没有往届题可以参考。闭卷考试的话FIRST、FOLLOW 集的计算步骤、LR 分析表的构造流程这类硬功夫必须闭着眼能写出来。3. 词法分析正则、NFA/DFA 与最小化的手算套路3.1 从正则到 NFAThompson 构造法的完整示例词法分析的复习主线是正则表达式是单词的描述工具NFA 是识别器DFA 是效率更高的识别器最小化后的 DFA 是可以直接写进词法分析器的最终形态。考试要求你亲手完成这个转换链条的每一步。Thompson 构造法把每个正则表达式递归地拆成 NFA单个字符构造两个状态连接、选择、闭包各有固定的拼装模板。以正则表达式a(b|c)*为例手工构造时先画b|c再对它做闭包最后和a连接。每一步有个核心约定每个 NFA 片段只有一个开始状态和一个接受状态拼装时靠 ε 跳转连接。写复习笔记时我会把 NFA 画成一张状态表而非图形这样考试时不会画错。状态表里每一行是一个状态号ε、a、b、c 各占一列格子填跳转去往的状态集合。闭包状态的处理是初学者最容易丢分的地方闭包记号对应的是“从当前状态可以经 ε 多次跳转到达的所有状态”。3.2 子集构造法与 DFA 最小化闭包运算是命门子集构造法把一个 NFA 转成 DFA核心操作是两个集合运算求 ε-闭包从某状态出发经任意条 ε 边能到的所有状态和求 move读入一个字符后能到的状态集合再求闭包。手工做题时我建议用“队列表”格式来写第一列是 DFA 状态名第二列是它对应的 NFA 状态子集后几列是读入各字符后的迁移结果。以刚才的 NFA 继续初始状态的 ε-闭包是 DFA 的初态然后逐个字符求迁移发现新子集就新增 DFA 状态重复到没有新状态出现。每步都用“子集计算→闭包→去重”三件套不要跳步跳步等于给检查老师送分。DFA 最小化用的是等价类划分法。初始按接受状态和非接受状态分成两组然后反复细化若某组内两个状态读同一字符后落入不同组就把它们拆开。问自己一个问题接受状态集合里所有状态都真的等价吗如果两个状态后面跟的字符不同它们在将来能被接受的可能性就是不同的必须拆开。最小化的结果通常是一个更紧凑的状态表对应最简自动机。3.3 词法分析器的代码骨架用 DFA 驱动识别 token复习时能手写一个迷你词法分析器考场上的原理题会很有底气。核心思路用状态表驱动识别循环每读一个字符就根据当前状态和输入字符查表跳转记录最近一次处于接受状态的时机遇到死路时回退并输出 token。下面这个 Python 版骨架足够展示这个机制# DFA 驱动的词法分析器示意状态表用字典表示 # 状态表键状态名值dict字符 - 下一状态 # 接受状态集合记录哪些状态能结束一个合法 token statetable { S0: {a: S1, b: DEAD}, S1: {a: S1, b: S2}, S2: {a: ACC, b: DEAD} } accepting {S1, S2, ACC} def next_token(text, pos, start_stateS0): state start_state last_accept, last_accept_pos None, pos i pos while i len(text): ch text[i] key (state, ch) if state not in statetable or ch not in statetable[state]: break state statetable[state][ch] i 1 if state in accepting: # 记录最近一次合法终点 last_accept, last_accept_pos state, i if last_accept is None: return None, pos, 非法字符 # 回退并切出 token典型实现是返回 (词素, 终点) return text[pos:last_accept_pos], last_accept_pos, None这个骨架体现了词法分析器的两个关键约定最长匹配和回退。每次状态合法都要更新last_accept读到死路时回退到最近一个接受位置这样能保证关键字和标识符这类最长匹配场景不会切错。识别完成后可以按最终状态或关键字表区分 token 类别这也是“查表”工作的雏形。3.4 词法分析容易丢分的三个理解偏差第一个偏差把正则里的闭包和编程语言里的闭包混淆。这里的*表示零次或多次不是捕获外部变量。第二个偏差忽略最长匹配原则。if和ifx同时出现时DFA 必须多读一个字符才能决定是关键字还是标识符。第三个偏差把 NFA 的 ε 边理解成“无输入”而不是“可选的空跳转”导致闭包计算漏状态。这三个偏差每年都有人踩复习时自己用笔推一遍例子比看十遍书印象深。4. 语法分析LL(1) 与 LR 家族的构建步骤和高分要点4.1 动手前先做文法等价变换消除左递归与提取左公因子语法分析的大题第一步往往不是构建表而是把文法改写成适合分析的格式。对 LL(1) 来说文法不能有左递归不能有左公因子。消除立即左递归用的是改写公式A - Aα | β改写成A - βAA - αA | ε。提取左公因子则是把A - αβ1 | αβ2变成A - αAA - β1 | β2。改写时要特别注意 ε 串引入后的连锁影响。比如消除左递归后新增的A - ε会影响 FIRST 集和 FOLLOW 集的计算后面算 LL(1) 表时就必须考虑空串是否能够推导出来。这一步是后面所有计算的地基地基歪了整套分析表都错。很多同学做题时喜欢直接跳进 FIRST 集计算忽略文法的等价变换。我的习惯是先盯着文法看十秒钟问自己——这个文法有左递归吗有公共前缀吗如果有先改写再动手否则大概率算到一半发现表里冲突一堆回头重改更浪费时间。4.2 FIRST、FOLLOW 与预测分析表的完整计算流程LL(1) 分析表的构造公式不复杂对每个产生式A - α把FIRST(α)中每个终结符 a 都填进M[A, a]如果α能推导出 ε再把FOLLOW(A)中每个终结符 b 填进M[A, b]。难点在于 FIRST 和 FOLLOW 的迭代计算不能漏。FIRST 集按文法定义递归展开终结符的 FIRST 就是自己非终结符要看它的产生式右部首符FOLLOW 集比 FIRST 更抽象它遵循三条规则开始符号的 FOLLOW 包含结束符$产生式A - αBβ中 B 的 FOLLOW 包含FIRST(β)β 可为空产生式A - αB中 B 的 FOLLOW 包含FOLLOW(A)。举个最常考的文法E - E T | T消完左递归后变成E - T E、E - T E | ε。算 FOLLOW 时最隐蔽的点是E - ε让FOLLOW(T)从E那里继承了FOLLOW(E)。也就是说 FOLLOW 的迭代往往需要算到两轮以上第一轮和最后一轮结果不一致很正常迭代到集合不再变化为止才算完。4.3 LR 分析LR(0)、SLR(1)、LR(1) 自动机构造路线LR 分析比 LL 难在状态更多、抽象程度更高复习时把三个变体放在一起对比会清晰很多。LR(0) 只看点的位置SLR(1) 用 FOLLOW 集消除归约冲突LR(1) 带向前看符号。它们的共同基础是 LR(0) 项目集规范族每个项目是一条产生式里加点表示分析进度闭包运算要反复把点后非终结符的所有产生式加进来。做项目集规范族时我习惯用“项目集编号 转移字符 目标项目集”的表格来画自动机。遇到归约项目A - α.和移进项目B - β.aγ同时出现就是经典的移进-归约冲突。SLR(1) 的做法是用 FOLLOW(A) 和当前输入符号做区分输入符号在 FOLLOW(A) 里才归约否则移进。如果 FOLLOW(A) 里也存在那个移进符号冲突消不掉就得升级到 LR(1)用更精确的向前看符号来区分。考试中如果给了 LR(1) 自动机通常考的是向前看符号的传播规则。核心就一句归约项目的向前看符号来自产生式被调用处的 FOLLOW而不是被归约者的 FOLLOW具体计算要看同一项目集中更早项目展开时传过来的符号。做例题时把每个项目的向前看符号来源标出来比直接背规则更有效。4.4 冲突消解与判卷的评分思路LR 分析表的构造过程会暴露文法的固有局限性。遇到移进-归约冲突先看看是不是 FOLLOW 集算错了——这是最高频的错误排除后考虑用人称约定的优先级和结合性来消解。比如表达式中乘号优先级高于加号时就规定遇到冲突优先移进这样乘号会“先入栈先归约”自然形成更紧密的结合。评分上语法分析大题通常是分步骤给分文法改写正确给一部分FIRST/FOLLOW 各项对一项给一项分分析表填写按格子给分。这意味着即使最终表没画完只要中间步骤正确也能拿不少分。所以答题时不要跳步每步都写在卷面上这是最朴素的得分策略。4.5 递归下降分析适合作为代码题的拿分方案如果期末考试里有代码大题——要求手写一个小型语法分析器——递归下降分析是优先考虑的解法。它本质上就是把每个非终结符写成一个函数用函数调用栈模拟语法树的下降过程。消除左递归后的文法可以对应每个产生式写一个 if 分支遇到终结符就调匹配函数遇到非终结符就递归调用。写递归下降时注意处理回溯和错误恢复。回溯可以通过在每个分支前保存输入位置实现发现分支不匹配就恢复到保存点。错误恢复是加分项设计一个error()函数输出报错位置并同步若干 token 继续读很多考试只要求识别合法串但错误处理能力能体现对语法分析的理解深度。5. 编译原理期末复习的五个高频翻车点与排查方法5.1 FIRST 与 FOLLOW 里混进空串导致全盘算错现象算出来的 FIRST 集是“非终结符集合”里面混进了εFOLLOW 集里也出现ε后面填表时把 ε 当成了输入符号。原因对“序列的 FIRST”和“单个非终结符的 FIRST”没做区分。FIRST(αβ)只有在α可以推出空串时才会包含FIRST(β)而FOLLOW集合定义里就不可能包含 ε。解决把集合计算分三步写清楚——先算每个符号的 FIRST再根据规则迭代算 FOLLOW最后标出哪些非终结符能推出 ε。填 LL(1) 表时手工核对ε是否真的出现在“展望位置”而不是出现在“遇到输入符号”的位置。5.2 LR 项目集里漏掉闭包运算后续状态全线出错现象手画 LR(0) 自动机时某个状态只列了初始项目没有把点的后续非终结符的全部产生式加进来。结果后面所有迁移边都少分析的移进归约动作也对不上。原因每次生成一个新项目集状态时必须对点后为终结符的全部产生式做一次闭包运算而且闭包引入的新项目可能再次触发新的闭包需要循环操作。漏闭包往往是只做了一遍就停了。解决闭包运算画圈直到集合不再变化。检查作业时对每个项目集状态回看一遍点后的非终结符是否已经包含了该非终结符的全部产生式。如果某个产生式你没写说明闭包没闭到底。5.3 语法制导翻译里把综合属性和继承属性用反了现象写语义动作时在产生式右部符号的语义栈上取了一个它没有的属性或者把子表达式的类型属性放到了父节点计算顺序里导致依赖循环。原因综合属性用于自底向上传递结果如表达式类型、地址继承属性用于自顶向下传递上下文如声明部分的类型信息。两者用反会让依赖图出现环。解决做题前先画一棵带属性标注的语法树用箭头把依赖关系画出来。箭头只朝上就是纯综合属性S-属性定义有向下箭头就是继承属性。检查时看每个属性的依赖值是否在所属结点的子树范围内。5.4 符号表作用域处理只填不删查表全错现象模拟器执行一段嵌套作用域代码时外层作用域中查到了一个内层的局部变量名而且不报错。原因作用域栈的实现里内层变量插入后没有在退出作用域时删除散列表链路上留下了脏数据。许多考试题目专门考这一点因为题目所给代码的内层变量恰好与外层同名。解决处理符号表时用一个作用域栈进入块时压入新一层退出时整层弹出销毁。查表时从栈顶往下逐层搜。手工做题时给每个变量标注其所属作用域编号遇到同名变量按“最近原则”查找。5.5 局部优化与全局优化分不清论述题翻车现象简答题里让你分析某段循环代码的优化方法你写了“DAG 消除公共子表达式”并说这是全局优化实际 DAG 作用范围是基本块内属于局部优化。原因术语层级混乱。局部优化范围是基本块内部全局优化范围跨越基本块循环优化属于全局优化的一种针对结构。解决记一张对应表基本块内——DAG、删除死代码、代数恒等式循环上——代码外提、强度削减、归纳变量删除。答题时先说范围再说手段能显著减少表述歧义。平时刷题可以把每种优化方法标好作用域临考时就不会答串。6. 冲刺阶段用一张自检清单验证复习有没有漏洞考前两三天不建议再看新题我习惯用一张自检清单把所有核心能力过一遍。这张清单按“能否不翻笔记手算出来”来设计能达到哪一档心里就有底。模块自检项验证方式词法分析正则转 NFA 再转 DFA 再最小化拿三个不同正则各练一遍卡壳处标红语法分析消除左递归、算 FIRST/FOLLOW、构造 LL(1) 表给出新文法20 分钟内独立完成全流程语法分析LR(0) 项目集规范族、SLR 分析表至少独立完成一个文法的完整自动机语义分析四元式翻译、回填技术把if-else和while语句翻译成中间代码符号表作用域栈的插入删除逻辑用嵌套代码手写查表过程优化区分局部/全局/循环优化给一段中间代码标注可用优化点这张表还有一个连带作用它本身就是知识地图能告诉你哪里还没复习到位。某个项目卡住说明对应模块的大题很危险立即回到对应章节做两道题再回来。另外一个值得坚持的习惯是“限时手算”。期末考语法分析大题时时间压力会让平时没卡过壳的人也出 bug。我当年就是把近十年真题的分析表构造题全部按考试时限重算了一遍每道题都要求自己在草稿纸上写出完整状态表和查询过程。算到第三张以后闭包运算和 FOLLOW 迭代的速度明显上来了考场上那种“算到一半忘记项目集闭包”的慌乱感也消失了。等到清单全勾完再有时间就去把每章名词解释过一遍比如“语法制导翻译”“回填”“基本块”这些术语考前背熟能防简答题没话说。我的教训是考前不要沉迷刷偏题怪题把这份清单逐项过掉比再多做三套模拟题都稳。希望帮到你。本文还有配套的精品资源点击获取