ch3 文法和语言.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,文法和语言的形式定义,文法的类型,上下文无关文法及其语法树,上下文无关文法,的句型分析,有关文法实用中的一些说明,第三章文法和语言,语言的词法和语法描述工具，用有穷规则描述语言的无穷句子。,3.1,文法的直观概念,采用巴克斯范式,BNF,，规则的集合来描述,元符号,:=,|,例子,p32,:=,2,高级语言都是由句子,(,程序,),的集合组成,语言是字母表上定义的，按照一定规则构成的字母表上基本符号串,(,源程序,),的集合。,字母表：是某语言基本符号的集合，如,if,是字母表中的一个元素，保留关键字、标示符、运算符、字母、数字和一些专用符号，如,/*,，；等。描述单词和语法的字母表不同。,符号串：字母表中符号组成的任何有穷序列。如字母表,=0,1,上的符号串,001100,3.,2,符号和符号串,符号串的头尾,z=xy,是符号串，,x,是,z,的头，,y,是,z,的尾。,x,非空，,y,是固有尾；,y,非空，,x,是,固有头,例子,z=abc,头,a,ab,abc,符号串的方幂,x,是符号串，将自身链接,n,次的符号串,z=xxx=x,n,设,x=ab,则,x,0,=,x,1,=ab,x,2,=abab,x,n,=x,n-1,x,符号串的集合,若集合,A,中所有元素都是某字母表上字符串。,符号串集合的乘积,-,笛卡尔乘积,4,符号串集合的乘积,-,笛卡尔乘积,集合,A,和,B,的乘积,AB=xy|x,A,y,B,A=a,b,B=c,d,AB=ac,ad,bc,bd,A=A,=A,字母表集合的闭包,*,定义在字母表,上的所有有穷长字符串的集合。,*,=,0,1,2,n,=,0,+,正闭包,+,=,1,2,n,=,*,例子：,=0,1,，,*,=,0,1,00,01,10,11,000,无穷,+,=0,1,00,01,10,11,000,5,6,3.3,文法和语言的形式定义,如何来描述一种语言？,如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示,.,如果语言是无穷的找出语言的有穷表示。语言的有穷表示有两个途经：,生成方式,(,文法,),：语言中的每个句子可以用严格 定义的规则来构造。,识别方式,(,自动机,),：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。,(,自动机与文法等价,),7,语言中的每个句子可以用严格定义的规则来构造。,规则：,也称,重写规则,、,产生式,或,生成式,，是形如,或,=,的,(,，,),有序对，其中,是字母表,V,的正闭包,V,+,中的一个符号，,是,V,*,中的一个符号。,称为规则的左部，,称作规则的右部。,文法的定义,推导的概念,句型、句子和语言的定义,8,文法定义,文法,G,定义为四元组,(,V,N,，,V,T,，,P,，,S,),其中,V,N:,非终结符号,(,或语法实体，或变量,),集；,V,T:,终结符号集；,P:,规则的集合；,V,N,，,V,T,和,P,是 非空有穷集。,S:,称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。,V,N,和,V,T,不含公共的元素，即,V,N,V,T,=,用,V,表示,V,N,V,T,，称为文法,G,的字母表或字汇表,9,文法的定义,例 文法,G=,（,V,N,，,V,T,，,P,，,S,）,V,N,=S,V,T,=0,1,P=S,0S1,S,01,S,为开始符号,例 文法,G=,（,V,N,，,V,T,，,P,，,S,）,V,N,=,标识符，字母，数字,V,T,=a,b,c,x,y,z,0,1,9,P=,a,z,0,9,S=,11,文法的写法,元,符号,:,=,|,习惯 大写字母表示非终结符 小写字母表示终结符,GS:,SaA,b,Aab,AaA,b,A,(2)GS:,Aab|aA,b,|SaA,b,描述文法的规则成为巴克斯范式,BNF,。也可以用语法图来表示。模仿第,2,章,p13-15,写出上例的语法图,.,12,推导的定义,直接推导,“”,是文法,G,的产生式，若有,v,w,满足：,v=,w=,其中,V,*,V,*,则称,v,直接,推导,到,w,记作,v,w,也称,w,直接,归约,到,v,例：,G,：,S,0S1,，,S,01,0S1 00S11,00S11 000S111,000S111 00001111,S,0S1,13,推导,.,(,.),.,.,(,),VAR;BEGIN READ()END.,VAR A;BEGIN READ()END.,(A),VAR A;BEGIN READ()END.,VAR A;BEGIN READ(A)END.,(A),14,推导的定义,若存在,v=w,0,w,1,.w,n,=w,(n0),则记为,v,=+,w,，称作,v,推导出,w,，或,w,归约到,v,若有,v,=+,w,或,v=w则记为,v,=*,w,15,例：,G,：,S,0S1,，,S,01,0S1 00S11,00S11 000S111,000S111 00001111,S,0S1 00S11 000S111 00001111,S,=+,00001111,00S11,=*,00S11,16,句型、句子的定义,句型,有文法,GS,，若,S,=*,x,，则称,x,是文法,G,的句型。,句子,有文法,GS,，若,S,=*,x,，且,x,V,T,*,，则称,x,是文法,G,的句子。,例：,GS,：,S,0S1,，,S,01,S,0S1 00S11 000S111 00001111,G,的句型,S,0S1,00S11,000S111,00001111,G,的句子,00001111,01,17,句型、句子,例：,G,E,：,EE+T|T TT*F|F F(E)|aE,E+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a,句子：用符号,a,，,+,，*，,(,和,),构成的算术表达式,18,(,文法生成的,),语言的定义,由文法,G,生成的语言记为,L(G),它是文法,G,的一切句子的集合,:L(G)=x|S,=*,x,，其中,S,为文法的开始符号，且,x,V,T,*,例：,G,：,S,0S1,，,S,01,L(G)=0,n,1,n,|n,1,例 文法,GS,：,（,1,）,S,aSBE,（,2,）,S,aBE,（,3,）,EB,BE,（,4,）,aB,ab,（,5,）,bB,bb,（,6,）,bE,be,（,7,）,eE,ee,L,（,G,）,=a,n,b,n,e,n,|n,1,G,生成的每个串都在,L(G),中,L(G),中的每个串确实能被,G,生成,20,文法的等价,若,L,（,G,1,）,=L,（,G,2,），则称文法,G,1,和,G,2,是等价的。,如文法,G,1,A,：,ADB,与,G,2,S,：,S0S1,等价,ADE S01,EAB,D0,B1,21,3.4,文法的类型,通过对产生式施加不同的限制,，,Chomsky,将文法分为,四种类型,：,0,型文法：对任一产生式,，都有,(V,N,V,T,),+,，,(V,N,V,T,),*,1,型文法：,对任一产生式,，都有,|,，仅仅,S,除外,2,型文法：,对任一产生式,，都有,V,N,3,型文法：,任一产生式,的形式都为,AaB,或,Aa,，其中,AV,N,，,BV,N,，,aV,T,*,22,文法的类型,例：,1,型（上下文有关）文法,文法,GS,：,SCDAbbA,CaCABaaB,CbCBBbbB,ADaD Ca,BDbD Db,AabD,23,文法的类型,例：,2,型（上下文无关）文法,文法,GS,：,S,AB,A,BS|0,B,SA|1,24,3,型文法,GS,：,S,0A|1B|0,A,0A|1B|0S,B,1B|1|0,GI,：,I,lT,I,l,T,lT,T,dT,T,l,T,d,25,文法的类型,2,型文法,1,型文法,0,型文法,四类,文法,之间,的,逐级,“,包含,”,关系,3,型文法,26,文法和语言,0,型文法产生的语言称为,0,型语言,1,型文法或上下文有关文法（,CSG,）,产生的语言称为,1,型语言,或上下文有关,语言（,CSL,）,2,型文法或上下文无关文法（,CFG,）,产生的语言称为,2,型语言,或上下文无关,语言（,CF L,）,3,型文法或正则（正规）文法（,RG,）,产生的语言称为,3,型语言,正则（正规）,语言（,RL,）,27,文法和语言,四种文法之间的关系 是将产生式做进一步限制而定义的。,语言之间的关系依次：有不是上下文有关语言的,0,型语言，有不是上下文无关语言的,1,型语言，有不是正则语言的上下文无关语言。,28,根据形式语言理论,文法和识别系统间有这样的关系,0,型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何,0,型语言都是递归可枚举的,1,型文法（上下文有关文法）：产生式的形式为,1,A,2,1,2,，即只有,A,出现在,1,和,2,的上下文中时，才允许,取代,A,。其识别系统是线性界限自动机。,29,2,型文法（上下文无关文法,CFG,）：,产生式的形式为,A,，,取代,A,时与,A,的上下文无关。其识别系统是不确定的下推自动机。,描述语法的构成。,3,型文法（正规文法,RG,）：,文法,G=(V,N,V,T,P,S),其中,P,中的,产生式的形式为,A,B,或者,A,，其中,A,和,B,是非终结符号，,V,T,*,。,产生的语言是有穷自动机（,FA,）所接受的集合。,复习,规则、文法、推导、句型、句子、语言,文法的等价性,文法分类,有用文法是上下文无关文法和正规文法,30,31,3,型,(,正规,),文法产生的语言是有穷自动机,(FA),所接受的字符串,(,句子,),集合,.,单词都是用,3,型文法定义。,定理,设,G=,（,V,N,，,V,T,，,P,，,S,）是,3,型文法，则存在一个非确定有穷自动机,M=(K,f,A,Z),，使得,L(M)=L(G),非确定有穷自动机,NFA M,五元组构造如下：,=,V,T,K=,V,N,N,N,为新状态,它不在,V,N,中,A=S,Z=N,对,G,中的形如,DtB,的产生式,t,为终结符或,有,f(D,t)=B,；,对,G,中形如,Dt,的产生式，,t,为终结符或,有,f(D,t)=N;,对,V,T,中的每一个,a,有,f(N,a)=,有穷,自动机,(FA),是描述,3,型文法的数学工具,32,3,型文法,和,有穷自动机（,FA,）,G,：,SaA|bB,A,bB|aD|a,BaA|bD|b,DaD|bD|a|b,BA,S,a,a,a,b,b,b,a,b,D,Z,a,b,a,b,33,3,型文法,和,有穷自动机（,FA,）,定理,已知一有穷自动机,NFA M=,(K,f,A,Z),存在有一个,3,型文法,G=,（,V,N,，,V,T,，,P,，,S,）,使得,L(G)=L(M),G,的定义：,V,T,=,V,N,=,K,S=A,若,f(D,t)=B,，则,DtB,在,P,中,若,f(D,t)=B,，且,B,在,Z,中，则,Dt,在,P,中,34,3,型文法,和,有穷自动机（,FA,）,G,：,SaA|bB,A,bB|aD|a,BaA|bD|b,DaD|bD|a|b,D,B,A,S,a,a,a,b,b,ab,b,正规式（定义见教科书,p52,）,35,36,正规文法和,正规式（定义见教科书,p52,）,对上的正规式,r,存在一个文法,G=(V,N,V,T,P,S),：,L(G)=L(r),初始，,V,T,=,S,V,N,，,生成正规产生式 S,r (R.1),对形如,Ar,1,r,2,的,正规产生式：,Ar,1,B Br,2,B,V,N,(R,.,2),对形如,A,rr,1,的,正规产生式：,ArB Ar,1,BrB Br,1,B,V,N,(R,.,3),对形如,A,r,1,r,2,的,正规产生式:,Ar,1,A r,2,不断应用,(R,.x,),做变换，直到每个产生式右端至多有一个,V,N37,例,r=a(ad),(1)Sa(ad),(2)SaA A(ad),A,(ad)B A,B(ad)B,B,Gs:,SaA A V,T,=a,d AaBV,N,=S,A,B AdB,BaB BdB B,38,正规文法和,正规式,对正规文法,G=(V,N,V,T,P,S),存在一个,=,V,T,上的正规式,r:,L(r)=L(G),AxB,By,形成正规式,A=xy,AxAy,形成正规式,A=x,y,Axy,形成正规式,A=xy,39,正规文法和正规式,Gs:S,aA|a,A,aAadAd,A,(ad)A(ad),A,(ad),(ad),S=a,(ad),(ad)a=a(ad),(ad)=aad),),R=a(ad),40,3.5,上下文无关文法及其语法树,上下文无关文法,(2,型文法,),有足够的能力描述程序设计语言的语法结构。,语法树,-,句型推导,的,直观表示。,41,语法树,-,句型推导,的,直观表示,G,E,：,EE+T|T TT*F|F F(E)|aE,E+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a,E,E+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a,E,E+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a,42,规范推导 规范句型,最左（最右）推导：在推导的任何一步,，其中,、,是句型，都是对,中的最左（右）非终结符进行替换,最右推导被称为规范推导。,由规范推导所得的句型称为规范句型,43,语法树,设,G=(,V,N,V,T,P,S,),为一,cfg,，若一棵树满足下列,4,个条件，则此树称作,G,的语法树,(,推导树,)(,派生树）：,1.,每个结点都有一个标记，此标记是,V,的一个符号,2.,根的标记是,S,3.,若一结点,n,至少有一个它自己除外的子孙，并且有标记,A,，则肯定,A,V,N,4.,如果结点,n,有标记,A,其直接子孙结点从左到右的次序是,n,1,，,n,2,，,，,n,k,，其标记分别为,A,1,，,A,2,，,，,A,k那么,AA,1,A,2,，,，,A,k,一定是,P,中的一个产生式,语法树的结果：,从左到右读出叶子的标记而构成句型,。树称为该句型的语法树。,44,上下文无关文法的语法树,句型,a,a,bbaa,的可能,推导,序列和语法树,例,:3.7,文法,GS:,S,a,AS,A,S,b,A,A,SS,S,a,A,ba,S,a,A S,S,b,A,a,a,b,a,S,a,A,S,a,A,a,a,S,b,A,a,a,S,b,ba,a,a,a,bbaa,S,a,A,S,a,S,b,A,S,a,a,b,A,S,aab,ba,S,aabba,a,S,a,A,S,a,S,b,A,S,a,S,b,A,a,a,ab,A,a,aab,ba,a,45,语法树,-,句型推导,的,直观表示,给定文法,G=(,V,N,V,T,P,S,),，对于,G,的任何句型都能构造与之关联的语法树,(,推导树,),定理：,G,为上下文无关文法，,对于,，有,S,=*,，当且仅当,文法,G,有以,为结果的一棵语法树,(,推导树,),46,一棵语法树表示了一个句型的种种可能的,(,但未必是所有的,),不同推导过程，包括最左,(,最右,),推导。但是，一个句型是否只对应唯一的一棵语法树呢,?,一个句型是否只有唯一的一个最左,(,最右,),推导呢,?,47,例：,G,E:E i,E E+E,E E*E,E (E),E,E+E,E*E i,i i,E,E*E,i E+E,i i,句型,i*i+i,的两个不同的最左推导：,推导,1,：,E,E+E E*E+E i*E+E i*i+E i*i+i,推导2：,E E*E i*E i*E+E i*i+E i*i+i,48,二义文法,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是,二义,的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是,二义,的,判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件,49,文法的二义性和语言的二义性,文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法,G,和,G,，其中,G,是二义的，但是却有,L(G)=L(G),，也就是说，这两个文法所产生的语言是相同的。,二义文法改造为无二义文法,G,E:E i GE,：,E T|E+T,E E+E T F|T*F,E E*E F,（,E,）,|i,E (E),引入非终结符,规定算符优先性和结合性,如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,50,3.6,（,上下文无关文法）,句型的分析,句型分析,就是,识别,一个符号串是否为某文法的,句型,，是某个,推导,的构造过程。,在语言的编译实现中，把,完成句型分析,的,程序,称为,分析程序,或,识别程序,。分析算法又称,识别算法,。,从左到右的分析算法,，即,总是从,左,到,右,地,识别输入符号串,，首先识别符号串中的,最左,符号，进而,依次识别右边,的一个符号，,直到分析结束,。,51,句型的,分析算法分类,分析算法可分为：,自上而下分析法,：,从文法的开始符号出发,，反复使用文法的产生式，,寻找,与,输入符号串,匹配,的,推导，,或者说，为输入串寻找一个最左推导。,自下而上分析法,：,从,输入符号串,开始,，,逐步进行,归约,，直至,归约,到,文法的,开始符号,。,52,两种方法反映了两种语法树的构造过程,自上而下方法,是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串。,自下而上方法,则是从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树。,53,自上而下的语法分析,例：文法,G,：,S,c,A,d,A,ab,A,a,识别输入串,w=,cabd,是否为该文法的,句子,SSS,c,A,d,c,A,d,a,b,推导过程：,S,c,A,d,c,A,d,c,ab,d,54,自下而上的语法分析,例：文法,G,：,S,c,A,d,A,ab,A,a,识别输入串,w=,cabd,是否该文法的,句子,S,A,A,c a b d,c a,b d,c a,b,d,规约,过程构造的推导：,c,A,d,c,ab,d S,c,A,d,55,自上而下的语法分析,(1)S,c,A,d,(2)A,ab(3),A,a,识别输入串,w=,cad,是否为该文法的,句子,若,S,cAd,后选择,(2),扩展,A,，,S,cAd,cabd,那将会？,w,的第二个符号可以与叶子结点,a,得以匹配，但第三个符号却不能与下一叶子结点,d,匹配,？宣告分析失败（其意味着，识别程序不能为串,cad,构造语法树，即,cad,不是句子）,-,显然是错误的结论。,导致失败的原因是在分析中对,A,的选择不是正确的。,S,c A d,a b,这时应该,回朔,，把,A,为根的子树剪掉，扫描过的输入串中的,a,吐出来,再试探用产生式（,3,）,56,自下而上的语法分析,(1)S,c,A,d,(2)A,ab (3),A,a,识别输入串,w=,cabd,是否为该文法的,句子,对串,cabd,的分析中，如果不是选择,ab,用产生式,(2),而是选择,a,用产生式,(3),将,a,归约到了,A,，那么在,c A b d,中无法找到一个可归约串了，最终就达不到归约到,S,的结果，因而也无从知道,cabd,是一个句子。,c,a,b d,c A b d,a,57,句型分析的有关问题,1),在自上而下的分析方法中,如何,选择,使用,哪个,产生式进行推导,？,假定要被代换的最左非终结符号是,B,，且有,n,条规则：,B,A1|A2|An,，那么如何确定用哪个右部去替代,B,？,LL(1),文法不用回溯。确定和不确定？,2),自下而上的分析方法中,如何,识别可归约的串,？,在分析程序工作的每一步，都是从当前串中,选择一个,子串,，将它,归约,到,某个非终结符号,，该子串称为“,可归约串,”,刻画,“,可归约串,”,-,句柄、素短语,文法,GS,句型的短语,S,*,A,且,A,+,，,则称,是,句型,相对于非终结符,A,的,短语,句型的直接短语,若有,A,，,则称,是句型,相对于非终结符,A,的,直接短语,句型的句柄,一个句型的,最左直接短语,称为,该句型,的,句柄,最左素短语,至少含有一个终结符的最左边的短语，且这个短语不包含别的短语。,例：,i*i+i,的短语、直接短语和句柄,E,E +T,T F,T *F,短语是句型的字串,i,3,短语,：,i,1,*,i,2,+,i,3,，,i,1,*,i,2,，,F,i,2,i,1,，,i,2,，,i,3,。,i,1,直接短语,：,i,1,，,i,2,，,i,3,。,句柄,：,i,1,最左素短语：,i,1,GE,：,EE+T|T TT*F|F F(E)|i,句型：,i*i+i,自下而上的语法分析,在分析程序工作的每一步，都是从当前串中,选择一个,子串,，将它,归约,到,某个非终结符号,，该子串称为“,可归约串,”,选择“,可归约串,”是最左素短语（至少含有一个终结符的最左边的短语，且这个短语不包含别的短语）,选择“,可归约串,”是句型的句柄称为规范归约,GE,：,EE+T|T TT*F|F F(E)|i,句型,i*i+i,的自下而上分析，,总是归约当前句型的句柄形成的规范推导序列：,E,E+TE+FE+iT+iT*F+iT*i+iF*i+i i*i+i,句型,i*i+i,的自下而上分析,总是归约当前句型的最左素短语形成的推导：,E,T+FT+iF*F+iF*i+i i*i+i,GE,：,EE+T|T TT*F|F F(E)|i,E,E +T,T F,T *F,i,3,F,i,2,句型,F*i,2,+,i,3,的最左素短语：,i,2,归约为,F,句型,F*F,+,i,3,的,最左素短语：,F+F,归约为,T,句型,T+i,最左素短语,i,3,归约为,F;,句型,T+F,最左素短语,T+F,归约为,E,63,3.7,文法实用中的一些说明,3.7.1,有关文法的实用限制,-,化简文法,文法中,不含有,有害规则,和,多余规则,有害规则,：形如,U,U,的产生式。会,引起,文法的,二义性,多余规则,：指文法中,任何句子的推导,都,不会用到的规则,文法中,不含有,不可到达和不可终止的,非终结符,1,）文法中某些,非终结符不在任何规则的右部出现,，该非终结符称为,不可到达,。,2,）文法中某些,非终结符,，由它不能推出终结符号串,，该非终结符称,为,不可终止,。,64,对于文法,GS,，为了保证任一非终结符,A,在,句子,推导中出现，必须满足如下两个条件：,1.A,必须在某句型中出现,即有,S,=*,A,，其中,，,属于,V,*,2.,必须能够从,A,推出终结符号串,t,来,即,A,=*,t,，其中,tV,T,*,65,化简文法,例：,GS,：,1),S,Be,2,),B,Ce,D,为不可到达,3,),B,Af C,为不可终止,4,),A,Ae,5,),A,e,6,),C,Cf,7,),D,f,产生式,2,），,6,），,7,）为,多余规则,应去,掉。,66,3.7.2,上下文无关文法中的,规则,上下文无关文法中某些规则可具有形式,A,，称这种规则为,规则,因为,规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现,两种定义的唯一差别是,句子在不在语言中,文法构思的启示是要找出语言的有穷描述，而如果语言,L,有一个有穷的描述，则,L,1,=L,也同样有一个有穷的描述，并且可以证明，若,L,是上下文有关语言、上下文无关语言或正规语言，则,L,和,L-,分别是上下文有关语言、上下文无关语言和正规语言。,67,练习,1.,写一文法，使其语言是偶正整数的集合。,要求：,允许,0,打头,(2),不允许,0,打头,2.,证明下述文法,G,表达式,是二义的。,表达式,=a|(,表达式,)|,表达式,运算符,表达式,运算符,=+|-|*|/,3.,令文法,G,E,为：,ET|E+T|E-T,TF|T*F|T/F,F(E)|i,证明,E+T*F,是它的一个句型,68,练习,4.,请,给出生成下述语言的上下文无关文法：,（,1,）,a,n,b,n,a,m,b,m,|n,，,m=0,(2)1,n,0,m,1,m,0,n,|n,，,m=0,5.,请,给出生成下述语言的三型文法：,(1),a,n,b,m,|n,m=1,(2)a,n,b,m,c,k,|n,m,k=0,6.,请,给出下述文法所对应的正规式：,S0A|1B,A1S|1,B0S|0,