什么是编译？

计算机程序语言可以分为：

机器语言(Machine Language)：
- 特点：可以被计算机直接理解
- 与人类表达习惯相去甚远
- 难记忆、编写、阅读，易写错
汇编语言(Assembly Language)：
- 特点：在机器语言的基础上引入助记符
- 依赖于特定机器，非专业人员使用受限制
- 编写效率依然很低
高级语言(High Level Language)：
- 特点：类似于数学定义或自然语言的简洁形式
- 接近人类表达习惯
- 不依赖于特定机器
- 编写效率高

一个例子：人工英汉翻译

编译(Compiling)：将高级语言(源语言)翻译为汇编语言或机器语言(目标语言)的过程

即：高级语言->编译->汇编语言->汇编->机器语言
或：高级语言->编译->机器语言
例：x=2 -> MOV x,2 -> C706 0000 0002(用十六进制表示的二进制数)

编译器在语言处理系统中的位置

为了建立可执行目标程序，除编译器还需要一些其他工具进行配合：

预处理器(Preprocessor)：
- 一个源程序可能分成几个模块存放在不同的文件里，需要预处理器把存储在不同文件中的源程序聚合在一起
- 把称为宏的缩写语句转换为原始语句
编译器(Compiler)：
- 将高级语言翻译成汇编语言或机器语言
汇编器(Assembler)：
- 将汇编语言翻译成可重定位的机器语言
- 若在编译器阶段已经直接将高级语言翻译成机器语言，则可以省略汇编器
- 可重定位(Relocatable)/可再装配
  - 数据在内存存放的起始位置L不是固定的，起始位置+相对地址=绝对地址)
链接器(Linker)：
- 将多个可重定位的机器代码文件(包括库文件)连接到一起
- 解决外部内存地址问题(一个文件中的代码可能指向另一个文件中的位置)
加载器(Loader)：
- 修改可重定位地址
- 将修改后的指令和数据放到内存中适当的位置(然后执行)

编译器结构：分析部分(前端)+综合部分(后端)

前端(front end)：与源语言相关
- 字符流——词法分析器——词法单元流——语法分析器——语法树——语义分析器——语法树——中间代码生成器
前端——中间表示形式——机器无关代码优化器——中间表示形式——后端
后端(back end)：与目标语言相关
- 中间表示形式——目标代码生成器——目标机器语言——机器相关代码优化器——目标机器语言

在分析过程中需要收集标识符的属性信息，使用符号表(Symbol Table)存放属性信息，生成的符号表可供编译的各个步骤使用

符号表是用于存放标识符的属性信息的数据结构
- 名字(name)：字段以字符串表形式存储
  - 将所有name字段组织成一个长的字符串，符号表中存储指向其起始位置的字符即可
  - name=标识符在字符串表中的起始位置+长度
- 种属(Kind)：简单变量、复合变量(数组、记录、…)、过程、…
- 类型(Type)：整型、实数型、字符型、布尔型、指针型、…
- 存储位置、长度
- 值
- 作用域(实际上是访问链的嵌套关系)
- 参数和返回值信息：参数个数、参数类型、参数传递方式、返回值类型、…
符号表的作用
- 辅助代码生成
- 一致性检查

词法分析

主要任务：从左向右逐行扫描源程序字符，识别出各个单词，确定单词的类型，将识别出的单词转成统一的机内表示——词法单元(token)形式

token：<种别码，属性值>

种别码由语法分析部分使用，属性值为指向符号表中关于此词法单元的条目(不是指单词对应的实际存储的值)

在上下文无关文法中，种别码一般是一个终结符号
种别码：
- 可以使用抽象符号作为种别码的名字，也可以使用单词本身
- 属性值可以为空

序号	单词类型	种别码	token类型
1	关键字	programme,if,else,then,…	一词一码
2	标识符	变量名,数组名,记录名,过程名,…	多词一码
3	常量	整型,浮点型,字符型,布尔型,…	一型一码
4	运算符	算术、关系、逻辑…	一型一码/一词一码
5	界限符	;,(),{},…	一词一码

例：程序中语句经词法分析后得到的token序列

输入：while(value!=100){num++;}
输出：

序号	程序符号	token
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, - >

语法分析

主要任务：从词法分析器输出的token序列中识别出的token，通过token中的第一个分量(种别码)构造语法分析树(parse tree)，语法分析树描述句子的语法结构

例：赋值语句的分析树

position = initial + rate * 60
token序列：
<id,1> <=> <id,2> <+> <id,3> <*> <\number,4>

例：变量声明语句的分析树
文法：

<D> -> <T> <IDS>;
<T> -> int|real|char|bool;
<IDS> -> id|<IDS>,id

输入：int a,b,c;

语义分析

主要任务：进一步收集类型信息，将这些信息放入语法树或符号表

语义检查

变量或过程是否未经声明就使用
变量或过程名是否重复声明
运算分量类型是否匹配
操作符与操作数之间的类型是否匹配
- 数组下标是否为整数
- 是否对非数组变量使用数组访问操作符
- 是否对非过程名使用过程调用标识符
- 过程调用的参数类型或数目是否匹配
- 函数返回类型是否正确

中间代码生成及编译器后端

常用中间表示形式

三地址码(Three-address Code)
- 三地址码由类似于汇编语言的指令序列组成，每个指令最多有三个操作数(operand)
- 可唯一确定运算完成的顺序(右部至多只有一个运算符)
语法结构树/语法树(Syntax Trees)
- 注意这里的语法格式树(AST)和语法分析阶段的语法分析树不同
三地址码中地址的形式可能是：
- 源程序中的名字(name)
- 常量(constant)
- 编译器生成的临时变量(temporary)
三地址指令的表示
- 四元式(Quadruples)
  - (op,y,z,x)
  - 四元式之间的联系是通过临时变量实现的(注意是四元式之间)
  - 四元式的优点是便于优化处理和表的变动
- 三元式(Triples)
- 间接三元式(Indirect triples)

常见的三地址指令

序号	指令类型	指令形式	四元式表示
1	赋值指令	x = y op z	(op,y,z,x)
2	复制指令	x = y	(=,y,-,x)
3	条件跳转	if x relop y goto n	(relop,x,y,n)
4	非条件跳转	goto n	(goto,-,-,n)
5	参数传递	param x	(param,-,-,x)
6	过程调用	call p,n	(call,p,n,-)
7	过程返回	return x	(return,-,-,x)
8	数组引用	x = y[i]	(=[],y,i,x)
9	数组赋值	x[i] = y	([]=,y,x,i)
10	地址及指针操作	x = & y	(&,y,-,x)
10	地址及指针操作	x = *y	(=*,y,-,x)
10	地址及指针操作	*x = y	(*=,y,-,x)

例：中间代码生成

while a<b do
    if c<5 then
        while x>y do
            z=x+1;
    else x=y;

100:(j<,a,b,102)
101:(j,-,-,112)
102:(j<,c,5,104)
103:(j,-,-,110)
104:(j>,a,b,102)
105:(j,-,-,100)
106:(+,x,1,t1)
107:(=,t1,-,z)
108:(j,-,-,104)
109:(j,-,-,100)
110:(=,y,-,x)
111:(j,-,-,100)
112: