1. 从“天书”到“通关秘籍”编译原理期末复习的正确打开方式又到了学期末看着《编译原理》课本上那些词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成……是不是感觉头都大了这门课被不少同学戏称为“天书课”概念抽象、算法复杂、前后关联紧密一个环节没搞懂后面就可能完全跟不上。期末复习时面对厚厚的教材和一堆似懂非懂的习题常常感到无从下手。别慌这几乎是每个学过编译原理的同学都会经历的阶段。我当年也是这么过来的但后来发现只要方法得当编译原理不仅不难其内在的逻辑美感甚至能让人着迷。这篇复习指南就是帮你把散落的知识点串成线、织成网从“看天书”的状态升级到手握“通关秘籍”的自信。我们不会枯燥地罗列概念而是聚焦于那些期末考试中最高频、最核心、最容易出错的考点通过典型习题的深度剖析带你理解背后的“为什么”并分享我总结的实战解题技巧与避坑指南。2. 词法分析正则表达式的实战化理解与DFA/NFA转化词法分析是编译器的“眼睛”负责把源代码字符串切分成一个个有意义的单词Token。这部分考试的重点永远绕不开正则表达式、**有限自动机NFA/DFA**以及它们之间的相互转化。2. 1 正则表达式不止是匹配更是构造的起点很多同学对正则表达式的理解停留在“用来匹配字符串”的层面但在编译原理中它的核心作用是形式化地描述一类单词的构成规则。考试中常给你一段自然语言描述如“标识符由字母开头后跟任意数量的字母或数字”要求你写出对应的正则表达式。关键考点与避坑运算符优先级闭包* 连接 或|。忘记优先级会导致正则表达式意义完全错误。例如a|b*表示的是a或(b*)而不是(a|b)*。在复杂表达式中善用括号来明确分组。“任意字符”与“字母数字”题目中如果说“任意字符”通常指字母、数字、下划线等构成的某个集合需要你根据上下文明确定义。例如定义标识符时字母集可能是[a-zA-Z]数字集是[0-9]。正闭包与星闭包*a表示至少一个aa*表示零个或多个a。描述“至少一位的数字”时应用digit而不是digit*。实战技巧拿到描述后先拆分最小单元。比如“无符号实数”如123.45, 0.78, 9.0。我们可以拆解为整数部分至少一位数字、小数点可选、小数部分如果有点则至少一位数字。那么一个可能的形式化描述是digit ( . digit )?。这里?表示可选是(ε| ...)的简写。这种分步拆解的思维能让你应对任何复杂的描述。2. 2 NFA 与 DFA从非确定到确定的转化艺术这是词法分析部分的大题高频区。题目通常给出一个正则表达式或一个NFA的状态转移图要求你将其转化为DFA并进行最小化。为什么需要DFANFA非确定有限自动机状态转移不确定同一个输入可能指向多个状态或有ε空转移虽然易于人工构造尤其从正则表达式构造但无法直接用于程序实现。DFA确定有限自动机每个状态对每个输入字符都有唯一确定的下一个状态运行效率高是词法分析器如Lex/Flex实际使用的模型。转化核心步骤子集构造法与易错点求ε-闭包ε-closure这是第一步也是容易算错的一步。状态s的ε-闭包包括s本身 从s出发经过任意条ε边所能到达的所有状态。计算时必须传递下去直到没有新的状态加入为止。构造DFA状态DFA的每个状态都是原NFA状态集的一个子集即NFA的一些状态的集合。起始状态就是NFA起始状态的ε-闭包。计算状态转移对于DFA状态A中的每个NFA状态s查看s在输入字符a下能到达哪些NFA状态集合T然后求T中所有状态的ε-闭包的并集这个并集就构成了DFA中从状态A经输入a到达的新状态B。标记终止状态只要DFA的某个状态即一个NFA状态子集中包含了NFA的任何一个终止状态那么这个DFA状态就是终止状态。一个经典陷阱在计算转移时只取了直接转移到的状态的ε-闭包而忘记了先对源状态子集里的每个状态求转移再对转移结果的并集求ε-闭包。正确的顺序是move(A, a) ε-closure( ∪_{s in A} move(s, a) )。最小化DFA划分法考试常要求对得到的DFA进行最小化。核心是“等价状态”的划分两个状态等价当且仅当对于所有输入符号它们都转移到等价的状态组。操作口诀先根据“是否为终止状态”分成两组终止组和非终止组然后不断地检查每组内的状态对于每个输入符是否都转移到当前划分的同一组内如果不是就拆分。重复直到不能再拆分。个人心得手画DFA/NFA图时一定要清晰标注状态编号、输入字符和终止状态常用双圈。在子集构造过程中建议画一个表格行是DFA新状态用NFA状态子集表示列是所有输入字符逐个填充。这个过程繁琐但绝不能跳步跳一步后面全错。3. 语法分析掌握LL(1)与LR(0)/SLR(1)的决胜心法语法分析是编译器的“骨架构建师”检查单词流是否符合语法规则并通常生成语法树。期末考的重中之重是自顶向下的LL(1)分析和自底向上的LR分析。3. 1 LL(1)分析预测与回溯的消除LL(1)分析的关键在于“预测”即看到当前输入符号和栈顶非终结符时能唯一确定选用哪条产生式。这依赖于三张表FIRST集、FOLLOW集和预测分析表。FIRST集计算常见错误如果A - ε是产生式那么ε一定在FIRST(A)中。计算FIRST(X1X2...Xn)时顺序查看。把FIRST(X1)中非ε的元素加入。只有当X1能推出ε时才继续查看FIRST(X2)并加入其中非ε的元素以此类推。如果所有Xi都能推出ε则把ε也加入。很多同学在计算FIRST(α)时忘记了这个“顺序查看与ε传播”的规则导致结果错误。FOLLOW集计算要点$输入结束符总是在文法开始符号的FOLLOW集中。规则A - αBβFIRST(β)中除ε外的所有符号都要加入FOLLOW(B)。这是FOLLOW集元素的主要来源之一。规则A - αB或A - αBβ 且 β 能推出 ε那么FOLLOW(A)的所有符号都要加入FOLLOW(B)。这是FOLLOW集的“继承”传播容易漏算。预测分析表构建与LL(1)文法判定 对于每条产生式A - α对于FIRST(α)中的每个终结符aa ≠ ε在表项[A, a]中填入A - α。如果ε在FIRST(α)中那么对于FOLLOW(A)中的每个终结符b包括$在表项[A, b]中填入A - α。判定LL(1)文法的充要条件预测分析表每个格子最多有一条产生式。常见冲突原因1) 文法左递归2) 文法不是经过提取左公因子后的。所以题目常先要求你消除左递归和提取左公因子。避坑指南在计算FIRST和FOLLOW集时建议多迭代几轮直到所有集合都不再变化。可以用下标表示迭代次数清晰展示推导过程。构建预测分析表时务必对照FIRST和FOLLOW集按上述两条规则机械地填写避免凭感觉。3. 2 LR(0)与SLR(1)分析移进与归约的博弈LR分析能力更强可以处理更多文法。期末考通常集中在**LR(0)和SLR(1)**的构造和分析上。核心概念——项目Item在产生式右部某处加一个点“·”如A - α·β。点表示分析进度。LR(0)自动机的构造项目集规范族闭包Closure操作若项目A - α·Bβ在集合I中且B - γ是一个产生式则将B - ·γ加入I。必须反复执行直到没有新项目加入。这一步是为了包含所有在当前状态下可能出现的规则。转移Goto操作对于集合I和文法符号XGoto(I, X)包含所有形如A - αX·β的项目其中A - α·Xβ在I中。然后再对结果求闭包。从初始项目集Closure({S - ·S$})S’是增广文法的开始符号开始反复应用Goto操作生成所有项目集。LR(0)分析表的构建与冲突移进shift如果项目A - α·aβ在Ik中且Goto(Ik, a) Ij则ACTION[k, a] sj。归约reduce如果项目A - γ·在Ik中则对于所有终结符a包括$ACTION[k, a] rjj是产生式A - γ的编号。接受accept如果项目S - S·$在Ik中则ACTION[k, $] acc。Goto表对于非终结符A如果Goto(Ik, A) Ij则GOTO[k, A] j。LR(0)冲突一个状态中同时存在移进项目和归约项目移进-归约冲突或存在多个归约项目归约-归约冲突。LR(0)文法要求无冲突。SLR(1)——简单的冲突解决 当LR(0)状态出现移进-归约冲突即有A - α·aβ和B - γ·时LR(0)会报冲突。SLR(1)则检查向前看一个符号仅当输入符号a属于FOLLOW(B)时才用B - γ进行归约否则进行移进。如果a既在FIRST(β)中需要移进又在FOLLOW(B)中则冲突无法解决该文法就不是SLR(1)。解题经验构造项目集规范族时务必为每个项目集状态编号并清晰画出Goto关系图类似DFA。填分析表时先填ACTION表移进和归约再填GOTO表。归约动作rj是填在整个FOLLOW集对应的列这是SLR(1)和LR(0)在填表时的唯一区别LR(0)归约是填所有列。判断是否是SLR(1)文法核心就是检查按照上述规则填表后ACTION表每个格子是否最多只有一个动作。如果存在一个格子既有s又有r或者有两个r则不是SLR(1)。4. 语法制导翻译与中间代码生成属性计算的逻辑这部分将语法分析和语义处理如类型检查、代码生成联系起来。考题常围绕语法制导定义SDD和翻译方案语法制导翻译方案SDT。4. 1 综合属性与继承属性综合属性自底向上传递。父节点的属性值依赖于子节点的属性值。在语法树中信息从叶子流向根。计算时机通常在产生式体右部的语法成分计算完成后再计算产生式头左部非终结符的属性。这非常契合自底向上的LR分析。继承属性自顶向下或水平传递。子节点的属性值依赖于父节点或兄弟节点的属性值。在语法树中信息从根或左兄弟流向当前节点。计算时机需要在进入子节点之前就计算好因此更契合自顶向下的LL分析。考题典型模式给出一段关于变量声明、类型检查或简单表达式计算的SDD要求你判断各属性是综合属性S还是继承属性I。为给定的输入句子如int a, b;绘制带属性值的注释语法分析树。判断该SDD是否是S-属性定义仅含综合属性或L-属性定义每个继承属性只依赖于其左边兄弟节点的属性和父节点的继承属性。绘制注释语法分析树的技巧先画出普通的语法分析树。为每个节点列出其所有属性根据SDD。从已知的、依赖关系最简单的属性开始计算。通常是词法分析器提供的词法值如id.lexeme或综合属性。按照依赖关系即SDD中的语义规则像解方程一样逐步计算出每个节点的属性值。继承属性的计算可能需要你“从上往下”看。4. 2 中间代码形式三地址码与DAG中间代码是编译器前、后端的分水岭。期末考试重点考察三地址码的生成。三地址码基本形式x y op z其中op是运算符x, y, z是操作数变量、常量或临时变量。它最多只有一个运算符。常见三地址指令赋值指令x y二元运算t1 b * ct2 a t1数组访问t1 a * 20(假设每行20个元素)t2 baseAddr t1x *t2(取内容)控制流ifFalse x goto Lgoto Lparam x(传参)call p, n(调用过程pn个参数)return y。考题方向给定SDD/SDT写出为某个赋值语句或表达式生成的三地址码序列。这里的关键是理解如何用临时变量t1, t2, ...来保存中间结果并注意运算顺序和优先级。将基本的三地址码序列优化成更简洁的形式或者识别出**有向无环图DAG**中的公共子表达式。例如对于代码t1 b * c; t2 a t1; t3 b * c; t4 t2 t3;可以发现b * c是公共子表达式可以只计算一次让t1和t3指向DAG中同一个节点。实战心得生成三地址码时临时变量的命名要有序t1, t2, ...这样代码清晰也便于后续优化。在画DAG时一个节点代表一个运算符或一个基本操作数如果多个变量持有相同的值如t1和t3都是b*c的结果它们应该指向同一个节点。DAG能直观地展示出哪些计算是重复的这是代码优化的基础。5. 运行时环境与代码优化理解程序执行的舞台这部分内容解释了程序在内存中是如何被组织和执行的以及编译器如何让生成的代码跑得更快。5. 1 活动记录与存储分配策略活动记录Activation Record每次函数/过程调用时在栈上分配的一块内存区域用于存储该次调用所需的信息。一个典型的活动记录包含从高地址到低地址实际参数调用者传入返回地址调用结束后回到哪里控制链动态链指向调用者的活动记录访问链静态链用于访问非局部数据在静态作用域语言中很重要保存的机器状态寄存器等局部变量临时变量三种存储分配策略静态分配在编译期就确定每个数据对象的存储位置。适用于全局变量、static变量。速度快无运行时开销但不支持递归和动态数据结构。栈式分配用于管理过程调用。活动记录在栈上分配和释放。支持递归高效实现局部变量的生命周期管理。这是考试重点要能画出嵌套调用时的栈变化图。堆式分配用于动态申请的内存如malloc/new。分配和释放顺序任意需要垃圾回收机制。管理开销最大。考题示例给出一段带有嵌套过程调用的代码要求画出在某个时刻运行时栈的活动记录情况。你需要清楚每个活动记录里大概有什么以及控制链动态链如何将它们串联起来形成“调用栈”。5. 2 代码优化局部优化与循环优化优化不是在写天书而是有章可循的逻辑变换。期末考常考一些经典的、可形式化描述的优化技术。局部优化基本块内公共子表达式消除如果同一个表达式在一个基本块内被多次计算且其操作数在中间未被重新定义则保留第一次计算结果后续直接使用。常量传播如果变量在某个点被赋值为一个已知常量那么后续对该变量的使用可以直接替换为该常量。死代码删除计算结果永远不会被使用的语句可以删除。循环优化代码外提将循环中不变的计算循环不变量移到循环之前。例如for(i0; in; i) { a x*y*z; ... }中如果x,y,z在循环内不变则t x*y*z可提到循环外。归纳变量与强度削弱循环中经常有类似于i i 1的变量归纳变量。如果存在另一个变量j其值与i成线性关系如j 4*i那么对j的更新可以从乘法削弱为加法j j 4。同时如果循环后不再需要i甚至可以删除对i的运算。循环展开将循环体复制多次减少循环控制判断和跳转的开销。解题思路面对优化题目首先将代码划分成基本块只有一个入口和一个出口的连续语句序列。然后在一个基本块内应用局部优化规则。对于循环识别出循环不变量和归纳变量。优化是一个迭代过程常常是应用一种优化后为另一种优化创造了条件。6. 目标代码生成从中间代码到汇编的临门一脚这是编译器的最后一步将相对机器无关的中间代码映射到具体目标机器的指令集。虽然期末考不会要求你写出完整的代码生成器但常考察一些核心概念和简单模式匹配。核心任务为三地址码这样的中间指令序列选择目标机器指令序列。这涉及到指令选择为每个中间代码操作选择合适的目标机指令。例如三地址码x y z可能对应汇编LOAD R1, y; ADD R1, z; STORE R1, x。寄存器分配决定哪些值放在有限的寄存器里哪些需要溢出Spill到内存。这是最复杂的部分之一考试可能涉及简单的图着色概念或最近最少使用LRU策略。指令调度重新排列指令顺序以充分利用目标机器的流水线避免数据冲突如写后读RAW、读后写WAR、写后写WAW导致的停顿。考题常见形式给定一个简单的三地址码序列和一个假想的简化机器模型如只有2个寄存器模拟简单的寄存器分配过程。例如采用“最近最少使用”策略当寄存器不够时将哪个寄存器的值存回内存。判断指令间的数据依赖关系。给出一个小指令序列要求指出哪些指令之间存在RAW、WAR、WAW冲突。这是指令调度的基础。理解基本块的有向无环图DAG表示与代码生成的关系。DAG不仅用于优化其拓扑排序也能为代码生成提供一个计算顺序同时便于在生成代码时复用已加载到寄存器的值。一个实用技巧在生成目标代码时对于像a b c这样的表达式如果b或c已经在寄存器中就应该直接使用寄存器进行操作而不是从内存重复加载。好的代码生成器会跟踪寄存器的内容状态。这在手写或分析简单代码生成序列时是一个重要的考虑点。复习编译原理切忌死记硬背。它是一门强逻辑的学科。最好的方法是以习题驱动在解题过程中串起知识点。当你看到一道关于LR分析表构造的题你能立刻联想到它可能涉及FIRST/FOLLOW集的计算、项目集闭包的求法、冲突的判别与解决这一整条链路。把每一道错题弄懂其价值远大于盲目刷十道新题。最后祝大家都能理顺思路在期末考试中把这张“天书”变成你的“高分秘籍”