预处理程序来产生，另外，为得到能运行的机器代码，编译程序的输出可能仍需要进一步 地处理。 前面介绍过，编译程序的基本任务是将源语言程序翻译成等价的日标语言程序我们 知道，源语言的种类成千上万，从常用的诸如FORTRAN,PASCAL和C语言，到各种各 样的计算机应用领域的专用语言，而目标语言也是成千上万的，加上编译程序根据它们的 构造不同，所执行的具体功能的差异又分成了各种类型，比如：一趟编译、多趟编译的、具 有调试或优化功能的等等，尽管存在这些明显的复杂因素，但是任何编译程序所必须执行 的主要任务基本是一样的，通过理解这些任务，使用同样的基本技术，我们可以为各种各 样的源语言和目标语言设计和构造编译程序。 据说第一个编译程序的出现是在20世纪50年代早期，很难讲出确切的时间，国为当 初大量的实验和实现工作是由不同的小组独立完成的，多数早期的编译工作是将算术公 式翻译成机器代码。用现在的标准来衡量，当时的编译程序能完成的工作十分初步，如只 允许简单的单目运算，数据元素的命名方式有很多限制，然而它们莫定了对高级语言编译 系统的研究和开发的基础，20世纪50年代中期出现了FORTRAN等一批高级语言，相 应的一批编译系统开发成功。随着编译技术的发展和社会对编译程序需求的不断增长，20 世纪50年代末有人开始研究编译程序的自动生成工具，提出并研制编译程序的编译程 序。它的功能是以任一语言的词法规则、语法规则和语义解释出发，自动产生该语言的编 译程序。目前很多自动生成工具已广泛使用，如词法分析程序的生成系统LEX,语法分析 程序的生成系统YACC等，20世纪60年代起，不断有人使用自展技术来构造编译程序 自展的主要特征是用被编译的语言来书写该语言自身的编译程序。1971年，PASCAL的 编译程序用自展技术生成后，其影响就越来越大。 随着并行技术和并行语言的发展，处理并行语言的并行编译技术正在深入研究之中 将串行程序转换成并行程序的自动并行编译技术也正在深入研究之中， 1.2编译过程概述 编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上 来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示 形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的，图1.3 给出了一个编译过程的各个阶段，这是一种典型的划分方法。事实上，某些阶段可能组合 在一起，这些阶段间的源程序的中间表示形式就没必要构造出来了，图1.3中将编译过程 划分成了词法分析，语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶 段，我们将分别介绍各阶段的任务。另外两个重要的工作：表格管理和出错处理与上述六 个阶段都有联系，编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段 的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作：如果编译过 程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造 成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译 程序还能自动校正错误，这些工作称之为出错处理。 ·2
我们从源程序在不同阶段所被转换成的表 示形式的不同来介绍各个阶段的任务。 源程序 词法分析阶段是编译过程的第一个阶 词法分析 段。这个阶段的任务是从左到右一个字符一个 字符地读入源程序，对构成源程序的字符流进 语法分析 行扫描和分解，从而识别出一个个单词（也称单 语义分析 司符号或符号)。这里所谓的单词是指逻辑上紧 密相连的一组字符，这些字符具有集体含义。比 中间代码生皮 如标识符是由字母字符开头，后限字母、数字字 代码优化 符的字符序列组成的一种单词。保留字（关键字 或基本字)是一种单词，此外还有算符，界符等 目标代码生成 等。例如某源程序片断如下 目标程序 begin var sum.first,count:real;sum : first+-count*l0end.词法分析阶段将构成这 图1.3编译的各个阶段 段程序的字符组成了如下单词序列： 1.保留字 begin 2.保留字 var 3.标识符 sum 4,逗号 5.标识符 first 6.逗号 7.标识符 count 8.目 号 9.保留字 real 10.分号 11.标识符 sum 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*l0则表示为id1= id2+id3*10 语法分析是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单 词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语，也称 语法单位，可表示成语法树，比如上述程序段中的单词序列： id1=id2+id3*10经语法分析得知其是PASCAI.语言的“赋值语句”，表示成如 图1.4所示的语法树或是图1.5所示的那种形式. 语法分析所依据的是语言的语法规则，即描述程序结构的规则，通过语法分析确定整 个输入串是否构成一个语法上正确的程序。 3▣
标识符 id3(count) 图1.4语句id1:=id2+id3*10的语法树 id2 id3 图1.5语句id1=id2+id3*10的语法树的另一种形式 程序的结构通常是由递归规则表示的，例如，我们可以用下面的规则来定义表达式： (1)任何标识符是表达式」 (2)任何常数（整常数、实常数）是表达式。 (3)若表达式1和表达式2都是表达式，那么：表达式1+表达式2 表达式1￥表达式2 (表达式1) 都是表达式 类似地，语句也可以递归地定义，如 (1)标识符=表达式是语句。 (2)while(表达式) do语句和 (表达式) then语句clse语句 都是语句。 上述赋值语句id1:=id2+id3*10之所以能表示成图1.4的语法树，依据的是赋值 语句和表达式的定义规则 词法分析和语法分析本质上都是对源程序的结构进行分析。但词法分析的任务仅对 源程序进行线性扫描即可完成，比如识别标识符，因为标识符的结构是字母打头的字母和 数字串，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所 有字母和数字组合在一起而构成单词标识符。但这种线性扫描则不能用于识别递归定义 的语法成分，比如就不能用此办法去匹配表达式中的括号， 语义分析阶段是审查源程序有无语义错误，为代码生成阶段收集类型信息，比如语 义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当 不符合语言规范时，编译程序应报告错误，如有的编译程序要对实数用作数组下标的情况 4
报告错误。又比如某些语言规定运算对象可被强制，那么当二目运算施于一整型和-一实型 时，编译程序应将整型转换成实型而不能认为是源程序的错误，假如在语句sum:=frs 十count*10中，*的两个运算对象：count是实型，10是整型，则语义分析阶段进行类型 审查之后，在语法分析所得到的分析树上增加一语义处理结点，表示整型变成实型的一目 算符inttoreal,则图l.5的树变成图1.6所示的那样， id? 图1,6桶入语义处理结点的树 中间代码生成在进行了上述的语法分析和语义分析阶段的工作之后，有的编译程 序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。所调 “中间代码”是一种结构简单，含义明确的记号系统，这种记号系统可以设计为多种多样的 形式，重要的设计原则为两点：一是容易生成：二是容易将它翻译成目标代码。很多编译程 序采用了一种近似“三地址指令”的“四元式”中间代码，这种四元式的形式为：（运算符，运 算对象1，运算对象2，结果)。 比如源程序sum=first-十count￥10可生成四元式序列，如图1.7所示，其中ti =1,2,3)是编译程序生成的临时名字，用于存放运算结果的。 (1) (inttoreal 10 t) (2) (￥ id3 t1t） (3) id2tata） (4) (= t id1) 图1.7中间代码 代码优化在此阶段的任务是对前阶段产生的中间代码进行变换或进行改造，目的 是使生成的目标代码更为高效，即省时间和省空间.比如图1.7的代码可变换为图1.8的 代码，仅剩了两个四元式而执行同样的计算。也就是编译程序的这个阶段已经把将10转 换成实型数的代码化简掉了，同时因为t,仅仅用来将其值传递给d1,也可以被化简掉， 这只是优化工作的两个方面，此外诸如公共子表达式的删除，强度削弱、循环优化等优化 工作将在第11章详细介绍。 (￥id310.0t) (id2 t id1) 图1.8优化后的中间代码 目标代码生成这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码或 可重定位的指令代码或汇编指令代码。这是编译的最后阶段，它的工作与硬件系统结构和 指令含义有关，这个阶段的工作很复杂，涉及到硬件系统功能部件的运用、机器指令的选 5
择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等】 例如，使用两个寄存器(R,和R),可能生成如图1.9的某汇编代码。 (D)MOVF id3. (2)MULF #10.0, R (3)MOVE id2, R. (40 . (5)MOV id 图1.9目标代码 第一条指令将id3的内容送至寄存器R2,第二条指令将其与实常数10.0相乘，这里 用#表明10.0处理为常数，第三条指令将i2移至寄存器R,第四条指令加上前面计算 出的R:中的值，第五条指令将寄存器R,的值移到id1的地址中，这些代码实现了本节开 头给的源程序片断的赋值。 前面提到过上述编译过程的阶段划分是一典型处理模式，事实上并非所有的编译程 序都分成这样几个阶段，有些编译程序并不要生成中间代码，有些编译程序不进行优化， 优化阶段即可省去，有些最简单的编译程序在语法分析的同时产生目标指令代码，如第2 章介绍的P1,/0语言编译程序。不过多数实用的编译程序都采用上述几个阶段的工作过 程。 1.3编译程序的结构 上述编译过程的六个阶段的任务，再加上表格管理和出错处理的工作可分别由几个 模块或程序完成，它们分别称作词法分析程序、语法分析程序，语义分析程序、中间代码生 成程序、代码优化程序、目标代码生成程序、表格管理程序和出错处理程序，从而可给出一 个典型的编译程序结构框图，如图1.10所示。 源程字 词法分桥程序 表 语法分析程序 格 语义分析程序 中间代码生成程序 序 代码优化程序 目标代码生成程序 目标程序 困1.10编译程序结构框图 ·6