编译原理—期末笔记

status

Published

type

Post

date

Jan 9, 2025

slug

compiler-final

summary

详细介绍了编译原理的基础知识，包括南大计科编译原理一学期的教学内容，以及部分软院编译原理的内容。

英文缩写

题型：给英文缩写，要求写出全称 + 意思

RE: Regular Expression，正则表达式。一种描述词素模式的表示方法。

NFA: Nondeterministic Finite Automaton，非确定性有限自动机。等价于状态转换图。NFA 允许非确定性和转移。（NFA 由一个有穷状态集合 S，一个输入符号集合，和转换函数组成。S 中的一个状态被指定为开始状态，S 的一个子集被指定为接受状态。）

DFA: Deterministic Finite Automaton，确定性有限自动机。DFA 的状态转移规则都是明确的。

CFG: Context Free Grammar，上下文无关文法。上下文无关指的是非终结符的推导和其前后串无关。由一个开始符号，终结符号，非终结符号和一组产生式构成。

AST: Abstract Syntax Tree，抽象语法树。每个结点代表一个语法结构；对应于一个运算符。结点的每个子结点代表其子结构；对应于运算分量。

DAG: Directed Acyclic Graph，有向无环图。指的是一个没有环的、有限的有向图。

SSA: Static Single Assignment，静态单赋值。SSA 中的所有赋值都是针对不同名的变量。每个变量在生命周期内只被赋值一次，每次赋值都会创建一个新变量。

SDD: Syntax Directed Definition，语法制导的定义，是对上下文无关文法的推广。将文法符号和一个语义属性集合关联，产生式和一组语义规则相关联。

SDT: Syntax Directed Translation，语法制导的翻译，是在产生式体中嵌入程序片断（语义动作）的上下文无关文法。

词法分析

题型：

根据描述写出正则表达式

画出状态转换图 NFA

NFA -> DFA

DFA 状态最小化

考试注意

自动机开始状态要用箭头 + start 指出，接受状态画两个圈。

状态转换图和 DFA 要给状态标号。

例：( | b)*ab)* 完成后三步

正则 -> NFA，按照 Thompson 构造法的三种模式。

或操作（新建两个状态）：

连接操作（直接并在一起）：

闭包（新建两个状态，两个 epsilon 转移）：

NFA 的转换函数：用语言描述为 “状态 0 接受 a 转换到状态 0, 1”，(0, a) -> {0, 1}

NFA -> DFA：子集构造法。一开始 DFA 的 states 中只有一个 closure(s0)，对 states 中的每一个状态，都求出对每一个输入字符 c 的 closure(move(T, c))，如果在此过程中产生了新的状态，则加入 states。最后所有的状态经过每个字符都能到达 states 中一个确定的状态。

DFA 最小化。

算法：从原理上讲，先将状态集合分为两个：结束状态和其他状态，然后再假设某两个状态相同，看有没有一个输入可以区分它们。如果在所有输入下这些状态要么回到自身的集合，要么到达相同的集合，那么它们等价。

对最小化的 DFA 来说，开始状态即为有开始状态的那个组，结束状态即为有结束状态的那个组。

做题时直接瞪眼看出哪两个状态是等价的，然后再试图证明。

例题：由字符 ‘a’, ‘b’ 组成的，不含连续两个 ‘a’ 的字符串。

语法分析

消除左递归

消除立即左递归

公式：重要！！不要忘记 A’ 这个一撇和 epsilon ！！

推广：

消除多步左递归

判断方法：给非终结符号排序。原理上可以任意排序，实际操作时一般按照从开始符号推导的顺序排序，这样在下一步时只需要看靠右的能否推导出靠左的即可。考试时最多迭代两次。

消除方法：替换并消除。注意！！替换时要全部替换！无论产生式有没有产生左递归，都要替换。

例子：

提取左公因子

找出可选项中的最长公共前缀。注意！！如果有一个产生式就是那个公因子，则不能遗忘 epsilon ！！！

预测分析

FIRST() 集合：可以从推导得到的串的首符号的集合。方法：不断展开直到开头为终结符。计算方法：

FOLLOW(A) 集合：可能在某些句型中紧跟在 A 后面的终结符号。计算方法：

注意：FIRST 和 FOLLOW 集合均为终结符号！两个例外：若可推导出 epsilon，则 epsilon 在 FIRST() 中；FOLLOW(开始符号) 含有 $，如果 A 是某些句型的最右符号，那么 $ 在 FOLLOW(A) 中。

要点：先写 FIRST 再写 FOLLOW，由 FIRST 推 FOLLOW。

预测分析表

构造方法：如果 t 在 FIRST(A) 中或者且 t 在 FOLLOW(A) 中，则在 table[A][t] 中填入

出错的格子留空即可（或者填 Error，但是要填就都要填上，不如留空）

LL(1) 文法：预测表中每个条目都唯一地指定了一个产生式，或者标明 Error。

非 LL(1) 文法或二义性文法：一个条目中有多个产生式。

重写非 LL1 文法使其变为 LL1：不断进行提取左公因子和消除左递归的过程。

句柄是最右推导的反向过程中被规约的部分。

在移入 / 归约分析框架中，句柄始终出现在栈顶。

移入 / 归约冲突：栈中的内容和接下来的k个输入符号，都不能确定进行移入还是归约操作（不能确定是否是句柄）。

归约 / 归约冲突：存在多个可能的归约到不同非终结符号的归约（不能确定句柄归约到哪个非终结符号）。

规范 LR(0) 项集族的构造

增广文法：G 的增广文法 G’ 是在 G 中增加新开始符号 S’，并加入产生式 S’->S 而得到的

子函数：CLOSURE(I)：I 的项集闭包（对应 DFA 化算法的 closure）。GOTO(I,X)：I 的 X 后继（对应 DFA 化算法的 MOVE(I,X)）。

内核项：初始项 S’ -> ·S 以及所有点不在最左边的项。

非内核项：除了 S’ -> ·S 所有点在最左边的项。

例：根据以下产生式，给出 LR(0) 项集规范族。

灰色部分（非内核项，CLOSURE）的构造：

注：非内核项的点在最左边。

SLR 语法分析表的构造

ACTION 全是终结符号。s5 表示移入状态 5，r5 表示利用第 5 条产生式归约。GOTO 全是非终结符号，1 表示去到第 1 个状态。

构造方法：

即：点右边有东西就填入 sX。点右边没东西就在 FOLLOW(A) 填入 rX，如果 A 是增广文法的 S’，则填入 acc。

例题：

语法制导的翻译

注释语法分析树

综合属性：分析树上非终结符号的属性值由子节点及本身的属性值来定义。

继承属性：依赖于父节点、本身和兄弟节点（一般是左侧）的属性值。

终结符号都是综合属性，从词法分析获得。

S 属性的 SDD：只含综合属性。

L 属性的 SDD：既有综合属性，又有继承属性。

注释语法分析树：包含各个节点的各属性值（全部属性值）的语法分析树。

依赖图：描述了某棵特定的分析树上各个属性实例之间的信息流（计算顺序）。

例子：给出如下的产生式和语义规则，画出 3*5+4 的依赖图（表示结束）。

注：上图中把箭头去掉便是注释语法分析树。依赖图更多在既有综合属性又有继承属性的注释语法分析树中用到，例如：

设计 SDT

题型：给定一个含左递归的产生式，化为自顶向下可以分析的 SDD（提取左公因子，消除左递归），画出依赖图。

注意：记得用数字下标来区别一个产生式中相同的终结符！！第一个产生式（增广）可以没有。

后缀 SDT 的栈的实现

题型：基于栈写出对应 S 属性的 SDD 的动作，注意 top 减去的值。

E -> E1 + T 中的 top - 2 是因为运算符在栈中，= 左边的 top-2 对应 E（归约后），= 右边的 top-2 对应 E1。F -> ( E ) 的 top - 2 是因为被归约后 F 在 ‘(’ 的位置，就是 top-2。

SDD -> SDT

题型：给一段语言描述，将动作嵌入 SDD 中。或给出一个 L 属性的 SDD，转换为 SDT。

做法：

判断 SDD 中各属性是综合属性还是继承属性（即判断是S属性还是L属性）。

然后画流程图（这一步是关键，这步做对了后面不容易错）。

综合属性 -> 最右边, 继承属性 -> 紧挨着非终结符号的左边。

S.next = B 不能出现，左边是标签右边是非终结符不能赋值，解决办法：S.next = newlabel()，… || label(S.next) || B || …

注意：语义规则即 SDD 不需要写出动作嵌入的位置，而 SDT 需要写出动作嵌入的位置。

判断是否可以 在LL或LR分析过程中实现 ？

如果一个 L 属性的 SDD 的基本文法可以使用 LL 分析技术，那么它的 SDT 可以在 LL 或者 LR 语法分析过程中实现；

递归下降方法实现 L 属性的 SDD：

方法：先声明需要用到的变量，然后按照 SDT 的顺序书写代码即可。记得最后要 return 回放在式子最右端的 S.code

中间代码生成

有向无环图

题型：用 DAG 表示一个中缀表达式

注意：除了复用表达式之外，原子节点（例如这里的 ‘a’）也需要复用。

基本块的 DAG

题型：给出一段含数组的代码，要求画出数组引用的 DAG。

方法：图中只画 = 右边的式子，根节点为操作符，= 左边的左值写在根节点旁边。[]= 操作符有3个操作数，因为它的左值没法用一个变量表示，这三个操作数从左往右分别是：数组，下标，右值。

注意

对数组 a 的元素赋值，杀死所有依赖于 a 的变量。

如果出现对同一个元素的多次赋值，需要用下标区分！

对指针赋值，杀死前面所有的变量。

注意：如果特意强调“XX 变量在基本块出口处活跃”，那么说明考察知识点为重组基本块，原则是：尽量将公共子表达式的结果赋值给活跃的变量。可以删除赋值。

三元式

题型：给出一个表达式，填三元式的表。

易忘点：用编号引用一个式子的结果。

回填

记住：M 在 S 的前面。时将 M.instr 设置为下一条指令的地址。

回填：truelist 和 falselist 中记录的是需要填写的指令地址，backpatch 函数是将该 list 中的所有指令填上 M.instr。

SSA

注意：三地址码转换为 SSA 不仅要加下标，而且记得在标签处（即控制流合并处）添加函数。

运行时环境

活动记录

题型：给出一段函数，求运行到某条代码时的堆、栈，要求标明变量名和值。

活动记录的内容：实参，返回值，控制链，访问链，保存的机器状态，局部数据，临时变量。（7 个）

坑点：如果函数中有一句 static int x = 0; 那么变量 x 在静态数据区中，和 m 在一起。（静态数据区存放静态变量和全局变量）

引用计数和垃圾回收

题型：引用计数，画图。注意：leak 的变量不能删除，只删除指向的边即可。

标记-清扫式垃圾回收

标记：从根集开始，跟踪并标记出所有可达对象。

清扫：遍历整个堆区，释放不可达对象。

代码生成

基本块和流图（必考）

题型：三地址 -> 基本块 -> 流程图（Entry and Exit 节点）

基本块划分的方法：

寻找首指令：第一条指令；跳转指令的目标指令；跳转指令的下一条指令

划分基本块：[第一条首指令，下一条首指令)

写出入口 Entry 和出口 Exit！！

例题：

注意：这个流图不完整，需要加上入口 Entry 和出口 Exit。

寻找一个 block 中的一个程序点，哪些变量是活跃的（从后往前看）。如果有 *q = y，此后活跃变量为空集（肯定能知道 q 指向哪里除外）。

寄存器分配

题型：三地址码 -> 机器码 + 寄存器描述符和地址描述符

不用特意记忆机器码格式。考试时会给出。

概念

寄存器描述符：各个寄存器都存放了哪些变量的当前值。

地址描述符：某个变量的当前值存放在哪个或哪些位置（包括内存位置和寄存器）上。（同时在寄存器和内存中都要写！）

更新描述符的算法

LD R, x

R 的寄存器描述符：只含 x
x 的地址描述符：添加 R
从其他不同与 x 变量的地址描述符中删除 R

ST x, R

x 的地址描述符：添加内存

ADD Rx, Ry, Rz

Rx 的寄存器描述符：只含 x
x 的地址描述符：只含 Rx
从其他不同与 x 变量的地址描述符中删除 R

x = y

若生成 LD Ry, y，按照第一种情况处理
Ry 的寄存器描述符：添加 x
x 的地址描述符：只含 Ry

例题：

注意：a=d 这个赋值不要忘记在 R2 中添加 a。

STORE 指令存活跃变量时，只需要存全局变量（临时变量不用存）。看哪个全局变量的地址描述符只有寄存器，对其使用 ST 指令。地址描述符有内存的不需要存。

机器无关的优化

数据流分析（必考）

概述：

到达定值分析和可用表达式都是前向，活跃变量分析是后向。

前向分析的特点是 IN = 所有前驱的 OUT，后向分析的特点是 OUT = 所有后继的 IN（即算出来了就用）。

到达定值分析和活跃变量分析交汇运算都是并，可用表达式是交。

它们的传递函数都是：当前 - def/kill 再并上 use。

迭代次数不能超过基本块数量（一般是 2~3 次）

到达定值（最可能考）

gen 和 kill 的例子：

算法：gen 就是该基本块内对变量的定值，一般不会超过一次，直接无脑填上就可以。kill 是其他基本块对该变量的赋值。

例题：计算上图的到达定值。

考试时不会给出 gen 和 kill，需要自己计算。

活跃变量分析（很可能考）

use：在 B 中引用，但是引用前没有被定值。

def：在 B 中定值，但是定值前没有被引用。

因为该分析是倒序，考试时看清楚表格给的顺序。

例题：给出上图的 use def in out

可用表达式（不太可能考）

e_gen：基本块求值了 x+y，并且之后没有对 x 或 y 进行赋值，那么它生成了 x+y。

e_kill：基本块对 x 或 y 进行赋值，并且之后没有对 x+y 进行求值，那么它杀死了 x+y。

自然循环

题型：给定一个流图，寻找其中的循环。

支配：如果每一条从入口结点到达 n 的路径都经过 d，我们就说 d 支配 (dominate) n，记为d dom n。每个节点都支配自己。

直接支配节点：从入口结点到达 n 的任何路径（不含n）中，它是路径中最后一个支配 n 的结点。

流图边的分类

前进边：从结点 m 到达 m 在 DFS 树中的一个真后代的边。DFS 中的所有边都是前进边。

后退边：从 m 到达 m 在 DFS 树中的某个祖先的边。

交叉边：src 不是 dst 的祖先，dst 不是 src 的祖先。（即既不是前进边，也不是后退边）

回边：边 a->b，b dom a。所有的回边都是后退边，但后退边不全是回边（换句话说对于边 a->b，b 是 a 的祖先，但 b 不一定支配 a）。

可归约性：如果所有的后退边都是回边，则流图是可归约的。（实践中出现的流图基本都是可归约的）

流图的深度：各条无环路径上后退边数中的最大值。

自然循环（重要！！）：给定边 n->d 的自然循环指的是 d 加上不经过 d 就能到达 n 的节点集合。d 称为循环头。

根据上图，找出所有的自然循环。

回边 7->4: {4, 5, 6, 7, 8, 10}

回边 10->7: {7, 8, 10}

回边 8->3, 4->3: {3, 4, 5, 6, 7, 8, 10}

回边 9->1: 整个流图

LLVM IR

考试前看一眼。

芝士点

语法分析树：从非终结符号开始，直到推导出终结符号为止，没有其他信息。例子如下：

任何正则语言都有一个唯一的（不计同构）状态数目最少的 DFA。

不可达代码：理论上不会执行的代码。死代码：执行了不会产生效果的代码。

支配节点：D(n) 是支配 n 的节点，不是 n 支配的节点。

课后题 / 往年卷

最左推导和最右推导：

最右句型的句柄

最右句型指的是每次展开最右侧的非终结符，因此最右句型的句柄需要从左往右寻找第一个可以被归约的式子（因为最后一个被归约的一定是最左边的）。

通过继承属性向下传递，通过综合属性向上传递

注释语法分析树的简单例子

用继承属性解决左递归

构造 DAG 一定要尽可能利用节点！举一个例子：

四元式、三元式、间接三元式

三元式和间接三元式的区别是间接三元式有一个指向三元式的列表，这样一来，三元式中重复的部分就可以去掉。

易错点：

a = b + c 这种，需要先 + b c t1 然后 = t1 _ a

四元式中有 =[]，没有 []=。三元式只有 []。因为三元式只能有两个操作数。对数组元素的赋值，都需要先求 [] 出地址再进行赋值。

使用下图所示的方案翻译XXX，步骤：先构造三地址码，然后画出注释语法分析树，属性就按照方案中的来。

这道题记得减去一开始的偏移量 1 0 5

显示表：指针 d[i] 指向栈中最高的、嵌套深度为 i 的活动记录。

除主程序外，其余的表项在开头要写上调用的函数及实参值，第二行写 保存的d[i]，第三行留空（表示还有其余内容）。

基本块的 DAG：标好下标！！

对归纳变量进行强度削减，可以将乘法换为加法。并将循环不变表达式外提。

计算支配关系，是 D(B)，表示支配 B 的节点！！！！

🐉编译原理—期末笔记