1.编译程序

     当前的电子计算机都是以系统的面貌出现的，它由硬件和软件组成。软件的功能与质量在很大程度上左右着整个计算机系统的功能。软件品种很多，对通用数字计算机来说，主要包括程序设计语言、系统软件与应用软件。操作系统、编译系统、诊断程序等等均属系统软件。
     我们知道，程序设计语言是人类用来和计算机系统进行通信，并控制其工作的人工语言。它经历了几代的发展，最早只有机器语言----不须翻译可直接为计算机所接受，然后从汇编语言、结构化程序设计语言、逻辑程序设计语言发展到今天的面向对象程序设计语言，每类语言的产生都反映了当时人们对程序设计方法的认识和理论研究成果。程序设计语言品种繁多，就以高级程序设计语言来说，近20多年来在我们曾广为流行或正在流行的便有数十种，如早期的ALGOL、FORTRAN，BASIC、COBOL语言；始于70年代的结构化程序设计语言：PASCAL、ADA、C；人工智能语言LISP、PROLOG；发展于80年代并将在90年代占主导地位的面向对象语言，如SMALLTALK、C++、面向对象PASCAL等等。
     这些高级程序设计语言的设计思想与方法、具备的功能以及应用范畴不尽相同，但有一个共同特点，即用它们编制程序比直接用机器语言编制可大大提高效率。可是迄今为止计算机主要是一种逻辑电子装置，它只能接受用二进制数表示的指令和数构成的程序。那么，它怎样接受源程序并完成计算呢？譬如，对于一个简单的赋值语句y ：=a+b*c，计算机怎样识别它，又怎样将它编制成能反映先乘后加的优先运算关系的一组机器指令，然后根据这组指令完成上述运算，并把结果保存在y单元中呢？这就有待于翻译。
     通常分两种翻译方式：一种为"编译"方式；另一种为"解释"方式。所谓编译方式是首先把源程序翻译成等价的目标程序，然后再执行此目标程序。而解释方式是边翻译边执行。它们之间的差别主要在于：解释程序不产生将被执行的目标程序，而是直接执行源程序本身。
     如果源语言(编写源程序的语言)是PASCAL、FORTRAN、COBOL、C等这类高级语言，而目标语言是某计算机的汇编语言或机器语言，则这种翻译程序称为编译程序。
     如果源语言是某一汇编语言，而目标语言是某计算机的机器语言，则称这种翻译程序为汇编程序。
     如果把编译程序看成一个"黑盒子"，它所执行的转换工作可以用图一来说明。

     一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员和程序设计专家独立于机器，这对于当今机器的数量和种类持续不断地增长的年代尤为重要。
     使用过计算机的人都知道，除了编译程序外，还需要一些其它的程序才能生成一个可在计算机上执行的目标程序。让我们分析一下一个程序设计语言程序的典型的处理过程，如图二所示，可以从中进一步了解编译程序的作用。

     一个源程序有时可能分成几个模块存放在不同的文件里，将这些源程序汇集在一起的任务，由一个叫做预处理程序的程序来完成，有些预处理程序也负责宏展开，像C语言的预处理程序要完成文件合并、宏展开等任务。图二中的编译程序生成的目标程序是汇编代码形式，需要经由汇编程序翻译成可再装配的机器代码，再经由装配／连接编辑程序与某些库程序连接成真正能在机器上运行的代码。也就是说，一个编译程序的输入可能要由一个或多个预处理程序来产生，另外，为得到能运行的机器代码，编译程序的输出可能仍需要进一步地处理。
     
     前面介绍过，编译程序的基本任务是将源语言程序翻译成等价的目标语言程序。我们知道，源语言的种类成千上万，从常用的诸如FORTRAN，PASCAL和C语言，到各种各样的计算机应用领域的专用语言，而目标语言也是成千上万的，加上编译程序根据它们的构造不同，所执行的具体功能的差异又分成了各种类型，比如：一趟编译、多趟编译的、具有调试或优化功能的等等。尽管存在这些明显的复杂因素，但是任何编译程序所必须执行的主要任务基本是一样的，通过理解这些任务，使用同样的基本技术，我们可以为各种各样的源语言和目标语言设计和构造编译程序。

2.编译的过程

编译过程概述
     编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的，图三给出了一个编译过程的各个阶段，这是一种典型的划分方法。事实上，某些阶段可能组合在一起，这些阶段间的源程序的中间表示形式就没必要构造出来了。图三中将编译过程划分成了词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段，我们将分别介绍各阶段的任务。另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作，如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。

我们从源程序在不同阶段所被转换成的示形式的不同来介绍各个阶段的任务。

词法分析阶段   
     词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词(也称单词符号或符号)。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。比如标识符是由字母字符开头，后跟字母、数字字符的字符序列组成的一种单词。保留字(关键字或基本字)是一种单词，此外还有算符，界符等等。例如某源程序片断如下：
begin var sum，first，count：real；sum：=first+count*10 end．

词法分析阶段将构成这段程序的字符组成了如下单词序列：
     1．保留字      begin            2． 保留字      var
     3．标识符      sum               4． 逗号         ，
     5．标识符      first            6． 逗   号      ，
     7．标识符      count            8． 冒   号      ：
     9．保留字      real             10． 分   号      ；
     11．标识符    sam               12． 赋值号      ：=
     13．标识符    first            14． 加   号      +
     15．标识符    count            16． 乘号         *
     17．整   数    10                18． 保留字      end
     19．界   符    ·
     
     可以看出，五个字符即b，e，g，i和n构成了一个分类为保留字的单词begin，两个字符即：和=构成了表示赋值运算的符号：=。这些单词间的空格在词法分析阶段都被滤掉了。
     我们使用idl，id2和id3分别表示sum，first和count三个标识符的内部形式，那么经过词法分析后上述程序片断中的赋值语句 sum := first + count * 10则表示为idl := id2 + id3 * 10。
语法分析   

   语法分析是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如"程序"，"语句"，"表达式"等等。一般这种语法短语，也称语法单位，可表示成语法树，比如上述程序段中的单词序列：
     idl := id2 + id3 * 10   经语法分析得知其是PASCAL语言的"赋值语句"，表示成如图四所示的语法树或是图五所示的那种形式。

语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。

     程序的结构通常是由递归规则表示的，例如，我们可以用下面的规则来定义表达式：
     (1)任何标识符是表达式。
     (2)任何常数(整常数、实常数)是表达式。
     (3)若表达式1和表达式2都是表达式，那么：表达式1 + 表达式2
                                                                  表达式1 * 表达式2   
                                                                 (表达式1)
  都是表达式
  类似地，语句也可以递归地定义，如
  (1)标识符 := 表达式          是语句。
  (2)while   (表达式)   do   语句                         和
      if      (表达式)   then   语句 else   语句
都是语句。
     上述赋值语句idl := id2 + id3 * 10之所以能表示成图四的语法树，依据的是赋值
语句和表达式的定义规则。
词法分析和语法分析本质上都是对源程序的结构进行分析。但司法分析的任务仅对源程序进行线性扫描即可完成，比如识别标识符，因为标识符的结构是字母打头的字母和数字串，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母和数字组合在一起而构成单词标识符。但这种线性扫描则不能用于识别递归定义的语法成分，比如就不能用此办法去匹配表达式中的括号。      

语义分析阶段
     语义分析阶段是审查源程序有无语义错误，为代码生成阶段收集类型信息．比如语义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。如有的编译程序要对实数用作数组下标的情况报告错误。又比如某些语言规定运算对象可被强制，那么当二目运算施于一整型和一实型时，编译程序应将整型转换成实型而不能认为是源程序的错误，假如在语句sum:=first
+ count * 10中，*的两个运算对象，count是实型，10是整型，则语义分析阶段进行类型审查之后，在语法分析所得到的分析树上增加一语义处理结点，表示整型变成实型的一目算符inttoreal，则图五的树变成图六所示的那样。

中间代码生成   
在进行了上述的语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。所谓"中间代码"是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。很多编译程序采用了一种近似"三地址指令"的"四元式"中间代码，这种四元式的形式为：(运算符，运算对象1，运算对象2，结果)。
     比如源程序   sum ：= first + count * l0可生成四元式序列，其中ti(i＝1，2，3)是编译程序生成的临时名字，用于存放运算结果的,如图七所示:

代码优化
在此阶段的任务是对前阶段产生的中间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空间。比如图七的代码可变换为图八的代码，仅剩了两个四元式而执行同样的计算。也就是编译程序的这个阶段已经把将10转换成实型数的代码化简掉了，同时因为t3仅仅用来将其值传递给id1，也可以被化简掉，这只是优化工作的两个方面，此外诸如公共子表达式的删除、强度削弱、循环优化等优化工作将在后面详细介绍。

目标代码生成   
这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的，指令代码或汇编指令代码。这是编译的最后阶段，它的工作与硬件系统结构和指令含义有关，这个阶段的工作很复杂，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等。
  例如，使用两个寄存器（R1和R2），可能生成如图九的某汇编代码。

这些代码实现了赋值功能。
  前面提到过上述编译过程的阶段划分是一典型处理模式，事实上并非所有的编译程序都分成这样几个阶段，有些编译程序并不要生成中间代码，有些编译程序不进行优化，优化阶段即可省去，有些最简单的编译程序在语法分析的同时产生目标指令代码，如要介绍的PL/0语言编译程序。不过多数实用的编译程序都采用上述几个阶段的工作过程。

3.编译程序的结构

编译程序的结构
     编译过程的六个阶段的任务，再加上表格管理和出错处理的工作可分别由几个模块或程序完成，它们分别称作词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序。从而可给出一个典型的编译程序结构框图，如图所示

(End)