编译原理 第一章(绪论)
程序文件编译过程
预处理器:
· 把存储在不同文件中的源程序聚合在一起
· 把被称为宏的缩写语句转换为原始语句
可重定位:
· 在内存中存放的起始位置L不是固定的
链接器
· 将多个可重定位的机器代码文件(包括库文件)连接到一起
· 解决外部内存地址问题(引用外部文件的内容造成的)
加载器:
· 修改可重定位地址;
· 将修改后的指令和数据放到内存中适当的位置
起始位置+相对地址=绝对地址
编译器的结构
词法分析
词法分析的主要任务
- 从左向右逐行扫描源程序的字符,识别出各个单词,确定单词的类型。
- 将识别出的单词转换成统一的机内表示——词法单元(token)形式
token:< 种别码,属性值>
例:词法分析后得到的token序列
输入
while(value!=100){num++;}
输出
1 while < WHILE , - >
2 ( < SLP , - >
3 value < IDN , value >
4 != < NE , - >
5 100 < CONST , 100 >
6 ) < SRP , - >
7 { < LP , - >
8 num < IDN , num >
9 ++ < INC , - >
10 ; < SEMI , - >
11 } < RP , - >
语法分析
语法分析器(parser)从词法分析器输出的token序列中识别出各类短语,并构造语法分析树(parse tree)
例:赋值语句的分析树
position = initial + rate * 60 ;
<id, position> <=> <id,initial> <+> <id, rate> <*> <num,60> <;>
例:变量声明语句的分析树
文法:
→ ;
→ int | real | char | bool
→ id | , id
输入:
int a , b , c ;
语义分析
收集标识符的属性信息
-
种属(Kind)
简单变量、复合变量(数组、记录、…)、过程、… -
类型(Type)
整型、实型、字符型、布尔型、指针型、… -
存储位置、长度
例 -
值
-
作用域
-
参数和返回值信息
参数个数、参数类型、参数传递方式、返回值类型、…
符号表
语义分析的主要任务
-
收集标识符的属性信息
-
语义检查
变量或过程未经声明就使用
变量或过程名重复声明
运算分量类型不匹配
操作符与操作数之间的类型不匹配数组下标不是整数
对非数组变量使用数组访问操作符
对非过程名使用过程调用操作符
过程调用的参数类型或数目不匹配
函数返回类型有误
中间代码生成
常用的中间表示形式
- 三地址码(Three-address Code)
三地址码由类似于汇编语言的指令序列组成,每个指令最多有三个操作数(operand) - 语法结构树/语法树(Syntax Trees)
常用的三地址指令
地址可以具有如下形式之一
源程序中的名字(name)
常量(constant)
编译器生成的临时变量(temporary)
三地址指令的表示
- 四元式(Quadruples)
(op, y, z, x) - 三元式(Triples)
- 间接三元式(Indirect triples)
三地址指令的四元式表示
//基本运算
x = y op z ( op , y , z , x )
x = op y ( op , y , _ , x )
x = y ( = , y , _ , x )
if x relop y goto n( relop , x , y , n )
goto n ( goto , _ , _ , n )
//函数调用
param x (param, _ , _ , x )
call p, n ( call , p , n , _ )
return x (return, _ , _ , x )
//数组运算
x = y[i] ( =[] , y , i , x )
x[i] = y ( []= , y , x , i )
//指针运算
x = &y ( & , y , _ , x )
x = *y ( =* , y , _ , x )
*x = y ( *= , y , _ , x )
例子
目标代码生成
- 目标代码生成以源程序的中间表示形式作为输入,并把它映射到目标语言
- 目标代码生成的一个重要任务是为程序中使用的变量合理分配寄存器
代码优化
为改进代码所进行的等价程序变换,使其运行得更快一些、占用空间更少一些,或者二者兼顾