《编译原理概况》PPT课件.ppt

2007年9月4日星期二5时12分32秒,共63页, Page1,编译原理,作者:杜亚军 ,版权所有,任何教师使用本课件必须与作者联系,2007年9月4日星期二5时12分32秒,共63页, Page2,参考文献,1.陈火旺，钱家桦，孙永强.程序设计语言原理.国防工业出版社，1983 2.杜淑敏，王永宁.编译程序设计原理.北京大学出版社，1986 3.俞瑞钊.数理逻辑.浙江大学出版社.1990,2007年9月4日星期二5时12分32秒,共63页, Page3,第一章 概论,主要内容 1.什么叫编译程序 2.编译过程 3.编译程序的组成 4.与编译原理有关的软件工具,2007年9月4日星期二5时12分32秒,共63页, Page4,1.1什么是编译程序,首先看一个示例： Main() int I,j; j=20; I=j+; printf(“i=%d,j=%d”,I,j); ,在tubro c下存为 ww.c文件，它是 不能执行的，必 须要complier后 生成ww.exe文件 才能执行,2007年9月4日星期二5时12分32秒,共63页, Page5,Delphi7.0的编译器,VC,VB,JAVA等都 有自己的编译器,2007年9月4日星期二5时12分32秒,共63页, Page6,什么叫编译程序(compiler)? 编译程序就是在一个开发工具中,将高级语 言写成的代码翻译成机器指令的一个程序,2007年9月4日星期二5时12分32秒,共63页, Page7,(1). 从功能上看，一个编译程序就是一个语言翻译程序。它把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价的程序,编译程序的特点,编译程序,源程 序代码,可执行 文件,图1.1编译程序的功能,2007年9月4日星期二5时12分32秒,共63页, Page8,源语言: FORTRAN，PASCAI, C, BASIC, FORTRAN,C+等那样的高级语言. 目标语言: 汇编语言或机器语言那样的低级语言，,2007年9月4日星期二5时12分32秒,共63页, Page9,（2）.一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员和程序设计专家独立于机器。,编译程序的特点,2007年9月4日星期二5时12分32秒,共63页, Page10,预处理,编译处理,汇编程序,连接生成 可执行文件,fortran,for1,pas2,link,exe,c,compile,make,build,exe,一个程序设计语言程序的典型的处理过程,2007年9月4日星期二5时12分32秒,共63页, Page11,（3）.一个源程序有时可能分成几个模块存放在不同的文件里，将这些源程序汇集在一起的任务，由一个叫预处理程序的程序来完成有些预处理程序也负责宏展开，像C语言的预处理程序要完成文件合并、宏展开等任务.,编译程序的特点,2007年9月4日星期二5时12分32秒,共63页, Page12,(4)代码形式，需要经由汇编程序翻译成可在装配的机器代码， 一个编译程序的输入可能一个或多个预处理程序来产生，另外，为得到能运行的机器代码，编译程序的输出可能仍需要进一步地处理。,编译程序的特点,2007年9月4日星期二5时12分32秒,共63页, Page13,(1)第一个编译程序出现在20世纪5O年代早 期，多数早期的编译工作是将算术公式翻译 成机器代码。用现在的标准来衡量，当时的 编译程序能完成的工作十分初步，如只允许 简单的单目运算，数据元素的命名方式有很 多限制然而它们奠定了对高级语言编译系 统的研究和开发的基础、,编译程序的发展,2007年9月4日星期二5时12分32秒,共63页, Page14,(2)20世纪50年代中期出现了FORTRAN等一 批高级语言，相应的一批编译系统开发成功,编译程序的发展,(3)20世纪50年代末有人开始研究编译程序自动 生成工具，提出并研制编译程序的编译程序、它 的功能是以任一语言的词法规则、语法规则和语 义解释出发，自动产生该语言的编译程序。目前 很多自动生成工具已广泛使用，如词法分析程序 的生成系统LEX，语法分析程序的生成系统YACC等,2007年9月4日星期二5时12分32秒,共63页, Page15,(4)20世纪60年代起不断有人使用自展技 术来构造编译程序自展的主要特征是用被 编译的语言来书写该语言自身的编译程序，,编译程序的发展,(5)1971年，PASCAL的编译程序用自展技术生成后 ，其影响就越来越大。 (6)随着并行技术和并行语言的发展处理并行语 言的并行编译技术正在深入研究之中将串行程序 转换成并行程序的自动并行编译技术也正在深入研 究之中。,2007年9月4日星期二5时12分32秒,共63页, Page16,编译程序完成从源程序到目标程序的翻 译是一个复杂的整体的过程 目标程序=Translation( 源程序) 从概念上来讲，一个编译程序的整个工 作过程是划分成阶段进行的。每个阶段将源 程序的一种表示形式转换成另一种表示形式 ，各个阶段进行的操作在逻辑上是紧密连接 在一起的,1.2编译过程,2007年9月4日星期二5时12分32秒,共63页, Page17,一种典型的划分方法,2007年9月4日星期二5时12分32秒,共63页, Page18,词法分析、 单词=T1(源程序) 语法分析、 语句= T2(单词） 语义分析、 语句= T3（语句） 中间代码生成、 中间代码= T4（语句） 代码优化、 代码= T5（中间代码） 目标代码生成、 目标代码= T6（代码） 六个阶段。,目标程序=Translation( 源程序)的分解,2007年9月4日星期二5时12分32秒,共63页, Page19,表格管理和出错处理与上述个阶段都有联系,表格管理和出错处理,2007年9月4日星期二5时12分32秒,共63页, Page20,A.任务： 词法分析阶段是编译过程的第一个阶段， 这个阶段的任务是从左到右一个字符一个 字符地读入源程序，对构成源程序的字符 流进行扫描和分解，从而识别出一个个单词 （也称词符号或符号）,（1)词法分析,2007年9月4日星期二5时12分32秒,共63页, Page21,这里所谓的单词是指逻辑上紧密相连的一组 宇符，这些字符具有集体含义比如标识符 是由字母字符开头，后跟字母、数字字符的 字符序列组成的一种单词保留字（关键字 或基本字）是一种单词，此外还有算符，界 符等等例如某源程序片断如下：,B.单词的含义,2007年9月4日星期二5时12分32秒,共63页, Page22,Begin Var sum,firt，count：real； sum:=firstcount* 10 end 词法分析阶段将构成这段程序的字符组成了 如下单词序列：,C.词法分析实例,2007年9月4日星期二5时12分32秒,共63页, Page23,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 界 符,2007年9月4日星期二5时12分32秒,共63页, Page24,使用id1,id2和id3分别表示sum，first和 count三个标识符的内部形式，那么经过词 法分析后上述程序片断中的赋值语句 sum:=firstCount*10则 表示为id1:=id2id3 * 10,D.词法分析另一任务,2007年9月4日星期二5时12分32秒,共63页, Page25,语法分析是编译过程的第二个阶段。 A.语法分析任务： 是在词法分析的基础上将单词序列分解 成各类语法短语，如“程序”“语句”，“表 达式”等等一般这种语法短语，也称语 法单位,(2)语法分析,2007年9月4日星期二5时12分32秒,共63页, Page26,将语法单位转换成语法树,B语法分析任务之二,比如上述程序段中的单词序列： id1:=id2id3 * 10 经语法分析得知其是PASCAL语言的“赋值语句 ”，表示成如图1.4所示的语法树或是图1.5所 示的那种形式,2007年9月4日星期二5时12分32秒,共63页, Page27,语句id1:=id2+id3*10的语法树,2007年9月4日星期二5时12分32秒,共63页, Page28,图1.5语句id1:=id2+id3*10的语法树另一种形式,简化的语法树,2007年9月4日星期二5时12分32秒,共63页, Page29,（A) 语法分析所依据的是语言的语法规则，即描 述程序结构的规则通过语法分析确定整个输入 串是否构成一个语法上正确的程序,C怎样进行语法分析规则,2007年9月4日星期二5时12分32秒,共63页, Page30,(B)程序的构成规则通常是递规法则表示： 例：表达式的递规规则定义： 1）任何标识符是表达式。 2）任何常数（整常数、实常数）是表达式 3) 若表达式1和表达式2都是表达式那么； 表达式1+表达式2 表达式1*表达式2 (表达式1） 都是表达式,语法规则的表示,2007年9月4日星期二5时12分32秒,共63页, Page31,例如：语句也可以递归地定义，如 1）标识符:=表达式 是语句。 2）while（表达式）do 语句和 IF（表达式）then 语句else 语句 都是语句。 上述赋值语句；id1:=id2id3*10之所以能 表示成图1.4的语法树，依据的是赋值语句 和表达式的定义规则。,实例分析,2007年9月4日星期二5时12分32秒,共63页, Page32,词法分析的任务仅对源程序进行线性扫描 即可完成，比如识别标识符，因为标识符的 结构是字母开头的字母和数字串，这只要顺 序扫描输入流，遇到既不是字母又不是数字 字符时，将前面所发现的所有字母和数字组 合在一起而构成单词标识符、但这种线性扫 描则不能用于识别递归定义的语法成分，比 如就不能用此办法去匹配表达式中的括号,D.词法分析和语法分析本质区别,2007年9月4日星期二5时12分32秒,共63页, Page33,A语义分析阶段任务 是审查源程序有无语义错误，为代 码生成阶段收集类型信息。,(3)语义分析阶段,2007年9月4日星期二5时12分32秒,共63页, Page34,(A).比如语义分析的一个工作是进行类型审 查, 审查每个算符是否具有语言规范允许的 运算对象，当不符合语言规范时编译程序应 报告错误。 (B).如有的编译程序要对实数用作数组下标 的情况报告错误。,B语义分析实例,2007年9月4日星期二5时12分32秒,共63页, Page35,(C).又比如某些语言规定运算对象可被强制， 那么当二目运算施于一整型和一实型时， 编译程序应将整型转换成实型而不能认为是 源程序的错误。,2007年9月4日星期二5时12分32秒,共63页, Page36,假如在语句sum:=fitstcount*10中的两个 运算对象；count是实型，10是整型，则语 义分析阶段进行类型审查之后，在语法分 析所得到的分析树上增加一语义处理结点， 表示整型变成实型的一目算符inttoreal, 则图1.5的树变成图 1.6所示的那样。,C语义分析实例,2007年9月4日星期二5时12分32秒,共63页, Page37,:=,10,id1,+,id2,*,id3,inttoreal,图1.5 语句id1:=id2+id3*10插入语义节点的语法树,语义分析实例,2007年9月4日星期二5时12分32秒,共63页, Page38,A.任务: 在进行了上述的语法分析和语义分析阶段的 工作之后，有的编译程序将源程序变成一种 内部表示形式，这种内部表示形式叫做中间 语言或中间代码“中间代码”是一种 结构简单、含义明确的记号系统，,（4）中间代码生成,2007年9月4日星期二5时12分32秒,共63页, Page39,a).多种多样的形式， b).重要的设计原则为两点： 一是容易生成； 二是容易将它翻译成目标代码,B.记号系统可以设计,2007年9月4日星期二5时12分32秒,共63页, Page40,很多编译程序采用了一种近似“三地 址指令”的四元式”中间代码，这种 四元式的形式为： （运算符，运算对象1，运算对象2，结果）,C.四元式记号系统,2007年9月4日星期二5时12分32秒,共63页, Page41,比如源程序 sum:=firstCount* 10可生成四 元式序列，如图1.7所示: (1) (inttoreal 10 - t1) (2) (* id3 t1 t2) (3) (+ id2 t2 t3) (4) (:= t3 - id1) 中ti(i=l,2,3）是编译程序生成的临时名字， 用于存放运算结的。,D.四元式中间代码实例,2007年9月4日星期二5时12分32秒,共63页, Page42,在此阶段的任务是对前阶段产生的中间代 码进行变换或进行改造，目的是使生成的目 标代码更为高效，即省时间和省空间。,(5)代码优化,2007年9月4日星期二5时12分32秒,共63页, Page43,(1) (inttoreal 10 - t1) (2) (* id3 t1 t2) (3) (+ id2 t2 t3) (4) (:= t3 - id1) 可变换为 (1) (* id3 10.0 t1) (2) (+ id2 t1 id1),代码优化实例,2007年9月4日星期二5时12分32秒,共63页, Page44,这一阶段的任务是把中间代码变换成特 定机器上的绝对指令代码或可重定位的 指令代码或汇编指令代码,(6)目标代码生成,2007年9月4日星期二5时12分32秒,共63页, Page45,这是编译的最后阶段，它的工作与硬件系统 结构和指令含义有关，这个阶段的工作很复 杂，涉及到硬件系统功能部件运用、机器指 令的选择、各种数据类型变量的存储空间分 配以及寄存器和后缓寄存器的调度等,目标代码生成相关因素,2007年9月4日星期二5时12分32秒,共63页, Page46,用两个寄存器（R1和R2）可能生成如图 1.9的某汇编代码 （1）MOVF id3 , R2 （2）MULF #10.0 ， R2 （3）MOVF id2 , R1 (4) ADDF R1 , R2 (5) MOV R1 , idl,目标代码生成实例,2007年9月4日星期二5时12分32秒,共63页, Page47,第一条指令将 id3的内容送至寄存器 R2， 第二条指令将其与实常数 10 0相乘。这里 用表明10.0处理为常数， 第三条指令将id2 移至寄存器R1， 第四条指令加上前面计算出的R2中的值 ， 第五条指令将寄存器RI的值移到id1地址中,目标代码生成实例的解释,2007年9月4日星期二5时12分32秒,共63页, Page48,(1)前面提到过上述编译过程的阶段划分是一理 想处理模式。 (2)事实上并非所有的编译程序都分成这样几个 阶段、有些编译程序并不要生成中间代码有些 编译程序不进行优化优化阶段即可省去， (3)有些最简 编译程序在语法分析的同时产生 目标指令代码。 如第2章介绍的PL0语言编译程序,总结,2007年9月4日星期二5时12分32秒,共63页, Page49,编编译过程的六个阶段的任务，再加上表格 管理和出错处理的工作可分别由几个模块或 程序完成，它们分别称作: 词法分析程序、 语法分析程序、 语义分析程序、 中间代码生成程序、,13编译程序的结构,2007年9月4日星期二5时12分32秒,共63页, Page50,代码优化程序、 目标代码生成程序、 表格管理程序 出错处理程序 从而可给出，个典型的编译程序 结构框图，如图 1.10所示。,2007年9月4日星期二5时12分32秒,共63页, Page51,编译程序的结构图,2007年9月4日星期二5时12分32秒,共63页, Page52,(a)常常把编译的过程分为: 前端（front end） 后端（back end）,编译程序的几点重要说明,2007年9月4日星期二5时12分32秒,共63页, Page53,前端由主要依赖于源语言而与目标机无关 阶段组成。通常这些阶段包括： 词法分析、 语法分析、 语义分析 中间代码生成 某些优化工作也可在前端做， 也包括与前端每个阶段相关的出错处 理和符号表管理工作。,2007年9月4日星期二5时12分32秒,共63页, Page54,后端工作指那些依赖于目标机而一般不依 赖源语言，只与中间码有关那些阶段: 目标代码生成， 以及相关出错处理和符号表操作,后端,2007年9月4日星期二5时12分32秒,共63页, Page55,(b)若按照这种组合方式实现编译程序， 可以设想，某一编译程序的前端加上相应 不同的后端则可以为不同的机器构成同一 个源语言的编译程序。 (c)也可以设想，不同语言编译的端生成 同一种中间语言，再使用一个共同的后端， 则可为同一机器生成几个语言的编译程序。,2007年9月4日星期二5时12分32秒,共63页, Page56,为了提高编程效率，缩短调试时间， 软件工作人员研制了不少对源程序 处理的工具。这些工具的开发不同 程度地用到编译程序各个部分的技 术和方法，下面仅是一些例子。,1.4编译原理的应用,2007年9月4日星期二5时12分32秒,共63页, Page57,结构化编辑器是引导用户在语言的语法制导 下编制程序能自动地提供关键字和与其匹 配的关键字，如if后必须有then，begin和 end的配对，左右括号的配对等这样可以减 少语法上的错误，可加快对源程序的调试， 提高效率和质量。,1）.语言的结构化编辑器,2007年9月4日星期二5时12分32秒,共63页, Page58,调试是软件开发过程中一个重要环节，结构 化编辑器只能解决语法错误的问题，而对一 个已通过编译的程序来说需进一步了解的 是程序执行的结果与编程人员的意图是否一 致，程序的执行是否实现预计的算法