《编译方法》第2章形式语言和文法

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,第,2,章 形式语言与文法,编译方法,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Click to edit Master title style,2.1,形式语言,第,2,章 形式语言和文法,2.4,文法的二义性,2.3,文法的分类和化简,2.2,文法,2.1,形式语言,2.1.1,语言的概念,2.1.2,语言的定义方式,语言：,符号串的集合。,元素,符号串,该语言的一个句子。,字母表,符号串中符号的来源。,句子的构成,按一定规则。,程序设计语言：,程序的集合,句子,程序（一个或长或短的字符串）。,字母表,固定的字符集，语言可以使用的所有符号。,编程时必须遵循一定的规则,语法规则,和,语义规则,。,语言的描述工具,文法,2.1.1,语言的概念,2.1,语言,1.,什么是语言,（,1,）有穷字母表,一个元素的非空有穷集合，其中的元素也称符号。,每个语言均有一固定的字母表。,例：,C,语言的字母表由基本字符集（字母，数字，括号，专用字符,+,、,*、,）、保留字（,int,、,long,、,if,、,struct,、,static,、,typedef,、,sizeof,、,）等组成。,2.1.1,语言的概念,2.1,语言,2,符号串的相关概念和术语,通常用,V,、,或其他大写字母表示。,例如,V=0,，,1,，,=a,，,b,，,c,，,d,，,e,等。,（,2,）符号串,字母表中的符号组成的任何有穷序列。,相关术语：,长度：,符号串中符号的个数。,符号串,x,的长度表示为,x,，,x,=,m,0,。,空符号串：,无任何符号的串，简称空串，用,表示，,|=,0,省略写法：,z,=,x,z,=,x,z,=,x,2.1.1,语言的概念,2.1,语言,【,例,2-1】,=,a,，,b,，,c,，,，,z,，,x,=“,laugh,”,，则,|,x,|=5,=,I,，,you,，,he,，,am,，,is,，,are,，,a,，,student,，,y,=“,I am a student,”,，空格不计算长度，则,|,y,|=4,。,（,3,）符号串的运算,连接：,符号串,x,、,y,的连接,xy,为一个新的符号串，该串的前面部分为,x,，,后面部分为,y,。,成立的等式：,|,xy,|=|,x,|+|,y,|,x,=,x,=,x,【,例,2-2】,若,x,=“,home,”,，,y,=“,work,”,则,|,x,|=4 ,|,y,|=4,xy,=“,homework,”|,xy,|=4+4=8,2.1.1,语言的概念,2.1,语言,方幂：,符号串,x,的方幂就是,n,个,x,自身连接,次，表示为,x,n,。,规定,x,0,=,。,【,例,2-3】,若,x,=“,ab,”,则,x,0,=,x,1,=“,ab,”,x,2,=“,abab,”,x,3,=“,ababab,”,成立的等式：,x,1,=,x,，,x,2,=,xx,，,x,3,=,xxx,，,若,n,0,，则有：,x,n,=,xx,n-1,=,x,n-1,x,x,*,表示,x,的任意多次方幂（可以是,0,次）,x,+,表示,x,的任意非,0,次方幂。,2.1.1,语言的概念,2.1,语言,（,4,）符号串的集合,若集合,A,中的所有元素都是某字母表上的符号串，则称,A,为该字母表 上的符号串集合。,乘积：,两符号串集,U,、,V,的乘积为,UV,=,|,U,V,成立的等式：,U,=,U,=,U,V,n,=,VVV,（,n,个,V,）,规定：,V,0,=,V,*,=,V,0,V,1,V,2,V,+,=,V,1,V,2,【,例,2-4】,若,U,=,a,，,b,，,V,=,c,，,d,则,UV,=,ac,，,ad,，,bc,，,bd,2.1.1,语言的概念,2.1,语言,闭包：,若指定字母表,，则,*,表示,上的所有有穷长的串的集合。,*,=,0,1,2,n,*,称为集合,的,闭包。,+,=,1,2,n,+,称为集合,的,正闭包。,成立的等式：,*,=,0,+,，,+,=,*,=,*,若符号串,x,是,*,的元素,则表示为,x,*,否则,x,*,。,2.1.1,语言的概念,2.1,语言,语言的句子个数有限,枚举,语言的句子有很多甚至是无穷多个,给出一些规则,说明这个语言的句子的组成结构。,规则,文法规则,2.1.2,语言的定义方式,2.1,语言,【,例,2-5】,文法规则：,student,English,computer,I,you,he,am,is,are,have,study,a,an,the,文法规则的作用：,（,1,）严格定义了一个语言的句子的结构；,（,2,）用适当条数的规则描述了一个语言的全部句子。,2.1.2,语言的定义方式,2.1,语言,2.2,文法,2.2.1,文法的形式定义,2.2.2,文法的表示方法,2.2.3,相关概念,2.2,文法,表示语言中的语法单位的符号，常用尖括号,“,”,括起。,一个非终结符一般可以推导出终结符串。,一个语言可使用的所有非终结符组成的集合称为非终结符集，,用,V,N,表示。,1,终结符,不可分割的符号串，是组成句子的最基本的单位。,一个语言允许使用的所有终结符组成的集合称为终结符集，,用,V,T,表示。,2,非终结符,2.2.1,文法的形式定义,2.2,文法,3,规则（重写规则、产生式、生成式）,形如,或,或,（,，,）,的有序对，其中,：某字母表,V,的,V,+,中的一个符号串（左部）,：,V,*,中的一个符号串（右部）,定义：一个文法是一个,四元组,G,（,V,N,，,V,T,，,S,，,P,）,V,N,：非终结符集（非空）；,V,T,：终结符集（非空），,V,N,V,T,；,S,：识别符号或开始符号，,S,V,N,，,且至少在一条规则中作为左部出现；,P,：规则（产生式）的集合。,用,V,表示,V,N,V,T,，称,G,的字母表或词汇表。,4,文法,2.2.1,文法的形式定义,2.2,文法,G,：,S,0,S,1,或,G,S,：,S,0,S,1,或,G,：,S,0,S,1|01,S,01,S,01,注意：左部相同的产生式可合并，用“,|”,表示“或”。,简化表示,只写出规则,（产生式），且第一条 规则的左部,是开始符号，用“,”,括起的或大写字母表示非终结符，,不用“,”,括起的或小写字母表示终结符。,文法,G,也常写成,G,S,，方括号中的,S,为开始符号。,【,例,2-6】,有一文法,G,（,V,N,，,V,T,，,S,，,P,）,其中,:,V,N,=,S,V,T,=0,，,1,开始符号是,S,P,=,S,0,S,1,，,S,01,2.2.1,文法的形式定义,2.2,文法,【,例,2-7】,文法,G,=(,V,N,，,V,T,，,S,，,P,),为：,V,N,=,，,，,，,，,，,，,，,V,T,=,student,，,computer,，,sister,，,English,，,I,，,you,，,he,，,am,，,is,，,are,，,have,，,study,，,a,，,an,，,the,开始符号是,P=,student,computer,sister,English,I,you,he,am,is,are,have,study,a,an,the,2.2.1,文法的形式定义,2.2,文法,【,例,2-8】,FORTRAN,语言中对标识符的规定是字母开头、长度小于等于,8,的,字母数字串，则标识符的规则可以描述为：,1.,BNF,表示法,巴科斯,-,诺尔范式（巴科斯范式）,采用四个元符号描述文法：“”（或“”）、“,”,，“,|”,2.,扩展的,BNF,表示法,增加三对元符号：,（,1,）“,”,表示符号串,t,的多次重复，,n,为重复的最小次数，,m,为重,复的最大次数，省略,n,、,m,表示,t,可以重复,0,到任意多次。,2.2.2,文法的表示方法,2.2,文法,（,2,）“,()”,用于提取产生式的公共因子，从而可以简化产生式。,若有文法规则,A,x,1,|,x,2,|,x,n,表示为,A,x,(,1,|,2,|,n,),【,例,2-9】,文法规则,S,0,S,1|01,简化为,S,0(,S,1|1),或,S,(0,S,|0)1,或,S,0(,S,|)1,（,3,）“,”,：,t,表示符号串,t,可选（即可有可无）。,【,例,2-10】,C,程序设计语言的条件语句的文法规则,BNF,表示：,if,(),；,|,if,(),；,else,；,扩展,BNF,表示：,if,(),；,else,；,2.2.2,文法的表示方法,2.2,文法,3.,语法图表示法,【,例,2-11】,C,语言条件语句的语法图,2.2.2,文法的表示方法,2.2,文法,else,语句,if,条件,(,),语句,终结符,非终结符,【,例,2-13】,对文法,G,：,S,0,S,1,S,01,有直接推导序列：,S,0,S,1 00,S,11000111,定义,：如,是文法,G,（,V,N,，,V,T,，,S,，,P,）,的一条规则，,、,V,*,，,若有符号串,v,、,w,满足,v,=,，,w,=,则称,v,（应用规则,）直接产生,w,，或称,w,是,v,的,直接推导,，反过,来称,w,直接归约,到,v,，记作,v,w,。,1,推导和归约,2.2.3,相关概念,2.2,文法,定义：,如果存在直接推导序列：,v,=,w,0,w,1,w,2,w,n,=,w,则称,v,推导（产生）,出,w,，,推导长度,为,n,，反过来称,w,归约,到,v,，,记作,v,w,。,如果有,v,w,，或,v,=,w,，,则记作,v,w,。,+,+,*,【,例,2-14】,S,0,S,1 00,S,11 000111,S,推导出“,000111”,，推导长度,3,“,000111”,归约到,S,表示成,S,000111,+,2.2.3,相关概念,2.2,文法,【,例,2-15】,推导,S,0,S,1 00,S,11 000111,定义：,文法,G,（,V,N,，,V,T,，,S,，,P,），若符号串,x,可由开始符号,S,推导出,（,S,x,），则称,x,是,G,的一个,句型,，若,x,仅由终结符组成，,则称,x,为,G,的一个,句子,。,*,2,句型和句子,句型,句子,2.2.3,相关概念,2.2,文法,注意：句型和句子都必须由开始符号,S,推出！,定义：,文法描述的语言是该文法的所有句子的集合，,记作,L,(,G,),。集合形式表示：,L,(,G,)=,|,S,V,T,*,【,例,2-16,】,文法,G,：,S,0,S,1,S,01,描述的语言：,L(G)=0,n,1,n,|,n,1,3,形式语言,+,2.2.3,相关概念,2.2,文法,【,例,2-17,】,有文法,G,A,：,A,0,R,A,01,R,A,1,定义：,若有文法,G,1,、,G,2,，它们描述的语言相同，即,L,(,G,1,),=L,(,G,2,),则称两文法,G,1,和,G,2,等价,。,描述的语言,L,(,G,)=0,n,1,n,|,n,1,。,4,文法的等价性,2.2.3,相关概念,2.2,文法,2.2.3,相关概念,2.2,文法,5.,递归规则和递归文法,递归文法,：含有递归规则的文法称递归文法。,递归规则,：形如,P,1,P,2,的规则称递归规则。,若,1,=,则称左递归规则,;,若,2,=,则称右递归规则。,P,1,P,2,的递归称,间接递归,含间接递归的文法也是递归文法。,+,2.3,文法的分类和化简,2.3.1,文法的分