编译原理笔记（1）绪论

1.什么是编译

编译的定义：将高级语言翻译成汇编语言或机器语言的过程。前者称为源语言，后者称为目标语言。

高级语言源程序的处理过程：

预处理器的功能：

• 把存储在不同文件中的源程序聚合在一起。
• 把被称为宏的缩写语句转换为原始语句。

可重定位的定义：在内存中存放的起始地址不是固定的，代码中的绝对地址是由起始位置和相对地址相加获得的。

加载器的作用：

• 修改可重定位地址；
• 将修改后的指令和数据放到内存中的合适位置处。

链接的定义：将可重定位的目标文件与其他可重定位的目标程序以及库文件连接。

链接器的作用：

• 将多个可重定位的机器代码文件和库文件连接到一起。
• 解决外部内存地址问题。

2.编译系统的结构

编译的各个阶段：

• 分析部分：也被称为编译器前端，是从词法分析器到中间代码生成器的部分。该部分只与源语言相关。
• 综合部分：也被称为编译器后端，包括目标代码生成器和机器相关代码优化器。该部分只与目标语言相关。

备注：在实际实现中，编译的各个阶段可能会整合在一起。如语义分析器常常和中间代码生成器放在一起。

语义制导翻译的概念：在分析语法规则时结合语义规则进行语义分析。这样，语法分析、语义分析和中间代码生成可以放在一起实现。

3.词法分析概述

词法分析的主要任务：

• 从左到右逐行扫描源程序的字符，识别出各个单词，确定单词的类型。
• 将识别出的单词转换为统一的机内表示——词法单元(token)形式。

词法单元token介绍：

• 构成方式：是一个二元组，表示为<种别码，属性值>。
• 区分方法：首先通过种别码区分不同的词语，如果种别码相同则通过属性值区分。如果种别码为一词一码，则该词语的词法单元就无需属性值。

单词类型的分类：

• 关键字：所有不同的关键字都对应唯一一个种别码。
• 标识符：所有不同的标识符共享同一个种别码。
• 常量：不同类型的常量对应的种别码不同；相同类型的常量使用同一个种别码。
• 运算符和界限符：不同的运算符和界限符都对应唯一一个种别码（有时一类运算符共享同一个种别码）。

4.语法分析概述

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

5.语义分析概述

语义分析包括对声明语句的分析和语义检查两个方面。

声明语句的分析：程序中的语句可以分为声明语句和可执行语句两种，语义分析需要对声明语句进行分析，来收集标识符的属性信息。

• 种属：表示一个标识符是简单变量，还是数组、记录等复杂变量，又或者是一个过程。
• 类型：标识符所表示的数据类型。
• 存储位置和长度。
• 值和作用域。
• 参数和返回值信息。

符号表概述：

• 符号表作用：用于存放标识符的属性信息的数据结构。
• 字符串表：符号表中常带有一个字符串表，用于存放程序中用到的标识符和字符常数。

语言检查：审查源程序有无语义错误，常见的语义错误如下：

• 变量或过程未声明就使用；
• 变量或过程名重复声明；
• 运算分量类型不匹配。
• 操作符与操作数之间的类型不匹配。

6.中间代码生成和后端概述

常见的中间表示形式：三地址码、语法结构树（也被称为语法树）。

三地址码概述：

• 结构组成：由类似于汇编语言的指令序列组成；
• 操作数个数限制：每个指令最多有三个操作数。
• 常见的三地址指令：
  

四元式概述：

• 四元式的作用：四元式用于表示一条三地址指令。
• 四元式的内容：元组中的第一个元素为操作符，后面三个分量为指令的操作数（但是不一定有三个操作数，因此可以空着）。

目标代码生成：

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

代码优化：

• 代码优化的作用：代码优化是为了改进代码所进行的等价程序变换，使得其运行得更快一些或占用的空间更少一些，又或者两者兼顾。
• 代码优化方式分类：机器无关优化和机器相关优化。前者是在中间代码层面进行优化，后者在目标代码层面进行优化。