编译原理期末总复习：从词法分析到代码生成的完整知识重构

1. 项目概述：为什么“期末总复习”是编译原理学习的关键一跃

又到了学期末，看着桌上那本厚厚的《编译原理》教材和一堆关于词法分析、语法分析、语义分析的笔记，是不是感觉头大？很多同学把编译原理视为计算机专业“最难啃的骨头”之一，知识点抽象、概念环环相扣，平时学起来就吃力，期末复习更是无从下手。网上搜索“编译原理 期末”，关联出来的往往是“java+编译原理”、“如何构造预测分析表”、“预测分析表是如何得出来的”这类非常具体且核心的问题，这恰恰说明了大家的痛点：知道它重要，但不知道如何把零散的知识点串联成一个能解题、能理解的系统。

我经历过这个阶段，也带过不少学弟学妹度过编译原理的考试周。我发现，最大的误区就是把期末复习等同于“再看一遍书”或“狂刷课后题”。编译原理的复习，本质上是一次“知识重构”。你需要从一个更高的视角，把前端（词法、语法、语义分析）、中端（中间代码优化）和后端（目标代码生成）的零散模块，像搭积木一样，按照“源代码 -> 目标代码”的完整流水线重新组装起来。这次“总复习”项目，目的就是帮你完成这次重构。它不是简单的知识点罗列，而是带你走一遍编译器设计师的思考路径，让你明白每个阶段“为什么”要这么做，以及“如何”从上一个阶段推导到下一个阶段。最终目标不仅是应对考试，更是让你真正建立起对程序如何从文本变成可执行文件这一过程的系统性认知。

2. 复习核心框架：构建你的“编译器”思维模型

2.1 从宏观视角理解编译的六个阶段

编译原理教材通常将编译过程划分为六个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。期末复习时，死记硬背这六个名字没有意义。你需要建立的是一个动态的、数据流驱动的思维模型。

想象你正在编写一个最简单的编译器，处理一段类似a = b + c * 2的赋值语句。你的“编译器”大脑应该这样工作：

1. 词法分析（扫描器）：你的眼睛就是扫描器。它读入字符流“a”, “=”, “b”, “+”, “c”, “”, “2”，识别出哪些是独立的单词（词素）。这里，“a”、“b”、“c”是标识符（ID），“=”是赋值号（ASSIGN），“+”、“”是运算符（OP），“2”是整数常量（NUM）。输出是一串记号（Token）序列：[ID(a), ASSIGN, ID(b), OP(+), ID(c), OP(*), NUM(2)]。复习关键：掌握正规式、有限自动机（NFA、DFA）及其等价转换。考题常给出一段单词的规则描述（如“标识符以字母开头，后接字母数字”），让你写出正规式或画出DFA。

2. 语法分析（解析器）：你的大脑现在开始理解句子结构。它接收Token流，根据预定义的语法规则（通常是上下文无关文法），构建一棵语法分析树。对于上面的表达式，文法规则可能是E -> E + T | T; T -> T * F | F; F -> ( E ) | id | num。解析器会推导出a = b + c * 2符合赋值语句 -> id = E的结构，并明确c*2是一个子表达式（T），然后再与b相加（E）。复习关键：这是重中之重。必须熟练掌握自顶向下（LL(1)）和自底向上（LR）两大类分析方法。尤其是LL(1)文法的判断、First集和Follow集的计算、预测分析表的构造；以及LR(0)、SLR(1)、LR(1)、LALR(1)分析器的构造和项目集规范族。

3. 语义分析（检查器）：现在检查句子是否“有意义”。语法树只保证结构正确，但a = b + c * 2是否合法，还需要语义规则。检查包括：变量a, b, c是否已声明？b和c的类型是否支持乘法运算？乘法结果与b的类型是否支持加法？加法结果类型能否赋值给a？此阶段会收集类型信息，装饰语法树。复习关键：掌握属性文法的概念，特别是综合属性和继承属性如何计算。理解符号表（Symbol Table）的数据结构（如哈希表、链表）和作用（记录标识符的名字、类型、作用域、存储位置等）。

4. 中间代码生成（翻译器）：将经过检查的语法树翻译成一种抽象、机器无关的表示形式，常见的有三地址码（如t1 = c * 2; t2 = b + t1; a = t2）、四元式、逆波兰式等。中间代码像是“通用汇编”，它抹平了具体语法细节，为后续优化和生成不同目标机的代码做准备。复习关键：掌握如何将常见的程序结构（赋值、算术运算、控制流if/while、数组访问等）翻译成三地址码。这是连接前端理论和后端实践的重要桥梁。

5. 代码优化（优化器）：对中间代码进行等价变换，以提高运行时效率或减少代码大小。例如，对于t1 = c * 2;，如果编译器知道2是2的幂，可能会优化为t1 = c << 1;（左移一位代替乘法）。优化可以在中间代码层面进行，也可以在目标代码层面进行。复习关键：掌握常见的局部优化（如常量传播、公共子表达式消除、死代码删除）和循环优化（如代码外提、强度削弱）的基本思想和方法。能识别出给定代码片段可进行的优化。

6. 目标代码生成（汇编器）：将优化后的中间代码映射到特定目标机器（如x86、ARM）的指令集和寄存器上，生成最终的汇编或机器码。这涉及到寄存器分配（哪个变量放哪个寄存器）、指令选择（用哪条机器指令实现一个操作）、栈帧管理（函数调用时如何分配局部变量）等。复习关键：了解基本块、流图的概念，掌握简单的寄存器分配策略（如寄存器描述符和地址描述符），理解如何为三地址码生成目标代码的框架。

注意：这六个阶段并非总是严格串行，现代编译器常采用多遍扫描，且阶段间有交叉。但复习时，先建立清晰的阶段划分模型，是理解一切的基础。

2.2 核心数据结构：符号表与语法树

贯穿整个编译过程，有两个核心数据结构像“中枢神经”一样重要：

• 符号表：从语义分析阶段开始建立，并在后续阶段不断查询和更新。它记录了所有标识符（变量、函数、常量等）的属性。复习时要掌握符号表的常见操作（插入、查找、删除）、作用域的实现（如通过栈式符号表管理嵌套作用域）、以及如何处理同名标识符在不同作用域的问题。
• 语法树/抽象语法树（AST）：语法分析产生分析树，但通常会被进一步简化为AST，去掉那些对语义无关紧要的语法细节（如分隔符、部分非终结符）。AST是后续语义分析、中间代码生成所依赖的核心中间表示。要理解AST与分析树的区别，并能根据文法画出对应代码段的AST。

3. 重难点深度剖析与解题心法

3.1 语法分析：预测分析表（LL(1)表）的构造——从First集与Follow集说起

这是期末考和考研中的绝对高频考点。问题“编译原理中的预测分析表是如何得出来的？”直击核心。很多同学能背步骤，但不懂原理，题目稍一变就出错。我们来彻底搞懂它。

核心思想：LL(1)分析器在决定用哪个产生式展开当前非终结符时，只向前看一个输入符号（Lookahead）。预测分析表M[A, a]就是一个指南，告诉分析器：“当栈顶是非终结符A，且当前输入符号是a时，应该选用哪个产生式（或者报错）。”

构造步骤与内在逻辑：

1. 计算每个文法符号X的First集：First(X)表示由X推导出的串的可能开头终结符集合。

   • 规则：若X是终结符，First(X) = {X}。
   • 若X是非终结符，且存在产生式X -> Y1 Y2 ... Yk。
     • 将First(Y1)中所有非ε的元素加入First(X)。
     • 如果First(Y1)包含ε，则继续查看First(Y2)，将其非ε元素加入，以此类推。
     • 如果所有Yi都能推出ε，则将ε加入First(X)。
   • 为什么？因为分析器要预测，它必须知道A展开后，产生的字符串第一个可能是什么终结符。

2. 计算每个非终结符A的Follow集：Follow(A)表示在某些句型中，紧跟在A后面的终结符集合。

   • 规则：
     • 将结束符$加入Follow(开始符号)。
     • 若有产生式B -> α A β，则将First(β)中所有非ε的元素加入Follow(A)。
     • 若有产生式B -> α A，或B -> α A β且β能推出ε（即ε ∈ First(β)），则将Follow(B)加入Follow(A)。
   • 为什么？考虑A可能推出空串ε的情况。如果A推出了ε，那么决定下一步动作的，就是原本跟在A后面的那个符号（即Follow(A)中的符号）。所以，Follow集是为了处理“空”产生式。

3. 构造预测分析表M：

   • 对文法G的每个产生式A -> α，执行以下两步：
     • 对于First(α)中的每个终结符a，将A -> α填入M[A, a]。这很直观：当前输入符a正好是α能推导出的串的开头。
     • 如果ε ∈ First(α)，那么对于Follow(A)中的每个终结符b（包括$），也将A -> α填入M[A, b]。这就是关键！因为α能推出空，意味着A可能“消失”，那么该用什么产生式，就由跟在A后面的符号（Follow(A)）来决定。
   • 如果同一表项被填入了多个产生式，则该文法不是LL(1)文法。

实战例题解析： 给定文法：

E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id

1. 计算First和Follow集（过程略，这是基本功）：

   • First(F) = { (, id };First(T') = { *, ε };First(T) = { (, id };First(E') = { +, ε };First(E) = { (, id }
   • Follow(E) = { $, ) };Follow(E') = { $, ) };Follow(T) = { +, $, ) };Follow(T') = { +, $, ) };Follow(F) = { *, +, $, ) }

2. 构造预测分析表：

   非终结符	id	+	*	(	)	$
   E	E -> T E'	E -> T E'
   E'	E' -> + T E'	E' -> ε	E' -> ε
   T	T -> F T'	T -> F T'
   T'	T' -> ε	T' -> * F T'	T' -> ε	T' -> ε
   F	F -> id	F -> ( E )

   • 以E' -> ε为例：因为First(ε) = {ε}，所以看Follow(E') = { $, ) }。因此，在E'行，)列和$列填入E' -> ε。这意味着当栈顶是E'，输入是)或$（句子结束）时，应用ε产生式，将E'弹出栈（因为它匹配了“空”输入）。
   • 以T' -> * F T'为例：First(* F T') = {*}，所以只在T'行，*列填入该产生式。

避坑指南：

1. 计算Follow集时最容易漏：规则“B -> α A β且β能推出ε，则Follow(B)加入Follow(A)”。很多同学只记得B -> α A的情况。
2. 表项冲突：如果同一个格子要填两个不同的产生式，说明文法不是LL(1)。常见原因有：左递归、公共左因子。复习时要掌握消除左递归和提取左因子的方法。
3. ε产生式的填写：务必记住，只有当一个产生式的First集包含ε时，才去查找对应非终结符的Follow集来填表。

3.2 语法分析：LR分析器家族（LR(0), SLR(1), LR(1), LALR(1)）的辨析与构造

这是另一个难点，尤其是项目集规范族（LR(0)项集族）的构造。核心是理解“状态”的概念。

核心思想：LR分析器维护一个状态栈（而LL是符号栈），状态代表了分析器在解析过程中所处的“位置”（即已经看到了产生式的多少部分）。通过查询 ACTION/GOTO 表来决定是移进、规约、接受还是报错。

构造流程与关键区别：

1. LR(0)项：一个产生式加上一个“·”点，表示已识别和未识别的分界，如A -> α·β。

2. 构造LR(0)项集规范族：

   • CLOSURE操作：如果项A -> α·Bβ在集合I中，且B是非终结符，那么对于B的所有产生式B -> γ，将B -> ·γ加入I。这表示我们期待接下来看到B推导出的东西。
   • GOTO操作：GOTO(I, X)是从项集I出发，所有形如A -> αX·β的项的集合（即点越过符号X）。
   • 从初始项集CLOSURE({S' -> ·S})开始，反复应用GOTO操作，直到不再产生新项集。每个项集就是一个状态。

3. 从项集到分析表（以SLR(1)为例，这是考试中最常考的）：

   • ACTION表：针对终结符。
     • 移进：如果项A -> α·aβ在状态i中，且GOTO(i, a) = j，则ACTION[i, a] = sj（移进a，并跳转到状态j）。
     • 规约：如果项A -> α·在状态i中（点在最后，表示一个完整产生式已识别），则对于Follow(A)中的所有终结符a，ACTION[i, a] = rk（用第k个产生式A -> α规约）。这就是SLR(1)！它用Follow集来限制规约范围。
     • 接受：如果项S' -> S·在状态i中，则ACTION[i, $] = acc。
   • GOTO表：针对非终结符。如果GOTO(i, X) = j，则GOTO[i, X] = j。

4. LR家族辨析：

   • LR(0)：最弱。只要状态中有规约项A -> α·，就对所有输入符号都执行规约动作。这必然会产生大量“移进-规约”冲突。实际很少直接用。
   • SLR(1)：在LR(0)的基础上，用Follow(A)限制了规约项A -> α·的适用范围。只有当当前输入符a在Follow(A)中时，才执行规约。解决了LR(0)的大部分冲突，能力较强且构造简单，是考试重点。
   • LR(1)：能力最强。它将“向前看符号”直接集成到项中，形成LR(1)项[A -> α·β, a]。规约项[A -> α·, a]只对特定的向前看符号a进行规约。状态数可能比SLR(1)多很多。
   • LALR(1)：在LR(1)的基础上，合并那些核心项（点位置相同）相同、仅向前看符号集不同的状态。状态数与SLR(1)相同，分析能力介于SLR(1)和LR(1)之间，是实践中（如Yacc/Bison）最常用的。

解题心法：

1. 画状态图：构造项集规范族时，建议在草稿纸上画出状态转换图。每个状态（项集）是一个节点，用符号X（终结符或非终结符）做边连接到下一个状态GOTO(I, X)。这能极大帮助你理解状态机的走向。
2. 冲突判断：SLR(1)表中，如果同一个ACTION[i, a]格子既有移进动作sj又有规约动作rk，这就是“移进-规约冲突”。如果同一个格子有两个不同的规约动作，是“规约-规约冲突”。出现冲突意味着该文法不是SLR(1)文法。
3. 牢记步骤：先拓广文法（增加S' -> S）-> 构造LR(0)项集规范族 -> 根据每个状态中的项和Follow集，填写SLR(1)分析表。按部就班，不要跳步。

3.3 语法制导翻译与中间代码生成

这部分考查将语法结构翻译成三地址码的能力。核心是理解“属性”如何在语法树中传递和计算。

关键考点：

1. S-属性文法与L-属性文法：

   • S-属性文法：只使用综合属性（属性值自底向上计算，从子节点传到父节点）。LR分析器可以方便地实现。
   • L-属性文法：属性计算可以是深度优先从左到右的顺序。包含了S-属性文法。LL分析器可以方便地实现。
   • 考试中常给出一段带有语义规则的文法，让你判断是S-属性还是L-属性，并说明如何计算。

2. 翻译模式与三地址码生成：

   • 你需要为每个语法规则配上一个或多个语义动作（用花括号{}括起）。
   • 例如，为表达式E -> E1 + T生成三地址码：

     E -> E1 + T { E.place = new_temp(); // 为E的结果分配一个临时变量 emit(E.place “ = ” E1.place “ + ” T.place); // 生成三地址指令 }

   • 控制流语句（if, while）的翻译是重点和难点，需要用到回填（backpatching）技术来管理跳转目标的标号。
     • 回填的核心：在生成条件跳转指令时，跳转目标（标号）可能还不知道。此时，先生成一个不完整的指令（目标地址留空），并将这条指令的地址存入一个列表。当后续知道目标标号时，再“回填”到这个列表中的所有指令地址上。

实战示例：While语句的翻译考虑文法：S -> while ( E ) S1为其设计翻译模式，生成三地址码。

S -> while ( E ) S1 { S.begin = new_label(); // 循环开始标号 E.true = new_label(); // E为真时跳往的标号（即S1的入口） E.false = S.next; // E为假时跳往的标号（即循环后的语句） S1.next = S.begin; // S1执行完后跳回循环开始 emit(S.begin “:”); // 生成标号 gen_code_for(E); // 生成E的代码，其跳转目标由E.true和E.false决定 emit(E.true “:”); gen_code_for(S1); emit(“goto ” S.begin); // S.next 已经在E.false中设置 }

这里，S.next是一个继承属性，表示S执行完后应该跳转到的标号，由外层环境提供。new_label()生成一个新的唯一标号。gen_code_for是一个递归过程，为子表达式或语句生成代码。

4. 期末备考策略与高频题型实战

4.1 高效复习路线图

距离考试可能只剩一两周，时间有限，必须高效。

1. 第一轮（2-3天）：建立框架，攻克核心算法

   • 目标：彻底弄懂NFA到DFA的转化（子集构造法）、First/Follow集计算、LL(1)预测分析表构造、LR(0)/SLR(1)项集规范族构造及分析表生成。这四大块是试卷大题最可能出现的。
   • 方法：不看细节描述，直接找3-5道经典例题（课本习题、往年考题），对照答案一步步推导。推导过程中，把每一步的“为什么”写在旁边。自己总结出算法步骤清单。

2. 第二轮（2-3天）：串联流程，掌握翻译与优化

   • 目标：理解从词法分析到目标代码生成的完整数据流。重点练习将小程序片段（赋值、算术、if、while）翻译成三地址码，以及在给定的三地址码序列上进行局部优化。
   • 方法：画出“源代码 -> Token流 -> 语法树 -> 三地址码 -> 优化后代码”的完整转换图。针对每种控制结构，默写其标准的翻译模板。

3. 第三轮（1-2天）：扫荡概念，查漏补缺

   • 目标：复习选择题、填空题可能涉及的所有概念。如：编译各阶段任务、文法的分类（Chomsky体系）、短语/句柄/素短语、活动记录、运行时存储空间组织（栈、堆）、常见的代码优化技术名称等。
   • 方法：快速浏览教材目录和章节小结，用自己的话复述每个概念。制作关键词闪卡。

4. 第四轮（考前1天）：模拟与错题回顾

   • 目标：找一套往年真题或模拟题，严格计时完成。不对答案，检验时间分配和答题手感。然后重点复习之前做错的题目和易混淆点（如LL vs LR， SLR vs LR(1)）。

4.2 高频题型与答题模板

题型一：文法与语法分析（综合大题）

• 题干形式：给一个文法G，可能要求：1) 判断文法类型；2) 计算First/Follow集；3) 判断是否为LL(1)并构造预测分析表；4) 判断是否为SLR(1)并构造分析表；5) 分析给定句子。
• 答题模板：
  1. 判断与预处理：如有左递归或公共左因子，先进行消除/提取。
  2. 计算First/Follow集：在草稿纸上清晰列出所有符号，逐步计算。在答卷上整齐呈现最终结果。
  3. 构造分析表：
     • 若是LL(1)，画一个矩阵，行是非终结符，列是终结符+$。根据First/Follow集规则逐一填写产生式。
     • 若是SLR(1)，先构造LR(0)项集规范族（需画出所有状态I0, I1...），然后为每个状态i和每个符号填写ACTION[i, a]和GOTO[i, A]。填写ACTION规约项时，务必写上“根据Follow(X)”这一依据。
  4. 分析句子：按照构造出的分析表，一步步模拟栈和输入的变化过程。步骤要清晰，格式要工整。

题型二：中间代码生成（大题）

• 题干形式：给一段小程序（包含变量声明、赋值、算术运算、if-else、while循环、数组访问等），要求生成三地址码、四元式或逆波兰式。
• 答题模板：
  1. 声明处理：为所有变量在符号表中分配虚拟地址（如offset）。
  2. 逐句翻译：
     • 算术表达式：引入临时变量，自底向上生成t = arg1 op arg2。
     • 赋值语句：x = y或x = t。
     • 数组访问a[i]：计算地址addr = base_a + i * width，然后通过t = *addr取值或*addr = t赋值。
     • 控制流：为if和while准备好标号（L1, L2...），严格按照翻译模式生成带条件/无条件跳转的代码。务必注意标号的管理和跳转目标的正确性。

题型三：代码优化（分析/应用题）

• 题干形式：给出一段基本块的三地址码，要求进行优化（如常量传播、公共子表达式消除、死代码删除），并写出优化后的代码。
• 答题模板：
  1. 画出DAG（有向无环图）：这是最直观的方法。为每个变量和运算建立节点，边表示依赖关系。
  2. 基于DAG进行优化：
     • 常量折叠：如果运算对象是常量，直接计算。
     • 公共子表达式：如果多个变量指向DAG中同一个运算符节点，则它们是公共子表达式，可以合并。
     • 死代码删除：如果一个变量的值生成后没有被任何后续语句引用，则生成该值的语句可删除。
  3. 从DAG重写代码：按拓扑序从DAG生成新的三地址码，同时复用临时变量。

4.3 考场实战技巧与常见失分点

1. 时间分配：编译原理考试计算量大。建议拿到试卷先通览，预估每道题耗时。将至少50%的时间留给最后1-2道语法分析或翻译的大题。选择题和概念题不要纠结，快速完成。
2. 书写规范：计算First/Follow集、构造分析表时，务必使用清晰的表格，保持卷面整洁。状态编号（I0, I1...）、标号（L1, L2...）、临时变量（t1, t2...）要前后一致。
3. 分步得分：即使最终结果不对，计算过程也有分。例如，构造SLR(1)表时，LR(0)项集规范族画对了就有可观的分数。一定要把关键步骤写在试卷上。
4. 常见失分点：
   • First/Follow集计算错误：这是连锁反应的起点，一步错步步错。务必复查，特别是ε产生式对First集的影响，以及Follow集中“包含$”和“继承Follow(B)”的规则。
   • 预测分析表冲突处理：遇到冲突，要明确写出冲突类型和原因（如“因First(X) ∩ Follow(A) 非空”），而不是简单地说“不是LL(1)文法”。
   • LR分析表ACTION/GOTO混淆：ACTION表对应终结符，决定移进、规约、接受；GOTO表对应非终结符，决定状态转移。填表时千万别搞混列。
   • 中间代码标号错误：if和while翻译中，条件为假时的跳转目标（S.next）最容易弄错。画一下控制流图有助于理清关系。
   • 优化过度：代码优化时，要确保优化前后的程序语义等价。特别是涉及指针、函数调用副作用时，不要轻易做优化。

编译原理的复习是一场硬仗，但也是一次将计算机科学中最精妙的思想之一——如何让机器理解人类的意图——系统化梳理的绝佳机会。当你不再视那些枯燥的算法为负担，而是将其看作构建一个复杂系统（编译器）所必需的精巧工具时，理解的门槛就已经跨过了一半。最后几天，沉下心来，用笔和纸去推导几个完整的例子，比反复看书更有效。祝你复习顺利，考试成功。