编译过程概述和编译程序的结构(希赛教育基础学院).doc

【课前思考】 什么是编译程序 编译过程和编译程序的结构 为什么要学习编译程序 【学习目标】 明确编译程序的功能及其在计算机系统中的作用。 了解源语言程序被编译为目标程序的整个过程，这个过程一般划分为哪些阶段。 知道编译技术可用于哪类软件的设计和开发。 【学习指南】编译程序是现代计算机系统的基本组成部分之一。编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。通过课程的学习应掌握各个成分的功能和设计原则，以及在编译阶段的逻辑关系。理解他们怎样作为一个整体完成编译任务的。【难重点】应该说,本章没有难以理解的内容,主要对编译程序的功能和结构做一综述。 【知识结构】1.1 什么是编译程序编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序。对有些高级语言甚至配置了几个不同性能的编译程序。一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员和程序设计专家独立于机器，这对于当今机器的数量和种类持续不断地增长的年代尤为重要。语言和翻译：语言是人类交流思想和信息的工具。如自然语言，世界上存在着许多种语言，各国之间要交流信息,就要有各种语言之间的翻译。计算机语言同样是丰富多彩的。从功能上看，一个编译程序就是一个语言翻译程序。它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序。源语言通常是一个高级语言，如FORTRAN，C 或Pascal。目标语言通常是一个低级语言,如汇编或机器语言。编译程序的功能如图1.1所示。请注意：所谓的源和目标程序的等价是什麽含义-他们的功能一样。图1.1编译程序作为一个语言翻译程序,也要在翻译过程中检查源程序的语法和语义，报告一些出错和警告信息，帮助程序员更正源程序.所以编译程序的功能也可以图示为：说到一个编译程序, 一定要知道它的源语言是什麽,目标语言是什麽,还有它的实现语言是什麽. 常使用T型图来表示一个编译程序所涉及的三个语言。有关编译程序的术语编译程序的源语言(源程序)编译程序的目标语言(目标程序)编译程序的实现语言给出这些术语的英文：编译程序-compiler源语言-source language源程序-source program目标语言-target or object language目标程序-target or object program实现语言-implementation language如果从计算机系统的角度看，什么是编译程序呢？我们说编译程序是一种软件，是系统软件。通常认为系统软件是居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。系统软件和具体的应用领域无关，如编译系统和操作系统等。编译程序也是一种语言处理系统，即把软件语言书写的各种程序处理成可在计算机上执行的程序。编译程序在计算机系统中的所在层来自计算机百科全书的定义 软件：计算机系统中的程序及其文档系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体的应用领域无关，如编译系统和操作系统等。 语言处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序。软件语言：用于书写软件的语言。它主要包括需求定义语言，功能性语言，设计性语言，程序设计语言以及文档语言。使用过计算机的人都知道，要把软件语言书写的各种程序处理成可在计算机上执行的程序，除了编译程序外，还需要一些其它的程序。让我们分析一下一个程序设计语言程序的典型的处理过程，如图1.2，可以从中进一步了解编译程序的作用。前面介绍过，编译程序的基本任务是将源语言程序翻译成等价的目标语言程序。我们知道，源语言的种类成千上万，从常用的诸如FORTRAN，PASCAL和C语言，到各种各样的计算机应用领域的专用语言，而目标语言也是成千上万的，加上编译程序根据它们的构造不同，所执行的具体功能的差异又分成了各种类型，比如：一趟编译、多趟编译的、具有调试或优化功能的等等。尽管存在这些明显的复杂因素，但是任何编译程序所必须执行的主要任务基本是一样的，通过理解这些任务，使用同样的基本技术，我们可以为各种各样的源语言和目标语言设计和构造编译程序。图1.2 高级语言程序的处理过程一个源程序有时可能分成几个模块存放在不同的文件里，将这些源程序汇集在一起的任务由一个叫做预处理程序的程序来完成，有些预处理程序也负责宏展开，像C语言的预处理程序要完成文件合并、宏展开等任务。如果编译程序生成的目标程序是汇编代码形式，需要经由汇编程序翻译成可再装配的机器代码，再经由装配/连接编辑程序与某些库程序连接成真正能在机器上运行的代码。也就是说，一个编译程序的输入可能要由一个或多个预处理程序来产生，另外，为得到能运行的机器代码，编译程序的输出可能仍需要进一步地处理。1.2编译过程概述和编译程序的结构编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。事实上，某些阶段可能组合在一起，这些阶段间的源程序的中间表示形式就没必要构造出来了。我们将分别介绍各阶段的任务。另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。图1.3表示了编译的各个阶段。 图1.3 编译的各个阶段下面，我们从源程序在不同阶段所被转换成的表示形式来介绍各个阶段的任务。 词法分析词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词(也称单词符号或符号)。这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符具有集体含义。比如标识符用于表示变量名,是由字母字符开头，后跟字母、数字字符的字符序列组成的一种单词。保留字(关键字或基本字)是一种单词，此外还有算符，界符等等。例如某源程序片断如下：begin var sum, first, count: real; sum=first+count*10 end.词法分析阶段将构成这段程序的字符组成了如下19个单词序列：1. 保留字begin2. 保留字var3. 标识符sum 4. 逗号，5. 标识符first6. 逗号，7. 标识符count8. 冒号：9. 保留字real 10. 分号；11. 标识符sum 12. 赋值号=13. 标识符first14. 加号+15. 标识符count 16. 乘号*17. 整数1018. 保留字end19. 界符可以看出，五个字符即b，e，g，i和n构成了一个称为保留字的单词begin，两个字符即和=构成了表示赋值运算的符号=。这些单词间的空格在词法分析阶段都被滤掉了。我们知道, 标识符用于表示变量名,可以很方便的使用id1，id2和id3分别表示sum，first和count三个标识符的内部形式，那么经过词法分析后上述程序片断中的赋值语句sum=first+count*10则表示为id1=id2+id3*10词法分析阶段的任务是读字符流的源程序、从中识别并构成单词。一个Pascal源程序片断：position := initial + rate * 60；词法分析后可能返回：单词类型 单词值标识符 position算符(赋值) :=标识符 initial算符(加) +标识符 rate算符(乘) *整数 60界符(分号) ；一个C源程序片断：int a;a = a + 2;词法分析后可能返回:单词类型 单词值保留字 int标识符 a界符 ;标识符 a 算符(赋值) =标识符 a算符(加) +整数 2界符 ；有关的英文词法分析-lexical analysis 或者scanning单词-token保留字-resered word标识符 -identifier(user-defined name)语法分析语法分析是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如程序，语句，表达式等等。一般这种语法短语，也称语法单位可表示成语法树，比如上述程序段中的单词序列：id1=id2+id3*10经语法分析得知其是PASCAL语言的赋值语句，表示成如图1.4所示的语法树或是图1.5所示的那种形式。图1.4 语句id1:=id2+id3*10的语法树图1.5 语句id1:=id2+id3*10的语法树的另一种形式语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个输入串是否构成一个语法上正确的程序。程序的结构通常是由递归规则表示的，例如，我们可以用下面的规则来定义表达式：(1) 任何标识符是表达式。(2) 任何常数(整常数、实常数)是表达式。(3) 若表达式1和表达式2都是表达式，那么：表达式1+表达式2以及表达式1 * 表达式2都是表达式。类似地，语句也可以递归地定义，如(1) 标识符=表达式是语句。(2) while(表达式)do语句和if(表达式 )then语句 else语句都是语句。词法分析和语法分析本质上都是对源程序的结构进行分析。但词法分析的任务仅对源程序进行线性扫描即可完成，比如识别标识符，因为标识符的结构是字母打头的字母和数字串，这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母和数字组合在一起而构成单词标识符。但这种线性扫描则不能用于识别递归定义的语法成分，比如就无法仅用线性扫描去匹配表达式中的括号。语法分析的功能是进行层次分析，把源程序的单词序列组成语法短语(表示成语法树)。.依据的是语法规则。Pascal语言的赋值语句的规则为：:=“:=”:=“+”:=“* ”:=“(”“)”:=id:=n单词序列id1 = id2 + id3 * 10之所以能表示成图1.4的语法树，依据的是赋值语句和表达式的定义规则。语义分析语义分析阶段的任务是审查源程序有无语义错误。源程序中有些语法成分，按照语法规则去判断，它是正确的，但它不符合语义规则。比如使用了没有声明的变量；或者给一个过程名赋值；或者调用函数时参数类型不合适或者参加运算的两个变量类型不匹配等等。比如下边的程序片段：int arr2,c;c = arr1 * 10 ;其中的赋值语句是符合语法规则的，但是因为没有声明变量arr1，而存在语义错。请你说出error1和error2分别违背了什么语义规则，warning呢？ Program p(input,output);Var rate:real;procedure initial;position := initial + rate * 60/* error1 */ /* error2 */ /* warning1 */;现在的程序段只剩下一个警告错误了 Program p(input,output);Var rate:real;Var initial :real;Var position :real ;position := initial + rate * 60一般，语义分析的工作还包括类型审查，类型提升以及为代码生成阶段收集类型信息. 比如审查每个算符是否实施于具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。又比如对实数用作数组下标的情况报告错误。又比如某些语言规定运算对象可被强制，那么当二目运算施于一个整型量和一个实型量时，编译程序应将整型量自动转换成实型量而不能认为是源程序的错误，或者给出警告信息后将整型量自动转换成实型量。假如在赋值语句sum=first+count*10中，算符*的两个运算对象分别是count和10,而count是实型变量，10是整型量.语义分析阶段进行类型审查之后，将整型量提升为实型量.在语法分析所得到的分析树上增加一个一目算符结点，这个结点的名称为inttoreal，表示进行将整型量变成实型量的语义处理，那么，图1.5的树变成图1.6所示的那样。图1.6 插入语义处理结点的树我们来总结一下语义分析主要的任务-完成静态语义审查和处理上下文相关性审查类型匹配审查类型转换中间代码生成阶段在进行了上述的词法分析，语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。所谓中间代码是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。很多编译程序采用了一种近似三地址指令的四元式中间代码，这种四元式的形式为：(运算符，运算对象1，运算对象2，结果)。比如源程序sum = first+count*10可生成四元式序列，如图1.7所示，其中ti(i=1,2,3)是编译程序生成的临时名字，用于存放运算结果的。 图1.7 id1:= id2 + id3 * 10的四元式序列 (1) (2) (3) (4) (inttoreal*+:= 10 id3id2t3 -t1t2- t1 )t2 )t3 )id1 ) 四元式(运算符，运算对象1，运算对象2，结果)常写成赋值语句的形式(结果=运算对象1 运算符 运算对象2)，比如c语言的源程序a = b * c + b * d 的四元式序列为(1) t1 = b * c(2) t2 = b * d(3) t3 = t1 + t2(4) a = t3翻译分支，循环和函数调用等语句时，四元式的生成通常要比上述例子复杂些。比如源程序：if ( a bif t1 goto lt2 = a ca = t2l : t3 = b * cc = t3代码优化代码优化阶段的任务是对前阶段产生的中间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空间。比如图1.7的代码可变换为图1.8的代码，仅剩了两个四元式而执行同样的计算。也就是编译程序的这个阶段已经把将10转换成实型数的代码化简掉了，同时因为t3仅仅用来将其值传递给id1，也可以被化简掉，这只是优化工作的两个方面，此外诸如公共子表达式的删除、强度削弱、循环优化等优化工作将在第11章详细介绍。1.8 id1:= id2 + id3 * 10的优化后四元式序列 （1） ( * id3 10.0 t1 )（2） ( + id2 t1 id1 )代码优化工作会降低编译程序的编译速度，因此编译优化阶段常常作为可选择阶段，编译程序具有控制机制以允许用户在编译速度和目标代码的质量间进行权衡。目标代码生成目标代码生成阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。这是编译的最后阶段，它的工作与硬件系统结构和指令含义有关，这个阶段的工作很复杂，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等。例如，使用两个寄存器(R1和R2)，图1.8的中间代码可生成如图1.9的某汇编代码。 第一条指令将id3的内容送至寄存器R2，第二条指令将其与实常数10.0相乘，这里用#表明10.0处理为常数，第三条指令将id2移至寄存器R1，第四条指令加上前面计算出的R2中的值，第五条指令将寄存器R1的值移到id1的地址中。这些代码实现了本节开头给的源程序片断的赋值。 前面说过，上述编译过程的阶段划分是一种典型的处理模式，事实上并非所有的编译程序都包括这样几个阶段。有些编译程序并不要中间代码，即不存在中间代码生成阶段；有些编译程序不进行优化，优化阶段即可省去;有些最简单的编译程序只有词法分析，语法分析；语义分析和目标代码生成，如第2章介绍的PL/0语言编译程序。编译程序的另外两个