第一章 绪论

一到四章的概念也就图一乐,真学习还得看第五章

引言

语言

语言:一组规则的组合

  1. 字母表的定义
  2. 词法规则单词符号的形成规则
  3. 语法规则:(短语、从句、句子、段落、文章)语法单位的形成规则
  4. 语义规则单词符号语法单位含义规则
  5. 语用规则:语义规则的发展和延伸。在一定的语境中,单词和语法单位体现出来的具体意义,需要根据上下文进行明确

机器语言、汇编语言、高级语言

机器语言 -> 汇编语言 -> 高级语言

  • 机器语言:由二进制指令组成。计算机可以直接执行
  • 汇编语言:将机器语言符号化的结果
  • 低级语言:与机器有关的语言(指令的操作码、指令格式、寻址方式、数据格式)
  • 高级语言:和机器无关的语言

翻译

  • 翻译:等价的变换

计算机只可直接执行用机器语言编写的程序。而用汇编语言和高级语言编写的程序,机器不能直接执行。必须将它们翻译成完全等价的机器语言程序才能执行。

  • 翻译过程:

机器语言 <–汇编程序– 汇编语言 <–编译程序– 高级语言

  • 实现:编写一个高级语言的编译程序的工作,通常称为对这个语言的实现

与编译有关的三种语言、三种程序:

  • 源语言、宿主语言、目标语言
  • 源程序、编译程序、目标程序
    高级语言涉及的三类人:
  • 设计者、实现者、使用者

解释

  • BASIC 是最简单的高级语言。BASIC 程序不是编译执行,而是对源程序进行解释(分析),直接计算出结果。
  • 解释需要解释程序(解释器)
  • LISP,ML,Prolog 和 Smalltalk 均是解释型的语言。
  • Java 被当作一种解释型语言。翻译产生字节码的中间代码, 可以在 Java 虚拟机上运行。

  • 解释执行特别适合于动态语言交互式环境,便于人机对话。
  • 重复执行的语句需要重复翻译,比编译执行要花去更多的时间,执行效率较低。

强制式语言、函数式语言、逻辑式语言、对象式语言

程序设计语言按设计的理论基础分为四类语言:

  1. 强制式语言:基础是冯·诺依曼模型
  2. 函数式语言:基础是数学函数(函数运算)
  3. 逻辑式语言:基础是数理逻辑、谓词演算
  4. 对象式语言:基础是抽象数据类型

绑定

  1. 实体:程序的组成部分,如变量,表达式、程序单元等
  2. 属性:实体具有的特性
  3. 绑定:实体与其各种属性建立起联系的过程称为绑定(约束)
  4. **描述符(表)**:描述实体属性的表格

静态和动态

  • 静态特性:编译时能确定的特性
  • 动态特性:运行时才能确定的特性

  • 静态绑定:绑定在编译时完成,且在运行时不会改变。
  • 动态绑定:绑定在运行时完成。

  • 静态作用域绑定:按照程序的结构定义变量的作用域(C语言等)。依据定义变量的位置进行确定。
  • 动态作用域绑定:按照过程的调用关系动态地定义变量的作用域(SNOBL4 语言等)

变量的四个属性

  1. 作用域:全局变量、局部变量、非局部变量
  2. 生存期
  3. 类型

快进到第四章

第二章 数据类型

第三章 控制结构

第四章 程序语言的设计

前言

语言 = 语法 + 语义

描述语法的方法:文法 or 语法图

文法和语法图是语言语法的等价表示。

文法:

1
2
3
4
5
<标识符><字母>
<标识符><标识符><字母>
<标识符><标识符><数字>
<字母>→A||Z|a||z
<数字>→0||9
语法图
语法图

描述语义的方法:许多语言仍采用自然语言描述语义。

文法

文法的形式定义

文法的形式定义: $G = (V_T, V_N, S, P)$

  • $V_T$ 为终结符的非空有限集;
  • $V_N$ 为非终结符的非空有限集;
  • $V=V_T \bigcup V_N$
  • $S$ 是文法的开始符号,有 $S\in V_N$ ;
  • $P$ 为产生式 $\alpha\to\beta$ 的非空有限集,其中:
  • $\alpha$ 和 $\beta$ 是由终结符、非终结符组成的串,且 $\alpha$ 至少应含有一个非终结符。即 $\alpha=V^*V_NV^*, \beta=V^*$
  • $^*$ 表示前面的符号重复零次或多次(这很正则表达式)

G: Grammar
T: Terminal Symbols
N: Non-Terminal Symbols
S: Start Symbol
P: Production

产生式的简化

$$\left.\begin{aligned}
\alpha&\to\beta_1 \\
\alpha&\to\beta_2 \\
&…\\
\alpha&\to\beta_n
\end{aligned}\right\}
\alpha\to\beta_1|\beta_2|\beta_n
$$

$\beta_1, \beta_2, \beta_n$ 称为 $\alpha$ 的候选式。

文法的表示

描述文法,直接给出产生式集合 (P) 即可。

$$\begin{aligned}
E &→ E+T | E-T | T \\
T &→ T*F | T/F | F \\
F &→ (E) | i
\end{aligned}$$

文法的分类

分为 0 型文法、1 型文法、2 型文法、3 型文法。数字越大,规定越严格,越规范。

文法 (在上一级基础上增加)限制 中文
0型文法(PSG) $\alpha\to\beta$ 无限制
1型文法(上下文有关文法CSG) $α$ 长度小于 $β$ 长度($S→ε$例外) 右边的表达式长于左边
2型文法(上下文无关文法CFG) $A→β$ 左边是独立的非标识符
3型文法(正则文法RG,或右线性文法RLG) $A→u$或$A→wB$, $u\in V_T^*, w\in V_T^+$ 右边不以非标识符开头

推导的表示

  • 直接推导(由产生式右边替换产生式左边): $wαγ\Rightarrow wβγ$
  • 任意步推导(0 步或多步):$y \Rightarrow^* z$
  • 多步推导(1 步或多步):$y \Rightarrow^+ z$
例 1
例 1
例 2 -- 最右推导
例 2 -- 最右推导

最右推导:总是展开最右边的非终结符

句型、句子、语言

$G = (V_T, V_N, S, P)$

  • 句型:S 能推导出的 $w$
  • 句子:S 能推导出的只含终结符的 $w$
  • 语言:G 产生的所有句子的集合 $L(G)=\{α│S\Rightarrow^+α 且 α\in V_T^*\}$
例 2 -- 标识符
例 2 -- 标识符
例 3
例 3

例 4 有点难。

例 4,需要上下有关文法表示,难点
例 4,需要上下有关文法表示,难点

文法等价

两个文法 $G$ 和 $G’$,如果有 $L(G)=L(G’)$,则称 $G$ 和 $G’$ 等价

推导树

对于文法 $E→E+E|E*E|(E)|i$,句子 $i+i*i$,其两棵推导树:

i+i*i 的推导树
i+i*i 的推导树

文法的二义性:一个句子有两棵不同的推导树。

第五章 编译

复习概念

  • 源语言、宿主语言、目标语言
  • 源程序、编译程序、目标程序

  • 自驻留:若编译程序生成宿主机执行的机器代码,称为自驻留的编译程序
  • 自编译:若编译程序用源语言编写的,则为自编译的编译程序
  • 交叉编译:若编译程序生成不是宿主机(别的机器)执行的机器代码,称为交叉编译

编译步骤

逻辑上:

  1. 源程序的分析
  2. 目标程序的合成

具体:

  1. 词法分析
  2. 语法分析
  3. 语义分析与中间代码生成
  4. 中间代码优化
  5. 目标代码生成

编译的每个步骤都需要进行符号表管理出错处理

词法分析

  • 分析输入字符串
  • 根据词法规则识别出单词符号:基本字、标识符、字面常量、运算符和界符

语法分析

  • 根据语法规则,识别各类语法单位:表达式、语句、程序单元和程序
  • 进行语法检查

语义分析与中间代码生成

  • 根据语义规则,对语法正确的语法单位进行翻译
  • 可以直接生成目标程序
  • 但目标程序的执行效率低
  • 因此,生成中间代码

中间代码:

  • 大多数编译器采用中间代码来描述源程序的语义。
  • 这种中间语言对应某种抽象机
  • 结构简单,语义明确,易于翻译成目标代码,同时也便于优化和移植。

优化

  • 对中间代码进行等价变换,提高代码的时空效率。
  • 语义分析产生的中间代码不依赖于实际机器,易于实现一些等价变换,使生成的目标程序占用空间更少,执行更快。

目标代码生成

  • 根据优化后的中间代码及有关信息,可生成较为有效的目标代码:
  • 目标机的机器语言程序或汇编语言程序
  • 若生成的是汇编语言程序,还需由将其汇编成机器语言程序。
编译器的结构
编译器的结构

完整的程序处理过程

从分析源程序到建立一个可执行的目标程序,处理过程还需要其它工具程序的配合:

  1. 预处理器
  2. 汇编器
  3. 连接器
  4. 装入器
完整的程序处理过程
完整的程序处理过程

编译前端和后端

  • 在现代编译器中,通常将编译过程划分为前端和后端两大部分,分别加以实现。
  • 前端和后端通过中间代码连接,可极大的提高编译器设计与实现的效率。
  • 前端:主要是与源程序相关的部分,包括词法、语法分析、语义分析和中间代码生成等。
  • 后端:主要是与目标程序相关的部分,包括优化、目标代码生成等。

第六章 词法分析

从这里才开始变难。

概述

词法分析:扫描源程序的字符串,按照词法规则,识别出单词符号作为输出;对识别过程中发现的词法错误(非法的字符、不正确常量、程序括号等) 进行处理。

词法分析器和编译器的关系(1)
词法分析器和编译器的关系(1)
词法分析器和编译器的关系(2)
词法分析器和编译器的关系(2)

单词的种类

  • 标识符
  • 关键字
  • 常量
  • 运算符
  • 分界符
1
2
3
4
5
6
7
8
9
10
11
12
13
while(*pointer!='\0') pointer++;

while 关键字
( 界符
* 运算符
pointer 标识符
!= 运算符
'\0' 常量
) 界符
pointer 标识符
++ 运算符
; 界符
'\n' 界符

单词的输出形式

采用二元式:(单词类别,单词)

  • 单词类别:区分单词所属的类(整数编码)
  • 单词:单词的属性值

单词类别的划分

单词的编码随类别不同而不同。
基本字、运算符、界符的数目是确定的,一字一码,它的第二元可以空缺

  • 标识符通归一类。
  • 常量可按整型、实型、字符型、布尔型等分类。
  • 常量或标识符将由第二元—-单词的属性值来区别:
    • 通常将常数在常量表中的位置(编号)作为常量的属性值;
    • 将标识符在符号表中的位置(编号)作为标识符的属性值。
单词符号的编码表
单词符号的编码表

状态转换图

状态转换图 例
状态转换图 例
标识符的状态转换图
标识符的状态转换图
整数的状态转换图
整数的状态转换图

词法分析器的转换图

词法分析器的转换图(1)
词法分析器的转换图(1)
词法分析器的转换图(2)
词法分析器的转换图(2)

词法分析器

略,看 PPT 吧

第七章 自上而下的语法分析

  • 编译理论中,语法分析是对高级语言的语法单位的结构进行分析。
  • 语法单位结构可以用上下文无关文法来描述。
  • 下推自动机可用于识别上下文无关文法所描述的语法单位。
  • 上下文无关文法及下推自动机是语法分析的理论基础。

语法分析:对无关文法 $G = (V_T, V_N, S, P)$ 及符号串 $w$,判断 $w$ 是否是文法 $G$ 的一个合法句子,即:
$$S\Rightarrow^*w$$

引言

语法分析的功能
语法分析的功能

语法分析的方法通常有两类:

  • 自上而下(自顶向下)的分析方法(第七章):从 $S$ 出发,能否找到一个最左推导序列,使得 $S\Rightarrow^*w$;或者从根结点 $S$ 开始,能否构造一棵语法树,使得该语法树的叶结点自左至右的连接正好是 $w$。
  • 自下而上(自底向上)的分析方法(第八章):从 $w$ 出发,能否找到一个最左规约(最右推导的逆过程)序列,逐步进行规约,直至文法的开始符号 $S$。

自上而下的语法分析可分为不确定和确定的两类。

  • 回溯分析法是不确定的分析方法。
  • 递归下降分析法预测分析法属于确定的分析方法。

回溯分析法

其实就是 DFS

实例:

$$\begin{aligned}
S&→xAy \\
A&→ab│a
\end{aligned}$$

输入串为 $xay$。

回溯分析的动画过程看 PPT。

  • 采取试探方法来分析每一个候选式,分析的过程很可能产生回溯
  • 可能产生回溯的原因有: (1)公共左因子 (2)左递归 (3)$ε$ 产生式

公共左因子

公共左因子,是指在文法的产生式集合中,某个非终结符的多个候选式具有相同的前缀。

$$A→αβ_1│αβ_2$$

  • 若所有候选式都没有公共左因子,就可以选择惟一匹配的候选式,减少不必要的回溯

左递归

  • 左递归:$A\Rightarrow^+Aβ$
  • 直接左递归:$A\Rightarrow Aβ$

回溯分析法特点

回溯分析法是一种不确定的方法:使用试探的方法穷举每一种可能,当分析不成功时,则回退到适当位置再重新试探其余可能的推导。穷尽所有可能的推导,仍不成功,才能确认输入串不是该文法的句子。

主要缺陷

  1. 选择候选式进行推导是盲目
  2. 若文法存在左递归,语法分析还可能产生无限递归
  3. 引起时间和空间的大量消耗
  4. 无法指出语法错误的确切位置

针对产生回溯的原因,提出消除回溯的方法:引进确定的语法分析方法——递归下降分析法预测分析法

为了消除回溯,对任何一个非终结符和当前的待匹配符号,期望

  • 要么只有一个候选式可用
  • 要么没有候选式可用

递归下降分析法

方法步骤

  1. 提取公共左因子(看 PPT)
  2. 消除左递归
  • 消除直接左递归(改写为右递归)
  • 间接左递归($A\Rightarrow^+Aα$)的消除利用算法进行
    a. 将文法 $G$ 的所有非终结符按任一给定的顺序排列为 $A_1,A_2,…,A_n$
    b. 消除可能的左递归(算法见后)
    c. 化简:删除多余产生式
1
2
3
4
5
6
// 消除左递归
for i:=1 to n do
for j:=1 to i-1 do
把形如Ai→Ajα的产生式改写为
Ai→δ1α|δ2α|...|δkα
消除Ai产生式可能的直接左递归

消除例子中的左递归:

$$\begin{aligned}
S&→Qc│c \\
Q&→Rb│b \\
R&→Sa│a \\
\end{aligned}$$

题解
题解
题解 2
题解 2

递归下降分析器的构造

在文法 G 中,如果

  • 没有任何公共左因子
  • 没有任何左递归
    则有可能构造出不带回溯的分析程序

预测分析法

构造 First 集

  1. A -> aB,A 就有 {a}
  2. A -> B,A 可以把 B 的复制过来
  3. A -> BC,若 B 可以为 ε,A 就还能复制 C 的

构造 Follow 集

  1. S

FIRSTVT
E + ( * i
T * ( i
F ( i

第八章 自下而上语法分析

概念

  • 短语:某个祖先的所有没孩子的子孙组成的语句
  • 直接短语:某个没有孙子的爸爸的孩子组成的语句
  • 句柄:最左直接短语
  • 素短语:短语至少有一个终结符,且不不含更小的素短语(若 i 是素短语,则 Fi* 不是素短语)

算符优先分析法

构造 FIRSTVT 集

  1. A -> aBcA -> Bac,A 就有 {a}
  2. A -> BC,A 可以把 B 的复制过来
  3. A -> BC,若 B 可以为 ε,A 就还能复制 C 的

构造 LASTVT 集

  1. A -> caBA -> cBa,A 就有 {a}
  2. A -> BC,A 可以把 C 的复制过来
  3. A -> BC,若 C 可以为 ε,A 就还能复制 B 的

算符优先关系表

  1. 优先:先归约的符号被称为优先级高。
  2. 先看行,再看列。如 +i 列为 >,则 + > i
  3. 规则:若 E+T,则 LASTVT(E) > ++ < FIRSTVT(T)
    • 还要添加 #S# 这个文法
    • 这里的大于、小于没有对称性(a>b 不能推出 b<a
    • 推荐先填等号,再按行填小于,再按列填大于

LR 分析法

第九章 语义分析

符号表

符号表:

1
名字 | 信息

常用的符号表结构:线性表、Hash 表

语义分析概论

语义分析的主要工作

语义分析 = 静态语义检查 + 语义处理

静态语义检查:
(1) 类型检查:数据的使用应与类型匹配
(2) 控制流检查:用以保证控制语句有合法的转向点:
如不允许goto语句转入case语句流; break语句需要在switch或循环语句.
(3) 一致性检查:如数组维数是否正确; 变量是否已经定义;变量是否重名;case常量不能相同等。

语义处理:
说明语句: 登记信息;
执行语句:生成中间代码。

语法制导翻译

每个产生式配上一个语义子程序

语法分析过程中,根据每个产生式对应的语义子程序(语义动作)进行翻译(生成中间代码)的方法称为语法制导翻译。

语法分析采用自底向上的LR分析法(1)
语法分析采用自底向上的LR分析法(1)
语法分析采用自底向上的LR分析法(2)
语法分析采用自底向上的LR分析法(2)
语法分析采用自底向上的LR分析法(3)
语法分析采用自底向上的LR分析法(3)

语义值

在描述语义动作时,需要赋予每个文法符号以各种不同的“值”,这些值统称为“语义值”.如,“类型”,“种属”,“地址”或“代码”等。通常用X.TYPE,X.CAT,X.VAL来表示这些值。

picture 7
picture 7

中间代码

中间代码一种与具体机器无关的抽象代码,有多种形式。四元式形式: (op,ARG1,ARG2,RESULT)

op—运算符
ARG1—第一运算量
ARG2—第二运算量
RESULT—结果

如: A:=(-B)*(C+D) 翻译成

1
2
3
4
(@,B,_,t1)
(+,C,D,t2)
(*,t1,t2,t3)
(:=,t3,_,A)

四元式出现顺序和表达式计值顺序一致;四元式之间的联系通过临时变量来实现。

简单赋值语法分析的翻译

语义变量及过程

  • X.a:文法符X相应属性a,如i.name,E.place。E.place:表示E所代表的变量在符号表的入口地址。
  • newtemp:语义函数,每调用一次产生一个新的临时变量。
  • entry(i):语义函数,查符号表,返回变量i的入口。
  • IP:指令指针,初始化为0,也可以是指定的初值。
  • gen(OP,ARG1,ARG2,RESULT):语义过程,生成一个四元式(OP,ARG1,ARG2,RESULT),并填入四元式表中。同时 ip:=ip+1

翻译方案

1
2
A → i:=E
E → E1 op E2 | -E1 |(E1)| i
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
A→i:=E
{
P=entry(i.NAME);
If(P!=0)
gen ( :=, E.place, _, P)
Else error();
}

E→E1 op E2
{
E.place:=newtemp;
gen(op,E1.place,E2.place,E.place)
}

E →-E1
{
E.place:=newtemp;
gen(@,E1.place,_,E.place)
}

E →(E1)
{ E.place:= E1.place }

E →i
{ P=entry(i.NAME);
If(P!=0) E.place:=P
Else error();
a:=-b*(c+d)的移进-归约过程
a:=-b*(c+d)的移进-归约过程

类型转换

对表达式E增加类型属性E.type;
引进类型转换指令 (itr,x,_,t)

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
t:=newtemp;
if E1.type=integer
and E2.type=integer
then begin
gen(opi,E1.place,E2,place,t);
E.type:=integer
end

else if E1.type=real and E2.type=real
then begin
gen(opr,E1.place,E2.place,t);
E.type:=real
end

else if E1.type=integer then
begin t1:=newtemp;
gen(itr,E1.place,_,t1);
gen(opr,t1,E2.place,t);
E.type:=real
end

else begin t1:=newtemp;
gen(itr,E2.place,_,t1);
gen(opr,E1.place,t1,t);
E.type:=real
end;

E.place:=t;

说明语句的翻译

不产生可执行指令
仅负责填表:将被说明对象的类型及相对存储位置记入各自的符号表中

文法

1
2
D→D;D│i:T
T→realintegerarray[num] of T1│↑T1

语义变量和过程

负责填下面两个东西!

(1)offset:相对位移量,初值为0,是一个全局变量
(2)T.type:数据类型
(3)T.width:数据宽度
(4)enter:语义过程,将变量名及其类型和相对存储位置记入符号表中。

翻译方案

1
2
3
4
5
S →MD
M →ε { offset:=0 }
D → D1;D2
D →i:T { enter(i.name,T.type,offset); offset := offset+T.width }
T→integer { T.type:=integer; T.width:=4 }

控制语句的翻译

布尔表达式的翻译

文法

1
2
3
4
5
6
B→i
B→i1 rop i2

1if B then S
2if B then S else S
3while B do S

语义变量

  • B.T:真出口,记录B为真的转移语句的地址;
  • B.F:假出口,记录B为假的转移语句的地址。

转移语句的四元式

1
2
3
(jrop,P1,P2,0) 
(jnz,P1,-,0)
(j,-,-,0)

0 是转移地址,从上往下分析的时候可能不知道要转义到哪里,所以会挖坑,后面会填坑。

翻译方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
B→i
{
B.T:=ip;
gen(jnz,entry(i),-,0);
B.F:=ip;
gen(j,-,-,0)
}

B→i1 rop i2
{
B.T:=ip;
gen(jrop,entry(i1),entry(i2),0);
B.F:=ip;
gen(j,-,-,0)
}

无条件转移语句翻译

goto L,L 已经定义

1
2
3
4

L: ... /*此时,将L登记入符号表*/

goto L; /*查表,发现L已定义,生成四元式*/

goto L,L 未定义

1
2
3
4
5
6
7
8

goto L; /*将L记入符号表,定义否标记为“否”,
地址栏写当前IP,生产无条件转移 */

goto L; /*拉链,即生成向上指的链表*/

L: … /*定义否标记改为“是”,回填,即根据链表依次改写跳转的地址栏*/

拉链
拉链

标号语句的处理方法

文法:

1
label →i:
  1. i(假定为L)不在符号表中:则把它填入,置“类型”栏为“标号”,“定义否”栏为“已”,“地址”栏为ip的当前值;
  2. 若L已在符号表中,“类型” 为“标号”, “定义否”栏为“否” :把“定义否”改为“已”,然后把“地址栏”中的链首q取出,同时把ip当前值填入其中,最后执行 backpatch(q,ip)语义过程进行回填
  3. 若L已在符号表中,但“类型”不为“标号”,或“定义否” 为“已”:则“名字重定义”

backpatch(q,ip)为语义过程:把q为链首的链上所有四元式的第四区段都填为ip

If 条件语句的翻译

文法

1
S→if B then S1if B then S1 else S2

if B then S1:S1的第一条四元式
用以“回填”
if B then S1 else S2:S1、S2的第一条四元式用以“回填”

(1)B具有真假出口
B为真假时的转向不同
在翻译B时其真假出口有待“回填”
(2)因if语句的嵌套,必须记录不确定转移目标的四元式的地址—拉链技术

语义变量及过程

  1. N.CHAIN:记录不确定转移目标的四元式形成的,不确定 label 地址时就调用这个一般来说,N.CHAIN 的含义是 N 结束以后要跳的位置
  2. merge(t1,t2): 语义函数,合并链表,返回合并后的链头t2,用于合并链表/拉链
  3. backpatch(t1,code): 语义过程,用code回填t1,确定 label 地址时就调用这个

如:

1
2
3
4
5
6
(p) (j, -, -, 0)     (u) (j, -, -, 0)
…… ……
(q) (j, -, -, p) (v) (j, -, -, u)
…… ……
(r) (j, -, -, q) (w) (j, -, -, v)
t1=r t2=w

执行merge(t1,t2)

1
2
3
4
5
6
7
(p) (j, -, -, 0)    (u) (j, -, -, r)
…… ……
(q) (j, -, -, p) (v) (j, -, -, u)
…… ……
(r) (j, -, -, q) (w) (j, -, -, v)

链头t2=w

执行backpatch(t2,120)

1
2
3
4
5
(p) (j, -, -, 120)  (u) (j, -, -, 120)
…… ……
(q) (j, -, -, 120) (v) (j, -, -, 120)
…… ……
(r) (j, -, -, 120) (w) (j, -, -, 120)

翻译方案

if-then 不负责生成四元式,只负责填 0!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
S→if B then S1
S→M S1
M→if B then

M→if B then
{
backpatch(B.T, ip); // B.T 即为下一句的地址,所以可以直接填当前 ip
M.CHAIN:=B.F // B.F 在后面,所以创建链表
}

/*
* 另外,在图9-3中,整个语句翻译完成后,B.F仍不能确定,只能
* 将它作为S的语义值S. CHAIN暂时保留下来。如果S,本身也是控
* 制语句(比如另一个嵌套的条件语句),它也有语义值S. CHAIN未
* 确定,则B.F和S.CHAIN应转到同一个地方,因此要将它们链
* 接起来,组成一个新的链,链首地址记录在S的语义值S. CHAIN
* 中,这项工作由语义函数merge()完成。
*/
S→M S1
{
S.CHAIN:=merge(M.CHAIN, S1.CHAIN) // B.F
}
例

这里还有一个 bug:S 执行完以后还没有回填 S.CHAIN。这一步其实是交给 S 后面的分号来做的,而这是执行语句的文法,已经脱离了本节讨论的控制语句文法。因此上面的例子(以及后面的例子)并没有提及。

分号时的回填
分号时的回填

if-then-else 只需要生成一个四元式:then 后的语句执行完以后要 jump 到 else 后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
S→if B then S1 else S2 
M→if B then
N→M S1 else
S→N S2

M→if B then
{
backpatch(B.T, ip);
M.CHAIN:=B.F
}

N→M S1 else
{
q:=ip;
gen(j,-,-,0);
backpatch(M.CHAIN,ip);
N.CHAIN:=merge(S1.CHAIN , q)
}

S→N S2
{
S.CHAIN:=merge(N.CHAIN, S2.CHAIN)
}
例子
例子

While 语句的翻译

文法

1
S→while B do S1

翻译方案

while 语句其实就是 if-then 语句多了一个 jump

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
W→while
D→W B do
S→D S1

W→while
{
W.code := ip;
}

D→W B do
{
backpatch(B.T, ip);
D.CHAIN = B.F;
D.code = W.code; // 子变量值传给父变量
}

S→D S1
{
backpatch(S1.CHAIN,D.code);
gen(j,-,-,D.code);
S.CHAIN:=D.CHAIN;
}
例子
例子

可以看出,许多语句的最后都有一个S.CHAIN链,然而对赋值语句来说,没有需要返填的三地址语句,为了统一,我们给赋值语句赋一个空链。语义程序如下:

1
2
S->A
{S.CHAIN=0;}

For 循环语句的翻译

文法

1
S→for i:=1 to N do S1

其语义为:

1
2
3
4
5
6
        i:=1;
again: if i<=N then begin
S1;
i:=i+1;
goto again
end

代码结构可为:

1
2
3
4
5
6
7
F+0:(:=,'1',-,i)
F+1: (j<=,i,N,F+3)
F+2: (j,-,-,0)
F+3: (S1的四元式序列)
...
D+0: (+,i, ‘1’,i)
D+1: (j,-,-,F+1)

语义变量

为了在生成S1的代码之前生成i:=1等三个语句,必须改写文法。

1
2
F→for i:=1 to N do
S→F S1
  • F.again:记录F+1
  • F.CHAIN:记录前述F+2的地址
  • F.place:记录i在符号表入口

翻译方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
F→for i:=1 to N do
{
gen(:=,'1',-,entry(i));
F.again:=ip;
gen(j<=,entry(i),N,F.again+2);
F.CHAIN:=ip;
gen(j,-,-,0);
F.place:=entry(i)
}

S→F S1
{
backpatch(S1.CHAIN,ip);
gen(+,F.place,'1',F.place);
gen(j,-,-,F.again);
S.CHAIN:=F.CHAIN
}
例题
例题

另一道例题:写出下面代码的中间代码序列。

1
for i=1 to 10 do if A>100 then C=C+1;
1
2
3
4
5
6
7
8
9
10
100: (=, 1, -, i)
101: (J<=, i, 10, 103) F.again=103
102: (J, -, -, 109)
103: (J>, A, 100, 105)
104: (J, -, -, 107)
105: (+, C, 1, t1)
106: (=, t1, -, C)
107: (+, i, 1, i)
108: (J, -, -, 103)
109:

更多例题:

1
if  (A<X) & (B>0) then while C>0 do C:=C+D;
1
2
3
4
5
6
7
8
9
10
11

100 (j<, A, X, 102)
101 (j, -, -, 109)
102 (j>, B, 0104)
103 (j, -, -, 109)
104 (j>, C, 0106)
105 (j, -, -, 109)
106 (+, C, D, T1)
107 (:=, T1, -, C)
108 (j, -, -, 104)
109

1
2
3
4
5
6
7
8
9
z := 3;
while j< 10 do
begin
j := x+1;
if x <10 then
y:= A+m;
else
y:= A-m;
end
1
2
3
4
5
6
7
8
9
10
11
12
13
100 (=, 3, _, z)
101 (J<, j, 10, 103)
102 (J, -, -, 113)
103 (+, x, 1, t1)
104 (=, t1, -, j)
105 (J<, x, 10, 107)
106 (J, -, -, 110)
107 (+, A, m, t2)
108 (=, t2, -, y)
109 (J, -, -, 112)
110 (-, A, m, t3)
111 (=, t3, -, y)
112 (J, -, -, 101)

过程的的翻译(自学)

第十章 代码优化和目标代码生成

优化是一种等价的,有效的程序变换
等价——不改变程序运行结果
有效——时空效率要高

优化按阶段分类:

  1. 源程序阶段的优化:优化数据结构和算法
  2. 编译优化:中间代码和目标代码优化

中间代码优化:便于移植(与机器无关)。又分为:

  1. 局部优化:在基本块内的优化
  2. 全局优化:超越基本块,基本块之间的优化

局部优化

划分基本块

(1)寻找入口语句

  • 程序的第一条语句
  • 由转向语句转移到的语句
  • 紧跟在条件转向语句后的那个语句
    (2)寻找出口语句
  • 转向语句
  • 停止语句
    (3)基本块为:
  • 每个入口地址(含)到下一个入口地址(不含)
  • 每个入口地址(含)到下一个出口地址(含)
    (4)不在任何基本块中的代码可以被删除
例题
例题

构造流图

下面是正确的废话:

$$G = (N, E, n_0)$$
(1)基本块集即为结点集N;
(2)包含程序第一个语句的基本块,为首结点n0;
(3)设基本块 Bi , Bj ∈ N ,若满足下列条件之一,则Bi ->Bj

  • Bj 紧跟在 Bi 之后,且 Bi 的出口语句不是无条件转向或停止语句
  • Bi 的出口语句为转向语句,其转向点恰为Bj 的入口语句
刚才那道例题
刚才那道例题

基本块内的优化

合并已知量
1
2
3
4
5
6
7
// 优化前
B := 1
C := 2
A := B + C

// 优化后
A := 3
删除公共子表达式
1
2
3
4
5
6
7
8
// 优化前
B := 1
C := 2
A := B + C
D := B + C

// 优化后
D := A
删除无用赋值
1
2
3
4
5
6
// 优化前
A := 1
A := 2

// 优化后
A :=2
删除死代码

若某个基本块实际不可能被执行,该基本块为死代码,可以删除。

例题
例题
例题

全局优化(自学)

本节只讨论对循环进行的优化。

循环的定义

循环:程序流图中,有唯一入口结点的强连通子图。

强连通子图:子图里面任意两个结点可以互通。

程序流图
程序流图

{5, 6, 7, 8, 9} 是循环:所有点都互通,且 5 是唯一入口。

循环的查找

  1. 必经结点:从流图的首结点出发,到达结点n的任一通路都必须经过的结点d,称为n的必经结点。记为 d DOM n
  • 每个结点是它本身的必经结点,即n DOM n
  • 首结点是任一结点的必经结点,即n0 DOM n

上图的必经节点集:

1
2
3
4
5
6
7
8
9
10
D(1)={1}
D(2)={1,2}
D(3)={1,2,3}
D(4)={1,2,4}
D(5)={1,2,4,5}
D(6)={1,2,4,5,6}
D(7)={1,2,4,5,6,7}
D(8)={1,2,4,5,6,8}
D(9)={1,2,4,5,6,9}
D(10)={1,2,4,10}
  1. 回边:若 d 是 n 必经节点,且存在边 n->d,则该边为回边。

上图有三条回边:

1
2
3
5->4
9->5
10->2
  1. 若 n->d 是回边,则图里能到n且不经过d的点的集合+n+d 就是由 n->d 组成的循环
程序流图
程序流图

上图的循环有:

1
2
3
5->4 组成 {5, 4, 6, 7, 8, 9}
9->5 组成 {9, 5, 6, 7, 8}
10->2 组成 {10, 2, 3, 4, 5, 6, 7, 8, 9}

循环优化方法

代码外提
1
2
3
4
5
6
7
8
9
10
11
12
13
// 优化前
for (int i = 0; i < n; i++)
{
float pi = acos(-1);
// ...
}

// 优化后
float pi = acos(-1);
for (int i = 0; i < n; i++)
{
// ...
}
强度削弱
1
2
3
4
5
6
7
8
9
10
11
12
// 优化前
for (int i = 1; i < 10; i++)
{
int j = i * 10 + 5;
}

// 把乘法优化成加法后
int j = 5;
for (int i = 1; i < 10; i++)
{
j += 10;
}

例子中,i=循环次数+c 叫做基本归纳变量;j=循环次数*c1+c2 叫做同族归纳变量。强度削弱把基本归纳变量变为同族归纳变量,将乘法变为加法,还可以将普通加法变为变址器加法。

删除归纳变量

即改用同族归纳变量作为判断条件

1
2
3
4
5
6
7
8
9
10
11
12
13
// 优化前
int j = 5;
for (int i = 1; i < 10; i++)
{
j += 10;
}

// 优化后
int j = 5;
for (; j < 5 + 10*10;)
{
j += 10;
}
例题

优化前:

1
2
3
4
5
6
7
8
9
10
11
12
(1)PROD := 0
(2)I := 1
(3)T1 := 4 * I
(4)T2 := a0 – 4
(5)T3 := T2[T1]
(6)T4 := 4 * I
(7)T5 := b0 – 4
(8)T6 := T5[T4]
(9)T7 := T3 * T6
(10)PROD := PROD + T7
(11)I := I + 1
(12)if I ≤ 20 goto (3)

优化后:

1
2
3
4
5
6
7
8
9
10
(1)PROD := 0
(2)T1 = 0;
(3)T2 := a04
(4)T5 := b0 4
(5)T1 := T1 + 4;
(6)T3 := T2[T1]
(7)T6 := T5[T1]
(8)T7 := T3 * T6
(9)PROD := PROD + T7
(10)if T180 goto (5)

目标代码生成

目标代码生成的主要问题:

  1. 选择合适的指令 生成最短的代码
  2. 充分利用有限的寄存器

如何充分利用寄存器(自学)

第十一章 运行时存储空间的组织

变量及存储分配