编译器流程

前端理解程序，后端生成机器码

ppt里面的流程长这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

源代码

↓ 词法分析

Token流

↓ 语法分析

AST语法树

↓ 语义分析

合法AST

↓ IR生成

中间代码

↓ 优化

优化后的IR

↓ 代码生成

汇编

↓ 汇编器

.o

↓ 链接器

ELF

详细流程

1+2+3

源语言只支持：

1
2

整数 n
加法 e1 + e2

目标机器是一台栈式计算机，只支持：

1
2

push n
add

现在来编译1+2+3

先词法分析，把字符拆成token然后识别这是什么词

然后构造语法树

    +
  
   / \
  
  +   3
  
 / \
  
1   2

(1 + 2) + 3

然后后序遍历

push 1

push 2

add

push 3

add

如果开了代码优化就直接是6

note1

从源代码到最后的二进制文件中间要经历这样一个过程

front end ->IR ->back end

前端包含词法分析，语法分析，语义分析

词法分析把字符流拆成token并标上记号

语法分析把token组织成语法树，语法正确不代表程序合理

语义分析

主要检查：

• 变量是否声明
• 类型是否匹配
• 函数参数数量是否正确
• 返回值类型是否正确
• 标识符的作用域
• 是否重复定义
• break 是否位于循环中
• 常量是否被修改

语义分析时通常会建立符号表记录变量函数等信息

前端合法后会生成中间表示（IR）

IR位于源码和最终文件之间

后端一般包括：

• 代码优化
• 指令选择
• 寄存器分配
• 指令调度
• 目标代码生成

词法分析

词法分析器把字符流转化成记号流（token流）

词法分析基础和手工构造实现

词法分析切成的token包含类型和原始文本（lexeme）,实际是否包含lexeme得看类型

还有枚举类型

词法分析手工构造实现

词法分析器可以通过手工构造或词法分析生成器实现，用生成器不好控制细节,手工构造的分析器通常效率更高

转移图

状态圆圈 当前识别进度

箭头上的字符 转移条件

双圆圈 成功识别 Token

星号 多读字符，需要回退

自环 可以重复读取某类字符

关系运算符转移图

伪c

标识符转移图

c语言中的表示符以字母或下划线开头，后面跟0个或多个字母，下划线或数字

标识符和关键字

词法分析上来看，关键字是标识符的一部分

关键字表算法

词法分析器会先按照标识符规则读一遍，然后准备一个关键字表（哈希表H），读取完整字符串后查询

H = {

"if"     → IF,
  
"else"   → ELSE,
  
"while"  → WHILE,
  
"return" → RETURN,
  
"int"    → INT

}

对所有的标识符和关键字，先统一按标识符的转移图进行识别。识别完成后，进一步查表H看是否是关键字

词法分析器自动生成

程序员只要写出声明式的规范，其余操作由Lex/Flex等工具完成，自动生成词法分析器

华老师表示一个几百行的声明式规范经由Lex/Flex后能生成2k左右的词法分析器。声明式的规范就是正则表达式，中间流程大致上是从正则表达式转化成自动机，从自动机转化成表驱动的算法

正则表达式

字符集根据具体的语言来定，如果是c则是ascll,java则是unicode,这里的字符集可以看成算数表达式中基本的数字

用正则表达式表示标识符

语法糖（Syntactic Sugar）

它完全不提供任何新的功能。 也就是脱了这层糖衣，用语言本身最基础的语法，依然能实现一模一样的逻辑。对于编译器来说，在生成机器码之前，都会进行“解糖”（Desugaring）操作，把语法糖还原成最基础的底层结构

c或java所提供的程序设计的语法都可以看作是语法糖，即在汇编层面上对赋值 跳转这两个运算的一种封装。

这些更高层的抽象可以让程序员构造程序更简单，也更容易被人类理解跟维护

有限状态自动机（FA）

自动生成法

能识别给的字符串就输出yes,不能就输出no

例1

可以看出字符表里面的元素为a,b

S是状态集，{0，1，2}

q0，起始状态规定只有一个单向箭头指向的边为起始状态，即0号状态

F是终结状态的集合，约定在一个状态上画上双圈就表示接受状态，有的自动机里会有多个接受状态

转移函数如图，对于一个字符串s=“abab”，根据转移函数做状态转移

例2

在q0上读取a时的转移函数指向的是一个状态集，可以向下走回到q0也可以向右走到q1,即两个元素构成的集合

在q0上读到b时指向确定的q1,在q1上读到b时可以回到q0，也可以自身循环

这种就是非确定有限状态自动机->NFA

在所有状态上对于给定的字符，它的状态转移都是对应的单元素的一个集合，如例1就是确定有限状态自动机->DFA

注意到，对于s=”a”,这个NFA既可以接受也可以不接受。但其实只要能走到一个接受状态那么就叫这个串可以被接受

NFA的判断开销比较大（需要回溯，遍历等运算），实际运用中在一些情况下我们可以把NFA转化成等价的DFA

小结

德尔塔是转移函数，S是状态集，西格玛是输入的字符集，里面的乘号表示笛卡尔积

DFA中，对于任意一个西格玛中的字符最多有一个状态可以转移（），其转移后状态属于S

NFA中的比较复杂，对于一个字符有多个状态可以转移。对于所有状态来说它的转移字符也发生了变化，除了西格玛还有一个空转，即从一个状态转移到另一个状态不需要消耗s中的任何一个字符。我们可以看到其值域是s的幂集，即所有子集构成的集合（2的n次方）

DFA的实现例子

我们可以把DFA看成一个带边和节点有向图，不过这里的边上跟节点上是有信息的

DFA跟NFA

正则表达式（re）到非确定有限状态自动机

正则表达式负责描述 Token，NFA 和 DFA 负责真正识别 Token，生成器再把 DFA 变成词法分析器代码

标识符：[A-Za-z_][A-Za-z0-9_]*

整数： [0-9]+

空白符：[ \t\n]+

关键字：if、while、int

只是在描述什么样的字符串属于哪一种token

这些规则就是声明式规范

re先通过thompson算法转化成非确定有限状态自动机，然后用子集构造法转化成确定的DFA，

之后通过hopcrotf算法生成词法分析器代码

DFA的代码表示有不同方式，看实际需要

RE->NFA thompson算法

thompson算法基于数学归纳法

首先对RE的结构归纳，基本的RE直接构造(base case)，复合的RE递归构造(inductive step)

递归算法基本上不超过100行c

基本的RE有两种

1.单个字符 (比如 a)

2.空字符 (ϵ, Epsilon)

ϵ 边在 NFA 里就相当于汇编里的 无条件跳转指令 (jmp)。不需要消耗任何输入字符，直接顺着指针跳到下一个状态

复合的RE有3种

拼接（正则表达式的连接），选择，闭包（AB,A|B,A*）

具体的thompson算法构造过程

注意到，对于正则e，前两个直接构造，后3个采用递归

前两种

把两个正则拼在一起

e1或e2

e1*表示0个或任意多个e1连在一起

从NFA到DFA

NFA写算法要用到回溯等运算，但DFA就不用考虑了

子集构造算法

DFA 中的每个状态，都是 NFA 状态集合的一个子集

假设 NFA 当前可能位于：

1

{n1, n3, n5}

那么在 DFA 中，不再分别记录三个状态，而是把整个集合起名为：

1

q0 = {n1, n3, n5}

以后 DFA 只需要记录：

1

当前状态是 q0

这样就把 NFA 的“多个可能状态”压成了 DFA 的“一个确定状态”

ε-closure：ε 闭包

ε-closure(T) 表示：

从状态集合 T出发，只沿着零条或多条 ε 边，能够到达的所有状态

例如：

1
2
3

n0 --ε--> n1 --ε--> n2
              \
               --ε--> n3

那么：

1

ε-closure({n0}) = {n0, n1, n2, n3}

ε 闭包可用深度优先或广度优先计算

move：字符转移

move⁡(T,c)表示：

从集合 T中的任意状态出发，读取字符 c后能到达哪些状态。

例如：

1
2
3

n0 --a--> n2
n1 --a--> n3
n1 --b--> n4

则：

1
2

move({n0, n1}, a) = {n2, n3}
move({n0, n1}, b) = {n4}

move 只走标有真实字符的边，不走 ε 边

假设 DFA 当前状态对应 NFA 状态集合 T，读取字符 c 后的新状态为：

U=ε-closure(move⁡(T,c))

也就是：

1
2
3
4
5
6
7

当前状态集合 T
      ↓ 读取字符 c
move(T, c)
      ↓ 再沿所有 ε 边扩展
ε-closure(move(T, c))
      ↓
新的 DFA 状态 U

这里要用到一个工作表，worklist,worklist在实际实现的时候可以用队列

维护两个集合：

1
2

Q         已发现的所有 DFA 状态
workList  已发现但还没有计算转移的状态

初始化：

1
2

Q = {D0}
workList = [D0]

从工作表取出一个集合 T，对字母表中的每个字符 c 计算：

1

U = ε-closure(move(T, c))

然后建立 DFA 转移：

1

T --c--> U

如果 U 是第一次出现：

1
2

把 U 加入 Q
把 U 加入 workList

直到工作表为空

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

D0 = epsilonClosure({nfaStart});

dfaStates = {D0};
workList = {D0};

while (workList 非空) {
    T = 从 workList 中取出一个状态集合;

    for (字母表中的每个字符 c) {
        U = epsilonClosure(move(T, c));

        添加 DFA 转移 T --c--> U;

        if (U 尚未出现在 dfaStates 中) {
            把 U 加入 dfaStates;
            把 U 加入 workList;
        }
    }
}

DFA的接受状态判断

假设 NFA 的接受状态是：

1

n9

某个 DFA 状态为：

1

D1 = {n1, n2, n6, n8, n9}

因为集合中包含 NFA 接受状态 n9，所以 D1 就是 DFA 接受状态

DFA 状态集合中只要包含至少一个 NFA 接受状态，它就是接受状态

例子

算法为什么能够运行终止

假设 NFA 有 N个状态。

DFA 中的每个状态都是 NFA 状态集合的一个子集。

一个含有 N 个元素的集合最多有2的n次方个不同子集。

例如三个 NFA 状态：

1

{n0, n1, n2}

所有子集是：

1
2
3
4
5
6
7
8

∅
{n0}
{n1}
{n2}
{n0,n1}
{n0,n2}
{n1,n2}
{n0,n1,n2}

一共：

2的3次方=8

所以最坏情况下 DFA 可能有 2的n次方个状态。

但实际运用中很多子集根本不可达

ε闭包的实现-深度优先

选择一条路径一直向下走，走不动以后再返回，继续搜索其他路径

1
2
3
4
5
6
7
8
9
10
11
12

void epsilonClosure(int state)
{
    if (visited[state])
        return;

    visited[state] = true;
    addToClosure(state);

    for (每条 state --ε--> next) {
        epsilonClosure(next);
    }
}

对于一个集合，要从集合中的每个状态开始 DFS：

1
2
3

for (state 属于 states) {
    epsilonClosure(state);
}

ε闭包的实现-广度优先

基于队列概念，先搜索距离起点最近的所有状态，再搜索下一层状态

1
2
3
4
5
6
7
8
9
10
11
12
13

closure = 初始状态集合;
queue = 初始状态集合;

while (queue 非空) {
    state = dequeue(queue);

    for (每条 state --ε--> next) {
        if (next 不在 closure 中) {
            把 next 加入 closure;
            enqueue(queue, next);
        }
    }
}

DFS 和 BFS 的结果相同，只是遍历顺序不同

DFA最小化

子集构造把 NFA 转换成 DFA 后，得到的 DFA 往往存在一些“重复状态”。

DFA 最小化的目标是：

合并行为完全相同的状态，在不改变可识别语言的前提下，让状态数量最少

即先按接受与非接受状态划分，再不断用输入字符拆分集合，直到集合不再变化

我们用子集构造算法将NFA转化成DFA，可以看出q1,q2,q3为接受状态

注意到有一些状态可以相互合并

q1跟q4也可以合并

Hopcroft算法

等价类

假设 DFA 中有状态 p 和 q。

如果从它们出发，输入任意后续字符串，最终的接受或拒绝结果都一样，那么 p 和 q 等价

为什么先以接受，非接受状态做区分

假设：

1
2

p 是接受状态
q 是非接受状态

即使不再读取任何字符，二者结果已经不同：

1
2

从 p 出发，空串 ε 被接受
从 q 出发，空串 ε 被拒绝

所以接受状态和非接受状态一定不等价。

因此最初先分成两组：

1
2
3
4

P₀ = {
    F,       // 接受状态
    Q - F    // 非接受状态
}

如何拆分集合

假设一个分组中有：

1

S = {p, q}

读取字符 a：

1
2

p --a--> 接受状态组
q --a--> 非接受状态组

那么 p 和 q 的未来行为不同，不能留在同一组。

要拆成：

1
2

{p}
{q}

所以判断一个组能否拆分的原则是：

同一个组中的状态，读取同一个字符后，是否进入不同的分组

例1

先划分

注意到，无论是b或c，都无法区分开q1,q2,q3的不同性，状态转移后始终在A等价类中

故，q1,q2,q3可以被合并成q4

例2

注意到RE为fee|fie,也可以写成f(ee|ie)

先切分

N为非接受，A为接受

注意到A不接受字符，该集合不可分裂

看N时发现，当循环到e时，q2,q4都转化到集合A，所以e可以划分N

注意到集合S都能接受e，且转化都到了A，不可再划分

集合D中，循环到e时进入S集合，故可以划分成q0,q1

DFA的代码表示

转移表

行为字符，列为状态编码

对于a(b|c),可以编码成23的矩阵，M行，N列（ASCII为256）

其它表象为error项

可以看出这张表为上面DFA等价的表示

一个词法分析器还需要驱动代码

驱动代码负责读输入，然后根据这个表里的内容来回答给定的输入是否能被接受

驱动代码

有两个核心变量，state,stack

state为目前走到的状态

该算法由两个循环组成

第一个循环是当state不为error时读入一个输入，然后判断state是不是accept,我们知道有一些状态是接受状态，

如果是接受状态就清空stack,把这个state push到stack中，然后在这个table中查字符c可以转化state到什么地方去。这是第一个循环

第二个循环是当state不为accept时把stack上的值赋值给state并用rollback()指针回滚，返回上一个读到的字符

最长匹配

这里就是stack这个结构的作用了，当一个程序设计语言里有这两个关键字时（if，ifif），一个关键字是另一个关键字的前缀，一般规定是尽可能识别第二个

这里是ifif,ifii两个例子，其中ifii两次rollback

跳转表

nextToken函数中的goto是跳转函数

这里是对q0和q1分别写了判断逻辑，每段代码负责当前状态识别

跳转表的好处是不用维护这么大的数组，unicode的数组可能有6万多列，几百甚至几千个状态，开销过大

flex就是用了跳转表的实现方式

语法分析

先回忆一下编译器的前端

词法分析器接收源程序后输出记号流，记号流是编译器中的内部数据结构，记号流随后输送给语法分析器

语法分析器的任务

输入记号流和语言的语法规则后输出语法树，根据语法规则判断程序合法性

例1

语法错误处理

分析后会给出错误提示

例2

当编译通过时进行语法树构建

路线图

语法分析阶段内容

上下文无关文法（CFG）

历史背景：乔姆斯基文法体系

从3到0型文法，相互嵌套

词法分析用正则表达式描述token，但re不适合描述多层嵌套

例如：

1
2
3
4
5
6

((1 + 2) * 3)
if (...) {
    while (...) {
        ...
    }
}

于是语法分析使用上下文无关文法context-free grammer

符号可以对应为：

1
2
3
4
5
6

s：羊 sheep
t：老虎 tiger
g：草 grass
w：水 water
e：吃 eat
d：喝 drink

其中：

1
2
3

S：一个完整句子
N：名词
V：动词

例如生成“羊吃草”：

1
2
3
4
5

S
→ N V N
→ s V N
→ s e N
→ s e g

最后得到：

1

seg

也就是：

1

羊 吃 草

S → N V N

表示：

一个 S 可以被替换为 N V N

句子 = 名词 + 动词 + 名词

N → s | t | g | w

N 可以是 s、t、g、w 中的任意一个

|表示或者

每个βi是一个符号，终结或非终结

上下文无关文法是一个四元组：

G=(T,N,P,S)

四个部分分别是：

推导

可以推出的其中一个句子

最左推导和最右推导

最左推导：每次推导都选择最左侧的非终结符进行替换

最右与最左对称

语法分析要解决的问题

给定文法G和句子s，语法分析要回答的 问题：是否存在对句子s的推导

分析树与二义性

树的遍历

主要分为**深度优先遍历（DFS）和广度优先遍历（BFS）**两大类

一、深度优先遍历（DFS）

尽可能深地搜索树的分支，走到尽头再回溯。根据访问根节点的时机，又分为三种（对二叉树）：

• 前序遍历（先序遍历）
  顺序：根 → 左子树 → 右子树
  特点：第一个访问的总是整棵树的根。常用于复制一棵树、输出目录结构等。
• 中序遍历
  顺序：左子树 → 根 → 右子树
  特点：仅对二叉树有意义。对于二叉搜索树，中序遍历得到的是有序序列。
  普通树没有中序遍历。
• 后序遍历
  顺序：左子树 → 右子树 → 根
  特点：最后访问根节点。常用于删除树（先删子节点再删父节点）、计算文件夹大小等。

普通树（多叉树）的深度优先
对于非二叉树，通常只有：

• 先根遍历：先访问根，再依次递归遍历每一棵子树（效果类似前序）。
• 后根遍历：先依次递归遍历每一棵子树，再访问根（效果类似后序）。

实现方式上，递归最直观；非递归则需要显式使用栈来模拟递归过程。

二、广度优先遍历（BFS）

• 层序遍历
  顺序：从根节点开始，从上到下、从左到右逐层访问。
  实现通常借助队列：根入队，每出队一个节点就将其子节点依次入队，直到队列为空。
  应用场景：求树的宽度、按层打印、最短路径问题等

推导与分析树

转化为树后，叶子节点表示句子

例子

注意到两个推导方式得到的句子是一样的，但数据结构不同

分析树的含义取决于树的后序遍历顺序，数据结构不同含义也不一样

上面是23，下面是35，考虑到优先级，前者是我们要的

显然这样的文法存在一些问题，从它推导出的句子可能有两个不同的含义

二义性文法

表达式文法的重写

通过 E、T、F 的层级体现优先级

重写为：

1
2
3

E → E + T | T
T → T * F | F
F → num | id

这样：

• * 的优先级高于 +；
• 3+4*5 只能解释为 3+(4*5)；
• 3+4+5 会按照左结合解释为 (3+4)+5

自顶向下分析

算法思想

语法分析：给定文法 G和句子 s，回答 s是否能 够从 G推导出来？

 基本算法思想：从 G的开始符号出发，随意推 导出某个句子 t，比较 t 和 s

 若t==s，则回答“是”

 若t!=s，则需要回溯

 因为这是从开始符号出发推出句子，因此称为 自顶向下分析

 对应于分析树自顶向下的构造顺序

例子

算法

• tokens[]：存放所有词法单元，分析的目标就是看它们能否由文法推导出来。
• i：输入指针，指向下一个要匹配的终结符。
• stack：分析栈，栈顶在右端。栈中存放的是文法符号（终结符或非终结符），它表示“为了最终匹配输入，还需要看到的结构”。

while (stack != [])
只要栈非空，就不断尝试匹配或展开。如果栈已空且输入也刚好读完，分析成功；若栈空但输入还有剩余，则失败。

• 如果栈顶是一个终结符 t，就把它与当前输入符号 tokens[i] 比较。

• 匹配成功：两者相同，说明推导出的终结符与输入一致。此时：

  • i++ 消耗掉这个输入符号
  • pop() 弹出栈顶终结符

• 匹配失败：说明当前推导路径无法与输入相符，必须回溯 (backtrack())。
  回溯会恢复到最近一个“选择点”（即某个非终结符展开时），换一条产生式右部重试

• 栈顶为非终结符 T 时，需要把它展开（用产生式替换），模拟一步最左推导。

• pop() 先把栈顶的 T 弹出。

• push(the next right hand side of T) 将 T 的下一个候选产生式右部压入栈中。
  因为要支持回溯，T 的所有产生式会按某种预设顺序逐个尝试。所谓 “next right hand side” 意味着：

  • 第一次遇到这个 T 时，压入它的第一个产生式右部；
  • 如果之后因失败而回溯到此处，就尝试第二个产生式，依此类推；
  • 如果所有产生式都试完仍失败，则向更早的选择点回溯。

推入顺序：因为是自顶向下最左推导，产生式右部必须反向压栈，让左端符号出现在栈顶，这样才能优先展开。例如，产生式 T → A B C，实际应 push(C)、push(B)、push(A)，使得 A 在栈顶

backtrack中如果所有可能推导路径都尝试完毕仍无法匹配，则报告语法错误

例子

可以发现，在匹配的过程中往往要用到回溯。这就给分析效率上鸭梨了

这就需要线性时间的算法（ 递归下降分析算法 和LL(1)分析算法 ）避免回溯

用“前看符号”避免回溯

我们可以用一个前看符号指导右边产生式的选择来避免回溯，与输入的串的规模成线性比例

前看符号指向当前还没有处理的下一个 Token

递归下降分析算法

它也叫预测分析，每个非终结符构造一个函数，并利用前看符号选择产生式 （分治法）

伪代码

递归下降的核心思想是：

每个非终结符对应一个分析函数。

例如：

1

S → N V N

就写成：

1
2
3
4
5
6

void parseS(void)
{
    parseN();
    parseV();
    parseN();
}

算法框架

分类讨论，遇到非终结符做递归调用，终结符做比较

算术表达式的递归下降分析

这里有两种可能路径，得回溯解决

消除左递归

原文法：

1
2
3
4
5

E → E + T 
    | T
T → T * F 
    | F
F → num

不能直接写成：

1
2
3
4
5

void parseE(void)
{
    parseE();
    ...
}

因为 parseE() 一进入就再次调用 parseE()，形成无限递归。

这叫左递归。

将：

1
2

E → E + T 
    | T

改写为：

1
2
3

E  → T E'
E' → + T E' 
    | ε

同理：

1
2
3
4
5
6

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

1

3 + 4 * 5

函数调用过程大致是：

1
2
3
4
5
6
7
8

parseE
 ├─ parseT
 │   └─ parseF：读取 3
 ├─ 读取 +
 └─ parseT
     ├─ parseF：读取 4
     ├─ 读取 *
     └─ parseF：读取 5

因此乘法在第二个 parseT() 中完成，自然得到：

1

3 + (4 * 5)

语法分析器自动生成

LL(1)算法

分析器架构

先回顾一下 自顶向下分析算法

显然我们要解决在什么情况下才能push correct 右部，如果能解决，backtrack也不需要了

LL(1)分析表

行为终结符，列为非终结符

根据前看符号，通过查表决定push哪个右部

FIRST集

推导出所有可能的开头终结符集合

first集不动点算法

由于 FIRST 集是有限集合，且每次迭代只增不减，最终一定会收敛到最小不动点

先把每一个非终结符的开始符号初始化空集

然后条件判断，只要有集合还在变化就持续循环（扫描产生式）

两个if判断，终结符和非终结符并入集合

推广到任意串上

构造LL(1)分析表

照着填

LL（1）分析表中的冲突

我们加上一条文法规则后发现对于w有两条产生式可以选

FIRST_S(β) ∩ FIRST_S(γ) ={} ，根据判别式可知4，5存在冲突

一般条件下LL(1)分析表构造

我们发现在这样一个文法下，Y可以推出为空，X也自然可以为空

当非终结符可以推出空串时，first集需要向后推

这时就需要引入NULLABLE集合

NULLABLE集合

可以直接推出空串或推出的都是非终结符且都属于NULLABLEJ集

与定义一致，可以看出这也是不动点算法

FIRST集合的完整计算公式

注意到，当右侧是非终结符时要将该非终结符也并入FIRST集合，并往后判断是否属于NULLABLE,直到某个Y不为NULLABLE

不动点算法

foreach (production p: N->β 1 … βn) 这一步是对产生式的遍历

例子

文法：

1
2
3

Z → d | XYZ
Y → c | ε
X → Y | a

第0轮（初始化）

1
2
3

FIRST(Z)={}
FIRST(Y)={}
FIRST(X)={}

第1轮

① Z → d

1

FIRST(Z)={d}

② Y → c

1

FIRST(Y)={c}

③ Y → ε

1

Y ∈ NULLABLE

（ε不加入FIRST）

④ X → Y

因为：

1

FIRST(Y)={c}

所以：

1

FIRST(X)={c}

且 Y 可空，所以：

1

X ∈ NULLABLE

⑤ X → a

加入：

1

FIRST(X)={a,c}

第1轮结果：

第2轮

处理：

1

Z → XYZ

从左到右：

X：

1

FIRST(X)={a,c}

加入 Z：

1

FIRST(Z)={a,c,d}

因为 X 可空，继续看 Y：

1

FIRST(Y)={c}

无变化。

最终 FIRST 集：

1
2
3
4
5

FIRST(Z)={a,c,d}

FIRST(Y)={c}

FIRST(X)={a,c}

NULLABLE：

1

Y、X

（因为 Y→ε，X→Y→ε）

FOLLOW集不动点算法

FOLLOW(A)：表示在所有句型中，非终结符 A 后面可能出现的终结符集合

例如：

1

S → AB

那么：

1

FOLLOW(A) 包含 FIRST(B)

1. 初始化：

1

FOLLOW(所有)=∅

2. 产生式：

1

A→β1β2...βn

3. 从右往左扫描
4. 遇到终结符：

1

temp={a}

5. 遇到非终结符 M：

1

FOLLOW(M)+=temp

6. 如果 M 不能推出 ε：

1

temp=FIRST(M)

7. 如果 M 能推出 ε：

1

temp=temp∪FIRST(M)

8. 一直循环到 FOLLOW 不变化

例子

1

Z→XYZ

从右往左：

Z

最后：

1

FOLLOW(Z)传给前面

Y

后面有 Z：

1
2

FOLLOW(Y)=FIRST(Z)
={a,c,d}

X

后面有 YZ：

先：

1

FIRST(Y)={c}

因为 Y 可空：

继续：

1

FIRST(Z)={a,c,d}

合并：

1

FOLLOW(X)={a,c,d}

最终：

1
2
3
4
5

FOLLOW(Z)={$}

FOLLOW(Y)={a,c,d}

FOLLOW(X)={a,c,d}

计算FIRST_S集合

注意到M为非终结符时要往后穿

对于：

1

FIRST_S(A B C)

从左往右看：

1. 如果遇到终结符 a：

1
2

加入a
停止

2. 如果遇到非终结符 M：

1

加入FIRST(M)

3. 如果 M 可以推出 ε：

继续看后面的符号。

4. 如果 M 不能为空：

停止。

构造LL(1)分析表

可以发现这里存在冲突

LL(1)分析器

使用一个分析栈 stack 和 输入 token 序列 tokens，根据 LL(1)分析表决定如何展开非终结符

LL(1)分析冲突处理

产生式不唯一，还是需要回溯处理，我们可以通过对文法的处理来扩大LL(1)文法能应用的范围

注意到0跟2都存在左递归

消除左递归

把“自己调用自己”改成“尾递归循环”，将 A→Aα|β 改成 A→βA'，A'→αA'|ε，使文法满足 LL(1) 分析要求

提取左公因子

LR(0)算法

LR(0) 是自底向上的语法分析算法，属于 LR 分析方法的一种。它通过构造 LR(0) 项目集族（DFA） 和 分析表（ACTION/GOTO表） 来完成移进-归约分析。

• L（Left）：从左到右扫描输入串
• R（Rightmost）：构造最右推导的逆过程（也就是自底向上归约）
• 0：不看任何向前搜索符（没有 lookahead）

LR(0)核心思想

例如文法：

1
2
3

S → C C
C → c C
C → d

目标分析：

1

ccd

LR(0) 不像 LL(1)：

1
2
3
4
5
6

从根开始展开
S
↓
CC
↓
...

而是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输入串
ccd

先找到句柄

d
↓
C

cC
↓
C

CC
↓
S

也就是：

不断找到可以归约的部分，把它变成非终结符

为了适应其要求，分析表中不能出现冲突，这就要涉及到文法的改写

自底向上分析算法

这种文法能分析的范围比LL(1)更大且往往不需要对文法进行特殊处理

算法思想

我们把产生式从左到右称作推导，从右到左叫归约

注意到做替换的符号总是位于当前最右侧位置上

点记号

生成一个逆序的最右推导

注意到问题的关键在于移进和归约的时机处理

构造 LR(0) 必须增加开始符号：

原：

1

S → CC

增加：

1

S' → S

方便判断接受。

最后：

1

S' → S.

表示分析成功。

我们把加了点号的产生式称作项目，这样的整体叫项目集

注意到在图中1为起始状态，6为接受状态，是一个确定的自动机

这个文法只能推出xxy$串，$为文件描述符，读到文件描述符终止

LR(0)分析表

动作表里面是终结符，转移表里面是非终结符

s表示shift，移进

r是reduce，表示按第几条规则做归约，因为状态和字符是两两配对，所以要多弹一个数据进去

LR(0)分析算法

1是状态机的初始状态

栈顶状态是状态机的编号

分别对移进和归约两种合法情况分析

LR(0)分析表构造算法

相当于对 LR(0) 项目集 DFA 做一次广度优先搜索

先对S’ -> . S $求闭包，得到C0初始集合

Q是工作表，表示哪些还没计算过

goto函数表示对于集合c，读入一个终结符或非终结符能够到达哪一个项目集

set用来记录一共产生了多少不同的状态

goto和closure

closure函数：

如果一个项目点号右边紧跟着一个非终结符，那么就意味着“为了匹配这个非终结符，它的所有产生式都有可能接下来出现”。因此，要把这些产生式全部扩展并加入集合中

goto函数：

给定一个项目集合（状态）C 和输入符号 x，计算识别完 x 之后应该转移到的下一个状态

SLR分析算法

LR(0)分析

• L (Left-to-right)：从左到右扫描输入源代码（程序）。
• R (Rightmost derivation)：构造的是最右推导的逆过程（即进行最左归约）。
• 0 (0个前看符号)：这是LR(0)的核心特征。在决定是否进行“归约”（即识别出一个语法成分）时，完全不看当前尚未读入的下一个输入符号

0前看：在 LR(0) 中，一个状态内部只要出现了**“归约项目”**（形如 A → α·，点号在末尾意味着已经完整匹配了产生式右部），分析器就会强制在该状态中进行归约，而不去看输入的下一个字符是谁。 这是导致它能力有限的最直接原因

LR(0)算法缺点

在 LR(0) 的状态中，只要圆点 • 跑到了产生式的最右边（表示完全匹配了右部），它就会立刻、无条件地执行归约动作。它根本不管接下来输入的是什么字符（0个前看符号）。虽然它最后确实能发现错误（不会漏掉错误），但报错的时机滞后了

• 移进-归约冲突 (Shift-Reduce Conflict)：这是最常见的情况。在 LR(0) 的某个状态里，可能同时出现了两种情况：
  1. 可以继续读入下一个输入符（移进）。
  2. 当前栈顶已经匹配完一个产生式，可以立即执行归约。
  3. 因为没有前看符号，LR(0) 完全无法决定是该“前进”还是该“收网”。遇到这种状态，分析表的构造就直接失败了。
• 归约-归约冲突 (Reduce-Reduce Conflict)：在同一个状态下，可能有两个不同的产生式都已经匹配完成（比如 A -> α• 和 B -> α•），机器完全不知道该用哪一条规则去归约。这也是冲突

SLR

和LR(0)分析算法基本步骤相同,仅区别于对归约的处理

对于状态 i 里的归约项目 X -> α ·，不能在所有的终结符下都进行归约。仅当当前输入符号 y 属于 FOLLOW(X) 集合时，才在 ACTION[i, y] 中填入归约动作

SLR 的本质是：

A→α⋅+当前输入符号∈FOLLOW(A)⟹归约

SLR冲突

状态 2：

• 项目 S -> L • = R 表示：目前已经匹配到了 L，下一个期待看到的输入符号是 =，这是一个移进动作（Shift）。
• 项目 R -> L • 表示：目前已经识别出 L，可以将它归约成 R（Reduce，使用 R -> L 规则）。

当语法分析器处于状态 2，且当前读入的输入符号是 = 时，它不知道该“移进 =”还是“归约成 R”，这就造成了冲突

LR(1)算法

SLR 使用整个非终结符的 FOLLOW 集决定归约，范围仍然太大；LR(1) 给每个项目单独记录一个前看符号

这里的“1”表示使用 1 个前看符号。

LR(1) 项目写成：

[A→α⋅β, a]

由两部分组成：

• A→α⋅β：LR(0) 项目，称为项目的“核心”；
• a：该项目自己的前看符号。

含义是：

• α 已经识别，位于分析栈顶部；
• 接下来需要识别 β；
• 完成整个产生式后，允许出现的符号是 a。

SLR 使用：

FOLLOW(R)={=,$}

FOLLOW(R) 汇总了 R 在整个文法中的所有情况，无法区分当前状态里的具体上下文

而 LR(1) 使用当前项目自己的前看符号：

[R→L⋅, $]

所以 LR(1) 更精确

LR(1) 的闭包 closure

LR(1) 和 LR(0) 的主要区别在闭包计算。

假设项目集中存在[A→α⋅Bβ, a]

圆点后面是非终结符 B，则对于每个产生式

B→γ 加入 [B→⋅γ, b]

其中b∈FIRST(βa)

不是简单地把原来的前看符号 a 传下去，而是计算FIRST(βa)

三种常见情况:

1. β 以终结符 = 开头：

FIRST(=Ra)={=}

新项目的前看符号就是 =。

2. β 为空：

FIRST(a)={a}

直接把原来的前看符号传下去。

3. β 可以推出空：

既要加入 FIRST(β) 中的终结符，也可能加入 a

LR(1)分析表构造

项目集构造完成后：

• A→α⋅aβ：在 a 列填写移进；
• A→α⋅Bβ：填写 GOTO；
• [A→α⋅,a]：只在 a 列填写归约；
• [S′→S⋅,$]：在 $ 列填写 accept

LR(1)项目集过多

有两个很像的状态：

I8:[R→L⋅,{=,$}]和I10:[R→L⋅,{$}]

把前看符号去掉，两者都是：

R→L⋅

但是 LR(1) 认为它们是不同状态，因为前看符号不同。

同样：

I5:[L→id⋅,{=,$}]I11:[L→id⋅,{$}]

也必须分开。

所以 LR(1) 的特点就是：

同一个 LR(0) 项目，因为所处上下文不同、前看符号不同，可能被拆成多个 LR(1) 状态。

这使 LR(1) 很精确，但项目集数量会膨胀

LALR分析算法

把“类似”的 LR(1) 项目集进行合并

例如：

I8=[R→L⋅,{=,$}]I10=[R→L⋅,{$}]

核心都是R→L⋅

所以 LALR 可以合并，前看符号取并集[R→L⋅,{=,$}]

同理I5+I11可以合并成[L→id⋅,{=,$}]

对二义性文法的处理

二义性文法无法使用LR分析算法分析

不过，有几类二义性文法很容易理解， 因此，在LR分析器的生成工具中可以对它们特殊处理

给出二义性文法：

E→E+E ∣ E∗E ∣ n

例如n+n∗n

有两种解释：

(n+n)∗n或者n+(n∗n)

所以文法本身有二义性。

即使使用 LR(1)，也可能出现：

E→E+E⋅同时又有E→E⋅∗E

现在输入 *：

• 第一项：表达式已经完整，可以归约；
• 第二项：可以继续移进 *。

于是产生移进-归约冲突

这次不是 LR(1) 不够精确，而是文法本身就没说清楚到底应该怎么解释。

用优先级解决

我们人为规定∗ > +

也就是乘法优先级高于加法。

例如当前已经识别n + n

下一个符号是*

此时不要急着n+n⇒E

而应该移进 *：n + n * …

最终得到n+(n∗n)

下一个运算符优先级更高 → 移进。

反过来，如果已经识别n * n

下一个是+

那么先归约n∗n⇒E

因为 * 优先于 +。

结合性解决同优先级

例如：

n+n+n

两个 + 优先级相同。

如果规定 + 左结合：

(n+n)+n

那么识别完第一个 n+n，看到下一个 + 时归约

如果是右结合运算符，则通常选择移进

• 后面的运算符优先级更高 → 移进
• 后面的运算符优先级更低 → 归约
• 优先级相同且左结合 → 归约
• 优先级相同且右结合 → 移进

LR 系列主线：

LR(0)→SLR→LR(1)→LALR

LR(1)分析工具

语法分析器可以通过先前的算法手动构造，也可以通过工具自动生成，自动生成时只需要写声明式

YACC

Yacc：Yet Another Compiler-Compiler

它是“生成编译器中的语法分析器”的工具

GNU Bison 可以理解成 Yacc 的 GNU 实现/扩展版本

一个 Yacc 文件分三部分

1. 声明部分
   定义 Token、优先级、结合性，以及需要使用的变量或代码。

1
2

%token NUM
%left '+'

2. 语法规则部分
   写上下文无关文法，并可以附加语义动作。

1
2
3
4
5

%%
E: E '+' E
 | NUM
 ;
%%

3. 用户代码部分
   写普通 C 代码，比如错误处理、辅助函数等。

1
2
3

void yyerror(char *s) {
    printf("error");
}

语法制导翻译

在进行语法分析的同时，根据产生式执行对应的“语义动作”。

也就是从“判断语法对不对”，进一步变成“知道这段程序是什么意思、该做什么”

基本思想

普通产生式：

E→E+E

给它附加一个语义动作：

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

Yacc 写法就是：

1

E : E '+' E    { $$ = $1 + $3; }

其中：

• $$：左边 E 的值
• $1：右边第一个 E 的值
• $2：+
• $3：右边第二个 E 的值

自底向上的 LR 分析中，在产生式“归约”的时候执行。

比如E→E+E

当分析器发现栈顶已经是：

1

E + E

准备归约：

E+E⇒E

这时候执行：

1

$$ = $1 + $3;

注意到必须先得到左右孩子的值，才能计算父节点：

1

7   8   +   9   +

也就是：

7, 8, +, 9, +

这正是表达式树的后序计算顺序

LR分析中的语法制导翻译

例如：

1

<E, 15, state?>

三个东西分别代表：

• symbol：终结符/非终结符，比如 E
• value：它的语义值，比如 15
• state：LR 分析状态

因此以前 LR 分析只关心符号 + 状态

现在增加了语义值

归约时：

E+E→E

不仅完成语法上的归约，还顺便：

15+9→24

抽象语法树

抽象语法树（AST, Abstract Syntax Tree）可以理解为：

把“分析树”中为了语法分析而存在的多余信息删掉，只保留程序真正的语法结构

具体语法和抽象语法

具体语法是语法分析器使用的语法，必须适合于语法分析，如各种分隔符、消除左递归、提取左公因子，等等

抽象语法是用来表达语法结构的内部表示

现代编译器一般都采用抽象语法作为前端（词法语法分析）和后端（代码生成）的接口

抽象语法树的定义(c语言)

数据结构

构造函数

malloc 创建节点

  ↓

填写节点数据

  ↓

返回节点指针

构造 2 + 3 * 4

文法：

E -> n

| E + E

| E * E

e1 = Exp_Int_new(2);

e2 = Exp_Int_new(3);

e3 = Exp_Int_new(4);

e4 = Exp_Times_new(e2, e3);

e5 = Exp_Add_new(e1, e4);

完整 AST：

1
2
3
4
5

  +
 / \
2   *
   / \
  3   4

所以 AST 实际上就是：

一个节点里面保存指向其他节点的指针，最终把所有节点连接成一棵树

树的遍历

后面的很多编译器操作，本质都是：

遍历 AST → 根据节点 kind 做不同事情。

比如：

• pretty_print()：重新输出代码
• numNodes()：统计 AST 节点数量
• compile()：把 AST 翻译成机器指令/中间代码

抽象语法树的自动生成

LR分析中生成抽象语法树

在语法动作中，加入生成语法树的代码片段

片段一般是语法树的“构造函数”

在产生式归约的时候，会自底向上构造整棵树，从叶子到根

假设文法：

1
2
3

E → E + E
E → E * E
E → n

给每条产生式加上语义动作：

1
2
3

E → E + E   { $$ = Exp_Add_new($1, $3); }
E → E * E   { $$ = Exp_Times_new($1, $3); }
E → n       { $$ = Exp_Int_new($1); }

$1、$2、$3 → 产生式右边各符号的值
$$ → 产生式左边 E 的值

例如：

1
2
3

E → E + E
    ↑ ↑ ↑
   $1 $2 $3

因此$$ = Exp_Add_new($1, $3);

表示用左边 E 的 AST 和右边 E 的 AST 创建一个新的 + 节点。

以2 + 3 * 4为例

LR 读到 2，之后归约E → n

执行$$ = Exp_Int_new(2);

产生2

读到 3，归约E → n

产生3

读到 4，归约产生4

当 LR 再执行E * E → E

对应语义动作$$ = Exp_Times_new($1, $3);

把之前已经构造好的 3、4 接起来：

1
2
3

  *
 / \
3   4

最后E + E → E

执行$$ = Exp_Add_new($1, $3);

得到：

1
2
3
4
5

  +
 / \
2   *
   / \
  3   4

LR 负责决定什么时候用哪条产生式归约；语义动作负责在归约时把右部已有的 AST 节点组合成新的 AST 节点

源代码信息的保留和传播

AST 不能只保存“程序结构”，还要保存必要的源代码信息

抽象语法树是编译器前端和后端的接口

程序一旦被转换成抽象语法树，则源代码即被丢弃

后续的阶段只处理抽象语法树

所以抽象语法树必须编码足够多的源代码信息

例如，它必须编码每个语法结构在源代码中的位置 （文件、行号、列号等）或者获取程序的执行刨面。这样，后续的检查阶段才能精确的报错

所以 AST 节点通常还要记录：

1
2
3
4
5

struct position_t {
    char *file;    // 哪个文件
    int line;      // 第几行
    int column;    // 第几列
};

例如一个 + 节点：

1
2
3
4
5
6
7
8

struct Exp_Add {
    enum kind kind;
    Exp *left;
    Exp *right;

    struct position_t from;
    struct position_t to;
};

这样后面语义分析发现：

3 + true

类型不匹配，就能准确告诉你：

test.c:10:5: type mismatch

否则编译器只知道 AST 有问题，却不知道源代码哪里有问题

语义分析

前面语法分析解决的是：

“写法合不合语法？”

现在语义分析解决：

“虽然写法没问题，但这样写有没有意义？”

语义分析也称为类型检查 、上下文相关 分析，负责检查程序（抽象语法树）的上下文 相关的属性

抽象语法树通过语义分析器生成中间代码

这是具体语言相关的，典型的情况包括，变量在使用前先进行声明，每个表达式都有合适的类型，函数调用和函数的定义一致

变量是否声明 x = 10;

如果 x 从来没有定义：

1
2

语法 √
语义 ×

表达式类型是否正确 3 + true

可能是int + bool

类型不匹配。

函数调用与定义是否一致：

1
2
3

void f(int *p);

f();

函数需要一个int *

但调用时没给参数，所以语义错误

例子

1
2
3
4
5
6
7
8
9
10
11
12
13

void f(int *p)
{
    x += 4;
    p(23);
    "hello" + "world";
}

int main()
{
    f() + 5;
    break;
    return;
}

它的语法基本都能形成 AST，但语义存在大量错误

• x += 4;
x 从未声明，属于使用未定义变量。
• p(23);
p 的类型是 int*（整型指针），不是函数指针，不能当作函数调用。
• "hello" + "world";
  两个字符串字面量（const char*）不能使用 + 相加，操作数类型非法。
• f() + 5;
  有两个错误：
  ① f 需要传入一个 int* 参数，这里没传参；
  ② f 返回 void，无法参与加法运算。
• break;
break 不在循环或 switch 结构中，非法。
• return;
main 函数的返回类型是 int，空返回语句缺少返回值，类型不匹配

通过了语法分析 ≠ 程序就是合法的

AST 可能完全构造成功：

1
2
3
4
5
6
7
8
9
10
11

AST
 ↓
语义分析
 ↓
变量声明检查
类型检查
函数参数检查
控制结构检查
 ↓
合法 → 继续生成中间代码
错误 → 报错

语义检查

类型检查

• ：两边必须是 INT，结果也是 INT

&& ：两边必须是 BOOL，结果也是 BOOL

类型检查，本质上也是一次 AST 递归遍历

变量声明的处理

x 到底是 INT 还是 BOOL？

光看 x 节点不知道。

必须找到int x;

才知道x → INT

符号表 Symbol Table

编译器处理

int x;
bool y;

时建立

语句的处理

遍历 AST，对每个语句节点检查类型是否匹配。赋值要求左右类型一致，printi要求表达式为int，printb要求表达式为bool

符号表

编译器用来记录“这个名字是谁、是什么类型、在哪个作用域”

符号表必须高效，程序中的变量规模一般很大

符号表的接口与结构

基本的新建、插入、查找功能

我们注意到符号表是典型的字典结构

为了高效，可以使用哈希表等数据结构来实现符号表，查找是O(1)时间

为了节约空间，也可以使用红黑树等平衡树，查找是O(lg N)时间

符号表的核心需求就是快速完成“名字 → 信息”的查询

符号表处理作用域

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int x;

int f()
{
    if (4) {
        int x;
        x = 6;
    }
    else {
        int x;
        x = 5;
    }

    x = 8;
}

内层作用域中声明的名字，会暂时屏蔽外层作用域中的同名名字

全局 x 并没有被删除，只是在当前内层作用域中暂时无法通过名字 x 直接访问

if 里的 x 和 else 里的 x 也不是同一个变量，因为它们位于两个不同的代码块作用域中

符号表处理作用域主要有两种方法：

1. 一张符号表

• 进入作用域：插入该作用域声明的变量。
• 查找变量：优先找到最近插入的同名变量。
• 退出作用域：删除该作用域插入的变量，使外层同名变量恢复可见。

2. 符号表栈

• 每个作用域单独建立一张符号表。
• 进入作用域：新符号表入栈。
• 查找变量：从栈顶向栈底查找，最先找到的就是当前使用的变量。
• 退出作用域：弹出栈顶符号表。

核心规则：始终优先使用距离当前位置最近的声明

符号表处理名字空间

名字空间用于区分“名字相同，但类别不同”的符号。编译器通常为每类名字空间建立一张符号表。

以 C 语言为例：

1
2
3
4
5
6

struct list {
    int x;
    struct list *list;
} *list;

list:

这里的 list 分别可以表示：

• struct list：结构体标签
• *list：普通变量
• 结构体中的 list：成员名
• list:：goto 标签

它们虽然同名，但处于不同名字空间，因此不会冲突。

方法：

1
2
3
4

普通变量 → 变量符号表
结构体标签 → 标签符号表
goto 标签 → 标号符号表
结构体成员 → 该结构体的成员符号表

作用域区分“不同位置的同类名字”，名字空间区分“不同类别的同名符号”

其它问题

类型相等与类型相容

类型检查经常需要判断：

1

t1 和 t2 能否一起运算或赋值？

这里不一定要求两个类型完全相等，还可能允许：

• 类型转换
• 子类赋值给父类
• 结构相同的类型互相赋值

虽然 A 和 B 不是相同类型，但 B 继承自 A，B 是 A 的子类型

因此x = y;

通常合法，表示把子类对象赋给父类变量，也叫向上转型

严格来说，赋值检查通常判断的是类型相容，而不只是类型相等

类型相容可能包括：

• 完全相同的类型；
• 可以自动转换的类型；
• 子类到父类；
• 语言允许的其他转换。

错误诊断

代码翻译

现代编译器的语义分析模块除了检查程序是否合法，通常还会为中间代码生成做准备。

例如源程序：

1

x = a + b;

AST 大致是：

1
2
3
4
5

Assign
├── x
└── Add
    ├── a
    └── b

语义分析遍历 AST 时会：

1. 查找 x、a、b 的符号信息；
2. 检查 a + b 是否合法；
3. 确定表达式结果类型；
4. 把类型、变量位置等信息标注到 AST；
5. 生成或准备生成中间表示。

可能生成：

1
2

t1 = a + b
x = t1

因此类型检查和代码翻译都可以通过遍历 AST 完成，只是遍历时执行的操作不同

代码生成

代码生成的核心任务是把已经通过语义检查的程序，翻译成目标机器能够执行的代码

最简单的方式是直接遍历抽象语法树生成汇编代码

这种方式容易实现，但不方便优化和适配不同机器。

现代编译器通常加入中间表示：

1

AST → IR → 优化 → 目标机器代码

这样前端只需要生成统一的 IR，后端再把 IR 翻译到 x86、ARM、RISC-V 等不同架构

代码生成主要有两个任务：

1. 给数据分配计算资源

决定程序中的数据放在哪里：

• 全局变量通常放在数据区；
• 局部变量通常放在栈或寄存器；
• 动态申请的数据放在堆；
• 临时结果尽量放在寄存器中。

2. 给代码选择机器指令

用机器指令实现高级语言的操作：

源程序的代码：

• 表达式运算、语句、函数等

机器指令：

• 算术运算、比较、跳转、函数调用返回

用机器指令实现高层代码的语义 ：

• 等价性
• 对机器指令集体系结构 （ISA）的熟悉

指令集体系结构 （ISA） 上的代码生成

栈式计算机

栈式计算机是一种以“操作数栈”为主要运算空间的计算机模型

• 栈式计算机在 20 世纪 70 年代比较流行。
• 真实的栈式处理器现在很少，主要原因是执行效率不如寄存器计算机。
• 但栈式代码生成非常简单，适合学习编译器的代码生成过程。
• 现代仍有很多栈式虚拟机，例如 JVM、Pascal P-code、PostScript

栈式计算机结构

栈式计算机指令集

指令的语义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 把常数 NUM 压栈
push NUM:
    top++;
    stack[top] = NUM;
// 把变量 x 的值压栈
load x:
    top++;
    stack[top] = x;
// 把栈顶值保存到变量 x
store x:
    x = stack[top];
    top--;
// 取栈顶两个数相加，将结果压回栈
add:
    temp = stack[top - 1] + stack[top];
    top -= 2;
    push temp;

变量的内存分配伪指令

栈式计算机只支持 int 类型，使用：

1

.int x

为变量 x 分配一块内存空间

它是伪指令：只在程序加载时负责分配内存，不会像 push、add 一样真正参与运算

递归下降代码生成算法

从 C– 到 Stack

递归遍历 C– 程序的抽象语法树，同时生成 Stack 栈式计算机指令

C– 的简化语法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

P -> D S              程序 = 变量声明 + 语句

D -> T id; D          变量声明
   | ε                声明可以为空

T -> int
   | bool             数据类型

S -> id = E           赋值
   | printi(E)        输出整数
   | printb(E)        输出布尔值

E -> n                整数
   | id               变量
   | true
   | false
   | E + E
   | E && E

语法树中的每类节点，对应一个递归函数：

1
2
3
4
5

Gen_P(D, S);       // 生成整个程序
Gen_D(T, id, D);   // 生成变量声明
Gen_T(T);          // 生成类型
Gen_S(S);          // 生成语句
Gen_E(E);          // 生成表达式

它们之间的调用关系是：

1
2
3
4
5

Gen_P
├── Gen_D
│   └── Gen_T
└── Gen_S
    └── Gen_E

所谓“递归下降”，就是从程序根节点 P 开始，根据语法树结构逐层调用对应函数

表达式的代码生成

Gen_E(e) 执行结束后，表达式 e 的值一定在栈顶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

void Gen_E(E e)
{
    switch (e->kind) {
    case E_INT:
        emit("push n");
        break;

    case E_ID:
        emit("load id");
        break;

    case E_TRUE:
        emit("push 1");
        break;

    case E_FALSE:
        emit("push 0");
        break;

    case E_ADD:
        Gen_E(e1);
        Gen_E(e2);
        emit("add");
        break;

    // E && E 等情况类似
    }
}

语句的代码生成

类型的代码生成

Stack 机器只支持一种数据类型：int。因此 C– 中的 int 和 bool 都翻译成 .int。

1
2
3
4
5
6
7
8
9
10
11
12

void Gen_T(T t)
{
    switch (t) {
    case T_INT:
        emit(".int");
        break;

    case T_BOOL:
        emit(".int");
        break;
    }
}

变量声明的代码生成

声明语法是：

1
2

D -> T id; D
   | ε

表示每个声明后面还可以继续跟一个声明，最后通过空产生式 ε 结束。

代码生成算法：

1
2
3
4
5
6
7
8
9

void Gen_D(D d)
{
    if (d == NULL)       // 对应 D -> ε
        return;

    Gen_T(d->type);      // 生成 ".int"
    emit(" id");         // 生成变量名
    Gen_D(d->next);      // 递归生成剩余声明
}

程序的代码生成

程序的语法结构：

1

P -> D S

表示一个程序由两部分组成：

• D：变量声明；
• S：可执行语句。

因此代码生成函数非常简单：

1
2
3
4
5

void Gen_P(P p)
{
    Gen_D(p->declarations);
    Gen_S(p->statement);
}

也就是先生成变量声明 → 再生成可执行指令

寄存器计算机

寄存器计算机主要依靠寄存器保存数据并完成运算：

• 真实机器通常有 16、32 个或更多寄存器。
• 算术运算只能在寄存器之间进行。
• 内存不能直接参与计算，必须先 load 到寄存器。
• 结果通过 store 写回内存

Reg的结构

主要包含：

• Memory：保存溢出到内存中的变量。
• Reg：寄存器，保存变量和临时计算结果。
• ALU：执行加减乘除。
• 执行引擎：读取并执行指令。

先假设有无限多个寄存器，这些实际上是虚拟寄存器。后面再把虚拟寄存器映射到有限的物理寄存器，这个过程叫寄存器分配

指令集

变量的寄存器分配伪指令

Reg机器只支持一种数据类型int，并且给变量x分配寄存器的伪指令是：

• .int x
• 在代码生成的阶段，假设Reg机器上有无限多个寄存器
• 因此每个声明变量和临时变量都会占用一个（虚拟）寄存器
• 把虚拟寄存器分配到物理寄存器的过程称为寄存器分配

递归下降代码生成算法

从C– 到Reg：

每个非终结符对应一个代码生成函数：

1
2
3
4
5

void Gen_P(P);   // 程序
void Gen_D(D);   // 变量声明
void Gen_T(T);   // 类型
void Gen_S(S);   // 语句
R_t  Gen_E(E);   // 表达式

只有 Gen_E()需要返回值，返回的不是计算结果本身，而是保存表达式结果的寄存器编号

文法：

表达式的代码生成

Gen_E(e) 返回后，表达式 e 的值保存在它返回的寄存器中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// 表达式的代码生成
// 不变式：表达式的值在函数返回的寄存器中
R Gen_E(E e) {
    switch (e) {
        case n: {
            r = fresh();
            emit("movn n, r");
            return r;
        }
        case id: {
            r = fresh();
            emit("mov id, r");
            return r;
        }
        case true: {
            r = fresh();
            emit("movn 1, r");
            return r;
        }
        case false: {
            r = fresh();
            emit("movn 0, r");
            return r;
        }
        case e1 + e2: {
            r1 = Gen_E(e1);
            r2 = Gen_E(e2);
            r = fresh();
            emit("add r1, r2, r");
            return r;
        }
        case e1 && e2: {
            r1 = Gen_E(e1);
            r2 = Gen_E(e2);
            r = fresh();
            emit("and r1, r2, r");
            return r;  // 非短路求值
        }
    }
}

fresh()表示申请一个新的虚拟寄存器

非短路计算指：逻辑表达式两边都会执行，不会因为左边已经能确定结果而跳过右边。

例如：

1

false && func()

• 短路计算：左边是 false，整个表达式必然为 false，所以不执行 func()。
• 非短路计算：即使左边是 false，仍然会执行 func()。

语句的代码生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// 语句的代码生成
void Gen_S(S s) {
    switch (s) {
        case id = e: {
            r = Gen_E(e);
            emit("mov r, id");
            break;
        }
        case printi(e): {
            r = Gen_E(e);
            emit("printi r");
            break;
        }
        case printb(e): {
            r = Gen_E(e);
            emit("printb r");
            break;
        }
    }
}

• Gen_E(e) 生成表达式代码，并返回结果寄存器 r。
• 赋值语句把 r 复制给变量。
• 输出语句直接输出 r

类型的代码生成

1
2
3
4
5
6
7
8
9
10
11

void Gen_T(T t) {
    switch (t) {
        case int:
            emit(".int");
            break;

        case bool:
            emit(".int");
            break;
    }
}

Reg 机器只支持 int，所以：

• int 生成 .int
• bool 也生成 .int，用 1/0 表示 true/false

变量声明

文法：

1

D → T id; D | ε

代码：

1
2
3
4
5

void Gen_D(T id; D) {
    Gen_T(T);      // 生成类型 .int
    emit("id");    // 生成变量名
    Gen_D(D);      // 递归处理后续声明
}

例如：

1
2

int x;
bool y;

生成：

1
2

.int x
.int y

遇到空产生式 ε 时，递归结束

程序

文法：

1

P → D S

代码：

1
2
3
4

void Gen_P(D, S) {
    Gen_D(D);   // 生成变量声明
    Gen_S(S);   // 生成语句
}

作用：从程序根节点开始，先处理全部变量声明，再处理程序语句。

调用关系：

1
2

Gen_P → Gen_D → Gen_T
      → Gen_S → Gen_E

中间表示

中间表示（Intermediate Representation，IR）是编译器内部用于表示程序的一种形式。

整个编译过程可以理解为：

1
2
3
4
5
6
7

源程序
  ↓ 词法、语法、语义分析
抽象语法树 AST
  ↓ 翻译
中间表示 IR
  ↓ 优化、代码生成
汇编代码

中间代码

为什么要使用多种中间表示

主要有两个原因。

工程上的原因

把编译过程拆成多个阶段：

1

复杂任务 → 多个简单任务

每个阶段只负责一种转换，更容易实现、调试

程序分析和优化的需要

不同优化适合不同 IR。

例如：

• AST：适合高级语言结构分析；
• 三地址码：适合常量折叠、复制传播；
• CFG：适合循环分析、不可达代码删除；
• SSA：适合数据流分析和变量优化。

通用编译器语言

IR让编译器更易支持多语言，多平台

三地址码

三地址码是一种接近机器指令的中间表示。

典型形式：

1

x = y op z

一条指令最多涉及三个地址：

• x：保存结果；
• y：第一个操作数；
• z：第二个操作数。

例如：

1

t1 = a + b

因此叫“三地址码”

三地址码基本思想

三地址码是一种中间表示，把复杂程序拆成简单指令。

例如：

1

a = 3 + 4 * 5;

转换为：

1
2
3

t1 = 4 * 5
t2 = 3 + t1
a = t2

特点：

• 每条指令只进行一次基本运算；
• 使用临时变量保存中间结果；
• if、while 等结构被转换为条件跳转、无条件跳转和标号；
• 形式接近机器指令，便于代码优化和生成汇编。

典型形式：

1
2
3
4
5
6

x = y + z
x = y
Cjmp(x, L1, L2)
Jmp L
Label L
Return x

只有最基本的控制流，没有各种控制结构，只有goto，call 等

所以三地址码可以看成是抽象的指令集（通用的RISC）

例子

这里的 x_1、x_2、x_3... 可以理解成临时变量/临时寄存器

其中 Cjmp** = Conditional Jump，条件跳转**。

1

Cjmp (x < y) L1 L2

意思就是：

1
2

如果 x < y → 跳到 L1
否则       → 跳到 L2

三地址码的定义

一条三地址码语句 s 可以有以下形式：

1
2
3
4
5
6
7
8
9
10
11

x = n              // 常数赋值
x = y ⊕ z          // 二元运算
x = Θ y            // 一元运算
x = y              // 数据移动
x[y] = z           // 内存写
x = y[v]           // 内存读
x = f(x1, ..., xn) // 函数调用
Cjmp(x1, L1, L2)   // 条件跳转
Jmp L              // 无条件跳转
Label L            // 定义标号
Return x           // 函数返回

其中：

• ⊕：二元运算符，如 +、-、*、<、&&。
• Θ：一元运算符，如 -、!。
• x[y] = z：把 z 写入以 x 为基址、y 为偏移的位置。
• x = y[v]：从以 y 为基址、v 为偏移的位置读取数据。
• Cjmp(x1,L1,L2)：x1 为真跳到 L1，否则跳到 L2。

三地址码的数据结构

1
2
3
4
5
6
7
8
9
10

enum instr_kind {
    INSTR_CONST,
    INSTR_MOVE,
    INSTR_ADD,
    ...
};

struct Instr_t {
    enum instr_kind kind;
};

加法指令：

1
2
3
4
5
6

struct Instr_Add {
    enum instr_kind kind;
    char *x;
    char *y;
    char *z;
};

表示：

1

x = y + z

关键点是：所有指令的第一个成员都是 kind。程序先检查 kind，再判断这究竟是加法、移动还是跳转指令

从c生成三地址码

整体过程：

1

抽象语法树 ──翻译1──> 三地址码 ──翻译2──> 汇编

与之前直接生成 Stack 指令相比，现在增加了三地址码作为中间层，使后续优化和汇编生成更容易。

主要语法

1
2
3

P -> F*                           // 程序由多个函数组成
F -> x ((T id,)*) {(T id;)* S*}  // 函数
T -> int | bool                  // 类型

语句：

1
2
3
4
5
6
7

S -> x = E
   | printi(E)
   | printb(E)
   | x(E1, ..., En)
   | return E
   | if(E, S*, S*)
   | while(E, S*)

表达式：

1
2
3
4
5
6

E -> n
   | x
   | true
   | false
   | E + E
   | E && E

对应的递归生成函数

1
2
3
4
5

Gen_P(P);  // 生成整个程序
Gen_F(F);  // 生成函数
Gen_T(T);  // 处理类型
Gen_S(S);  // 生成语句
Gen_E(E);  // 生成表达式

这些函数按照抽象语法树的结构递归遍历。

关键不变式是：

1

Gen_E(e) 返回保存表达式 e 结果的临时变量

递归下降代码分析算法

赋值语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Gen_S(S s) {
    switch (s) {

        case x = e:
            x1 = Gen_E(e);
            emit("x = x1");
            break;

        case printi(e):
            x = Gen_E(e);
            emit("printi(x)");
            break;

        case printb(e):
            x = Gen_E(e);
            emit("printb(x)");
            break;
    }
}

x=e是赋值语句

• Gen_E(e) 先生成表达式 e 的三地址码。
• 返回保存结果的临时变量 x1。
• 最后把 x1 赋值给变量 x

printi和printb分别输出int和bool值

函数调用和return语句

1
2
3
4
5
6

case x(e1, ..., en):
    x1 = Gen_E(e1);
    ...
    xn = Gen_E(en);
    emit("x(x1, ..., xn)");
    break;

遇到函数调用时，先把每个参数表达式算出来，再调用函数

1
2
3
4

case return e:
    x = Gen_E(e);
    emit("return x");
    break;

先计算返回表达式，再返回计算结果

if-else** 的代码生成**

1
2
3
4
5
6
7
8
9
10
11
12
13
14

case if(e, s1, s2):
    x = Gen_E(e);
    emit("Cjmp(x, L1, L2)");

    emit("Label L1:");
    Gen_SList(s1);
    emit("jmp L3");

    emit("Label L2:");
    Gen_SList(s2);
    emit("jmp L3");

    emit("Label L3:");
    break;

含义：

1. Gen_E(e)：计算条件，结果保存在 x。
2. Cjmp(x,L1,L2)：x 为真跳到 L1，否则跳到 L2。
3. Gen_SList(s1)：生成真分支的语句。
4. Gen_SList(s2)：生成假分支的语句。
5. 两个分支完成后都跳到汇合点 L3

while循环

1
2
3
4
5
6
7
8
9
10
11
12

case while(e, s):
    emit("Label L1:");

    x = Gen_E(e);
    emit("Cjmp(x, L2, L3)");

    emit("Label L2:");
    Gen_SList(s);
    emit("jmp L1");

    emit("Label L3:");
    break;

三个标号的作用：

• L1：判断循环条件。
• L2：执行循环体。
• L3：退出循环。

小结

控制流图 CFG（ Control Flow Graph ）

三地址码是线性排列的，程序分支关系隐藏在 Cjmp、jmp、Label 中，不够直观。

控制流图把这些跳转关系直接画成图

控制流图能够清楚显示程序结构，方便分析：

• 程序中是否存在循环；
• 某个基本块能否执行；
• 某行代码处变量可能是什么值；
• 后续的数据流分析和代码优化。

基本概念

基本块

基本块是连续执行的一组语句，具有两个特点：

• 不能从中间进入，只能从第一条进入。
• 不能从中间退出，只能从最后一条离开。

因此，跳转指令只能出现在基本块末尾

控制流图

控制流图是有向图：

1

G = (V, E)

• ** 结点 V：基本块。 **
• ** 边 E：基本块之间可能发生的跳转**

控制流图的基本定义

控制流图可以看作组织得更精细的三地址码。

普通语句 S

1
2
3
4

S -> x = n
   | x = y + z
   | x = y
   | x = f(x1, ..., xn)

这些是基本块内部顺序执行的普通指令，不负责改变控制流。

跳转语句 J

1
2
3

J -> jmp L
   | cjmp(x, L1, L2)
   | return x

J 决定基本块执行完成后去哪里：

• jmp L：跳到 L。
• cjmp：根据条件选择 L1 或 L2。
• return：退出函数。

基本块 B

1
2
3

B -> Label L;
     S1; S2; ...; Sn;
     J

一个基本块由三部分组成：

1

入口标号 + 普通语句序列 + 结尾跳转

因此每个基本块：

• 开头有唯一的 Label；
• 中间包含若干普通语句；
• 最后必须有一条跳转或返回指令。

函数与程序

1
2

F -> x() { B1, ..., Bn }
P -> F1, ..., Fn

即：

• 一个函数由多个基本块组成；
• 一个程序由多个函数组成。

数据结构

1
2
3
4
5

struct Block {
    Label_t label;  // 基本块入口标号
    List_t stms;    // 普通语句列表
    Jump_t j;       // 结尾跳转指令
};

核心结构就是：

1

函数 → 基本块 → 三地址指令

如何生成控制流图

方法一：直接从抽象语法树生成

1

抽象语法树 → 控制流图

适合控制结构比较规整的语言，例如只有标准的 if、while。

但遇到 C 语言的 goto 等非结构化跳转时，处理会比较复杂。

方法二：先生成三地址码

1

抽象语法树 → 三地址码 → 控制流图 → 汇编

优点：

• 三地址码已经把 if、while、goto 统一成跳转指令；
• 只需要根据 Label、Cjmp、Jmp、Return 划分基本块；
• 更适合 C 这类包含 goto 的语言；
• 阶段划分清楚，编译器更容易实现和维护

由三地址码生成控制流图算法

初始化：

1
2
3

List_t stms;               // 所有三地址码
List_t blocks = {};        // 已生成的基本块
Block_t b = Block_fresh(); // 当前基本块

然后从头到尾扫描每条指令：

1
2
3
4
5
6
7
8
9
10
11
12
13

foreach (s ∈ stms) {
    if (s 是 Label L)
        b.label = L;

    else if (s 是跳转指令) {
        b.j = s;
        blocks ∪= {b};
        b = Block_fresh();
    }

    else
        b.stms ∪= {s};
}

处理规则：

• 遇到 Label L：设置当前基本块的入口标号。
• 遇到普通指令：加入当前基本块的语句列表。
• 遇到 Jmp、Cjmp、Return：设置块的结尾，将该块保存，然后创建新块

控制流图的基本操作

控制流图本质上是有向图，所以可以直接使用图论算法。

常见操作包括：

• DFS/BFS 遍历：判断哪些基本块可以从函数入口到达。
• 生成树：记录遍历过程中基本块之间的关系。
• 必经节点（支配结点）：如果从函数入口到达块 B 的所有路径都必须经过块 A，那么 A 是 B 的必经节点。
• 拓扑序、逆拓扑序：确定分析基本块的处理顺序

死代码基本块删除

1
2
3
4
5
6

while (i < 10) {
    i = i + 1;
    printi(i);
    continue;
    printi(i);     // 永远不会执行
}

执行到 continue 后，会直接跳回循环条件，因此后面的：

1

printi(i);

永远无法执行

删除算法

1
2
3
4
5
6
7
8

dead_blocks_elim(g) {
    dfs(g);

    for (each node n in g) {
        if (!visited(n))
            delete(n);
    }
}

执行过程：

1. 从控制流图的入口基本块开始 DFS。
2. DFS 能访问到的基本块标记为 visited。
3. 遍历所有基本块。
4. 没有被访问的基本块就是不可达块，直接删除

数据流分析

控制流图描述的是“程序可能怎么执行”；数据流分析则进一步研究：

程序沿着这些控制流路径执行时，变量的值或定义可能怎样传播

优化的一般模式

• 程序分析
  分析控制流、数据流、依赖关系等，获得程序的静态信息。
• 程序重写
  根据分析结果安全地修改程序，例如常量传播、删除无用代码

原中间代码 → 程序分析 → 静态信息 → 程序重写 → 优化后的代码

静态保守

判断“某个变量的哪些赋值可能到达某个位置”的分析，叫作到达定义分析。

把变量替换成确定的常量，叫作常量传播

y可能是2或3，保守估计不能常量替换

数据流分析定义

数据流分析是通过静态分析程序代码，获得与程序数据相关的保守信息

必须保证程序分析的结果是安全的

根据优化的目标不同，需要进行的数据流分析也不同

到达定义分析

定义与使用

• 定义（def）：给变量赋值。
• 使用（use）：读取变量当前的值

1
2
3

1: y = 3       // 定义 y
2: Cjmp(x, ...) // 使用 x
7: a = y       // 定义 a，同时使用 y

到达定义分析需要回答在语句 7 使用 y 时，前面的哪些 y 赋值可能到达这里

如果只有y = 3能到达就把a = y优化成a = 3

到达定义

对每个变量的使用点有哪些定义可以到达（即该变量的值是在哪儿赋值的）

定义 d: x = ... 能够到达位置 p，需要满足：

1. 从定义 d 到位置 p 存在一条控制流路径；
2. 这条路径中没有再次给 x 赋值

数据流方程

1
2
3
4

defs[y] = {1, 4, 5}
defs[z] = {2, 6}
defs[x] = {3}
defs[a] = {7}

这里集合里记录的是定义语句编号，而不是变量的具体值

gen

1

gen[d: x = ...] = {d}

意思是当前语句自己产生了一个新的定义

比如 4: y = 6

那么gen[4] = {4}

因为执行第 4 条语句之后，第 4 条语句成为 y 的一个新定义

kill

1

kill[d: x = ...] = defs[x] - {d}

表示当前语句重新给 x 赋值，所以以前对 x 的其他定义都失效了

in，out

1

in[si] = out[si-1]

上一句执行完还能存活的定义，就是这一句执行前能到达的定义

out，gen

1

out = gen ∪ (in - kill)

出去的定义 = 新产生的定义 + 进来以后没有被杀死的定义

从数据流方程到算法

在一个基本块里，语句是顺序执行的，所以“上一条语句的 out 集合”就是“下一条语句的 in 集合”

1
2
3
4
5
6
7
8
9
10
11

// 算法：对一个基本块的到达定义算法
// 输入：基本块中所有的语句
// 输出：对每个语句计算in和out两个集合
List_t stms;      // 一个基本块中的所有语句
set = {};         // 当前到达定义集合

reaching_definition()
    foreach (s ∈ stms)
        in[s] = set;
        out[s] = gen[s] ∪ (in[s] - kill[s])
        set = out[s]

基本块内部从前往后扫描，每条语句用 out = gen ∪ (in-kill) 更新到达定义集合，当前 out 直接作为下一条语句的 in

例子

顺序扫描：上一条 out → 下一条 in，再用 gen/kill 算新的 out

对于一般的控制流图

对于某条语句 s，它可能有多个前驱 p，所以不能再写：

1

in[s] = out[上一条]

而要改成：

1
2

in[s] = ⋃ out[p]
        p ∈ pred(s)

也就是把所有前驱语句的 out 集合取并集，得到当前语句的 in。

然后 out 的计算不变：

1

out[s] = gen[s] ∪ (in[s] - kill[s])

从数据流方程到不动点算法

如果控制流图里有循环，某个语句的 out 又可能反过来影响前面的 in，所以不能只扫描一遍

1
2
3
4
5
6
7
8
9
10
11

while (某些 in/out 集合还在变化)
    foreach (s ∈ stms)
        set = {}

        foreach (s 的前驱 p)
            set ∪= out[p]

        in[s] = set

        out[s] =
            gen[s] ∪ (in[s] - kill[s])

foreach (predecessor p of s)

set ∪= out[p]

即合并所有前驱

1
2
3
4
5

  A
 / \
B   C
 \ /
  D

则：

1

in[D] = out[B] ∪ out[C]

while循环

假设 CFG 有循环：

1
2
3

A → B → C
    ↑   |
    └───┘

第一次算 B 时，C 的信息可能还没算出来。

第一轮B 的 in 不完整

算完 C 后，C 又能回到 B：

1

C.out → B.in

所以要重新算。

不断迭代直到所有 in/out 都不再变化

这就叫达到不动点（fixed point）

例子

活性分析

在代码生成的讨论中，我们曾假设目标机器有无限多个（虚拟）寄存器可用

编译器得判断哪些变量能共用同一个寄存器

寄存器分配的优化任务就需要进行活性分析

活跃变量

在程序的某个位置，如果变量当前保存的值在后面还可能被使用，并且使用前没有被重新定义，那么该变量在这个位置是活跃的

1
2
3
4

a = 1;
b = a + 2;
c = b + 3;
return c;

注意到三个变量的活跃区间互不重叠：

1
2
3

a：第一条语句之后到第二条语句
b：第二条语句之后到第三条语句
c：第三条语句之后到 return

由于 a、b、c 不会同时活跃，因此它们可以交替使用同一个物理寄存器 r

1
2
3
4

r = 1;
r = r + 2;
r = r + 3;
return r;

只有活跃区间发生重叠的变量，才不能分配到同一个寄存器

数据流方程

1
2

1: x = y + z
2: z = z + x

对于任意一条语句 [d: s] ，首先计算两个集合

gen[d: s] = {x | 变量x在语句s中被使用}

kill[d: s] = {x | 变量x在语句s中被定义}

• gen：这条语句要读取哪些变量
• kill：这条语句会重新赋值哪些变量

基本块内的后向数据流方程

对每条语句 s：

• in[s]：执行语句 s 之前的活跃变量
• out[s]：执行语句 s 之后的活跃变量

基本块内部，下一条语句只有一个，因此out[si]=in[si+1]

而一条语句执行前的活跃变量为in[s]=gen[s]∪(out[s]−kill[s])

即执行前活跃的变量= 本条语句要使用的变量 ∪ 执行后仍然活跃、且没有被本条语句重新定义的变量

out[s] - kill[s]

表示从执行后的活跃变量中，删除本条语句重新定义的变量

例子

1
2
3
4

1: a = 1;
2: b = a + 2;
3: c = b + 3;
4: return c;

从最后一条语句向前计算

活性分析是后向数据流分析，因为要判断变量现在的值以后还会不会使用

一般数据流方程

其中 succ[s] 表示语句 s 的所有直接后继

只要变量在任意一条后继路径中活跃，它在当前语句执行后就是活跃的

例子

1
2
3
4
5
6
7
8

1: a = 0
2: b = a + 1
3: c = c + b
4: a = b * 2
5: a < N
   true  -> 2
   false -> 6
6: return c

• in[s]：执行语句 s之前必须保留的变量。
• out[s]：执行语句 s之后仍然需要的变量。
• gen/use：本语句使用的变量。
• kill/def：本语句重新定义的变量

因为程序中存在循环：

1

2 → 3 → 4 → 5 → 2

计算出的活跃信息会沿着循环不断向前面的语句传播，因此一次计算不能得到最终结果

这里同样是用不动点算法，循环到集合不变为止

最终：

干扰图

干扰图用于表示变量之间能不能共用寄存器，是一个无向图G=(V,E)

构造方法：

1. 每个变量对应一个结点。
2. 如果两个变量在某个程序点同时活跃，就在它们之间连边。

边表示：

两个变量的值必须同时保存，不能使用同一个寄存器

代码优化

优化的位置

代码优化并不是编译器中的单独一步，而是可以出现在多个阶段：

1
2
3
4
5
6
7
8
9

源程序
  ↓
词法、语法、语义分析
  ↓
抽象语法树 AST —— 可优化
  ↓
中间表示 IR —— 可多次优化
  ↓
汇编代码 —— 仍可优化

例如：

• AST 阶段：常量折叠、删除恒假分支
• IR 阶段：公共子表达式消除、死代码删除
• 汇编阶段：寄存器分配、指令调度、窥孔优化

前面的控制流、数据流和活性分析，都是为了判断某种优化是否安全

基本概念

什么是代码优化

代码优化是对程序进行的一种语义保持的变换。

“语义保持”就是优化前后程序的可观察行为不能改变，包括：

• 输出结果相同
• 对外部文件、网络等操作相同
• 正常情况下产生相同的副作用

变换的目的是让程序能够比变换前更小、更快、cache行为更好、更节能等等

编译器从业者永不失业定理

图灵已经证明：

不存在一个算法，可以判断所有程序在任意输入下是否会停机

1
2

L:
    jmp L

如果存在“完美优化器”，它需要判断任意程序 p 是否与这个死循环等价，也就是判断 p 会不会终止。但停机问题已经被证明不可判定，因此不存在能够完美优化所有程序的编译器

困难性

不能保证优化总能产生“好”的结果

优化的顺序和组合很关键

很多优化问题是非确定的

优化的正确性论证很微妙

一个编译器拥有足够多且可靠的优化，就可以称为好编译器

编译器优化追求的是“安全、有效、覆盖常见情况”，而不是对所有程序都得到绝对最优结果

优化分类

前端优化

特点：局部、流不敏感，通常直接处理 AST。

“流不敏感”表示不考虑语句之间复杂的控制流关系，只观察当前表达式或语句。

常见优化：

• 常量折叠
• 代数化简
• 简单死代码删除

中期优化

特点：全局、流敏感，通常在 CFG 等中间表示上进行。

“流敏感”表示需要考虑语句的执行顺序、分支和循环。

常见优化：

• 常量传播
• 拷贝传播
• 死代码删除
• 公共子表达式消除

前面学的到达定义、活性分析主要服务于这一阶段。

后端优化

在汇编代码或机器相关的 IR 上进行，例如：

• 寄存器分配
• 指令调度
• 窥孔优化

前端优化

常量折叠

在编译期间直接计算常量表达式的结果

a = 3 + 5 ==> a = 8

if (true && false) … ==> if (false)

可以在整型、布尔型、浮点型等数据类型上进行

算法

1
2
3
4
5
6
7
8
9
10
11
12
13

const_fold(Exp_t e) {
    while (e还在变小) {
        switch (e->kind) {
            case EXP_ADD:
                l = e->left;
                r = e->right;

                if (l是数字 && r是数字)
                    e = 新建数字节点(l->value + r->value);
                break;
        }
    }
}

AST 为：

1
2
3

  +
 / \
3   5

发现左右节点都是常量，就把整个加法节点替换成数字节点 8

异常

不能只按数学规则计算，还要考虑数据类型、溢出和异常：

1

0xffffffff + 1

• 对固定宽度无符号整数，通常回绕为 0
• 对其他类型或语言，结果可能不同
• 除零等表达式还可能产生异常

代数化简

利用代数规律，把表达式改写得更简单。

例如：

1
2

a = 0 + b;    // → a = b
a = 1 * b;    // → a = b

还可以把开销较大的运算替换为较小的运算，这叫强度削弱：

1
2

2 * a    // → a + a
2 * a    // → a << 1

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14

alg_simp(Exp_t e) {
    while (e还在变小) {
        switch (e->kind) {
            case EXP_ADD:
                l = e->left;
                r = e->right;

                if (l是数字0)
                    e = r;
                break;
            case ...: ...; // 类似
        }
    }
}

异常

数学等价不一定代表程序语义等价：

1

(i - j) + (i - j)

不能随意变成：

1

i + i - j - j

原因包括：

• 运算顺序发生变化
• 整数可能溢出
• 浮点运算存在精度误差
• 表达式可能包含副作用

所以代数化简必须根据具体语言和数据类型判断

死代码（不可达代码）删除

静态删除永远不可能执行的代码

在控制流图上也可以进行这些优化，但在早期做这些优化可以简化中后端

1
2
3
4

if (false)
    s1;
else
    s2;

可以直接优化为：

1

s2;

算法

1
2
3
4
5
6
7
8
9
10
11
12
13

deadcode(Stm_t s) {
    while (s还在变小) {
        switch (s->kind) {
            case STM_IF:
                e = s->condition;

                if (e是false)
                    s = s->elsee;
                break;
            case ...: ...; // 类似
        }
    }
}

中间表示上的优化

不同的 IR 会决定优化方法，例如：

• CFG（控制流图）：表示基本块之间“可能跳到哪里”
• CDG（控制依赖图）：表示一段代码是否执行依赖于哪个条件
• SSA（静态单赋值形式）：规定每个变量只被赋值一次，方便数据流分析
• CPS（后续传递风格）：把“程序下一步执行什么”显式表示出来

共同的特点是需要进行程序分析，优化是全局进行的，而不是局部

优化的一般模式

程序分析 → 得到静态信息 → 程序重写

第一步进行控制流、数据流等分析，得到安全、保守的信息；第二步根据这些信息修改程序

常量传播

算法

1
2
3
4
5
6
7
8
9
10

const_prop(Prog_t p) {
    // 第一步：分析每个变量有哪些到达定义
    reaching_definition(p);

    // 第二步：重写程序
    foreach (语句s中的变量xi) {
        if (xi只有一个到达定义，并且是 xi = 常量n)
            用n替换xi;
    }
}

拷贝传播

算法

1
2
3
4
5
6
7
8

copy_prop(Prog_t p) {
    reaching_definition(p);

    foreach (语句s中的变量xi) {
        if (xi唯一的到达定义是 xi = z)
            用z替换xi;
    }
}

死代码删除

语句能够执行，但它产生的结果以后不再使用。

例如：

1
2
3

x = v;
...
return 0;

如果活性分析得到：

1

x ∉ live_out[x = v]

说明执行完 x = v 后，x 的值不再被使用，因此可以删除

算法

1
2
3
4
5
6
7
8
9

dead_code(Prog_t p) {
    // 第一步：程序分析
    liveness_analysis(p);
    // 第二步：程序改写
    foreach (语句s: y = ...) {
        if (y不属于live_out[s])
            remove(s);
    }
}