编译程序的构成课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,1.2,编译程序,的,逻辑结构,词法分析程序,语法分析程序,语义分析程序,中间代码生成,代码优化程序,目标代码生成,信 息 表 管 理 程 序,错 误 检 查 和 处 理 程 序,源,程,序,目,标,代,码,1.2 编译程序的逻辑结构词法分析程序语法分析程序语义分析,1,1.3,编译程序的组织,需要注意的是，前面所说的各部分之间的关系，是指它们之间的,逻辑关系,，而不一定是执行时间上的先后顺序。,事实上，可按不同的执行流程来组织上述各部分的工作，这在很大程度上依赖于编译过程中,对源程序扫描的遍数,，以及如何划分各遍扫描所进行的工作。,此处所说的“,遍,”,是指对源程序或其内部表示从头到尾扫视一次,并进行有关的加工处理工作。,1.3 编译程序的组织需要注意的是，前面所说的各部分之间,2,例如，对于要求经,一遍扫描,就能完成从源程序到目标代码翻译的编译程序，我们可,以语法分析程序为中心,来组织它的工作流程。,例如，对于要求经一遍扫描就能完成从源程序到目标代码翻译的编译,3,语法分析,程序,语义分析及,代码生成程序,词法分析,程序,整理目标程序,源程序,目标程序,停机,开始,图,1-3,以语法分析程序为中心的编译程序逻辑结构,语法分析语义分析及词法分析整理目标程序源程序目标程序停机开始,4,显然，由于整个编译程序只对源程序进行一次扫描，故,不必产生中间代码,。,对于某些程序语言，例如,PASCAL,和,C,，用一遍扫描的编译程序去实现比较困难，宜于采用,多遍扫描,的编译程序结构。,显然，由于整个编译程序只对源程序进行一次扫描，故不必产生中间,5,本章内容结束,本章内容结束,6,第,2,章,前后文无关文法和语言,在,20,世纪,50,年代，,N.Chomsky,首先对语言的描述问题进行了探讨。他提出了一种用来描述语言的数学系统，并以此定义了四类性质不同的语言，称为,语言（文法）的,Chomsky,分类,。,人们把用一组数学符号和规则来描述语言的方式称为,形式描述,，把所用的数学符号和规则称为,形式语言,。,目前，,形式语言与自动机理论,已成为计算机科学中的一个重要分支。,第2章 前后文无关文法和语言在20世纪50年代，N.Ch,7,2.1,文法及语言的表示,首先，我们确定一个概念：什么是语言？据统计，目前在世界各地，人们所使用的语言达,2700,多种。,Webster,的定义：“,为相当大地区的公众所懂得并使用的话，以及组成这些话的方法的统一体,”,。,上述定义对于建立语言的数学理论而言不够精确。,2.1 文法及语言的表示首先，我们确定一个概念：什么是语,8,所以，有人又将语言定义为：“,某一字母表上符号串（句子）的集合,”,此定义仍需精确化。因为：,1,）还应为所定义的句子,提供一种结构性的描述（,语法规则,）,；,2,）最好能再提供一种手段，以便,能准确地判别什么是该语言中的正确句子（,即识别方法、分析方法等,）,。,所以，有人又将语言定义为：“某一字母表上符号串（句子）的集合,9,遗憾的是，对于自然语言来说，目前尚无能够完全刻划一语言全部句子的结构的方法。,然而，对大多数程序设计语言来说，此问题已被解决。,1960,年，,P.Naur&J.Backus,首先用,BNF,（,Backus-Naur-Formal,（范式）对,ALGOL,语言进行了描述。,应指出，,BNF,成功地解决了程序设计语言的语法描述问题，但描述其语义，还必须借助自然语言。,遗憾的是，对于自然语言来说，目前尚无能够完全刻划一语言全部句,10,通常，可用如下方式表示或定义一种语言：,（,1,）若语言的句子有限时，可用,枚举法,。,例如，只含两个句子的语言：,“I am a teacher”,“You are students”;,通常，可用如下方式表示或定义一种语言：,11,（,2,）制定,有限条规则,，用于产生所要描述的语言的全部句子,(,可无限多,),，这些规则构成了该语言的,文法,。,例如，文法,G,1,标识符,：,标识符,字母,|,标识符,字母,|,标识符,数字,字母,a|b|c|z,数字,0|1|2|9,（2）制定有限条规则，用于产生所要描述的语言的全部句子(可无,12,（,3,）建立一种,装置（算法或过程）,，,它以某字母表上的符号串为输入，判别该符号串是否为所描述语言的句子。此装置称为,自动机。,c,a,b,b,c,a,a,S,A,B,F,（3）建立一种装置（算法或过程），它以某字母表上的符号串为输,13,2.2,文法和语言的定义,2.2.1,基本概念和术语,1,、,字母表（符号表、符号集）,由若干元素（符,号、字母）所组成的有限非空集合。,2,、,符号串,用字母表中的符号所组成的任何有限,序列。,符号串的长度,=,符号串中所含符号的个数。,例：,aba,的长度为,3,。记为：,|,aba,|=3,空串,不含任何符号的符号串，记为,。,显然，,|=0,。,2.2 文法和语言的定义2.2.1 基本概念和术语1、,14,本课约定,用,A,、,B,、,C,、,等表示字母表或,符号串集；,用,a,b,c,S,T,U,等表示符号；,用,s,t,u,x,y,z,等表示符号串。,3,、,符号串的前（后）缀及子串,设,，,，,x,是符号串，,若,x,=,，则称,是,x,的,子串,；,特别地，,当,=,（,=,）时，称,是,x,的,前（,后,）缀,。,本课约定 用A、B、C、等表示字母表或,15,4,、,符号串的连接和方幂,连接,设,x,y,是符号串，将,y,直接拼接到,x,之后所得的新符号串称为,x,与,y,的连接，记为,xy,。,注意，一般说来，,xy,不等于,yx,；,但,x=x=x,方幂,符号串,x,与其自身的,n-1,次连接称为,x,的,n,次方幂，记为：,4、符号串的连接和方幂,16,5,、,符号串集合的和与积,设,A,，,B,为两个符号串集合，定义：,和：,A+B,（或,A,B,）,=w|w,A,，或,wB,例如，若,A=a,b,c,，,B=00,11,，则,A+B=a,b,c,00,11,。,积：,AB,（或,AB,）,=xy|xA,且,yB,例如，若,A=a,b,c,，,B=00,11,，则,AB=a00,a11,b00,b11,c00,c11,显然，,A+=+A=A,；,A=A=,；,A=A=A,5、符号串集合的和与积,17,6,、,符号串集合的方幂,例如，若,A=a,b,，则,6、符号串集合的方幂例如，若A=a,b，则,18,7,。,符号串集合的闭包,根据符号串集合的和运算，我们又可分别定义符,号串集合,A,的,正闭包,A,+,及,自反传递闭包,A,*,如下：,7。符号串集合的闭包,19,例如，若,A=a,b,，则,例如，若A=a,b，则,20,例,A=,a,b,c,例A=a,b,c,21,2.2,文法和语言的形式定义,我们从“产生语言”的角度出发，讨论文法和语言的形式定义。,产生语言,指制定出有限条规则，借助它们就能产生出某些语言的句子。,我们以几个英语句子构成的语言为例进行讨论。并设每个句子都是“主,-,谓,-,宾”结构。,2.2 文法和语言的形式定义我们从“产生语言”的角度出发,22,其中，每个用“,”,括起来的部分是所要定义语言中的一个语法实体（称为语法单位、语法结构、,语法范畴,、语法变量等）。,“,:=,”,是用于定义语法结构的符号，其含义（并读作）“,定义为,”。,语法规则也称为,产生式,(,Production,),。,:=,:=,the,其中，每个用“”括起来的部分是所要定义语言中的一个,23,:=,:=,the,:=,:=,:=,monkey,:=,banana,:=,eat,:=,has,:=,the,:=,a,:=,24,现在讨论如何用上述规则,推导,出相应语言的全部,句子,。,推导,从语言最大的一个,语法范畴,（本例中是,）开始，反复用语法规则中“,:=,”,右侧的符号串取代其左侧符号，直到所得的符号串中不再含有可被替换的,语法范畴,。,每次替换称为一步（,直接,）,推导,，并用符号“,”表示。例如，,现在讨论如何用上述规则推导出相应语言的全部句子。,25,首先用规则进行第一步推导,(,derivation,),，就可得到,，,记为：,所得的符号串含有两个,语法范畴,，可对其中任一个,(,如对,),进行新的,推导,（替换）：,重复上述过程，可得到一个推导序列：,首先用规则进行第一步推导(derivation)，就可得到,26,推导 所用 所得的符号串,步骤 规则,1 ,2 ,3 ,the,4,the,5 ,the,monkey,6,the monkey,eat,7 ,the monkey eat,a,8 ,the monkey eat a,banana,推导 所用 所得的符号串,27,从前面的推导看，从,出发，经,8,步推导,得到了一个英语句子。故前面的推导称为,长度为,8,的推导,。,若不关心推导的中间过程，可将从一符号串到,另一符号串的推导用记号 表示，例如，,上例中经过,5,步的推导记为：,从前面的推导看，从出发，经8步推导得到了一个英语句子,28,规则的简化表示,在前面的语法规则定义中,有些语法范畴,(,如,、,),有若干条不同的规则来定义它。,为简明起见，我们可以将它们写在同一个左部语法范畴下，将其定义值用符号,“,|,”,(,读作,或,),隔开。如,、,、,的定义规则可简记为：,:=monkey|banana,:=eat|has,:=the|a,规则的简化表示在前面的语法规则定义中,有些语法范畴(如名词,29,语法规则及其产生的语言,前面的语法规则可以产生,16,个不同的句子，,由这,16,个句子组成的集合，就是该规则所定义（或所产生）的,语言,。,应指出，所产生的句子中，有些句子的含义是,荒谬,的（如,the banana eat a monkey,和,the banana eat the banana,等,）。,然而，若不考虑,语义,，则我们就必须承认它们是语法上,合法,的句子。,语法规则及其产生的语言前面的语法规则可以产生16个不同的句子,30,为得到文法的严格定义，对前面的规则进,行如下的概括：,含有一系列需要定义的语法范畴，通常我们把它们的名字称为,非终结符号,。,由这些非终结符号组成的集合称为,非终结符号集,，用,V,N,记之。对于上例，我们有：,V,N,=,句子,主语短语,动词短语,宾语短语,名词,动词,冠词,为得到文法的严格定义，对前面的规则进含有一,31,含有若干个基本符号，由于这些基本符号不需要进一步定义，故通常将它们称为,终结符号,。,由终结符号组成的集合称为,终结符号集,，以,V,T,记之。对于上例有：,V,T,=monkey,banana,eat,has,the,a,含有若干个基本符号，由于这些基本符号不需要进一步定义，故通常,32,注,：,为使用上的方便，我们用,代替产生式中的,:=,。另外，在不强调开始符号,S,时，可将文法,GS,简记为,G,。,注：为使用上的方便，我们用代替产生式中的,33,当然，上述定义中的,、,都可以是空串,。另外，推导符号下面的,G,表示推导是以文法,G,的规则进行的，若,G,无须指明，则可简写为,当然，上述定义中的、都可以是空串。另外，推导符号,34,例如，由前面的文法,G,，,可得推导：,其中，,=,=,=,:=,:=,the,:=,例如，由前面的文法G，可得推导：:=,35,编译程序的构成课件,36,例,2.1,：,GA:A Bb B a,该文法仅有,3,个句型,A,Bb,ab,，,仅有,1,个句子,ab,例2.1：GA:A Bb B,37,例,2.2,：,GS:S aB|Bb B a|b,该文法仅有,6,个句型,S,aB,Bb,aa,ab,bb,，,仅有,3,个句子,aa,ab,bb,。,例2.2：GS:S aB|Bb,38,例,2.1,：