电子科技大学编译原理期末复习精华笔记

编译原理期末复习精华笔记

考完了，松一口气。说实话这门课真不简单，概念抽象、推导繁琐，临场做题还得手速快。不过好在重点相对集中，只要抓住核心模块，系统梳理一遍，应付考试还是有谱的。

这份笔记是我根据课堂PPT、北航冯耀东老师的B站视频讲解以及历年真题整理出来的，包含知识点串联、典型题型拆解和老师划的重点方向。不建议全盘照搬（毕竟我自己也漏了不少），但用来查漏补缺、快速回顾非常合适。语雀原版体验更佳：点击查看

核心知识体系重构与实战要点

文法基础：从形式定义到语言分类

编译的第一步是“理解结构”，而文法就是描述程序结构的数学工具。一个上下文无关文法 $ G = (V_N, V_T, S, P) $ 看似简单，但背后藏着整个语法分析的设计逻辑。

比如这个经典例子：

S → aSb | ε

它生成的语言是 $ { a^n b^n \mid n \geq 0 } $，正是这种“嵌套匹配”特性让递归下降难以处理左递归——因为会无限调用下去。

乔姆斯基四类文法中，我们真正关心的是2型（CFG）和3型（正则文法）：

实际上，词法分析器通常基于有限自动机实现，对应的就是正则文法；而语法分析器处理的是CFG。

说到推导方式，“最左推导”对应自顶向下分析（LL系列），“最右推导”则是自底向上（LR系列）的基础。别小看这点区别，它直接决定了你后续构建分析表时的状态转移策略。

至于句型和句子的区别——前者可以含非终结符，后者全是终结符。考试常考选择题让你判断某个串是否为句型或句子。

还有一个容易混淆的概念集合：短语、直接短语、句柄、素短语。

• 短语：某棵子树的所有叶子拼起来的串。
• 直接短语：该子树高度为2，即由一条产生式一步生成。
• 句柄：最左边的那个直接短语，规约的关键依据。
• 素短语：含有终结符且其真子串都不是短语的短语，用于算符优先分析中的规约单位。

画语法树的时候一定要标清楚这些位置，尤其是求“句柄”几乎每年都会出现在填空或选择里。

词法分析：状态机的艺术

词法分析的任务是从字符流中切出一个个有意义的 token，比如if、变量名、常数、运算符等。常见类别如下：

核心工具是状态转换图（Transition Diagram），本质上是一个有向图：

• 圆圈表示状态
• 边代表输入字符触发的转移
• 双圈是接受状态，意味着成功识别一个token

实际编码时，常用 switch-case 模拟状态机流转。例如识别整数的过程：

state = 0; while ((ch = getchar()) != EOF) { switch(state) { case 0: if (isdigit(ch)) state = 1; break; case 1: if (isdigit(ch)) continue; else accept(NUMBER); break; } }

虽然现代项目多用 Lex 自动生成词法器，但手动设计有助于理解 DFA 构造过程，对后续学习 NFA→DFA 转换也有帮助。

语法分析：重中之重，贯穿始终

这部分占分比极高，必须熟练掌握 LL(1) 和 SLR(1) 的完整流程。

自顶向下：LL(1) 分析的关键门槛

LL(1) 要求无回溯，这就带来了三个硬性条件：

1. 不能有左递归
2. 不能有公共左因子
3. SELECT集互不相交

左递归消除技巧

遇到直接左递归：

A → Aα | β

改写为：

A → βA' A' → αA' | ε

间接左递归需要先代入转化。例如：

A → Ba B → Ab

将第二式代入第一式得 A → Aba，再按直接左递归处理即可。

注意顺序：先提取公共左因子，再消左递归。否则可能引入新的左递归。

FIRST/FOLLOW 集计算实战

以经典表达式文法为例：

E → T E' E' → + T E' | ε T → F T' T' → * F T' | ε F → ( E ) | id

逐层计算：

• FIRST(F) = { ‘(‘, id }
• FIRST(T’) = { ‘*’, ε } ⇒ 因为可空，继续看后继
• FIRST(T) = FIRST(F) = { ‘(‘, id }
• FIRST(E’) = { ‘+’, ε }
• FIRST(E) = FIRST(T) = { ‘(‘, id }

FOLLOW 集合依赖传递：

• FOLLOW(E) = { #, ‘)’ } （开始符号加 #，右括号来自 F → (E)）
• FOLLOW(E’) = FOLLOW(E)
• FOLLOW(T) = { ‘+’, ‘#’, ‘)’ } （来自 E’ → + T E’ 和 E → T E’ 且 E’ 可空）
• FOLLOW(T’) = FOLLOW(T)
• FOLLOW(F) = { ‘*’, ‘+’, ‘#’, ‘)’ } （来自 T → F T’ 和 T → F）

计算时建议列表迭代，直到各集合不再变化为止。

有了这两个集合，就能构造 SELECT 集：

对于 A → α：
- 若 ε ∉ FIRST(α)，SELECT = FIRST(α)
- 否则 SELECT = (FIRST(α){ε}) ∪ FOLLOW(A)

最终判断是否为 LL(1)：同一非终结符的所有产生式 SELECT 集必须两两不交。

预测分析表 M[A,a] 的填写规则也很明确：

• 对每个产生式 A → α，将其 SELECT 中所有终结符 a 对应的位置填上该产生式
• 初始栈为 #S，输入串末尾加 #

一旦出现冲突（同一个格子有两个动作），就不是 LL(1) 文法。

自底向上：SLR(1) 是考试主力

LR 系列的核心思想是“移进-规约”，通过 DFA 控制状态转移。相比 LR(0)，SLR(1) 利用 FOLLOW 集缓解冲突，更适合教学和考试。

构造流程详解

1. 拓广文法：引入新开始符 S’ → S
2. 构造项目集闭包（CLOSURE）
3. 使用 goto 函数生成项目集族
4. 构建 DFA
5. 填写 ACTION 和 GOTO 表

项目形如 A → α•β，• 表示当前扫描位置：

• • 在左端：等待移进
• • 在右端：可规约

闭包操作 CLOSURE(I) 的关键是：若 A → α•Bβ ∈ I，则把所有 B → •γ 加入。

goto(I, X) 是从状态 I 经过符号 X 能到达的新状态，需再次取闭包。

当某个项目集包含规约项（如 A → α•）时，检查 FOLLOW(A) 来决定哪些输入符号可以触发规约。

实践经验：如果同时存在移进和规约动作，通常允许移进（避免过早规约破坏结构）。只有当 FOLLOW 冲突才判定为文法不满足 SLR(1)。

算符优先分析：专攻表达式

对于像E → E + T | T这样的表达式文法，可以采用算符优先法，忽略非终结符，只关注终结符间的优先关系。

关键步骤：

1. 构造 FIRSTVT(B)：B 推导出的第一个终结符
   - 若 B → a… 或 B → Ca…，则 a ∈ FIRSTVT(B)
   - 若 B → C…，则 FIRSTVT(C) ⊆ FIRSTVT(B)

2. 构造 LASTVT(B)：最后一个终结符，方法类似但反向

3. 建立优先关系表：

然后利用该表查找“最左素短语”进行规约。注意这不是规范规约，但效率高，适合表达式解析。

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

每条产生式绑定一段语义动作，这就是语法制导翻译的思想。

例如：

E → E1 + T { E.val = E1.val + T.val }

属性分为两类：

• 综合属性：子节点传给父节点（bottom-up），适合表达式求值
• 继承属性：父节点传给子节点（top-down），用于类型检查、作用域传递

最常见的中间表示是四元式，格式为(op, arg1, arg2, result)。

常见模式：

临时变量用 t1, t2…命名，标签用 L1, L2…管理跳转逻辑。

比如这段条件语句：

if (a > b) x = y + z; else x = y - z;

对应的四元式应为：

(>, a, b, L1) (j, _, _, L2) L1: (+, y, z, t1) (=, t1, _, x) (j, _, _, L3) L2: (-, y, z, t2) (=, t2, _, x) L3: ...

注意两个分支都要跳过对方，最后汇合到 L3。

中间代码优化：提升性能的手段

优化分局部和全局两种。

局部优化（基本块内）

• 常量合并：3 + 4 → 7
• 公共子表达式消除：t1 = a + b; t2 = a + b → 复用 t1
• 删除无用赋值：x = 10; 后面没用 → 删除
• 强度削弱：x * 2 → x << 1

这类优化可以直接在线性四元式序列上完成。

全局优化（跨基本块）

主要是循环优化：

• 代码外提：把循环不变量提到外面
• 归纳变量消除：i*4 → base + offset 形式
• 循环展开：复制多次体减少跳转开销（空间换时间）

虽然考试侧重局部优化，但了解整体框架有助于理解现代编译器的工作机制。

目标代码生成与运行时环境

函数调用离不开活动记录（Activation Record），也就是栈帧，典型的布局包括：

• 临时变量区
• 局部变量
• 参数存储
• 返回地址
• 动态链（指向调用者的栈底）
• 静态链（指向静态外层，用于嵌套作用域）
• 现场保护信息（寄存器值等）

不同语言采用不同的存储分配策略：

参数传递方式也常考对比：

举个例子：f(i, A[i])，若 i 在函数中被修改，名传递会导致 A[i] 的索引动态变化。

真题实战精讲

【题1】FIRST/FOLLOW 集计算（重现率极高）

文法：

E → T E' E' → + T E' | ε T → F T' T' → * F T' | ε F → ( E ) | id

前面已详细计算过，这里强调几个易错点：

• FOLLOW(T’) = FOLLOW(T)，因为它出现在 T → F T’ 的末尾
• FOLLOW(F) 包含 ‘‘，因为 T’ → * F T’，所以 ‘’ ∈ FIRSTVT(T’)，进而影响 FOLLOW(F)
• FOLLOW(E’) = FOLLOW(E)，因 E → T E’ 且 E’ 可空

务必多轮迭代，确保稳定后再停止。

【题2】SLR(1) 分析表构造（必动手）

拓广后得到 S’ → E。

从初始项目 [S’ → •E] 开始，逐步扩展闭包，生成所有项目集。

每个状态若有规约项 A → α•，则对所有 a ∈ FOLLOW(A)，设 ACTION[i,a] = “r<编号>”。

如果有移进项（• 后跟终结符），则对应 ACTION[i,a] = “s “。

若同一格既有 s 又有 r，且不在 FOLLOW 内，则冲突；否则一般保留移进（合法路径）。

建议对照 PPT 第80页左右的例题反复练习。

【题3】四元式生成（逻辑清晰为王）

条件语句的关键在于跳转标签的组织：

if (a > b) x = y + z; else x = y - z;

分解逻辑：

1. 判断 a > b，成立跳转到 then 分支（L1）
2. 不成立则执行 else 分支（L2）
3. then 分支结束后跳过 else
4. 最终汇合到 L3

因此四元式序列为：

(>, a, b, L1) (j, _, _, L2) L1: (+, y, z, t1) (=, t1, _, x) (j, _, _, L3) L2: (-, y, z, t2) (=, t2, _, x) L3: ...

注意不要遗漏中间的无条件跳转，否则控制流会串行执行两个分支。

必会技能清单（自测用）

最后提醒：高效备考策略

• 别死记公式，要搞懂背后的动机。比如为什么 FOLLOW 能解决 SLR 冲突？因为它提供了“何时结束”的上下文信息。
• 多动手画图：语法树、DFA 状态图、分析栈演变过程，图像记忆远胜文字。
• 刷历年真题，题型重复率很高，尤其 FIRST/FOLLOW、SLR 表、四元式几乎是年年必考。
• 聚焦重点章节：第七章（语法分析）、第八章（语法制导翻译）合计占比超60%，优先投入时间。

资源推荐：

• B站搜索：“北航 冯耀东 编译原理” → 讲解通俗，配合动画演示
• 《编译原理》清华第二版（龙书简化版）→ 习题经典，适合打基础
• GitHub 搜mini-compiler→ 找个小项目动手实践，加深理解

注：本文内容基于个人笔记、授课PPT及公开资料整理，可能存在疏漏，仅供参考。一切以教材和教师讲授为准。

祝学弟学妹们顺利通过，少走我踩过的坑！