> For the complete documentation index, see [llms.txt](https://lewiszlw.gitbook.io/notebooks/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lewiszlw.gitbook.io/notebooks/blogs/history/bian-yi-yuan-li-yin-lun.md).

# 编译原理引论

## 什么是编译程序

从功能上看，一个编译程序就是一个语言翻译程序。语言翻译程序把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价程序。

在计算机上执行一个高级语言程序一般要分为两步：

1. 用一个编译程序把高级语言翻译成机器语言程序；
2. 运行所得的机器语言程序求得计算结果。

翻译程序（Translator） 通常所说的翻译程序是指这样的一个程序，它能够把某一种语言程序（称为源语言程序或源程序）转换成另一种语言程序（称为目标语言程序或目标程序），而后者与前者在逻辑上是等价的。

* 汇编程序（Assembler） 如果源语言是某种汇编语言，而目标语言是某种计算机的机器语言，这样的一个翻译程序就称为汇编程序。
* 编译程序（Compiler） 如果源语言是某种高级语言，而目标语言是某种低级语言（汇编语言或机器语言），这样的一个翻译程序就称为编译程序。
* 解释程序（Interpreter） 这是另外一种类型的翻译程序，在翻译过程它按照高级语言源程序在计算机上执行的动态顺序对源程序的语句逐条翻译（解释），边解释边执行直至结束，它不产生目标程序，它的工作结果就是源程序的执行结果，这样的一个翻译程序就称为解释程序。

宿主机（host machine）：运行编译程序的计算机。 目标机(object machine) ：运行编译程序所产生目标代码的计算机。

## 编译过程和编译程序的结构

### 编译过程概述

编译程序的工作过程一般也可以划分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。

#### 词法分析

词法分析的任务： 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词：

* 保留字（begin、end、if、for、while等）
* 标识符（x1、s等变量名）
* 常数（3.14、100等）
* 算符（+、-、and、or等）
* 界符（标点符号、左右括号等）

在词法分析阶段的工作中所依循的是语言的词法规则（或称构词规则）。 描述词法规则的有效工具是

* 正规式
* 有限自动机

#### 语法分析

语法分析的任务是： 在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴），如“短语”、“子句”、“句子”（“语句”）、“程序段”和“程序”等。通过语法分析，确定整个输入串是否构成语法上正确的“程序”。

语法分析所依循的是语言的语法规则。 语法规则通常用**上下文无关文法描述**。

#### 语义分析与中间代码产生

此阶段的任务是： 对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。

中间代码是一种独立于具体硬件的记号系统。 常用的中间代码：三地址码，四元式，三元式、间接三元式、逆波兰式，树形表示等。

#### 优化

优化的任务: 对产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。

优化的主要方面有： 公共子表达式提取、循环优化、删除无用代码等等。有时，为了便于“并行运算”，还可以对代码进行并行化处理。

优化所依循的原则：程序的等价变换规则。

#### 目标代码生成

这一阶段的任务是： 把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。

### 编译程序的结构

![编译原理引论1](http://ofolh8dcq.bkt.clouddn.com/%E7%BC%96%E8%AF%91%E5%8E%9F%E7%90%86%E5%BC%95%E8%AE%BA1.PNG)

#### 表格管理

编译程序在工作过程中需要保存一系列的表格，以登记源程序的各类信息和编译各阶段的进展状况。

#### 出错处理

一个编译程序不仅应能对书写正确的程序进行翻译，而且应能对出现在源程序中的错误进行处理。

源程序中的错误通常分为语法错误和语义错误两大类。

* 语法错误是指源程序中不符合语法（或词法）规则的错误，它们可在词法分析或语法分析时检测出来。 例如，词法分析阶段能够检测出“非法字符”之类的错误；语法分析阶段能够检测出诸如“括号不匹配”、“缺少；”之类的错误。
* 语义错误是指源程序中不符合语义规则的错误，这些错误一般在语义分析时检测出来，有的语义错误要在运行时才能检测出来。 语义错误通常包括：说明错误、作用域错误、类型不一致等等。

#### 编译前端和后端

前端主要由与源语言有关但与目标机无关的那些部分组成。这些部分通常包括词法分析、语法分析、语义分析与中间代码产生，有的代码优化工作也可包括在前端。

后端包括编译程序中与目标机有关的那些部分，如与目标机有关的代码优化和目标代码生成等。通常，后端不依赖于源语言而仅仅依赖于中间语言。

## 编译程序和程序设计环境

编译程序无疑是实现高级语言的一个最重要的工具。但支持程序设计人员进行程序开发通常还需要一些其它的工具如编辑程序；连接程序；调试工具等。编译程序与这些程序设计工具一起构成所谓的程序设计环境。

一个集成化的程序设计环境的特点是，它将相互独立的程序设计工具集成起来，以便为程序员提供完整的、一体化的支持，从而进一步提高程序开发效率，改善程序质量。在一个好的集成化程序设计环境中，不仅包含丰富的程序设计工具，而且还支持程序设计方法学，支持程序开发的全生命周期。

***

> 《编译原理（第2版）》张素琴 吕映芝 蒋维杜 戴桂兰 著