编译原理笔记

编译原理学习笔记。参考：

​ 编译原理(中科大)：https://www.bilibili.com/video/BV16h411X7JY?p=1

​ 编译原理(哈工大)：https://www.bilibili.com/video/BV1zW411t7YE?p=1

笔记是根据书+网课+本校课程按照理解过程记录，和书或网课的顺序不一致。主要的算法都是来自《现代编译原理：c语言描述》(虎书)，因为与一般学习编译原理用的龙书有差异，将需要注意的情况在下面列出，这些不同主要在语法分析部分，不影响语法分析的算法思想和过程，列出来仅是为了避免在学习过程中产生困惑。

• 自顶向下的语法分析计算了NULLABLE集，FIRST集，FOLLOW集，FIRST_S集，其中的FIRST_S集更常见的说法是SELECT集。
• 使用算法计算FIRST(N)集时，没有将空串加入FIRST集，这是因为已经计算了NULLABLE集，不需要把空串包含到FIRST集当中了。
• 在使用虎书的方法计算FIRST集，FOLLOW集中，不包含#符号和$符号，实际这两个符号也只是标记结束，不影响语法分析过程。

第一章 引论

1.语言处理器

• 编译器
• 解释器

2.编译器的结构

• 词法分析：将语素转换为词法单元
• 语法分析：使用词法单元创建树形的中间表示，常用语法树。
• 语义分析：检查源程序是否和语言定义的语义一致，并进行类型检查。
• 中间代码生成
• 代码优化
• 代码生成：以源程序的中间表示形式作为输入，映射到目标语言。

3.程序设计语言的发展历程

4.编译器相关科学

5.编译技术应用

6.程序设计语言基础

• 静态和动态的区别：使用的策略可处理编译时刻可决定的问题，则为静态策略；一个只允许在运行程序时作出决定的策略则为动态策略。
• 声明的作用域：仅阅读程序就可以确定一个声明的作用域，则该语言使用的是静态作用域。
• 环境：名字到存储位置的映射。
• 状态：内存位置到值的映射。
• 块结构：{}界定一个块。
• 静态作用域规则：如果名字x的声明D属于B块，那么D的作用域包含整个B，但是以任意深度嵌套在B中，重新声明了x的所有块C不在此作用域中。
• 动态作用域：一个作用域策略依赖于一个或多个在程序执行时刻才能知道的因素，就是动态的。

//动态作用域例：
#define a (x+1)
int x = 2;
void b() { int x =1; printf("%d\n",a);}
void c() {printf("%d\n",a);}
void main(){b();c();}

• 参数传递：参数可以通过值或引用的方式从调用过程传递给被调用过程。通过值传递传递大型对象时，实际被传递的是指向这些对象的引用。
• 别名：当参数被以引用传递方式传递时，两个形式参数可能会指向同一个对象，这会造成一个变量的修改改变了另一个变量的值。

第二章 词法分析

在开始词法分析之前，需要了解一些基本概念。

1.词法&语法分析基本概念

字母表

字母表是有穷符号的集合。两个字母表可以进行乘积，幂，正闭包，克林闭包运算。

• 乘积：{0,1}{a,b} = {0a,0b,1a,1b}
• 幂：{0,1}^3 = {0,1}{0,1}{0,1}
• 正闭包：{a,b,c,d}+ = {a,b,c,d,aa,ab……}
• 克林闭包：{a,b,c,d}* = {a,b,c,d}+ ε(空串)

串

串是字母表中符号的一个有穷集合，串s的长度通常记作|s|。串的运算为连接和幂，串x=str1，y=str2，则xy=str1str2，幂运算同理。 **文法**

文法是用来描述语法结构(语言规则)的。一个自然语言的文法例子如下： - <句子> -> <名词短语><动词短语> - <名词短语> -> <形容词><名词短语> - <名词短语> -> <名词> - ...其他规则 - <形容词> -> {...} - <名词> -> {...}

文法的形式化定义：G=(Vt,Vn,P,S)。

• Vt：终结符集合。终结符是文法所定义语言的基本符号。例如Vt={difficult，parse，course…..}
• Vn：非终结符集合。非终结符是表示语法成分的符号，也被称为语法变量。例：{<句子>，<名词短语>，<动词>……}

• P：产生式集合。产生式描述了终结符(基本符号)和非终结符(语法成分)组成串的方式。一般形式为：α→β。例如：<句子>→<动词短语><名词短语>。另外，同一个非终结符(语法成分)的产生式可以组合在一起表示，用|分隔：
  list → list + digit，list → list-digit可以合并成list → list+digit | list-digit。(|的优先级最低)

• S：开始符号，文法中最大的语法成分。例：S=<句子>

有了语言规则，就可以判断一个词串是否是一个语言的句子了。句子可以进行推导，也可以进行规约，分别对应着生成语言和识别语言的角度，下面是自然语言的例子：

2.词法分析和词法分析器

词法分析是编译的第一个阶段，任务是把源程序的输入字符(词素)转换为已知语言的成分(词法单元序列)。转换后的词法单元序列会交给语法分析器进行语法分析。通常语法分析起有一个getNextToken命令让词法分析器读取输入字符，直到词法分析器能识别一个词素，并将该词素生成为词法单元交给语法分析器。实现一个词法分析器有两种方式，第一种是手动用代码实现(需要画状态转移图辅助)，另一种是使用词法分析器生成工具(需要使用正则表达式描述出词素的模式)。

下面是词法分析使用的术语：

• 词法单元：由一个词法单元名和一个可选属性值组成。词法单元名是表示词法单位的抽象符号，属性值表示了词法单元的相关信息。比如一个词法单元“id”表示程序设计语言的标识符，那么属性值就是指向这个具体的标识符信息(在符号表里)的指针；一个词法单元“number”表示数字常量，那么属性值就是这个数字常量的具体值。
• 模式：描述了一个词法单元的词素可能具有的形式。
• 词素：源程序的一个字符序列，和一个词法单元的模式匹配，可以被识别为一个词法单元的实例。

例：

3.输入缓冲

识别输入流中的词素之前，首先要读入输入流。为了处理输入的字符，需要使用两个缓冲区。每个缓冲区容量都是N个字符，通常N是一个磁盘块的大小。处理读入字符流时有两个指针，lexemeBegin指针指向当前词素的开始处，forward指针一直扫描，直到发现某个模式匹配为止。如果forward已经扫描到了EOF，就再读入N个字符到另一个缓冲区，这样只要词素的长度不大于N，就不会在识别到词素之前覆盖掉缓冲区中的词素。EOF也被称为哨兵标记，输入的末尾和缓冲区的末尾都有该字符。

*4.正则表达式

正则表达式是用来描述语言的一种方式，可以描述字母表上的符号通过并，连接，闭包这些运算而得到的语言。用符号给正则表达式命名，然后进行定义，写法与文法很相似，例如用正则表达式表示无符号数(5280,0.01234,6.336E4，1.89E-4)的串number：

digit ——→ 0|1|...|9
digits ——→ digit digit*
optionalFraction ——→ . digits | e
optionalExponent ——→ (E(+|-|e)digits) | e
number ——→ digits optionalFraction optionalExponent

正则表达式还有一些扩展的写法，如后缀+表示语言的及其正闭包，后缀?表示零个或一个出现，字符类可以用[a-z]表示a|b|...|z。

5.状态转换图

构造一个状态转换图可以体现词素转换的过程，每识别一个字符，就更新到下一个状态，如果已经找到了词素对应的词法单元，当前的字符不是上一个词法单元中的一部分，则要让forward指针回退一个位置。下面这个例子清晰的表现了状态转换图是怎么体现词素识别过程的。

对于保留字(if，else)的识别，通常为这些保留字建立单独的状态图。也可以将其先填入符号表中，识别该词法单元后，如果符号表中没有该符号，就说明不是保留字，添加到符号表，并返回条目指针作为属性。

6.词法分析工具Lex

开始介绍词法分析时，提到了将词素转换为词法单元有两种方式：第一种是手动用代码实现(需要画状态转移图辅助)，另一种是使用词法分析器生成工具(需要使用正则表达式描述出词素的模式)。画状态转移图的方式已经介绍过了。而Lex就是另一种方式的工具，即词法分析器生成工具。

Lex中，使用正则表达式描述词法单元的模式，Lex编译器将输入的模式转换成一个状态转换图，并生成相应的实现代码，存放到lex.yy.c文件中。Lex编译器编译的内容是由Lex语言表示的。因此Lex的使用方式如下：

Lex程序结构如下：

声明部分
%%
转换规则
%%
辅助函数

• 声明部分：包括变量和明示常量(如一个词法单元的名字)。
• 转换规则：形式为：模式{动作}，模式为正则表达式，动作则是代码片段。
• 辅助函数：各个动作需要的辅助函数。

仅看上面的结构很难理解Lex程序到底是怎么构造的，需要结合下面这个例子来理解各个部分：

%{
	/*明示常量:LT,LE,NE,...,ID,NUMBER...*/
    /*这部分(%{%})里面的内容会直接复制到C代码中*/
    #define LT 10000
    ......
%}

/* 一些正则表达式 */
delim   [ \t\n]
ws 	    {delim}+
letter	[a-zA-Z]
digit	[0-9]
id		{letter}({letter}|{digit})*
number	{digit}+(\.{digit}+)?(E[+-]?{digit}+)?						//\.表示‘.’
%%
    
{ws}	{}
if		{return(IF);}												//保留字先被列出
then	{return(THEN);}
else	{return(ELSE);}
{id}	{yyval = (int)installID();return(ID);}
{number}{yyval = (int)installNum();return(NUMBER);}
"<"		{yyval = LT;return(RELOP);}
......
%%
    
int installID(){
    /*
    将找到的词素放到符号表中
    返回一个指向符号表的指针到yyval，这是个全局变量，语法分析器或编译器等后续组件可以使用
    把词法单元名返回到语法分析器。
    */
}
...

最后，如果Lex遇到了冲突，即一个词素可以被识别为多种词法单元，按照以下规则处理：

• 选择最长前缀(例如选择<=，而不是<)。
• 有多个模式可匹配，选择在Lex中先被列出的。

书中还提到了关键字不是保留字的情况，这里不讨论。

*7.有穷自动机

以上已经说明了Lex的使用，下面说明Lex是如何将输入程序变成一个词法分析器的。转换的核心是被称为有穷自动机(FA)的表示方法。自动机本质上是与状态转换图类似的图，由许多状态构成，不同状态之间通过有向的标号(标记)可以转换。

• 有穷自动机是识别器，只能对可能的输入串回答’是’或’否’。
• 有穷自动机分为两类：
  • 不确定的有穷自动机(NFA)：对其边上的标号没有限制，可以是空串，且一个符号可以标记离开一个状态的多条边。(一个状态接收到一个符号后，可能到达不同的状态)
  • 确定的有穷自动机(DFA)：对于每个状态及自动机输入字母表中的每个符号，有且只有一条离开该状态，以该符号为标号的边。(一个状态接收一种符号，只到达一种下一状态)

7.1 不确定的有穷自动机(NFA)

一个NFA由以下几个部分组成：

不管是NFA还是DFA，实际上都可以用转换图来表示，但是NFA与状态转换图的不同在于：

• 同一个符号可以标记从同一状态到多个目标状态的边。(一个符号可以转换到不同状态)
• 标号不仅是字母表中的符号，还可以是空符号串ε

下面是一个识别正则表达式(a|b)*abb的NFA的转换图:

上面的状态3表示串被接收，所有该FA接受的串构成的集合记为L(M)，称为被该FA定义(或接收)的语言。从状态0接收到‘a’，可能到达状态0，也可能到达状态1，因此这个FA是不确定有穷自动机NFA。除了状态转换图以外，转换表也可以表示NFA，以下是上图的NFA对应的转换表：

上面已经看到NFA接收一个符号，可能转换到不同状态的特点了，下面的例子展现了另一个特点，空串也可以作为状态转换的标号：

7.2 确定的有穷自动机(DFA)

DFA是NFA的特例，特点是：

• 没有输入ε的转换动作。
• 每个状态s和符号a，只有一条标号为a的边离开s。

DFA相对于NFA识别更加具体和简单，因为一个符号只能导致从一个状态转换到另一个特定的状态(而不是不确定的多个状态)，由于每个NFA都可以转变为一个接收相同语言的DFA，实际上我们模拟和实现的都是DFA。

*8.正则表达式到自动机

介绍自动机是要说明Lex词法分析的过程。自动机本质其实就是状态机，可以说Lex的工作就是根据自动机的状态变化产生词法分析代码。我们输入Lex的是正则表达式，因此Lex要先把这些正则表达式转化为自动机。通常先把正则表达式转换为NFA，再把NFA转换为DFA(因为直接从正则表达式构建DFA比较复杂)。

8.1 正则表达式到NFA

对正则表达式进行NFA的构造只要按照以下规则：

8.2 NFA到DFA

有了NFA后，需要将NFA转换为DFA。这个过程采用的是子集构造法。基本思想是：DFA的每个状态是NFA的状态集合(例如NFA中的某个状态A，得到字符x后可能回到A，可能到B或C，那么转换到DFA后，ABC就是为一个状态集合，表示DFA中的一个状态。)。下面直接看两个例子：

8.3 DFA最小化

对于同一个语言，存在多个识别该语言的DFA。使用DFA来实现词法分析器，总是希望使用的DFA状态数最少。因此需要进行DFA最小化。DFA最小化通常使用的是Hopcroft算法，也称为基于等价类的算法。

该算法的原理是，假设有一个状态集合S，如果有一个字符c，可以将S切割，那么这个S就被切割成S1，S2。不断的进行切割，直到不可切割时，每个集合S1，S2...中的状态就是可以合并的。字符c可以切割S这样解释，假设状态1,2,3一开始都在集合S中，状态1和状态2接收到字符c都转换为状态4，而状态3接收到c不转换到状态4，那么就说字符c可以切割集合S，集合S被切割成S1(状态1，状态2)和S2(状态3)。最开始的时候，现将所有状态分成两个集合，接收状态的集合和非接受状态的集合。该算法的描述如下：

split(S)
    foreach (character c)
    	if(c can split S)
            split S int T1,...,Tk
hopcroft()
    split all nodes into N,A
    while (set is still changes)
    	split(S)

9.DFA到词法分析器代码

能够从正则表达式构建NFA，将NFA转换到DFA并最小化，最后一步就是将DFA转变成词法分析器的代码。DFA是一个有向图，可以表示为转移表，哈希表等不同的表示，具体的表示取决于在实际实现中对时间空间的权衡。

先看一下转移表的表示：

状态\字符	a	b	c
0	1
1		1	1

状态的变化可以直接查表，再加上驱动代码就可以构成词法分析器：

nextToken(){
    state = 0;
    stack = [];
    while(state!=ERROR){
        c = getchar();
        if(state is ACCEPT) clear(stack);
        push(state);
        state = table[state][c];
    }
    while(state is not ACCEPT){
        state = pop();
        rollback();
    }
    if(state is ACCEPT) return ACCEPT_TOKEN;
}

还有使用跳转表的代码实现，使用goto语句进行状态跳转，if语句进行字符判断并状态跳转。这样实现的方式优点是不需要存储状态表，当状态表很大，状态非常多的时候，这样能节省许多空间。

第三章 语法分析

语法分析的任务是根据给定的文法识别输入句子中的各个成分，并构建抽象语法树。在构建抽象语法树前，首先根据输入的串和给定的文法构建语法分析树。如果输入串的各个单词从左自右为分析树的叶子节点，那么这个串就是该语言的一个句子。然后通过语法制导翻译，产生抽象语法树。

下面先考虑语法分析树的构造，按照分析树的构造方向，语法分析可以分为两类：自顶向下的语法分析，自底向上的语法分析。

在语法分析中，使用上下文无关文法(CFG)来描述语言的规则。一个上下文无关文法的定义为:G=(T,N,P,S)

• T：终结符集合
• N：非终结符集合
• P：一组产生式规则
• S：唯一的开始符号

1.自顶向下分析概述

自顶向下从根节点向底部节点构造分析树，可以看成是从文法开始符号S推导出词串w的过程。

在进行推导的过程中需要解决两个问题：

• 替换当前句中的哪个非终结符
• 用该终结符的哪个候选式进行替换

对于第一个问题，有两种选择方式：最左推导；最右推导。

• 最左推导：总是选择每个句型的最左非终结符进行替换。
• 最右推导：总是选择每个句型的最右非终结符进行替换。

对应于推导，语法分析也可以使用规约的方式，因此有相应的最左规约和最右规约。

在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范归约，而最右推导相应地称为规范推导。

一个串总是自左向右进行语法分析，因此自顶向下的语法分析采用最左推导的方式。构造语法分析树时，选定最左非终结符的产生式，将串的字符与产生式相匹配。

例：

自顶向下语法分析是具体通过递归下降分析实现的。递归下降分析中，每个非终结符都有一个过程，从文法开始符号的S对应过程开始，递归调用文法中其它非终结符对应的过程，直到整个输入串都被扫描。

2.自顶向下分析

2.1 需要回朔的自顶向下算法

自顶向下分析的伪代码描述如下：

tokens[];
i=0;
//栈中一开始只有开始符号
stack=[s];								
while(stack!=[])
    if(stack[top] is a terminal t){
        //匹配成功
        if(t==tokens[i++]) pop();
        //匹配失败，要把刚刚入栈的元素出栈，换回原来的非终结符
		else backtrack();
    }
	else if(stack[top] is a nonterminal T){
        //非终结符出栈，换为产生式中的成分，从右往左入栈
        pop();
		push(the next right hand side of T)
    }

在尝试用产生式进行匹配时，不可避免的需要进行回朔，这导致分析效率存在极大的问题。实际情况中，总是需要线性时间的算法，因此有了递归下降分析算法和LL分析算法。

2.2 递归下降分析(预测分析算法)

递归下降分析算法是自顶向下分析算法的一种，通过前看符号避免回朔，基本思想如下：

• 每个非终结符构造一个分析函数
• 用前看符号指导产生式规则的选择

示例如下：

//产生式
X -> aBcD   
	|bD
B -> …   
D -> …         
//每个非终结符的函数
parse_X(){
    token = nextToken();
    if(token==a){
        move token;
        parse_B();
        if(token==c){
            move token;
            parse_D();
        }
        else error();
    }
    else if(token==b){
        move token;
        parse_D();
    }
    else error();
}

当产生式的多个选择中含有公因子，前看符号就无法指导分支选择了，因此需要提取左公因子，方法如下：

A -> aB1
	|aB2
	|aB3
	...
# 提取左公因子
A -> aA'
A'->B1|B2|B3|...

另一个可能出现的问题是，当产生式为一个递归式时，将无法调用产生式右部非终结符的分析函数，因此需要将左递归消除，方法如下：

A -> Aa|B
# 消除左递归
A -> BA'			#推导结束的时候，一定有一个B在开始的位置上
A'-> aA'|ε			#B之后有多个a

有些情况，使用以上方法并不能消除掉左递归，也就无法通过一个前看符号预测正确的产生式。一个上下文无关文法不一定有对应的无回朔文法，是否存在对应的无回朔文法是不可判定的。

2.3 LL(1)分析算法

LL(1)分析算法是另一种自顶向下分析算法。LL(1)表示从左向右分析，使用最左推导，采用一个前看符号。该算法的基本思想是使用分析表来指导产生式规则的选择，因此被称为是一种表驱动的分析算法。

tokens[];
i=0;
//栈中一开始只有开始符号
stack=[s];								
while(stack!=[])
    if(stack[top] is a terminal t){
        //匹配成功
        if(t==tokens[i++]) pop();
        //匹配失败，要把刚刚入栈的元素出栈，换回原来的非终结符
		else backtrack();
    }
	else if(stack[top] is a nonterminal T){
        //非终结符出栈，换为产生式中的成分，从右往左入栈
        pop();
		push(the next right hand side of T)
        //↓ 使用分析表确定将哪个具体的产生式入栈
    }

从每个产生式S开始推导，最终产生的句子可能有多种开头，分析表就是基于这些开头进行前看分析的。这些开头的集合称为FIRST_S(p)集，这个集合也一般被称作SELECT集。而产生式的开头可能是什么非终结符，又是由产生式开头的非终结符N决定的。非终结符N开始推导得出的句子开头的所有可能终结符集合为FIRST(N)集。

FIRST(N)集的获取，只要对N的产生式的开头的非终结符进行替换，直到替换到终结符就可以了，所有最终替换到的终结符的集合就是FIRST(N)集。但是要考虑到开头的非终结符最终可能为空串，那样的话，整个非终结符N的开头就不是由开头的非终结符产生的了。例如N->XY，而X->ε|a，那FIRST(N)就不仅仅是{a}，还要考虑Y最终可以替换为什么终结符。因此还需要考虑哪些非终结符最终能产生空串，这些非终结符的集合称为NULLABLE集。

一个非终结符X属于NULLABLE集合由以下两种情况：

• X->ε|…
• X->Y1Y2…Yn，Y1-Yn都属于NULLABLE集

NULLABLE集的产生过程如下：

//伪代码描述
NULLABLE={};
while (NULLABLE IS STILL CHANGING){
    foreach(产生式：X->β)
        if(β==epsilon)
            NULLABLE ∪= {X}
    	if(β==Y1Y2...Yn){
            if(Y1,Y2,...Yn∈NULLABLE)
                NULLABLE ∪= {X}
        }
}
//进一步伪代码描述
NULLABLE={};
while (上一轮结束，NULLABLE集还在变化){
    foreach(遍历每一条产生式：X->β)
        if(β为空串)	X添加到NULLABLE集当中;
    	if(β为Y1Y2...Yn){
            if(Y1,Y2,...Yn都在NULLABLE中，都可以推导到空串)
                X添加到NULLABLE集中;
        }
}

考虑了空串的FIRST(N)集算法如下：

//伪代码描述
foreach (N)
    FIRST(N)={}
while(set is changing){
    foreach(N->X1X2...Xn){/*对每个产生式更新FIRST(N)*/
        foreach(Xi){
    		if(Xi==a){/*终结符并入集合*/
                FIRST(N) ∪= {a}
                break
            }
            if(Xi==M..){/*非终结符要确认是不是在NULLABLE中*/
                FIRST(N) ∪= FIRST(M)
                if(M not in NULLABLE) break
            }
        }
    }
}

考虑一个产生式的第一个符号，存在这样一种情况，s->N1N2，N1N2可以为空串，这时就没办法知道什么时候使用产生式s了，为了知道什么时候使用产生式s，需要知道非终结符N后面会跟什么符号，N后面会出现的符号集合称为FOLLOW(N)集。

FOLLOW(N)集的算法如下：

//伪代码描述
while(有任何非终结符的FOLLOW集还发生变化){
    for(每个产生式N->β1...βn){
        tail = FOLLOW(N);
        for(i=n;i>0;i--){
            if(βi==a) tail = a;
            if(βi==M){
                FOLLOW(M) ∪= tail;
                /*M可以为空串，则M前面出现的非终结符的FOLLOW集包含FIRST(M)，也包含M后面可能出现的终结符，因此这里是并*/
                if(M in NULLABLE) tail ∪= FIRST(M);
                else tail = FIRST(M);
                /*如果M不可以为空串，那么M前面的非终结符的FOLLOW集只有FIRST(M)，不能有M后面的东西了*/
            }
        }
    } 	
}

计算FOLLOW集是一个遍历产生式，对每个非终结符出现的情况，向非终结符的FOLLOW集添加元素的过程。

有了NULLABLE，FIRST，FOLLOW集，就可以求产生式的FIRST_S集(SELECT集)了。

calculate_first_s(p:N->b1b2...bn){
    for(i=1;i<=n;i++){
        if(bi==a){
            FIRST_S(p) ∪= {a};
            return;
        }
        if(bi==M){
            FIRST_S(p) ∪= FIRST(M)-ε;
            if(M not in NULLABLE) return;
        }
    }
    /*整个产生式的元素都可以走到空串*/
    FIRST_S(p) ∪= FOLLOW(N);
}

需要注意，SELECT集即FIRST_S集中不含有空串。有了FIRST_S集(SELECT集)，分析表的填写就很容易了，例如产生式p1，p2都是N的产生式，就在分析表上N的一行上，哪个终结符在FIRST_S(p1)/SELECT(p1)当中就在哪一列填写产生p1，p2同理。

3.自底向上分析

自底向上分析是另一种语法分析的方式，与自底向下的推导不同，自底向上是一个规约的过程。自底向上分析中最重要的是LR分析算法，即移进-规约算法。使用这种分析方法，对记号流进行规约时，使用一个 · 将已经读入的和未读入的输入分开。用一个栈表示读入的记号，读入的记号入栈，称为移进，栈顶的一些元素匹配产生式，将这些元素出栈，产生式左部入栈， 称为规约。

什么时候进行移进，什么时候进行规约，实际上也是通过预先构造的分析表完成的。分析表为以下形式：

其中的$表示结束，表示可以接收，结束语法分析。通常将需要分析的文法进行拓展，补充一条产生式。例如一个文法由S开始，在这个文法中加入一条产生式S'->S$，其他产生式不变，然后再进行语法分析。这个新的文法也被称为是原文法的增广文法。分析时使用两个栈，一个状态栈，一个记号栈，根据上面的分析表进行移进和规约。状态栈栈顶根据记号栈栈顶进行状态变化。

重点就在于构建分析表，考虑不采用前看符号的自顶向下分析，即LR(0)算法中，分析表的构建。

3.1 LR(0)

LR(0)分析算法中分析表的构造分为两个步骤：

• 构造DFA
• 根据DFA生成LR(0)分析表

构造的DFA形式如下，每一个产生式被称作一个项目，每一个状态是状态集或者称为项目集。可以看出通过终结符产生的状态是移进的过程，通过非终结符产生的状态是规约。遇到了非终结符，就将遇到的非终结符的产生式加入到状态中。这一步也被称为求项集的闭包。

根据DFA构造分析表的过程比较简单，注意移进，规约，转移这三个动作就可以了。在分析表中，用sn表示移进，rn表示规约，gn表示转移。

3.2 SLR分析算法

LR(0)分析算法有两个缺点。第一个缺点是延迟了错误发现的时机，当已经读入的记号可以规约时，就进行规约，哪怕后续的记号是错误的，也先把读入的全部规约后才发现后续的错误；另一个缺点是可能存在冲突，例如有产生式S->T和S->T+，既可以移进也可以规约，无法一步作出正确的选择。为了解决LR(0)分析算法的问题，在LR(0)的基础上，修改规约表项的生成，就是SLR分析算法。

SLR分析算法相比于LR(0)的修改之处为：生成分析表时，若某状态包含A->α·，只对FOLLOW(A)中的输入记号添加对产生式A->α的规约操作。因此对于上面在LR(0)中已经见到过的分析表，使用SLR分析算法构建的表如下：

如果最终产生的分析表没有冲突项，那么就说这个文法是SLR文法。可能的冲突有两种：移进-规约冲突；规约-规约冲突。在分析表中，体现为一个状态在接收到一个符号后，既可以移进又可以规约，或有两个不同的规约方法。

3.3 LR(1)分析算法

在SLR分析算法中，最终得到的分析表仍然可能存在冲突，因为进行规约时，对于非终结符A，只要后面出现了FOLLOW(A)的元素就进行规约。分析表的作用就是为了选择正确的产生式，但是FOLLOW(A)对于确认在哪个产生式中发生了规约是不够精确的。因此考虑采用前看符号，确认产生式的选择，即采用LR(1)分析算法。

LR(1)中定义项目为[X ➝α•β, a]，其含义是： - 已读入α - 剩余的输入能够匹配βa；若β=ε，可以用该条产生式归约（α归约成X）

LR(1)分析算法其他和LR(0)相同，仅状态集的产生和归约表项的产生不同。

• 状态集(项目集)的产生：对项目为[X ➝ α •Y β, a]，添加[Y -> • γ,b]到项目集(状态集)，其中b属于FIRST_S(βa)

• 归约表项的产生：对包含项目[X ➝ α β •, a]的状态，对输入a产生该产生式的归约项rn

下面是一个LR(1)中产生项集闭包的例子，可以看到第一条产生式中遇到非终结符S，而第一条产生式S后面只有$，因此下面添加S的产生式到项集时，前看符号是FIRST_S($)={$}；第二条产生式遇到了L，L后面是=R，该条产生式的前看符号是$，因此下面添加L的产生式到项集时，前看符号是FIRST_S(=R$)={=}。

最后总结一下自底向上分析的步骤：

• 向原文法添加产生式S’->S$，产生增广文法
• 使用DFA构造法产生状态转移过程，每个状态是一个项集
• 根据DFA生成分析表
• 利用状态栈和记号栈，使用分析表进行自底向上分析

4.语法制导翻译

语法分析结束后，需要进行语义分析和中间代码生成，这两步可以合称为语义翻译，语义翻译可以在语法分析时一并完成，因此语法分析，语义分析，中间代码生成可以合称为语法制导翻译阶段。

4.1 概述

以上所述的语法分析的过程中，最终将给定的句子按照给定的文法构建了一颗语法分析树，在这个过程中也判断了句子是否是合法的。但是仅仅完成以上的工作还不够，语法分析还需要产生抽象语法树，并完成类型检查，目标代码生成，中间代码生成等工作。这些后续的工作，可以通过语法制导翻译完成。

语法制导翻译(SDT)是语法分析指导下的翻译，用于生成抽象语法树，语义分析以及生成中间代码。翻译的方法是在语法分析时，给产生式附加一个动作。翻译动作包括：

• 生成动作：生成抽象语法树，生成中间或目标代码
• 语义动作：赋予类型、检查类型

语法分析在使用产生式时，插入翻译的动作.

在自底向上分析中，体现为分析时多了一个动作栈：

进行语法分析时，相应的动作也入栈执行。

4.2 抽象语法树

在语法分析树中，保留了使用产生式推导的过程，这些信息在后续的语义分析和代码生成中不需要，占用额外空间。因此将语法分析树中对后续工作没有用的节点取去掉，，仅保留必要的信息，得到的就是抽象语法树。语法分析树存储的是具体的语法信息，而抽象语法树只需要保留程序构造的动作和执行对象。以3+4*5为例，对应的抽象语法树如下：

以下是一个简单的抽象语法树的数据结构定义：

enum kind {E_INT,E_ADD,E_TIMES};
struct Exp{
    enum kind kind;
}
// *的抽象语法树节点 
struct Exp_Times{
    enum kind kind;
    struct Exp *left;
    struct Exp *right;
}
// 整型的抽象语法树节点
struct Exp_Int{
    enum kind kind;
    int n;
}
// +的抽象语法树节点
struct Exp_Add{
    enum kind kind;
    struct Exp *left;
    struct Exp *right;
}

语法分析中，通常采用自底向上的方法，例如语法分析器生成工具Bison就是对LALR文法进行自底向上分析。采用自底向上的方法，抽象语法树应该是从子节点开始建立的。最先建立的是终结符对应的叶子节点，此后每次使用产生式进行规约时，就建立一个新的节点，并将产生式中成分的节点设置为新节点的子节点。相关的函数和调用大致为以下的形式：

//产生一个终结符的叶子节点，创建节点并赋相应的值
Exp_int *Exp_Int_new(int n){
    struct Exp_Int *p = malloc(sizeof(p));
    p->kind = E_INT;
    p->n = n;
    return p;
}
//添加一个加法节点
Exp_Add *Exp_Add_new(Exp *left,  Exp *right){
    Exp_Add *p = malloc(sizeof(p));
    p->kind = E_ADD;
    p->left = left;
    p->right = right;
    return p;
}
//语法分析时调用动作函数
E -> n		{e=Exp_Int_new(n)}
     |  E+E		{e=Exp_Add_new(e1,e2)}
     |  E*E		{e=Exp_Times_new(e1,e2)}

以上的抽象语法树节点相当简化，实际上应该包含更多信息，如文件，行号，列号等，因为程序被转换为抽象语法树后，源代码就被丢弃了，必须保留足够的信息，使后续过程能够准确的报错。

4.3 语法制导翻译理论

语法制导翻译是建立在语法制导定义SDD基础上的。SDD是一种上下文无关文法，每个文法符号具备一个属性(对于一个结点X，用X.a表示其属性)，每个产生式有一个语义动作。一些输出等动作称为副作用，如果SDD中没有副作用，则这种SDD被称为属性文法。一个SDD包含了语法分析与语法制导翻译的过程。但不是所有的语法制导翻译都可以在语法分析中完成(即动作能完成的工作是有限的)。SDD被分为两类：

• S属性的SDD：只存在自底向上的属性依赖关系，每个属性都是综合属性。

  • 综合属性：节点的综合属性只能通过子节点或者节点本身的属性来定义。

  

• L属性的SDD：只存在自底向上，自顶向下，自左向右的属性依赖关系，每个属性都是继承属性。

  • 继承属性：节点的继承属性由父节点，节点本身或兄弟节点的属性来定义。

    

对于S属性的SDD，只要在使用产生式把右部规约为左部时执行翻译动作就可以了，这也是上面构造语法分析树的方式。而对于L属性的SDD，由于是继承关系，可以考虑采用递归下降的语法分析，对非终结符N的产生式成分调用子分析函数进行分析时(此处可回顾递归下降分析的分析函数)，N的继承属性是子函数的参数，综合属性是子函数的返回值，并且左边的子函数先执行，所以左依赖的属性值先计算，按照这个顺序完成翻译动作。

自底向上分析也可以完成L属性的SDD的语法制导翻译，此处不讨论，在龙书中5.5.4节有介绍。

S属性的语法制导翻译是一个自底向上的过程，子节点总是属性值已知，父节点的值由子节点的属性值决定，例如计算式3+5*4,3和5和4为子节点，5*4构成父节点factor，其属性值为20，然后3和factor再构成父节点expression，值为3+20，这个计算式的代码也可以按照这个过程生成。中科大配套实验的第四个实验就是这样自底向上生成代码，计算抽象语法树的结点属性值的。通常情况下是先建立好语法分析树，然后进行深度优先遍历语法分析树，计算节点的属性值，完成语义分析，代码生成。

4.4语法制导翻译方案(模式)

语法制导翻译的方案(模式)就是在SDD基础上进行语法制导翻译的具体实现，可以看作是对SDD的实现细节的具体说明。翻译方案是在产生式右部嵌入了程序片段的文法，其中的程序片段称为语义动作。按照管理，语义动作放在{}内。例如:

D → T {L.inh = T.type} L
T → int {T.type = int}

T → real {T.type = real}

语义动作的位置决定了动作的执行时间。

对于S属性的SDD，将每个语义动作放在产生式的最后(只有子结点都分析完毕，才可以计算父节点的综合属性)。将L属性的SDD转换为SDT，需要将计算非终结符A的继承属性的动作插入到产生式右部A出现之前的位置，将综合属性的动作放到产生式右部的最右端。

对以上的语义动作放置位置进行举例：对于产生式P → T X = E和E → E + E，处理到E结点时，调用子节点E1和E2的处理函数，E1和E2的值计算完毕后，才可以计算E的值，所以语义动作必须放在最后。而E的类型取决于前面的声明，是一个继承属性，因此在调用E的处理函数之前，就要告知E的类型，这样之后才能确定E1和E2进行什么类型的加法运算(生成什么加法指令)，并进行语义检查(例如检查E1和E2是否为同一个类型，是否需要转换)。因此其翻译模式如下：

P → T X = {E.type = X.type} E

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

第四章 语义分析

语义分析也称为类型检查，上下文相关分析，主要负责检查程序的上下文相关的属性，例如变量使用前要声明，函数调用要与声明一致等。

1.语义规则

通常来说，程序设计语言都采用自然语言来表达程序语言的语义，语义规则与具体语言相关，编译器的实现者必须对语言的语义规定有全面的理解。

2.符号表

对于上下文相关的属性，必须进行记录才能保证程序能够运行，例如变量的声明必须有所记录，语义检查也是通过这些记录完成好呢个的。程序中的变量相关信息记录在符号表当中，包含变量的类型，作用域，访问控制信息，符号表的使用伴随了编译的全过程。

符号表实现时，比较复杂的是考虑作用域的情况，不同作用域可以使用一个链表来记录：

也可以符号表栈，进入一个作用域就插入新的符号表，退出则删除栈顶符号表。

语义分析中包含的其他问题还有类型相容等。现代的编译器中的语义分析模块，除了做语义分析外，还要负责生成中间代码或目标代码。因此，语义分析模块往往是编译器中最庞大也最复杂的模块。接下来就介绍代码生成的部分。

第五章 代码生成

生成了抽象语法树，前端的工作就结束了。后端的工作是将输入的抽象语法树翻译生成目标代码。即代码生成。

代码生成是将源程序翻译成目标机器上的代码的过程，主要完成两个任务，同时要保证等价和效率。

• 给源程序的数据分配存储资源
  • 数据：全局变量，局部变量，动态分配等。
  • 存储资源：寄存器，内存。
• 给源程序的代码选择指令
  • 源程序的代码：表达式，语句，函数等。
  • 机器指令：算术运算，比较，跳转等。

代码生成技术与指令集有关，主要研究两种不同的指令集上的代码生成技术：栈计算机，寄存器计算机。

1.栈式计算机的代码生成技术

栈式计算机现在已经基本淘汰了，研究其代码生成技术的原因是其代码生成比较简单，且现在仍然有许多栈式的虚拟机。

栈式计算机的结构和指令集如下：

栈式计算机只支持一种数据类型int，给变量x分配内存的伪指令是：.int x。其他的指令执行的操作如下：

push NUM
    top++;
	stack[top] = NUM;
load x
    top++;
	stack[top] = x;
store x
    x = stack[top];
	top--;
add 
    temp = stack[top-1] + stack[top];
	top = top-2;
	push temp;

语法如下：

每个非终结符都有一个代码生成函数，在代码生成时，表达式对应的值总是在栈顶。

Gen_E(E e){
    switch (e)
        case n: 
    		emit("push n");
    		break;
    	case id: 
    		emit("load id");
    		break;
    	case true:
            emit("push 1");
            break;
        case e1+e2:
            Gen_E(e1);
            Gen_E(e2);
            emit("add");
            break;
        case...
}
Gen_T(T t){
    switch(t)
        case int:
    		emit(".int");
    		break;
    	case bool:
    		emit(".int");
    		break;
}
Gen_S(S s){
    switch (s)
        case id=e:
    		Gen_E(e);
    		emit("store id");
    		break;
}
Gen_D(T id; D){
    Gen_T(T);
    emit(" id");
    Gen_D(D);
}
Gen_P(D S){
    Gen_D(D);
    Gen_S(S);
}

一个代码生成的示例如下：

2.寄存器计算机的代码生成技术

寄存器计算机是目前最流行的机器体系结构。寄存器计算机中寄存器代替了栈式计算机的栈，在寄存器存放部分变量和中间结果。在考虑代码生成技术时，假定有无限多个寄存器。代码生成的过程和栈式计算机相似。只是目标指令不同，入栈出栈都转变为了寄存器分配，然后存值。

以下是一个简单寄存器计算机的指令集：

文法仍然为上述介绍栈式计算机时的文法，每一个非终结符的函数变为：

Gen_E(E e){
    switch (e)
        case n: 
    		r = getNewReg();
    		emit("movn n,r");
    		return r;
    	case id: 
    		r = getNewReg();
    		emit("mov id,r");
    		return r;
    	case true:
            r = getNewReg();
    		emit("movn 1,r");
    		return r;
        case e1+e2:
            r1 = Gen_E(e1);
            r2 = Gen_E(e2);
    		r3 = getNewReg();
            emit("add r1,r2,r3");
            break;
        case...
}
Gen_T(T t){
    switch(t)
        case int:
    		emit(".int");
    		break;
    	case bool:
    		emit(".int");
    		break;
}
Gen_S(S s){
    switch (s)
        case id=e:
    		r = Gen_E(e);
    		emit("store r,id");
    		break;
}
Gen_D(T id; D){
    Gen_T(T);
    emit(" id");
    Gen_D(D);
}
Gen_P(D S){
    Gen_D(D);
    Gen_S(S);
}

一个代码生成的示例如下：

第六章 中间表示

在上一章中介绍了代码生成，即从抽象语法树生成目标代码的过程。实际在编译过程中，抽象语法树通常不直接生成目标代码，而是先生成一些中间表示，再通过中间表示，生成不同目标机器上的目标代码。中间表示的作用是提供一个中间层，抽象语法树只需要生成中间表示，而不需要根据具体的机器生成目标代码，由后端在后续过程中将中间表示进行优化，并转换为目标代码。基本思想是与目标机器无关，且对于多种源语言通用。

一般编译器有多阶段的中间表示，高层中间表示接近源语言，便于进行语义分析和冗余检查；低层中间表示接近目标语言，便于优化和翻译。常用的中间表示有：

• 图IR：树和有向无环图DAG
• 线性IR：三地址码
• 混合IR：控制流图CFG，静态单赋值形式SSA

下面分别介绍这几种中间表示。

1.有向无环图DAG

有向无环图DAG是抽象语法树AST的进一步抽象，解决抽象语法树存储开销大，不便于优化的问题。

使用有向无环图DAG的一般用途为：

• 减少内存占用：减小AST的内存开销
• 后端代码优化：查找冗余，减少翻译出的机器指令

DAG在生成时，会检查节点是否已经存在，如果需要的节点已经生成，就直接进行引用。手动构造一个DAG的步骤如下：

• 将操作数不重复的排成一排
• 标出表达式中运算符生效的顺序
• 按顺序加入运算符 结果保存在操作数最大层数的上一层
• 检查同层运算符是否能够合并

其中合并可以直接在加入运算符时进行。

2.三地址代码

三地址代码是一种每个指令最多有三个操作数，一个运算符的代码。基本思想是：

• 给每个中间变量和计算结果命名，没有复合表达式
• 只有最基本的控制流，只有goto和call指令
• 是指令集的抽象

以下是一个三地址代码的例子：

//源代码
a = 3 + 4 * 5;
if (x < y)
  z = 6;
else
  z = 7;
//三地址码
t1 = 4 * 5;
a = 3 + t1;
if (x < y) goto L_1;
goto L_2; 
L_1:
z = 6;
goto L_3;
L_2:
z = 7;
goto L_3:

使用三地址码的好处是：

• 类似寄存器计算机的指令，便于代码生成
• 代码紧凑，空间占用少
• 形式灵活，表达清晰，且每个中间变量和计算结果命名，便于控制名字和值的复用

三地址码的主要不足在于程序的控制流信息是隐式的，因为控制流被简化了，因此通过三地址代码难以理解源程序的控制流结构。

三地址码的生成过程和第五章代码生成中的生成方式很相似。也可以使用语法制导定义SDD直接在语法分析时生成，直接跳过抽象语法树的生成。

3.控制流图CFG

控制流图是一个有向图G=(V,E)。其中每个节点V是一个基本块，E是基本块之间的边，表示跳转关系。每个基本块只能从第一条语句进入，从最后一条语句离开。主要的用途为：

• 控制流分析：分析程序的内部结构，如是否存在循环。并可以通过分析修改或优化程序，例如删除死基本块。
• 数据流分析：例如一个变量可能的取值。

控制流图可以由三地址码生成。而控制流图的操作可以使用图论中的各种算法实现。

控制流图的缺点在于没有显式的数据流信息。不能通过数据流对程序进行优化。

4.静态单赋值形式SSA

静态单赋值形式在数据流图的基础上添加了数据流信息，基本思想是：

• 每个变量只定义一次。
• 使用数据时必须指向一个特定的变量。

主要的用途就是基于数据流和控制流进行优化。由于在数据流图的基础上显式添加了数据流，主要是在数据流的基础上进行优化：

• 删除冗余赋值
• 常量传播

第七章 代码优化

代码优化是一个在保持语义的基础上进行代码变换的过程。可以按照不同的阶段分为：

• 前期优化
  • 在抽象语法树上进行
  • 常量折叠、代数优化、不可达代码删除等
• 中期优化
  • 在中间表示上进行
  • 常量传播、拷贝传播、死代码删除、公共子表达式删除等
• 后期优化
  • 在后端(汇编代码级)进行
  • 寄存器分配、指令调度、窥孔优化等

1.前期优化

前期优化包括常量折叠，代数优化，不可达代码删除。在抽象语法树上进行。

常量折叠是对程序中表达式的常量计算进行优化。因为一些表达式的值在编译过程中就可以得到，例如a=3+5，可以直接优化为a=8。在语法树或者中间表示上，这种优化是容易实现的，且通常实现为公共子函数，可以被其他优化调用。但在优化过程中必须遵守语言的语义，例如考虑异常或溢出，例如x=4294967294+1，如果x为unsigned int，则值正常+1，如果x是int，结果为-1。

代数优化是对表达式计算的化简，利用的是代数系统的性质。例如a=1*b = a*b，a+1024+b-1024 = a+b。进行代数化简，也要注意遵守语言的语义，考虑溢出或异常。

不可达代码删除的基本思想是删除程序中不会执行的代码。这种优化也可以中期在控制流图上完成。

2.中期优化

前期优化可简化中后端处理，但是优化能力有限，进行如不可达代码删除这样的优化很不方便。在中间表示位置可以进行进一步的优化。优化的方式则依赖于具体所使用的中间表示。本部分介绍基于控制流图的中期优化。

中期优化一般分为两步。第一步是程序分析，通过控制流分析，数据流分析，依赖分析等得到被优化程序的静态保守信息(对动态运行行为的保守估计)。第二步是程序重写，基于程序分析的信息对程序进行重写。

本章主要介绍的是程序分析的两种方法：到达定义分析和活性分析。

2.1 到达定义分析

到达定义分析主要分析的是对每个变量的使用点，有哪些定义可以到达。其中定义指的是对变量的赋值，使用点是对变量值的读取。

使用集合来表示到达定义分析的结果，分析每一个语句对到达定义的改变。设每一个语句都有一个in集，表示到达该语句时，有哪些语句的定义有效，每一个语句还有一个out集，表示经过该语句后，还有哪些语句的定义是有效的。

为了求解in和out集，每个语句还有一个gen集和一个kill集，分别表示该语句产生了一个语句定义，该语句使哪些语句的定义无效。

假设每条语句编号i，对变量x定义，则到达定义的计算为：

• gen = {i}

• kill = defs[x] - {i}

  • defs[x]表示所有定义x的语句

• in[i] = 所有到达i的语句的out集

• out[i] = gen[i] ∪ (in[i] - kill[i])，即经过该语句有效的定义语句，是当前语句加上到达该语句有效的定义语句再减去当前语句使之无效的那些语句。

由于后面的定义需要包含前面的有效定义，即out[i]依赖于in[i]，对于语句in和out集的计算应该从前往后进行，即从第一条语句开始，计算in和out集的方程被称为前向数据流方程。

以下是一个控制流图的到达定义分析示例，由于in集取决于来源语句的out集，而来源语句的out集可能还没有计算结束，因此要反复计算in和out集，直到集合不发生改变。

2.2 活性分析

到达定义分析分析的是对变量的使用点，有哪些定义可以到达。另一种常用的程序分析方法是活性分析，分析的是在程序的每个语句，有哪些变量正在处于使用状态。活性分析主要用于寄存器分配，在中间代码生成时，通常假设有无限多个寄存器，从而简化代码生成，最终产生目标代码，必须将无限的虚拟寄存器分配到机器的有限的寄存器当中。进行活性分析，可以确定哪些变量可以共用一个寄存器。

活性分析需要确定变量在哪些语句是活跃的，活跃的这些语句就是变量的活跃区间。变量活跃的定义如下：

• 如果变量x在程序点p(含)之后被使用，则x在p点是活跃的。(显然，如果变量x在点p被有效定义，在点p也是活跃的)

• 否则，如果变量x在程序点p(含)之后未被使用，则x在p点是死的。(如果变量x在点p被定义，在后面却没有被使用，这个定义实质是无效的，x在点p不是活跃的。)

根据以上的变量活跃的定义，变量活跃，只需要重点关注使用情况，而不需要关注定义情况。并且在分析时，还应该将一些无效的定义语句将被排除在变量活跃区间以外。例如下面的例子：

在语句3和语句4都有对变量c的定义，根据变量活跃的定义，语句3开始就是c的活跃区间，但语句3的定义是无效的，c的活跃区间里不应该有语句3。在求活跃区间时避免这种情况的方式是：从后往前求活跃区间。下面描述一下求解过程。

类似到达定义分析，设每个语句都有一个in集和一个out集，分别表示到该语句仍然活跃的活跃变量，在该语句之后的还保持活跃的活跃变量。还使用两个辅助的集合use集和def集，分别表示该语句使用了哪些变量，定义了哪些变量。假设语句编号i，这是个集合的计算如下：

• use = {x|x在语句i中出现}
• def = {x|x由语句i定义}
• out[i]：所有从该语句离开，所到达的语句的in集合的并集
• in[i] = use[i] ∪ (out[i] - def[i])

为了解决上面已经提到的无效定义问题，应该从后往前计算，即in[i]依赖于out[i]，所以从最后的语句开始进行分析，且先计算out集，再计算in集。计算in和out集的方程被称为后向数据流方程。

对于上图中的程序，求出的in和out集如下：

以下是一个控制流图的活性分析示例，由于out集取决于从当前语句离开所到达语句的in集，而对应语句的out集可能还没有计算结束，因此要反复计算in和out集，直到集合不发生改变。由于要反复进行计算，尽管应该按照从后往前的顺序计算，但实际上从前往后或从后往前都可以，因为整个集合不改变时才停止计算，不会遗漏。

以上已经给出了求in和out集的方法，求in和out集的目的是求变量的活跃区间。因此此时再来分析以下这两个集合，in表示到该语句仍然活跃的活跃变量，out表示在该语句之后的还保持活跃的活跃变量，所以只要根据变量是否在该语句的in集或out集当中，就可以划分出变量的活跃区间了。

2.3 优化方法

中期优化一般分为两步。第一步是程序分析，通过控制流分析，主要的两种方法就是到达定义分析和活性分析。第二步是程序重写，基于程序分析的信息对程序进行重写。接下来就用例子展现程序重写的方法：常量传播，拷贝传播，死代码删除。

常量传播优化

拷贝传播优化：

死代码删除

其中的死代码删除和前期优化提到过的不可达代码删除是有区别的。不可达代码不会被执行，而死代码是可以执行，但没有意义的代码。

3.后期优化

后期优化在生成代码后，在汇编代码级进行优化。后期优化与目标机器相关，和寄存器数量，指令集等都有关系。后期优化的方法有寄存器分配，指令调度，窥孔优化等。这里重点介绍寄存器分配。

在代码生成时，为了简化代码生成的过程，假设寄存器有无限个，真实的目标机器的寄存器数量是有限的，不同机器的寄存器数量也不一样，例如RISC机器通常有32个寄存器。因此在生成代码后，要进行寄存器分配，重写代码，将使用的多个变量分配到少数物理寄存器中，保证使用的寄存器数量不超过机器的真实寄存器数量。以下是一个寄存器分配的例子：

寄存器分配的主要思路就是让不同时活跃的变量共用一个寄存器，从而减少寄存器数量。一种简单的寄存器分配算法是遇到一个变量就使用一个当前不活跃变量所使用的寄存器，如果分配失败，就把某个变量放回内存，重用他的寄存器。这种方式分配效率很低，程序性能可能很差。在1980年，IBM研究员尝试了使用图着色算法进行寄存器分配，这种方法分配更简单，效果也更好。

图着色算法分配寄存器的步骤如下：

• 计算活性分析
• 画出寄存器冲突图(RIG)
• 对RIG着色分配寄存器
• 将无法分配寄存器的变量溢出到内存

下面以一个完整的例子说明图着色算法分配寄存器的过程。

活性分析

对以下控制流图所示的程序进行活性分析，结果标在图中。

画出寄存器冲突图

寄存器冲突图是一个无向图，每个节点是一个变量，如果两个变量有同时活跃的情况，添加一条边连接两个变量对应的节点。如果两个变量没有边连接，说明他们可以使用同一个寄存器。

以上程序的寄存器冲突图如下：

对RIG进行图着色分配寄存器

给每个节点着色，相当于为每个变量分配寄存器。如果一个图可以被k种颜色着色，两个连接的节点颜色不相同，该图为k可着色图。k可着色图的特点是，从图中删除一个边小于k的点，如果删除后的图是k可着色的，那么原图也一定是k可着色的，因为这个删除的点连接的边数小于k，总能找到一种不一样的颜色。根据这个特点，可以使用启发式算法对RIG进行图着色，将着色算法分为两部分：

• 删除点
  • 选择一个邻居数量小于k个的节点t(暂时假设总能找到)，从RIG中删除t和它所有的边
  • 把t放在栈顶
  • 重复上述步骤直到RIG中没有节点
• 着色
  • 从栈顶弹出1个节点
  • 给该节点选择1种与其邻居都不同的颜色
  • 重复上述步骤直到栈为空

将无法分配寄存器的变量溢出

如果使用以上的着色算法无法找到邻居数量小于k个的节点，就需要溢出变量，将其存放在内存里。方式是选择一个邻居大于等于k的节点f照常入栈，然后进行着色，直到出栈节点为溢出的节点f，先尝试对其进行着色，如果无法着色，就在每次使用节点前插入load指令，在每次定义节点后插入store指令，然后重新计算活性分析，再重新画出RIG图，进行寄存器分配。

找到可行的图着色方案，可能需要多次溢出，溢出哪个变量很关键，也很难确定，可能的启发式算法有：

• 选择与其他变量冲突最多的变量
• 选择使用较少的变量
• 避免溢出循环内部的变量