本笔记基于北京邮电大学出版的李文生编著的《编译程序设计原理与技术》整理

​

1. 翻译和解释

1.1. 翻译程序

翻译程序 扫描所输入的源程序，并将其转换为目标程序，或将源程序直接翻译成结果。

其中，若源语言是汇编语言，目标语言是机器语言，则该翻译程序称为 汇编程序；如果源语言为高级语言，目标语言是某机器的机器语言或汇编语言，则该翻译程序称为 编译程序。

实现程序到目标程序的转换所占用的时间称为编译时间。源程序和数据是在不同时间（即分别在编译阶段和运行阶段）进行处理的。

​

1.2. 解释程序

解释程序 解释执行源程序，不生成目标程序，即同时处理源程序和数据。

某些解释程序每次直接分析一条要执行的源程序语句很费时间，一种有效的方法：先将源程序转换为某种中间形式，然后对中间形式的程序解释执行。

​

2. 编译的阶段和任务

按照编译程序的执行过程和所要完成的任务，可以把它分成前后两个阶段，即 分析阶段 和 综合阶段。

分析阶段根据原语言的定义，分析源程序的结构，以检查是否符合语言的规定，确定源程序所表示的对象和规定的操作，并以某种中间形式表示出来。分析阶段包括：

  • 词法分析
  • 语法分析
  • 语义分析

综合阶段根据分析结果构造出所要求的目标程序。综合阶段包括：

  • 中间代码生成
  • 代码优化
  • 目标代码生成

​

一种典型的编译程序结构：

​

2.1. 词法分析

词法分析 又称为扫描，是一种『线性分析』，是编译过程的第一个阶段。

词法分析器 ：

  • 依次读入源程序中的每个字符，对构成源程序的字符串进行分解，识别出每个具有独立意义的字符串作为记号（token）并组织成记号流，形成记号的字符串叫做该记号的单词(lexeme)。
  • 把需要存放的单词放到符号表中，如变量名，标号，常量等。

词法分析的工作依据是源语言的构词规则(即词法)，也称为模式(pattern)。

​

2.2. 语法分析

语法分析 是一种『层次结构的分析』，在词法分析的基础上把记号流按语言的语法结构层次地分组，以形成语法短语。源程序的语法短语常用分析树表示，语法分析树也称为语法树。

语法分析的工作依据是元语言的语法规则。

程序的层次结构通常由递归的规则表示，如表达式的定义如下：

  • 任何一个标识符是一个表达式
  • 任何一个数是一个表达式
  • 如果 $expr_1$和 $expr_2$ 是表达式，$expr_1 + expr_2$ 、$expr_1 * expr_2$ 、$(expr_1)$ 也都是表达式

这里，规则 1 和规则 2 是非递归的基本规则，而规则 3 是把运算符作用于其他表达式来定义表达式的规则。

​

2.3. 语义分析

语义分析 是对语句的意义进行检查，以保证程序各部分能够有机结合在一起，并为以后生成目标代码收集类型等必要信息。语义分析使用语法分析确定的层次结构来表示各语法成分。

语义分析的工作依据是源语言的语义规则。

语义分析的一个重要任务：类型检查

  • 根据规则检查每个运算符及其运算对象是否符合要求；
  • 数组的下标是否合法；
  • 过程调用时，形参与实参个数、类型是否匹配等

​

2.4. 中间代码生成

中间代码 是经语法分析和语义分析之后，编译程序通常将源程序生成的一种中间表示形式。我们可以把中间代码看成是一种抽象的机器程序。

中间代码应具有两个重要的特点：

  • 易于产生
  • 易于翻译成目标代码

​

2.5. 代码优化

代码优化 是对代码进行改进，使之占用的空间少、运行速度快。编译程序的代码优化首先是在中间代码上进行的，从优化的中间代码可以得到较优的目标代码。

​

2.6. 目标代码生成

生成的目标代码一般是可以重定位的机器代码或汇编语言代码。

涉及到的两个重要问题：

  • 对程序中使用的每个变量要指定存储单元
  • 对变量进行寄存器分配