什么是编译

计算机程序设计语言以及编译

机器语言
- 可以被计算机直接理解
- 二进制和十六进制
- 编写阅读困难
汇编语言
- 引入注记符
- 依赖于特定机器
- 书写效率低
高级语言
- 类似数学定义和自然语言
- 更接近人类习惯
- 不依赖特定机器
- 简洁

将高级语言翻译成汇编语言或者直接翻译成机器语言的过程称为编译。

将汇编语言翻译成机器语言的称为汇编。

编译的定义：将高级语言（源语言）翻译成汇编语言或机器语言（目标语言）的过程。

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

预处理器把存在不同文件中的源程序聚合在一块，把称为宏的编写语句转换为原始语句
加载器修改可重定位地址：将修改后的指令和数据放到内存中适当的位置
链接器将多个可重定位的机器代码文件（包括库文件）链接在一块，解决外部内存地址（引用其他文件对象或过程）问题
可重定位：在内存中存放的起始位置L不是固定的

编译系统的结构

高级语言程序 =》编译器 =》机器语言

下面是编译的流程图，编译过程，编译器主要进行如下步骤

词法分析

原理概述

词法分析是编译器的第一个阶段。

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

token：<种别码，属性值>

种别码是单词的种类（词性词类）

属性值是区分同一种别的标识，具体来说就是存储字面值

词法分析例子

while是一个关键字，一词一码，种别码就可以唯一确定这个单词，所以属性值空。同样的道理，左括号、不等号、右括号、左花括号、++、封号、右花括号他们都是一词一码，所以属性值空。
value和num是两个标识符，还有100是常量，仅仅凭借种别码不能唯一确定，所以在属性值中放入他们的字面值，来唯一确定他们。

语法分析

语法分析是编译的第二个阶段。

语法分析的主要任务：语法分析器(parser)从词法分析输出的token序列中识别出各类短语，并构造语法分析树(parse tree)

语法分析树描述了程序语句的语法结构

例1：赋值语句的语法分析树

1	position = initial + rate * 60;

经过词法分析我们可以得到对应的token序列

1 2	position = initial + rate * 60; <id,position><=><id,initial><+><id,rate><*><num,60>

我们可以的到语法分析树：

一个标识符和一个常数，它们本身可以构成表达式。一个表达书通过运算符，例如“+、*”又可以构成另外一个表达式。
标识符连接上一个赋值符号再连接上一个表达式最后连接一个封号可以构成赋值语句。

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

文法，文法是一系列规则构成的：

这里的D表示declaration，表示声明语句
T是type，表示类型
IDS是identifier sequence，表示标识符序列

<D>-><T><IDS>;
一个声明语句是由一个类型连接上一个标识符序列和一个封号构成
<T>->int|real|char|bool
类型可以是int，real，char，bool中的一个
<IDS>->id|<IDS>,id
一个标识符id本身可以构成一个标识符序列；一个标识符序列和一个id通过","连接起来，可以构成一个更大的标识符序列

根据上面的文法，我们输入：
1
int a,b,c;
可以得到它的分析树

语义分析

语义分析是编译的第三个阶段

语义分析的主要任务：

收集标识符的属性信息

语义检查

收集标识符属性信息

标识符的属性

标识符都有哪些属性呢？

种属（Kind）
- 简单变量、复合变量（数组、记录、…）、过程、…
类型（Type）
- 整型、实型、字符型、布尔型、指针型、…
存储位置、长度
值
过程的作用域
参数和返回值信息
- 参数个数、参数类型、参数传递方式、返回值类型、…

符号表

语义分析的到的标识符的信息都会存放在符号表中。

上面的表中，每一行，称为符号表的一条记录。每一个标识符都会对应一条记录。每一个字段就对应了标识符的一个属性，比如类型type、种属kind等。

符号表通常带有一个字符串表，存放程序中用到的标识符和常字符串。

NAME分成两部分，一部分存放标志符在字符串表中的起始位置，另一部分用来存放标识符的长度。

语义检查

语义分析主要包括如下工作

变量或过程未经声明就使用
变量或过程名重复声明
运算分量类型不匹配（可能进行强制类型转换）
操作符和操作数的类型不匹配
- 数组下标不是整数
- 对非数组变量使用数组访问操作符
- 对非过程名使用调用操作符
- 过程调用的参数类型或数目不匹配
- 函数返回类型有错误

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

中间代码生成

常用的中间表示形式

三地址码（Three-address Code）
- 三地址码由类似于汇编的指令序列组成，每个指令最多有三个操作数（operand）
- 常用的三地址指令
  - 地址可以具有如下形式之一
    - 源程序中的名字（NAME）
    - 常量（constant）
    - 编译器生成的临时变量
- 三地址指令表示
  - 四元式（Quadruples）
    - （op，y，z，x）
    从上面的示例，我们可以看出：三地址指令序列唯一确定了一个运算完整的顺序
  - 三元式（Triples）
  - 间接三元式（Indirect triples）
语法结构树/语法树（Syntax Trees）
- 请注意这里的的语法结构树和起那面的语法分析树不是一回事

中间代码生成的例子

右边的式中间代码，左边的式语法结构树。

其中左边的树中：S是中间代码集合，B是判断语句，E是表达式

目标代码生成

目标代码生成以源程序的中间表示形式作为输入，并把它映射到目标语言
目标代码生成的一个重要任务是为程序中使用的变量合理分配寄存器

代码优化

为改进代码所进行的等价程序变换，使其运行得更快一些、占用空间更少一些、或者两者兼顾

包括例如：自动识别代码中得重复运算

Puitar's Blog

编译原理学习笔记1