简介

tokens => lexical analysis词法分析 grammar => syntactic analysis语法分析 typing rules => semantic analysis语义分析 evaluation rules => code generation and optimization代码生成和优化

Operational Semantics

与变量声明类似，这里声明的是运算值

示例说明

变量名和位置map

变量值存储

Cool对象表达方式

特殊场景

其他

Cool Semantics

复杂示例1

复杂示例2

通用表达

示例说明

if条件满足: while条件不满足： while条件满足： 有新申明的变量：

声明对象T通用语法

• 声明内存存放类对象T的所有属性
• 设置所有属性的默认值
• 对象属性初始化
• 返回新对象地址

对象默认值

对象属性初始化

示例说明

e0.f(e1,…,en)的通用语法

• 按照参数顺序e1,…,en处理
• 处理目标对象e0
• 声明X为动态类目标对象
• 获取X的f(有n个参数)定义
• 创建n个新局部变量和一个环境
• 初始化局部变量
• 将self指向目标对象

通用表达式

示例说明

Intermediate Code中间码

简介

在源码与目标码之间的语言； 提供一种抽象的中间层； - 比源码拥有更多细节； - 比目标码少细节； 中间语言等同高级汇编； 每个指令采用三操作数方式；

特点

与汇编代码生成器类似； 可以使用任意个中间寄存器存储结果；

表达式

igen(e,t)表示：在寄存器t中，计算表达式e的值得代码

示例说明

简介

编译流程

L.A. Parsing Semantic A. Opt. Code Gen. 代码优化器是现在编译器中最复杂的，也是耗时最长的。

优化时机

• 对于AST Pro：机器无关 Con：层次太多
• 对于汇编 Pro：暴露优化选项 Con：机器相关 Con：不同目标必须重新实现优化器
• 对于中间码 Pro：机器无关 Pro：暴露优化选项

Basic block基本块

是一个最大指令序列，拥有以下特性： - 没有标签（第一行指令除外） - 没有跳转（最后一行指令除外）

思路

• 不能跳转到基本块内部（第一行指令除外）
• 不能跳出基本块外部（最后一行指令除外）
• 基本块是一个单入口、单出口、单线性代码段

示例说明

一般不能优化。除非能其他地方没有使用t变量。

Control-flow graph控制流图

有以下特点： - 基本块为节点 - 一条边由基本块A指向基本块B，即A的最后一条指令指向B的第一条指令

示例

所有节点都有结束

目的

代码优化主要是提升程序资源利用率，比如： - 执行时间 - 代码大小 - 网络消息 优化不能改变计算结果。 按粒度分有三类优化器： - 局部优化：应用在基本块 - 全局优化：应用在控制流（方法体中） - 函数间优化：应用在跨方法边间 大部分编译器做局部优化，许多会做全局优化，只有少数会做函数间优化。

Local Optimization

最简单的优化器。 主要关注基本块内部。

删除优化

简化优化

常量折叠

在编译时，根据上下文能计算结果的可以优化：

注意

常量优化有时是比较危险的。比如在嵌入式开发中进行交叉编译，浮点数常量会存在精度问题。

不可达优化

代码块没有被其他jump指令跳转即不可达基本块。移除不可达基本块可以减小生成代码大小，有时运行会更快。

单声明

每个寄存器只进行一次声明，减少重复声明。

相同表达式

中间过程寄存器值不变，直接结果赋值。

拷贝传播

代码块中有w:=x的申明，使用x替换w。 一般配合其他优化共同作用，常量折叠、删除优化等。

特点

• 优化器交叉作用
• 编译优化需要不断调用优化器，直到没有提升的可能结束

综合示例

示例1 示例2 初始化代码： 最终形式：

Peephole Optimization

简介

直接应用于汇编代码。 Peephole是一组精简（通常是连续的）的指令序列。 优化器使用等效的代码序列替换它们。

示例说明

示例1

示例2

示例3

特点

与[[#Local Optimization]]相似，要想获得最佳效果必须要不断重复进行优化。

Dataflow Analysis

简介

为使用常量k替换变量x，需要满足条件： - 使用变量x的每条路径均为x:=k

示例说明

X为常量，可以优化： 左边X值改变，不能优化：

特点

• 检测条件是否满足不能太琐碎
• 所有路径包括循环路径和条件分支
• 检测条件依赖全局数据流分析 全局优化任务有几个方法：
• 依靠执行程序已知的属性X
• 依靠整个程序的体系在任意点证明X
• 保守没问题 全局数据流分析是解决这类问题的标准技术。 全局常量传播是一种优化手段，它依赖全局数据流分析。

Constant Propagation

约定

假定需要在每个代码点观测X的值，定义如下符号： 对于每个状态s，可以在s前后迅速得到x的值信息：

规则

Rule 1

前面有声明，则输入为声明

Rule 2

前面存在不同常量，则输入为T

Rule 3

前面所有值为相同常量或未执行，则输入为常量

Rule 4

前面都为未执行，则输入为未执行

Rule 5

输入为未执行，输出为未执行

Rule 6

输入不为未执行，且c为常量，输出为常量

Rule 7

输入不为未执行，且x:=f(…)，输出为声明

Rule 8

输出与输入相同，声明y且y不等于x

通用步骤

1. 程序的每个入口s，初始值为C(s,x,in)=T
2. 除步骤1的每个地方C(s,x,in)=C(s,x,out)=⊥
3. 不断遍历所有状态s，将不满足规则1-8的，进行更新。直到全部s符合规则

示例说明

初始状态 最终状态

Orderings

简化分析表达，可以得到：⊥ < c < T 使用图形表达是 构造函数lub计算最小上边界，例如： lub(⊥,1)=1 lub(T,⊥)=T lub(1,2)=T 任意两点通过图形找到通用的边界 使用lub可以将Rule 1改写为： C(s,x,in)=lub{C(p,x,out)|p是s的前一状态}

特点

• 状态值只能由⊥开始，并持续上升
• ⊥可以变为常数，常数可以变为T
• C(s,x,in/out)最多只能变化两次

Liveness Analysis

简介

如图，第一个X没有被使用，就是dead；第二个X就是live。

基本定义

如何判断变量x在状态s中一直存活： - 存在一个状态s’使用变量x - 有一个路径由s指向s’ - 这个路径中没有重新声明x 若在变量x声明后又遇到x:=…，就说明x存活结束（dead）

规则

Rule 1

Rule 2

Rule 3

Rule 4

通用步骤

1. 初始化所有L(…)=false
2. 重复选择规则1-4中的s，并按照规则更新，直到所有s满足规则1-4

示例说明

特点

• false可以变为true，但不能反向；（即false<true）
• 每个值只能改变一次，因此循环结束有保障
• 使用存活分析，可以消除多余代码很容易 前面介绍的常量传播是正向分析，即信息由输入到输出推出的； 存活分析是后向分析，即信息由输出反向到输入推出的；

Register Allocation

简介

中间码使用大量的临时变量。需要使用与物理寄存器数量匹配的临时变量。 主要方式有： - 为每个寄存器声明多个临时变量 - 不能改变程序行为 简单示例

示例说明

获取每个点存活的变量：

register interference graph

构建一个无向图，这也是寄存器干涉图 - 每个临时变量一个节点 - 边连接的节点不能同时被相同寄存器替代 两个能用相同寄存器存储的节点，不存在边直接连接它们 简单示例

Graph Coloring

简介

边连接的节点有不同的颜色。若图有k种颜色，则它就是k可着色（k-colorable） 其中有多少颜色就需要等量的寄存器。

问题

如何计算图有多少颜色不是很容易的。 - 可以使用heuristics 若需要的寄存器少于颜色 - 可以使用后面讲解spilling

简单方案

步骤： - 在图中选择邻居少于k的节点t - 从图中将节点t和它的边移除 - 若结果图就是k可着色，那这就是原图

泛化步骤： 1. 构造堆栈 - 在图中选择邻居少于k的节点t - 从图中将节点t和它的边移除，并将节点t放入堆栈 - 重复上述步骤直到图为空

2. 为节点涂色

• 从堆栈中获取节点
• 新节点颜色与上色的邻居不一致即可

示例说明

开始的图形： 所有节点少于4邻居： 所有节点入栈： 节点上色： 最终结果：

Spilling

若最终寄存器数量不足，则需要将数据“持久化”。 示例： 使用图中三颜色 可以选择一个节点，比如f将它存入内存。 简化后可以得到满足条件的图 即

具体步骤

• 若颜色优化失败，则声明内存存放f
• 在每处读取f前，增加指令从内存中恢复f再操作
• 在每处写入f后，增加指令将结果写入内存 示例 spilling后的图可以化简为

注意

spilling选定的临时变量有一些要求： - 邻居要尽量多 - 声明少且使用少 - 避免在循环内使用（会增加循环时间复杂度）

缓存管理

简介

编译器擅长管理寄存器，但不擅长管理缓存。编译器可以对缓存进行优化的空间很小。

内存管理

简介

需要对临时对象内存的生命周期进行管理（声明由程序进行）。 如何判断对象是否为不再使用则是内存管理的关键。 示例：

管理方法

标记mark阶段： 清理sweep阶段： 遍历堆中所有对象标记为0的，将其加入到释放列表中

完整过程示例

简介

概述

需要将分解好的Token进行语法匹配，生成抽象语法树(Abstract Syntax Tree , AST）。在此过程中需要检测非法语法，并指出问题所在。 在实现上一般由语法解析器驱动词法分析器进行分析。 实现上一般被称作Parser（解析器）。 语法分析程序产生器YACC，使用根据语法规则生成C语言语法分析器。

Abstract Syntax Tree（抽象语法树）

叶子节点是终止符（[[#定义]]），非叶子结点是非终止符（[[#定义]]）。

原理

Grammars（文法)

定义

文法是用来描述语言的语法成分结构构造的形式规则， 我们通常用G表示。

• 语法成分由句子和构成句子的词素组成
• 语言由句子组成

则将文法G定义为：

其中：

终止符（Terminal）集合为：，也可记为，也可以理解为语言中的字符串，不可分割 非终止符集合为：，也可记为，它需要不断被迭代替换为终止符组成的句子 开始符号为： 产生式为：，它定义了一组符号推导规则

推导

由文法开始符号开始推导， 用产生式的右部取代产生式的左部， 直到推到终结符号为止。 推导分为最左推导和最右推导， 最左推导每次替换式子的最左边， 最右替换每次推导式子的最右边。

示例

假定有文法

对于输入字符串：

可以得到整个推导过程：

规约

规约是句子通过文法规则将产生式的左部取代右部， 直到规约到开始符号为止。 规约也分为最左规约和最右规约。 最左规约和最右推导互为逆过程，同样，最右规约和最左推导互为逆过程。

语言形式

文法具体又可以分为0型文法， 1型文法， 2型文法，3型文法。下面的说明中

0型文法

中的产生式，其中并至少含有一个非终结符，。又叫做短语文法或无限制文法， 识别0型语言的自动机称为图灵机（TM）。

1型文法

中的产生式，除可能有外均有。若有，规定不得出现在产生式的右部。又称为上下文有关文法或者长度增加文法， 通过线性界限自动机（LBA）识别。

2型文法

中的产生式具有形式，其中，。又称为上下文无关文法，记作CFG（Context-Free Grammar）， 通过下推自动机（PDA）识别。

3型文法

中的产生式具有形式，或者，，其中，。又称为正规文法，记作RG（Regular Grammar）， 通过有限状态自动机识别。 Backus-Naur Form（BNF,巴克斯范式）是一种上下文无关文法。 通常研究上下文无关文法和正规文法， 因为程序设计语言的语法和词法规则主要与2型文法和3型文法有关。

Ambiguity（二义性）

一个文法，如果它的一个句子有两棵或两棵以上的语法树，则称此句子具有二义性。如果一个文法含有二义性的句子，则该文法具有二义性。 二义性问题是不可判定问题，即不存在一个算法在有限步骤内，确切判定一个文法是否有二义性。

分析方法

自上而下

从文法的开发符号出发，反复使用各种产生式，寻找“匹配”的推导。 从树的根部开始，构造语法树。 主要方法有：递归下降算法和预测解析器 需要解决的核心问题：回溯问题和文法左递归问题

Recursive Descent Algorithm（递归下降算法）

树的构建过程从上而下，从左往右。

示例 假定有文法

输入字符串为： 第1次解析，推导到，左括号与int不匹配

第2次解析，推导到，左括号与int*T不匹配

第3次解析，推导到，左括号与(E)匹配，继续解析E

第4次解析，推导到，int匹配，继续解析(E)剩余部分

第5次解析，推导到，有括号匹配，解析完毕

实现

定义TOKEN，泛化为tokens类别 定义next为全局指针指向下一个输入的token

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

tokens []TOKEN; // 词法解析的结果
TOKEN next=tokens[0]; // 初始化指向输入点

// 返回输入token类型与指定是否匹配
bool term(TOKEN tok) { return *next++ == tok; }

// 定义E的产生式
// E->T
bool E1() { return T(); }
// E->T+E
bool E2() { return T() && term(PLUS) && E(); }
// E相关产生式
bool E() {
	TOKEN *save = next;
	return (next=save, E1())
		|| (next=save, E2());
}

// 定义T的产生式
// T->int
bool T1() { return term(INT); }
// T->int*T
bool T2() { return term(INT) && term(TIMES) && T(); }
// T->(E)
bool T3() { return term(OPEN) && E() term(CLOSE); }
// T相关产生式
bool T() {
	TOKEN *save = next;
	return (next=save, T1())
		|| (next=save, T2())
		|| (next=save, T3());
}

特点 - 优点 非常容易实现 - 缺点 若部分成功，不会尝试其他推演； 不是适配所有语法 需要单独处理左递归和回溯问题

左递归问题

当存在一种推导路径，算法会陷入无限循环中。根据左递归方式，可以有如下处理方式。

产生式左递归

通用文法记为：，其中不包含起始的 重新改写为：

整体思路：将左递归改为右递归方式，先判断终止符再递归即可防止无限递归。 推导路径左递归

将非终止符按顺序排列，后面的非终止符不应包含前面非终止符的左递归形式，若存在则使用推导方式将其消除。然后就简化为产生式左递归，按照上面方式进行处理即可。

回溯问题

产生式中存在相同终止符开头的选择，算法需要暂时存储上下文，某条分支不匹配又需要重新恢复。消除这种选择即可消除回溯问题。

First Sets（首字符集）

获取字符集（即X = ）的可能包含的第一个终止符（包括），其定义如下：

特性： 若为终止符，则 若，则 若，并且每个都存在，则 若，并且每个都存在，则

Follow Sets（后继字符集）

获取字符集（即X = ）的可能的紧邻的一个终止符（包括文本结尾符），其定义如下：

特性： 若为开始符， 若每个产生式，则 若每个产生式，并且，则

示例

假定有文法

根据产生式(2)，可以得到；再根据产生式(1)，可以得到；综合可得。 同理，可得

得到非终止符的后继字符集：

根据产生式(4)，可得；再加上产生式(3)，可得和；

其他终止符同理，可以得到终止符的后继字符集：

Predictive Parsers（预测解析器）

在递归下降算法基础上，增加预测功能。即向后查看更多的token。 一般使用LL(1)，只预测一个token。

示例

假定有文法

对于产生式(1)要能生效，当前非终止符为，根据产生式(3)输入只能是(和int。 对于，需要根据文法和非终止符逆推非终止符后面可能的输入。比如，右侧有的只有产生式(1)，因，则；再逆推到产生式(3)有，则。具体建表规则间后面。 其他同理，可以得到LL(1)解析表：

步骤

1. 初始化栈为，并初始化next指向下一个输入token；
2. 获取栈顶两个元素；
3. 若为非终止符，则根据和输入token查找解析表。若命中表达式，则将重新入栈；若未命中则直接报错；
4. 若为终止符，则判断是否与输入token匹配，next指向下一个token。若匹配则将重新入栈；若未命中则直接报错；
5. 重复步骤2-4，直到栈为空；

使用表格推演示例解析输入过程：

解析表构建方法

对于文法需要构建LL(1)解析表，则每个产生式进行如下处理： - 每个终止符，都有 - 若存在，则每个终止符都有 - 若存在并且，都有

注意，对于表格项。若为空或多个不同值，则解析异常。

自下而上

从输入字符串开始，逐步进行归约，直到文法的开始符号。 从树的叶节点开始，构造语法树。 主要方法有：算符有限分析法和LR分析法 需要解决的核心问题：识别可规约串

算符优先法

特点

优点：简单，快速 缺点：可能错误接受非法句子 适用范围：用于分析各类表达式

示例

假定有文法

可以得到优先关系表：

优先关系表构建方法

下面小写字母为终结符，大写字母为非终结符。 - 确定满足关系的所有终结符对 ，当文法G中含有形如或的产生式 - 确定满足关系和的所有终结符对 ，当文法G中含有形如的产生式，而或；记为 ，当文法G中含有形如的产生式，而或；记为

关键转换为构建FIRSTVT(P)和LASTVT(P)。

构造FIRSTVT(P)的算法，反复使用下面规则： - 若有产生式，则 - 若，且有产生式，则

FIRSTVT(P)算法伪码：

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

BEGIN
	FOR a,P in Vt,Vn DO
		F[P, a] := FALSE;
	FOR Product in G DO
		F[P, a] = TRUE;
		INSERT(P, a); // into STACK, P->a... P->Qa...
	WHILE STACK not empty DO
	BEGIN
		Q,a := top of STACK
		FOR Product in G DO
			F[P, a] = TRUE;
			INSERT(P, a); // P->Q...
	END OF WHILE;
END

LASTVT(P)伪码类似，按照定义编写即可。 优先关系表算法伪码：

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

FOR PRODUCT in G DO
BEGIN
	FOR i:=1 TO n-1 DO
	BEGIN
		IF Xi,Xi+1 in Vt THEN Xi EQ Xi+1
		IF i<=n-2 && Xi,Xi+2 in Vt && Xi+1 in Vn THEN Xi EQ Xi+2
		IF Xi in Vt && Xi+1 in Vn THEN
			FOR a in FIRSTVT(Xi+1) DO
				Xi LT a
		IF Xi in Vn && Xi+1 in Vt THEN
			FOR a in LASTVT(Xi) DO
				a GT Xi+1
	END
END

素短语

定义

一个文法G的句型是指一个短语，它至少包含一个终结符，并除它自身以外不再含任何更小的素短语。 最左素短语是指处于句型最左边的素短语。

定理

算符优先文法句型一般形式：。 一个算符优先文法G的任何句型的最左素短语满足如下条件的最左子串，

获取最左素短语伪码，其中LTD:, GTD:, EQD:, ：

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

k := 1;
S[k] := '#';
REPEAT
	a := READ string;
	IF S[k] in Vt THEN j:=k ELSE j:=k-1;
	WHILE S[j] GTD a DO
	BEGIN
		REPEAT
			Q:=S[j];
			IF S[j-1] in VT THEN j:=j-1 ELSE j:=j-2
		UNTIL S[j] LTD Q
		S[j+1]...S[k] => N
		k:=j+1
		S[k]:=N
	END OF WHILE
	IF S[j] LTD a OR S[j] EQD a THEN
		BEGIN k:=k+1;s[k]:=a END
	ELSE  ERROR
UNTIL a='#'

LR分析法

基本概念

1965年由Knuth提出“the art of computer programming” L：从左到右扫描输入串 R：自下而上进行归约

定义

令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有

则β称是句型相对于非终结符A的短语 如果有，则称β是句型相对于规则的直接短语 一个句型的最左直接短语称为该句型的句柄 规范归约是最左归约 规范归约的逆过程就是最右推导

最右推导也称为规范推导 由规范推导推出的句型称为规范句型 活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即对于规范句型，β为句柄，如果， 则符号串是的活前缀。（必为终结符串）

分析过程

假定初始格局为：

分析器根据确定下一步动作 1. 若为移进，且s为下一状态，则格局变为： 2. 若为按归约，格局变为： 此处，，r为β的长度， 3. 若为“接受”，则格局变化过程终止，宣布分析成功。 4. 若为“报错”，则格局变化过程终止，报告错误。

LR(0)项目

有四个项目