文档介绍：1 章
引论
什么叫编译程序
从理论上说,构造专用计算机来直接执行用某种高级语言编写的程序是可能的。但是,
目前的机器能执行的是非常低级的语言,即机器语言,那么,一个基本的问题是,高级语
言最终是怎样在计算机上执行的呢?
在计算机上执行一个高级语言程序一般要分为两步,第一步,用一个编译程序把高级
语言翻译成机器语言程序,第二步,运行所得的机器语言程序求得计算结果。
现代计算机系统一般都含有不止一个的高级语言程序,对有些高级语言甚至配置了几
个不同性能的编译程序,供用户根据不同需要进行选择。高级语言的编译程序是计算机系
统软件的组成部分之一,也是用户最直接关心的工具之一。
从功能上看,一个编译程序就是一个语言编译程序,它能够把某一种语言程序(称为
源语言程序)转换成另一种语言程序(称为目标语言程序),而后者与前者在逻辑上是等价
的。比如,汇编程序是一个翻译程序,它把汇编语言程序翻译成机器语言程序。如果源语
言是像 FORTRON、Pascal、C、Ada、Smalltalk 或 Java 这样的“高级语言”,而目标语言
是诸如汇编语言或机器语言之类的“低级语言”,这样的一个翻译程序就被称为编译程序。
如果把编译程序看成一个“黑盒子”,它所执行的转换工作可以用图 来说明。
根据不同的用途和侧重,编译程序可
进一步进行分类。专门用于帮助程序开发
和调试的编译程序称为诊断编译程序图 编译程序的功能
(piler),着重于提高目标代
码效率的编译程序叫优化编译程序(piler)。现在很多编译程序同时提供了调
试、优化等多种功能,用户可以通过“开关”进行选择。运行编译程序的计算机被称为宿主机,
运行编译程序所产生目标代码的计算机被称为目标机。如果一个编译程序产生不同于其宿主机
的机器代码,则称它为交叉编译程序(piler)。如果不需重写编译程序中与机器无关
的部分就能改变目标机,则称该编译程序为可变目标编译程序(piler)。
世界上第一个编译程序—FORTRON 编译程序是 20 世纪 50 年代中期研制成功的。
当时,人们普遍认为设计和实现编译程序是一件十分困难、令人生畏的事情。经过 40 年的
2 编译原理简明教程
努力,编译理论与技术得到了迅速发展,现在已形成了一套比较成熟的、系统化的理论与方
法,并且已经开发出了一些好的编译程序的实现语
言、环境与工具。在此基础上设计并实现一个编译
程序不再是高不可攀的事情。使用过计算机的人都
知道,除了编译程序外,还需要一些其他的程序才
能生成一个可在计算机上执行的目标程序。分析一
下一个程序设计语言的典型的处理过程,如图
所示,可以从中进一步了解编译程序的作用。
一个源程序有时可能被分成几个模块存放在
不同的文件里,将这些源程序汇集在一起的任务,
由一个叫做预处理程序的程序来完成,有些预处
理程序也负责宏展开,像 C 语言的预处理程序要
完成文件合并、宏展开等任务。图 中的编译
程序生成的目标程序是汇编代码的形式,需要经
由汇编程序翻译成可再装配的机器代码,再经由
装配/连接编辑程序与某些库程序连接成真正能
在机器上运行的代码。也就是说,一个编译程序
图 高级语言程序的处理过程
的输入可能是由一个或多个预处理程序来产生
的,另外,为得到能运行的机器代码,编译程序的输出可能仍需要进一步的处理。
本书主要介绍设计和构造编译程序的基本原理和方法,重点讲一些原理性的东西,也
会反映一些最新的进展。
编译过程概述
编译程序的工作包括从输入源程序开始到输出目标程序为止的整个过程,是非常复杂
的。但就其过程而言,它与人们进行自然语言之间的翻译有许多相近之处。把一种文字翻
译为另一种文字,例如把一段英文翻译为中文时,通常需经如下步骤。
(1)识别出句子中的一个个单词。
(2)分析句子的语法结构。
(3)根据句子的含义进行初步翻译。
(4)对译文进行修饰。
(5)写出最后的译文。
类似地,编译程序的工作过程也可以划分为 5 个阶段,即词法分析、语法分析、语义
分析与中间代码生成、代码优化、目标代码生成。每个阶段将源程序的一种表示形式转换
成另一种表示形式,各个阶段进行的操作在逻辑上是紧密连接在一起的。
(1)第一阶段,词法分析。词法分析的任务是从左到右一个字符一个字符地读入源程
序,对构成源程序的字符流进行扫描和分解,从而识别出一个个单词(也称单词符号或符
号)。这