引论
# 引论
课件
# 什么是编译
# 计算机程序设计语言及编译
- 编译是将高级语言(源语言)翻译成汇编语言或机器语言(目标语言) 的过程
高级语言,汇编语言,机器语言的关系以及编译过程示意图
# 语言处理器
# 解释器
- 除了翻译器,解释器也是一种常见的语言处理器,其不通过翻译的方式生成目标程序,而是逐个语句的执行源程序
- 编译器最终生成的机器语言的目标程序执行速度通常较快
- 解释器的错误诊断效果通常比编译器好,因为其是逐条执行语句的
# 编译器
语言编译的基本过程示意图
预处理器
- 把存储在不同文件中的源程序聚合在一起
- 把被称为 宏 的缩写语句转换为原始语句
链接器
- 将多个可重定位的机器代码文件连接到一起,包括
- 库文件
- 其它可重定位的目标程序
- 因为大型程序经常被分为多个部分进行编译
- 一个文件中的代码可能指向另外一个文件中的位置, 这个外部内存地址的问题由链接器解决
加载器
- 修改可重定位地址;
- 起始位置 + 相对地址 = 绝对地址
- 将修改后的指令和数据放到内存中适当的位置
笔记
- 编译器产生汇编语言而不是机器语言的原因是汇编语言更容易输出与调试
- 可重定位(Relocatable):
- 在内存中存放的起始位置L不是固定
# 编译器的结构
- 由分析部分和综合部分两个部分组成
分析部分
- 分析部分为前端,与源语言相关
- 分析部分将源程序分解成多个组成要素,并在这些要素之上加上语法结构,然后使用这个结构创建源程序的一个中间表示
- 如果分析部分检查出语法上的错误或者语义上的不一致,其必须提供相应的信息,以方便用户修改
- 分析部分会收集有关源程序的信息,并将信息存放在一个称为符号表(symbol table)的数据结构中
- 输出为符号表和中间表示形式
- 分析部分将源程序分解成多个组成要素,并在这些要素之上加上语法结构,然后使用这个结构创建源程序的一个中间表示
综合部分
- 综合部分为后端,与目标语言相关
- 根据中间表示形式和符号表中的信息来构建目标程序
编译器结构示意图
- 编译过程顺序执行了一组步骤
- 每个步骤将源程序的一种表示方式转变为另一种表示方式
- 在前端和后端之间,有些编译器会有一个与机器无关的优化步骤
# 词法分析概述
- 词法分析也称为扫描(scanning)
词法分析主要任务
- 从左向右逐行扫描源程序的字符,识别出各个单词,确定单词的类型
- 将识别出的单词转换成统一的机内表示——词法单元(
token
)形式token
:< 种别码,属性值 >- 种别码表示由语法分析步骤使用的抽象符号
- 属性值指向符号表中关于这个词法单元的条目
单词类型 种别 种别码 1 关键字 program、if、else、then、… 一词一码 2 标识符 变量名、数组名、记录名、过程名、… 多词一码 3 常量 整型、浮点型、字符型、布尔型、… 一型一码 4 运算符 算术( + - * / ++ -- ) 关系( > < == != >= <= ) 逻辑( & ~ ) 一词一码 或 一型一码 5 界限符 ; ( ) = { } … 一词一码
例:词法分析后得到的 `token` 序列
# 语法分析概述
- 语法分析也称为解析(parsing)
- 语法分析器(parser)从词法分析器输出的
token
序列中识别出各类短语,并构造语法分析树(parse tree)- 语法分析树描述了句子的语法结构
示意图
- 语法分析树描述了句子的语法结构
- 详细内容见第 4 章
# 语义分析概述
- 收集标识符的属性信息并生成符号表
属性信息分类
- 种属 (Kind)
- 简单变量、复合变量(数组、记录、…)、过程、…
- 类型 (Type)
- 整型、实型、字符型、布尔型、指针型、…
- 存储位置、长度
- 值
- 作用域
- 参数和返回值信息
- 参数个数、参数类型、参数传递方式、返回值类型、…
符号表:用于存放标识符的属性信息的数据结构
# 语义检查
语义检查的内容
- 变量或过程未经声明就使用
- 变量或过程名重复声明
- 运算分量类型不匹配
- 操作符与操作数之间的类型不匹配
- 数组下标不是整数
- 对非数组变量使用数组访问操作符
- 对非过程名使用过程调用操作符
- 过程调用的参数类型或数目不匹配
- 函数返回类型有误
# 中间代码生成及编译器后端概述
# 常用的中间表示形式
三地址码 (Three-address Code)
- 三地址码由类似于汇编语言的指令序列组成,每个指令最多有三个操作数(operand)
序号 | 指令类型 | 指令形式 |
---|---|---|
1 | 赋值指令 | x = y op z x = op y |
2 | 复制指令 | x = y |
3 | 条件跳转 | if x relop y goto n |
4 | 非条件跳转 | goto n |
5 | 参数传递 | param x |
6 | 过程调用 | call p, n |
7 | 过程返回 | return x |
8 | 数组引用 | x = y[i] |
9 | 数组赋值 | x[i] = y |
10 | 地址及 指针操作 | x =& y x =* y *x = y |
地址可具有如下形式之一
- 源程序中的名字(name)
- 常量(constant)
- 编译器生成的临时变量(temporary)
三地址指令的表示
- 四元式 (Quadruples)
- (op, y, z, x)
- op 为操作符
- y, z 为操作数
- x 为返回值
- (op, y, z, x)
- 三元式 (Triples)
- 间接三元式 (Indirect triples)
- 四元式 (Quadruples)
# 目标代码生成
- 目标代码生成以源程序的中间表示形式作为输入,并把它映射到目标语言
- 目标代码生成的一个重要任务是为程序中使用的变量合理分配寄存器
# 代码优化
为改进代码所进行的等价程序变换,使其运行得更快一些、占用空间更少一些,或者二者兼顾
编辑 (opens new window)