程序设计语言 编译原理(第三版)第2章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,章高级语言及其语法描述,2.1,程序语言的定义,2.2,高级语言的一般特性（略）,2.3,程序语言的语法描述,1,2.1,程序语言的定义,自然语言与计算机语言的区别与联系：,计算机程序语言,一个记号系统，,类似于自然语言，由语法,+,语义定义,自然语言,（,1,）人与人的通讯工具,（,2,）语义：由环境、背景知识、语气等决定,二义性（常有）,难以形式化,计算机语言,（,1,）计算机系统间、人机间通讯工具,（,2,）具有严格的语法、语义,易于形式化（严格）,2,2.1,程序语言的定义,一、语法,一组规则，使用它可以形成和产生一个合式的程序，则这组规则称为语法,。,定义了程序的形式结构，是判断输入字符串是否构成一个形式上（即合式）正确程序的依据。,词法规则,单词符号的形成规则，即规定了字母表中,哪样的字符串是一个单词符号。,单词符号,语言中具有独立意义的最基本结构。,语法规则,语法单位的形成规则，即规定了如何从单,词符号形成更大的结构（即语法单位）。,3,2.1,程序语言的定义,二、语义,1.,语义规则：,一组规则，使用它可以定义一个程序的意义,。,离开语义，语言只不过是,一堆符号的集合,；在许多语言中有着,形式上,完全相同的语法单位,，但,含义,却不尽相同。,.,注意：,阐明语义要比阐明语法难得多，现在还没有一,种公认的形式系统，借助于它可以,自动地,构造,出实用的编译程序。,本书,基于属性文法的语法制导翻译方法较接近形式化,4,2.,程序语言的语法描述,基本概念,1.,有穷字母表。,中的每个元素。,由中的符号所构成的一个,有穷序列,。,空字,，不包含任何符号的序列。,上的所有符号串的全体，包括,。,注：,区分：,、,、,空集,：不含任何元素的集合,：,符号：,上的符号串：,：,*,：,5,2.,程序语言的语法描述,.,（连接）积,：,UV=,|,U,V,U,、,V,*,UV,不一定等于,VU,但,(UV)W=U(VW),V,n,=VV,VV,0,=,V*=V,0,V,1,V,2,V,3,V,+,=VV*,n,个,V,的闭包,V,的正则闭包,注：,V,*,中的每个符号串都是由,V,中的符号串经,有限次,连接而成的。,6,例：,=a,b,U=ab,b V=aa,bb,a,b*=a,b,0,a,b,1,a,b,2,.=,a,b,ab,aa,bb,ba.,a,b,+,=a,ba,b*,=a,b,a,b,ab,aa,bb,ba.,=,a,b,ab,aa,bb,ba.,ab,b aa,bb=abaa,abbb,baa,bbb,U V=,*=,+,=,7,2.,程序语言的语法描述,一、上下文无关文法,1.,定义：,文法：,描述语言的语法结构的,形式规则,（即语法规则）。,上下文无关文法：,所定义的语法范畴（或语法单位）是,完全独立,于这种范畴可能出现的环境,的一种文法。,描述语法规则的且独立于环境,描述语法规则,例：,英语中，一般句子是由,主,谓,二部分构成。,8,2.,程序语言的语法描述,2.,文法,语法的类比：,分析：,The grey wolf will eat the goat,.,The,grey wolf will,eat,the goat,直接宾语,名词,动词,谓语,名词,形容词,冠词,主语,句子,助动词,动词原形,冠词,9,2.,程序语言的语法描述,.,产生句子的规则,从产生语言的角度,(1),(2),the,grey,(5),(6),(9),will,eat,wolf,goat,10,2.,程序语言的语法描述,B.,句子的语法组成,终结符号集，非终结符号集，,语法规则，开始符号,终结符号集,V,T,=the,grey,wolf,will,eat,goat,非终结符号集,V,N,=,语法规则集,P=,开始符号,S=,11,2.,程序语言的语法描述,C.,句子的派生（推导）,根据规则,the ,the grey ,the grey wolf ,the grey wolf ,the grey wolf will eat the goat,12,2.,程序语言的语法描述,D.,句子的语义要求,the grey wolf will eat the goat,the grey wolf will eat the wolf,the grey goat will eat the wolf,the grey goat will eat the goat,符合语法且符合语义的句子仅是：,the grey wolf will eat the goat,13,2.,程序语言的语法描述,3.,上下文无关文法的形式定义,是一个四元组（,，,，）,终结符号集，非空有限集,非终结符号集，非空有限集,终结符号：,描述单词符号,组成语言的基本符号，是一个,语言的不可再分的基本符号。,例如：,基本字，标识符，常数，算符，界符等,非终结符：,代表语法范畴，一个非终结符代表一个一定的语,法概念，每个非终结符表示一定符号串的集合。,例如：,算术表达式，布尔表达式，赋值句，分程序，过程等,14,2.,程序语言的语法描述,开始符号，一个特殊的非终结符号,产生式集合，有限集,产生式：,定义语法范畴的一种书写规则,形式：,A,AV,N,(V,T,V,N,)*,注：,“,”,:,“,定义为,”,“”：,“,或,”,非终结符号,:,用大写字母、,或汉语组代表,终结符,:,用小写字母,代表,至少必须在某个产生式的左部出现一次,15,2.,程序语言的语法描述,例,1,：,上下文无关文法：,E,i|EAE,A+|*,非终结符号：,开始符号：,终结符号：,E,，,A,E,+,i,GE,16,2.,程序语言的语法描述,例,2,：算术表达式的文法,标识符,(id)(,常量、变量,),是表达式,(E),；,表达式加一个表达式是表达式；,表达式减一个表达式是表达式；,表达式乘一个表达式是表达式；,表达式除一个表达式是表达式；,表达式加上括号是表达式；,E,id,E,E+E,E,E-E,E,E*E,E,E/E,E,(E),P:E,id,|,E+E,|,E-E,|,E*E,|,E/E|(E),17,2.,程序语言的语法描述,.,文法与语言的关系,中心思想：,从文法的开始符号出发，反复连续使用产,生式，对非终结符施行,替换,和,展开,。,一个上下文无关文法如何定义一个语言呢？,18,2.,程序语言的语法描述,(,),(,+,),(,+,),(,+,),例：,E,id,|,E+E,|,E-E,|,E*E,|,E/E|(E)(i+i),注：,我们可以从出发，进行一系列的推导，推出种种不,同的算术表达式出来,该推导过程证明了（,+,）是文法所定义的一个算术表达式。,19,2.,程序语言的语法描述,“,”,：,若,，则称该序列是从,至,的一个推导（,可推导出,）,：,：,+,*,表示,“,直接推出,”,，即仅推出一步。,A,仅当,是一个产生式，且,(,),*,“,推导,”,：,从,出发，经过,步,或,若干步,，可推导出,从,出发，经,一步,或,若干步,，可推导出,注符号的含义,20,2.,程序语言的语法描述,“,句型,”,：,设是一个文法，是其开始符号，,(,V,N,)*,*,5.,语言,“,句子,”,：,仅含终结符号的句型是一个句子。,+,“,语言,”,：,文法所产生的句子的全体是一个语言，记为,（）,*,21,2.,程序语言的语法描述,6.,最左右推导,定义：,任何一步,都是对,中的,最左最右,非终结符,进行替换的。,+,+,（）（*,+,）（*,+,）,（,+,）（）,+,（）（,+,）（）,（）（）,（）,最左推导：,最右推导,：,22,练习：,GS:,S,a|,|(T),TT,S|S,分别给出下列句子的最左和最右推导过程：,（,1,）（,a,a,a),（,2,）,(a,(a,),（,1,）最左推导：,S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,a),（,2,）最左推导：,S=(T)=(T,S)=(S,S)=(a,S)=(a,(T)=(a,(T,S)=(a,(S,S)=(a,(a,S)=(a,(a,),23,2.,程序语言的语法描述,7.,例题,例,.,考虑一个文法,：,定义了一个什么样的语言？,.,.,.,（）,？,24,2.,程序语言的语法描述,例,.,考虑文法,：,定义了一个什么样的语言？,分析：,？,与类似,由,可知，其必产生,，且以此终结25,2.,程序语言的语法描述,例,.,构造一个文法,，使（,）,分析：,与,的区别在于，,必须使、出现的,次数相,等,，故而、必须,同时出现。,G,：,26,2.,程序语言的语法描述,思考,:,考虑文法,D,D,；,D|TL,Tint|char,LL,，,id|id,定义了一个什么样的语言？,27,2.,程序语言的语法描述,二、语法分析树与二义性,.,语法分析树,用,树的形式表示一个句型的推导生成,，有助于理解,一个句子语法结构的层次。,树根：,开始符号,中间结点：,非终结符,叶结点：,终结符非终结符,28,2.,程序语言的语法描述,例,：,（）的最左推导（）,（根）,（）,+,次 ,层,结论：,一个句型不一定有唯一的一棵语法树。,即,一个句型的最左右推导可能不唯一。,29,2.,程序语言的语法描述,例：,（）关于文法的另一个最左推导（,）,（）,*,+,（）（*）,（）,（,+,）,（）,（）,30,2.,程序语言的语法描述,2.,二义文法,用若一个文法中存在某个句子，它有两个不同的,最左右推导，则该文法为二义文法,例：,上述文法,*（）,实质：,同一个句子存在两棵语法分析树。,31,2.,程序语言的语法描述,例：,句子,+,的最左推导过程,*,+,+,*,最,左,推导,+,*,*,*,32,2.,程序语言的语法描述,最,右,推导,*,+,+,*,+,*,*,+33,2.,程序语言的语法描述,注意：,、区分：文法的二义性,语言的二义性,二义文法无二义文法,但（）（,）,例如：,：,+,*（）,：,+,*,（）,（）（,）,34,B,、二义问题是不可判定的：,即,不存在,一个算法，它能在,有限步骤内,，确切,的判定一个文法是否为二义的,所能做的只是为无二义性寻找一组充分条件,2.,程序语言的语法描述,35,2.,程序语言的语法描述,三、形式语言,G=(V,T,V,N,S,),0,型文法：,(V,N,V,T,)*,，,至少有一个非终结符,任何产生式,均满足,|,|,|,；,仅,S,例外，但,S,不得出现在任何产生式的右部。,1,型文法：,短语,文法,上下文,有关,文法,36,2.,程序语言的语法描述,2,型文法：,A,AV,N,(V,N,V,T,)*,G,的任何产生式为,A,B,或,A,其中,V,T,*,，,A,、,B V,N,。,3,型文法：,G,的任何产生式为,A,B,或,A,，,其中,V,T,*,，,A,、,B V,N,。,上下文,无关,文法,正规,文法,右线性,正规文法,左线性,正规文法,37,