1. 从“天书”到“通关秘籍”：编译原理期末复习的正确打开方式

又到了学期末，看着《编译原理》课本上那些词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成……是不是感觉头都大了？这门课被不少同学戏称为“天书课”，概念抽象、算法复杂、前后关联紧密，一个环节没搞懂，后面就可能完全跟不上。期末复习时，面对厚厚的教材和一堆似懂非懂的习题，常常感到无从下手。别慌，这几乎是每个学过编译原理的同学都会经历的阶段。我当年也是这么过来的，但后来发现，只要方法得当，编译原理不仅不难，其内在的逻辑美感甚至能让人着迷。这篇复习指南，就是帮你把散落的知识点串成线、织成网，从“看天书”的状态，升级到手握“通关秘籍”的自信。我们不会枯燥地罗列概念，而是聚焦于那些期末考试中最高频、最核心、最容易出错的考点，通过典型习题的深度剖析，带你理解背后的“为什么”，并分享我总结的实战解题技巧与避坑指南。

2. 词法分析：正则表达式的实战化理解与DFA/NFA转化

词法分析是编译器的“眼睛”，负责把源代码字符串切分成一个个有意义的单词（Token）。这部分考试的重点永远绕不开正则表达式、**有限自动机（NFA/DFA）**以及它们之间的相互转化。

2. 1 正则表达式：不止是匹配，更是构造的起点

很多同学对正则表达式的理解停留在“用来匹配字符串”的层面，但在编译原理中，它的核心作用是形式化地描述一类单词的构成规则。考试中常给你一段自然语言描述（如“标识符由字母开头，后跟任意数量的字母或数字”），要求你写出对应的正则表达式。

关键考点与避坑：

1. 运算符优先级：闭包（*）> 连接 > 或（|）。忘记优先级会导致正则表达式意义完全错误。例如，a|b*表示的是a或(b*)，而不是(a|b)*。在复杂表达式中，善用括号来明确分组。
2. “任意字符”与“字母数字”：题目中如果说“任意字符”，通常指字母、数字、下划线等构成的某个集合，需要你根据上下文明确定义。例如，定义标识符时，字母集可能是[a-zA-Z]，数字集是[0-9]。
3. 正闭包（+）与星闭包（*）：a+表示至少一个a，a*表示零个或多个a。描述“至少一位的数字”时，应用digit+，而不是digit*。

实战技巧：拿到描述后，先拆分最小单元。比如“无符号实数”（如123.45, 0.78, 9.0）。我们可以拆解为：整数部分（至少一位数字）、小数点（可选）、小数部分（如果有点，则至少一位数字）。那么一个可能的形式化描述是：digit+ ( . digit+ )?。这里?表示可选，是(ε| ...)的简写。这种分步拆解的思维，能让你应对任何复杂的描述。

2. 2 NFA 与 DFA：从非确定到确定的转化艺术

这是词法分析部分的大题高频区。题目通常给出一个正则表达式或一个NFA的状态转移图，要求你将其转化为DFA，并进行最小化。

为什么需要DFA？NFA（非确定有限自动机）状态转移不确定（同一个输入可能指向多个状态，或有ε空转移），虽然易于人工构造（尤其从正则表达式构造），但无法直接用于程序实现。DFA（确定有限自动机）每个状态对每个输入字符都有唯一确定的下一个状态，运行效率高，是词法分析器（如Lex/Flex）实际使用的模型。

转化核心步骤（子集构造法）与易错点：

1. 求ε-闭包（ε-closure）：这是第一步，也是容易算错的一步。状态s的ε-闭包包括：s本身 + 从s出发经过任意条ε边所能到达的所有状态。计算时必须传递下去，直到没有新的状态加入为止。
2. 构造DFA状态：DFA的每个状态，都是原NFA状态集的一个子集（即NFA的一些状态的集合）。起始状态就是NFA起始状态的ε-闭包。
3. 计算状态转移：对于DFA状态A中的每个NFA状态s，查看s在输入字符a下能到达哪些NFA状态（集合T），然后求T中所有状态的ε-闭包的并集，这个并集就构成了DFA中从状态A经输入a到达的新状态B。
4. 标记终止状态：只要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 -> α，：

1. 对于FIRST(α)中的每个终结符a（a ≠ ε），在表项[A, a]中填入A -> α。
2. 如果ε在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)自动机的构造（项目集规范族）：

1. 闭包（Closure）操作：若项目A -> α·Bβ在集合I中，且B -> γ是一个产生式，则将B -> ·γ加入I。必须反复执行，直到没有新项目加入。这一步是为了包含所有在当前状态下可能出现的规则。
2. 转移（Goto）操作：对于集合I和文法符号X，Goto(I, X)包含所有形如A -> αX·β的项目，其中A -> α·Xβ在I中。然后再对结果求闭包。
3. 从初始项目集（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] = rj（j是产生式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)。

解题经验：

1. 构造项目集规范族时，务必为每个项目集（状态）编号，并清晰画出Goto关系图（类似DFA）。
2. 填分析表时，先填ACTION表（移进和归约），再填GOTO表。归约动作（rj）是填在整个FOLLOW集对应的列，这是SLR(1)和LR(0)在填表时的唯一区别（LR(0)归约是填所有列）。
3. 判断是否是SLR(1)文法，核心就是检查按照上述规则填表后，ACTION表每个格子是否最多只有一个动作。如果存在一个格子既有s又有r，或者有两个r，则不是SLR(1)。

4. 语法制导翻译与中间代码生成：属性计算的逻辑

这部分将语法分析和语义处理（如类型检查、代码生成）联系起来。考题常围绕语法制导定义（SDD）和翻译方案（语法制导翻译方案，SDT）。

4. 1 综合属性与继承属性

• 综合属性：自底向上传递。父节点的属性值依赖于子节点的属性值。在语法树中，信息从叶子流向根。计算时机：通常在产生式体（右部）的语法成分计算完成后，再计算产生式头（左部）非终结符的属性。这非常契合自底向上的LR分析。
• 继承属性：自顶向下或水平传递。子节点的属性值依赖于父节点或兄弟节点的属性值。在语法树中，信息从根或左兄弟流向当前节点。计算时机：需要在进入子节点之前就计算好，因此更契合自顶向下的LL分析。

考题典型模式：给出一段关于变量声明、类型检查或简单表达式计算的SDD，要求你：

1. 判断各属性是综合属性（S）还是继承属性（I）。
2. 为给定的输入句子（如int a, b;）绘制带属性值的注释语法分析树。
3. 判断该SDD是否是S-属性定义（仅含综合属性）或L-属性定义（每个继承属性只依赖于其左边兄弟节点的属性和父节点的继承属性）。

绘制注释语法分析树的技巧：

1. 先画出普通的语法分析树。
2. 为每个节点列出其所有属性（根据SDD）。
3. 从已知的、依赖关系最简单的属性开始计算。通常是词法分析器提供的词法值（如id.lexeme）或综合属性。
4. 按照依赖关系（即SDD中的语义规则），像解方程一样，逐步计算出每个节点的属性值。继承属性的计算可能需要你“从上往下”看。

4. 2 中间代码形式：三地址码与DAG

中间代码是编译器前、后端的分水岭。期末考试重点考察三地址码的生成。

三地址码基本形式：x = y op z，其中op是运算符，x, y, z是操作数（变量、常量或临时变量）。它最多只有一个运算符。

常见三地址指令：

• 赋值指令：x = y
• 二元运算：t1 = b * c，t2 = a + t1
• 数组访问：t1 = a * 20(假设每行20个元素)，t2 = baseAddr + t1，x = *t2(取内容)
• 控制流：ifFalse x goto L，goto L，param x(传参)，call p, n(调用过程p，n个参数)，return y。

考题方向：

1. 给定SDD/SDT，写出为某个赋值语句或表达式生成的三地址码序列。这里的关键是理解如何用临时变量（t1, t2, ...）来保存中间结果，并注意运算顺序和优先级。
2. 将基本的三地址码序列优化成更简洁的形式，或者识别出**有向无环图（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）：每次函数/过程调用时，在栈上分配的一块内存区域，用于存储该次调用所需的信息。

一个典型的活动记录包含（从高地址到低地址）：

1. 实际参数（调用者传入）
2. 返回地址（调用结束后回到哪里）
3. 控制链（动态链，指向调用者的活动记录）
4. 访问链（静态链，用于访问非局部数据，在静态作用域语言中很重要）
5. 保存的机器状态（寄存器等）
6. 局部变量
7. 临时变量

三种存储分配策略：

• 静态分配：在编译期就确定每个数据对象的存储位置。适用于全局变量、static变量。速度快，无运行时开销，但不支持递归和动态数据结构。
• 栈式分配：用于管理过程调用。活动记录在栈上分配和释放。支持递归，高效实现局部变量的生命周期管理。这是考试重点，要能画出嵌套调用时的栈变化图。
• 堆式分配：用于动态申请的内存（如malloc/new）。分配和释放顺序任意，需要垃圾回收机制。管理开销最大。

考题示例：给出一段带有嵌套过程调用的代码，要求画出在某个时刻运行时栈的活动记录情况。你需要清楚每个活动记录里大概有什么，以及控制链（动态链）如何将它们串联起来，形成“调用栈”。

5. 2 代码优化：局部优化与循环优化

优化不是在写天书，而是有章可循的逻辑变换。期末考常考一些经典的、可形式化描述的优化技术。

局部优化（基本块内）：

• 公共子表达式消除：如果同一个表达式在一个基本块内被多次计算，且其操作数在中间未被重新定义，则保留第一次计算结果，后续直接使用。
• 常量传播：如果变量在某个点被赋值为一个已知常量，那么后续对该变量的使用可以直接替换为该常量。
• 死代码删除：计算结果永远不会被使用的语句，可以删除。

循环优化：

• 代码外提：将循环中不变的计算（循环不变量）移到循环之前。例如，for(i=0; i<n; 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）导致的停顿。

考题常见形式：

1. 给定一个简单的三地址码序列和一个假想的简化机器模型（如只有2个寄存器），模拟简单的寄存器分配过程。例如，采用“最近最少使用”策略，当寄存器不够时，将哪个寄存器的值存回内存。
2. 判断指令间的数据依赖关系。给出一个小指令序列，要求指出哪些指令之间存在RAW、WAR、WAW冲突。这是指令调度的基础。
3. 理解基本块的有向无环图（DAG）表示与代码生成的关系。DAG不仅用于优化，其拓扑排序也能为代码生成提供一个计算顺序，同时便于在生成代码时复用已加载到寄存器的值。

一个实用技巧：在生成目标代码时，对于像a = b + c这样的表达式，如果b或c已经在寄存器中，就应该直接使用寄存器进行操作，而不是从内存重复加载。好的代码生成器会跟踪寄存器的内容状态。这在手写或分析简单代码生成序列时是一个重要的考虑点。

复习编译原理，切忌死记硬背。它是一门强逻辑的学科。最好的方法是以习题驱动，在解题过程中串起知识点。当你看到一道关于LR分析表构造的题，你能立刻联想到它可能涉及FIRST/FOLLOW集的计算、项目集闭包的求法、冲突的判别与解决这一整条链路。把每一道错题弄懂，其价值远大于盲目刷十道新题。最后，祝大家都能理顺思路，在期末考试中把这张“天书”变成你的“高分秘籍”！