文法和语言的基本知识.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,#,/38,2.,4,语法树,例如 设有文法,GE:,构造句型,i*i+i,的语法树。,首先给出句型的推导过程(最左推导)：,E,E+T|ET|T,T,T,*,F|T/F|F,F,(,E)|i,EE+TT+TT,*,F+TF,*,F+Ti,*,F+T,i,*,i+Ti,*,i+Fi,*,i+i,第,1,页,/,共,70,页,2.,4,语法树,根据推导过程构造句型,i,*,i+i,的语法树如下：,EE+T,E,E,+,T,T+T,T,T,*,F+T,T,*,F,F,*,F+T,F,i,*,F+T,i,i,*,i+T,i,i,*,i+F,F,i,*,i+i,i,第,2,页,/,共,70,页,2.,4,语法树,由例可知，,语法树的构造过程是从文法的开始符号出发，构造一个推导的过程。,因为文法的每一个句型(句子)都存在一 个推导，所以文法的每个句型(句子)都存在一棵对应的语法树。,第,3,页,/,共,70,页,EE+T,E+F,E+i,T+i,T,*,F+i,T,*,i+i,F,*,i+i,i,*,i+i,2.,4,语法树,对句型,i,*,i+i，,还可给出最右推导：,E,E,+,T,T,T,*,F,F,i,i,F,i,第,4,页,/,共,70,页,2.,4,语法树,这也就是说，一棵语法树表示了,一个句型的种种可能的(但未必是所,有的)不同推导过程,包括最左(最右),推导。,第,5,页,/,共,70,页,2.4,语法树,2.子树,语法树的子树是由某一结点连同所有分枝组成的部分。,E,E,+,T,T,T,*,F,F,i,i,F,i,第,6,页,/,共,70,页,2.4,语法树,3.简单子树,语法树的简单子树是指只有单层分枝的子树。,(,即一步推导,),E,E,+,T,T,T,*,F,F,i,i,F,i,第,7,页,/,共,70,页,2.,4,语法树,句型的短语、直接短语和句柄的,直观解释是：,短语,：子树的末端结点形成的符号串是,相对于子树根的短语。,直接短语,：简单子树的末端结点形成的,符号串是相对于简单子树根的直接短语。,或者：某子树根经过,1,步推导而获得的短语。,句柄,：句型中最左直接短语。,第,8,页,/,共,70,页,2.,4,语法树,短语:,i*i+i,i*i,第一个,i,第二个,i,第三个,i,三个,i,都是直接短语,第一个,i,是句柄,注意:,i+i,不是句型的短语,句子,i,*,i+i,E,E,+,T,T,T,*,F,F,i,i,F,i,第,9,页,/,共,70,页,2.,4,语法树,前例 对文法,GS=(S,A,B,a,b,P,S),其中,P,为：,可用语法树非常直观地求出句型,baSb,的全部短语，直接短语和句柄。,S,AB,A,Aa|bB,B,a|Sb,第,10,页,/,共,70,页,2.,4,语法树,分析,首先根据句型,baSb,的推导过程画出对,应的语法树如下：,Sb,为句型的相对于,B,的短语、直接短语,baSb,为句型的相对于,S,的短语,ba,为句型的相对于,A,的短语,a,句型的相对于,B,的短语、直接短语和句柄,SABbBBbaBbaSb,SABASbbBSbbaSb,S,A,B,b,B,S,b,a,由语法树可知,第,11,页,/,共,70,页,2.5.,1,文法的二义性,从前面的讨论可以看出，对于文法,G,中,任一句型的推导序列,我们总能为它构造,一棵语法树，现在我们提出一个问题：,文法的某个句型是否只对应唯一的一棵,语法树呢？也就是，它是否只有唯一的一,个最左(最右)推导呢？,第,12,页,/,共,70,页,2.5.,1,文法的二义性,例如 设有文法,GE：,句子,i,*,i+i,有两个不同的最左推导，对应两棵不同的语法树。,E,E+E|E,*,E|(E)|i,第,13,页,/,共,70,页,2.5.,1,文法的二义性,最左推导1,E,E+EE,*,E+E,i,*,E+Ei,*,i+E,i,*,i+i,最左推导2,E,E,*,Ei,*,E,i,*,E+Ei,*,i+E,i,*,i+i,E,E,*,E,E,+,E,i,i,i,E,E,+,E,E,*,E,i,i,i,第,14,页,/,共,70,页,2.5.,1,文法的二义性,如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义性的。,或者说，若一个文法中存在某个句子，它有两个不同的最左(最右)推导，则这个文法是二义性的。,E,E+E|E,*,E|(E)|i,第,15,页,/,共,70,页,2.5.,2,文法二义性的消除,1.不改变文法中原有的语法规则,仅加,进一些非形式的语法规定。,E,E,+,E,E,*,E,i,i,i,第,16,页,/,共,70,页,2.5.,2,文法二义性的消除,2.,构造一个等价的无二义性文法。即,把排除二义性的规则合并到原有文法中,改写原有的文法。,例如，对于上例文法,GE，,将运算符的,优先顺序和结合规则：,*,优先于;、,*,左结合加到原有文法中,可构造出无二义,性文法如下：,第,17,页,/,共,70,页,2.5.,2,文法二义性的消除,则句子,i*i+i,只有唯一一棵语法树：,E,E+T|T,T,T,*,F|F,F,(,E)|i,E,E,+,T,T,T,*,F,F,i,i,F,i,第,18,页,/,共,70,页,2.5.,2,文法二义性的消除,例2 定义某程序语言条件语句的文法,G,为:,试证明该文法是二义性的并消除之。,分析 该文法的句子,if b if b A else A,对应下面两棵不同的语法树：,S,if b S,|,if b S else S,|,A (,其它语句）,第,19,页,/,共,70,页,2.5.,2,文法二义性的消除,所以该文法是二义的。,S,if,b,S,b,S,S,if,A,else,A,S,b,S,S,if,A,else,A,if,b,S,S,if b S,|,if b S else S,|,A,句子,if b if b A else A,第,20,页,/,共,70,页,2.5.,2,文法二义性的消除,消除文法的二义性可采用下面两种方法：,不改变已有规则，仅,加进一非形式的语法规,定：,else,与前面最接近,的不带,else,的,if,相对。,S,if,b,S,b,S,S,if,A,else,A,文法,G,的句子,if b if b A else,只对应唯一的一棵语法树,，,消除了二义。,第,21,页,/,共,70,页,2.5.,2,文法二义性的消除,2.改写文法,G,为,G,S,S,1,|S,2,S,1,if b S,1,else S,1,|A,S,2,if b,S,|,if b S,1,else S,2,G,:,S,if b S,|,if b S else S,|,A (,其它语句）,G:,第,22,页,/,共,70,页,2.5.,2,文法二义性的消除,这是因为通过分析，得知引起二义性的原因是:,if,else,语句的,if,后可是,if,型，因此改写文法时规定:,if,else,之间只能是,if,else,语句或其他语句。,第,23,页,/,共,70,页,2.5.,2,文法二义性的消除,S,S,1,|S,2,S,1,if b S,1,else S,1,|A,S,2,if b,S,|,if b S,1,else S,2,if,b,S,b,if,A,else,A,S,S,2,S,1,S,1,S,1,对改写后的文法，句子,if b if b A else A,只对应唯一的一棵语法树。,第,24,页,/,共,70,页,通常我们只说文法的二义性,而不说语言的二义性,这是因为可能有两个不同的文法,G,和,G,，,而且其中一个是二义性的，另一个是无二义性的,但却有,L(G)=L(G,),即这两个文法所产生的语言是相同的。,2.5.,2,文法二义性的消除,应该指出的是文法的二义性和语言的二义性是两个不同的概念。,第,25,页,/,共,70,页,2.5.,2,文法二义性的消除,将一个语言说成是二义性的，是指对它不存在无二义性的文法，这样的语言称为先天二义性的语言。,例如,L=a,i,b,j,c,k,|i=j,或,j=k,且,i,j,k,1,便是这种语言。,第,26,页,/,共,70,页,2.6 文法和语言的分类,著名的语言学家乔姆斯基(,Chomsky),将文法和语言分为四大类，即,0型、1型、2型、3型,。划分的依据是对文法中的规则施加不同的限制。,第,27,页,/,共,70,页,2.6 文法和语言的分类,0型文法（无限制文法）,若文法,G=(V,N,V,T,P,S),中的每条规则,是这样一种结构：,而且,中至少含一个非终结符,则称,G,是0型文法。,(,V,N,V,T,),+,(,V,N,V,T,),*,0型文法描述的语言是0型语言。,0型文法没有加任何限制条件，又称为,无限制性文法，相应的语言称为无限制,性语言。,0型语言由图灵机识别。,第,28,页,/,共,70,页,2.6 文法和语言的分类,例如，有0型文法,G=(V,N,V,T,P,S),其中：,V,N,=A,B,S,V,T,=0,1,其描述的 0 型语言为,L,0,(GS)=,P:S,0AB,1B,0,B,SA|01,A1,SB1,A0,S0B,第,29,页,/,共,70,页,2.6 文法和语言的分类,1型文法（上下文有关文法）,1型文法也称为上下文有关文法，相应,的语言又称为上下文有关语言。,若文法,G=(V,N,V,T,P,S),中的每一条规则的,形式为,A,其中：,(,V,N,V,T,),*,A,V,N,则称,G,是1型文法。,1型文法描述的语言是1型语言。,1型语言由线性界限自动机识别。,(,V,N,V,T,),+,第,30,页,/,共,70,页,2.6 文法和语言的分类,例如，有1型文法,G=(V,N,V,T,P,S),其中：,V,N,=S,A,B,V,T,=a,b,c,P:S,aSAB|abB,BA,BA,BA,A,A,AA,AB,bA,bb,bB,bc,cB,cc,其描述的1型语言为,L,1,(GS)=a,n,b,n,c,n,|n,1,第,31,页,/,共,70,页,2.6 文法和语言的分类,2型文法（上下文无关文法）,2,型文法又称上下文无关文法，其产生的,语言又称为上下文无关的语言。,若文法,G=(V,N,V,T,P,S),中的每一条规则的,形式为,A,其中：,A,V,N,(,V,N,V,T,),*,则称,G,是2型文法。,2型文法描述的语言是2型语言。,2型语言由下推自动机识别。,第,32,页,/,共,70,页,例如前面描述算术表达式的文法,GE:,E,E+E|E,*,E|(E)|i,2.6 文法和语言的分类,第,33,页,/,共,70,页,其描述的语言为,L,2,(GS)=x|x,a,b,+,且,x,中,a,和,b,的个数相同,例如，有2型文法,G=(V,N,V,T,P,S),其中：,V,N,=S,A,B,V,T,=a,b,P=S,aB|bA,A,a|aS|bAA,B,b|bS|aBB,2.6 文法和语言的分类,第,34,页,/,共,70,页,2.6 文法和语言的分类,3型文法（正规文法）,右线性文法和左线性文法都称为3型文法。,若文法,G=(V,N,V,T,P,S),中的每一条规则的形式,为,A,aB,或,A,a,其中：,A,B,V,N,a,V,T,*,则称,G,是右线性文法。,若文法,G=(V,N,V,T,P,S),中的每一条规则的形式,为,A,Ba,或,A,a,其中：,A,B,V,N,a,V,T,*,则称,G,是左线性文法。,3型文法描述的语言是3型语言。,3型语言由有穷自动机识别。,3型文法也称正规文法。正规文法产生的语言,称为正规语言。,第,35,页,/,共,70,页,例如，用左线性正规文法和右线性正规文法定义标识符,2.6 文法和语言的分类,用,I,代表标识符;,l,代表任意一个字母;,d,代表任意一个数字;则定义标识符的文法为：,左线性文法:,P:I l|Il|Id,右线性文法:,P:I l|lT,Tl|d|lT|dT,第,36,页,/,共,70,页,例如，用左线性正规文法和右线性正规文法定义无符号整数,2.6 文法和语言的分类,用,N,代表无符号整数;,d,代表任意一个数字；则定义的无符号整数文法为：,左线性文法:,P:N Nd|d,右线性文法:,P:N dN|d,第,37,页,/,共,70,页,2.6,文法分类总结,0,型文法：,左部：,V,N,和,V,T,组成,(,可以由多个,V,N,多个,V,T,组成,但至少一个,V,N,),右部：,V,N,和,V,T,组成,(,可以由多个,V,N,多个,V,T,组成,),。,1,型文法：,左部：,V,N,和,V,T,组成,(,可以由多个,V,N,多个,V,T,组成,且至少一个,V,N,),右部：,V,N,和,V,T,组成,(,可以由多个,V,N,多个,V,T,组成,),。,|,左部,|=|,右部,|,第,38,页,/,共,70,页,2.6,文法分类总结,2,型文法：左部：只有一个,V,N,。,右部：,V,N,和,V,T,组成,(,可以由多个,V,N,多个,V,T,组成,),。,3,型文法：左部：只有一个,V,N,。,右部：最多一个,V,N,，且在最左或最右。,第,39,页,/,共,70,页,2.6 文法和语言的分类,由上述四类文法的定义可知,从0型文法到3型文法,是,逐渐增加对规则的限制,条件而得到的，因此每一种正规文法都是上下文无关的文法，每一种上下文无关的文法都是上下文有关的文法，而每一种上下文有关的文法都是0型文法,而由它们所定义的语言类是依次缩小的，,有,L,0,L,1,L,2,L,3,。,第,40,页,/,共,70,页,2.7 有关文法的实用限制和变换,文法是用来描述程序设计语言的，在,实际应用中需要对文法加一些限制条件。,1.文法中不能含有形如,A A,的规则。这种规则我们称之为有害规则。,对文法的实用限制有以下两点：,第,41,页,/,共,70,页,2.7 有关文法的实用限制和变换,2.文法中不能有多余规则。所谓多余规则是指文法中出现以下两种规则：,(1)某条规则,A,的左部符号,A,不在所属文法的任何其他规则右部出现，即在推导文法的所有句子中始终都不可能用到的规则。,(2)对文法中的某个非终结符,A，,无法从它推出任何终结符号串来。,第,42,页,/,共,70,页,2.7 有关文法的实用限制和变换,例如 设有文法,GS:,P:S,Bd,A,Ad|d,B,Cd|Ae,C,Ce,D,e,删除多余规则后的文法变换为:,P:S,Bd,A,Ad|d,B,Ae,第,43,页,/,共,70,页,2.7 有关文法的实用限制和变换,若程序设计语言的文法含有多余规则，其中必定有错误存在，因此检查文法中是否含有多余规则对我们来说是很重要的。,第,44,页,/,共,70,页,作业,P,第,45,页,/,共,70,页,本章重点介绍了语言的语法结构的形式描,述、语法树以及文法的二义性,主要内容有：,1.设计一个文法定义一个已知的语言,(1)文法是一个四元组,G=(V,N,V,T,P,S)，,文法四大要素中，关键是一组规则,它定义（或描述）了一个语言的结构。,从文法定义可知,文法对于程序设计者来,说，文法给出了语言的精确定义和描述。,本章小结,本小结花时,45,分钟,第,46,页,/,共,70,页,(2)分析已知语言句子的结构特征,设计,出相应的一组规则，但不唯一。,(4)若语言是无穷集合,设计该语言的文,法一定是递归的。,本章小结,(3)设计的文法必须能定义已知的语言,不能超出或缩小所定义语言的范围。,第,47,页,/,共,70,页,分析 根据语言句子的结构特征，设计出相 应规则,例1.给出语言,L,2,=a,n,b,m,|mn1,的文法,P,2,:SAB,L,2,=ab,abb,abbb,aabb,aabbb,aabbbb,aaabbb,aabbbb，,AaAb|ab,BbB|,本章小结,第,48,页,/,共,70,页,分析 根据语言句子的结构特征，设计出相 应规则,例2.给出语言,L,1,=a,2n+1,|n0,的文法,P,1,:,AaB|a,P,1,：AaAa|a,或,L,1,=a,aaa,aaaaa,aaaaaaa,aaaaaaaaa，,Baa|aBa,本章小结,第,49,页,/,共,70,页,本章小结,分析 根据语言句子的结构特征，设计出相应规则,例3.,给出语言,L,3,=a,n,b,m,c,k,|n,m,k0,的文法,P,3,:AaA|bB|cC|,P,3,:AaA|B,或,L,3,=,a,aa,aaa,b,bb,bbb,c,cc,ccc,ab,abb,bc,bcc，,CcC|,BbB|cC|,CcC|,BbB|C,第,50,页,/,共,70,页,本章小结,L,4,=0,2,4,6,8,10,12,14,16,18,20,22,24,26,例4,.,写一个,文法,使其语言是正偶数的集合,每个偶数不以0开头。,P,4,:NE|AE,N0|2|4|6|8|BN,或,分析 不以0开头的偶数集合中串的结构特征:,AD|AD,E0|2|4|6|8,D1|2|3|9,D,0|1|2|3|9,B1|2|3|9|B0,P,4,:,第,51,页,/,共,70,页,本章小结,A 0A1,|,P,:S 1S0|0A1|,例5.给出语言,L=1,n,0,m,1,m,0,n,|n,m0,的,文法。,分析 根据语言句子的结构特征,设计,出相应规则,L=,01,0011,10,1100,1010,100110,110100,11001100,第,52,页,/,共,70,页,本章小结,P,:S a|0S0|,1S1,例6.,给出语言,L=WaW,t,|W,0|1,*,W,t,表示,W,的逆的文法,。,分析 根据语言句子的结构特征，设计,出相应规则,L=a,0a0,1a1,01a10,10a01,00a00,11a11,101a101,110a011,100a001,W=,0,1,01,10,00,11,101,110,100,111,第,53,页,/,共,70,页,本章小结,2.已知一个文法，确定该文法所定义的,语言。,(2)给定一个文法，可根据语言和推导定,义推导出文法的句子，从而确定出该文法,所定义的语言。,(1)文法所定义的语言,L(GS)=x|S,x,且,x,V,T,*,*,第,54,页,/,共,70,页,本章小结,自然语言描述。,例如,L=x|x,a,b,+,且,x,中,a,b,个数相同,式子描述。例如,L=a,2n,bb|n0。,正规式描述。,(3)语言可用,第,55,页,/,共,70,页,本章小结,例1 文法,GA=(A,a,b,AbA|a,A),所生成的语言是什么？,分析 ,A,bA,bbA,bbbA,b,n,A,b,n,a,L(GA)=b,n,a|n0,第,56,页,/,共,70,页,本章小结,例2 文法,GN,为:,N ND|D,D 0|1|2|3|4|5|6|7|8|9,(1)GN,所生成的语言是什么？,(2),给出句子0127的最左,、,最右推导,。,第,57,页,/,共,70,页,本章小结,L(GN)=,|0,1,2,9,+,=,|,为可带前导0的正整数,=,|,为数字串,最左推导:,N,ND,N7,ND7,N27,ND27,N127,D127,0127,最右推导:,N,ND,NDD,NDDD,DDDD,0DDD,01DD,012D,0127,N ND|D,D 0|1|2|3|4|5|6|7|8|9,第,58,页,/,共,70,页,本章小结,例3.已知文法,GS=(A,B,a,b,c,d,P,S),其中,P,为:,分析,S,AB,aAbB,a,2,Ab,2,B,a,n-1,Ab,n-1,B,a,n,b,n,B,a,n,b,n,cBd,a,n,b,n,c,2,Bd,2,a,n,b,n,c,m-1,Bd,m-1,a,n,b,n,c,m,d,m,L(GS)=a,n,b,n,c,m,d,m,|n,m1,该文法,所生成的语言是什么？,A aAb|ab,B cBd|cd,S AB,第,59,页,/,共,70,页,本章小结,3.求句型的短语、直接短语和句柄,(1)短语、直接短语和句柄是对某句,型而言的。,(2)短语总是句型的某个子串，它对应,子树未端结点形成的符号串。,(3)直接短语是某条规则右部，它对应,简单子树未端结点形成的符号串。,(4)最左边的直接短语是句柄。,第,60,页,/,共,70,页,本章小结,例1 已知文法,GE：,证明,E+T,*,F,是它的一个句型,指出这个句型的短语直接短语和句柄。,E,E+T,E+T,*,F,短语:,E+T,*,F,、,T,*,F,E+T,*,F,是它的一个句型,。,画出该句型的语法树:,句柄:,T,*,F,直接短语:,T,*,F,E,T,F,T,+,E,*,EE+T|E,-,T|T,TT,*,F|T/F|T,T(E)|i,第,61,页,/,共,70,页,本章小结,例2 已知文法,GS：,试找出符号串(,a),和(,A(SaA)(b),的短语,直接短语和句柄(如果有的话)。,S(AS)|(b),A(SaA)|(a),符号串(,a),不是文法的句型，因此,它没有短语直接短语和句柄。,分析 ,S,(AS),(a)S),(a),/,第,62,页,/,共,70,页,本章小结,S,(AS),(A(AS),(A(A(b),(A(SaA)(b),符号串(,A(SaA)(b),是文法的句型，画出该句型的语法树如下图：,S(AS)|(b),A(SaA)|(a),第,63,页,/,共,70,页,本章小结,从句型的语法树求,短语:,(A(SaA)(b),(SaA)(b),(SaA),(b),直接短语：(,SaA)、(b),句柄：(,SaA),S,A,(,S,),A,(,S,),(,S,a,A,),),b,(,S(AS)|(b),A(SaA)|(a),对于句型(,A(SaA)(b),第,64,页,/,共,70,页,本章小结,4文法二义性的判断,一个文法存在某个句子对应两棵不同的语法树或对应两个不同的最左（最右）推导，则该文法是二义性的。,第,65,页,/,共,70,页,本章小结,例1 设有文法,GS:SiSeS|iS|i,试证明文法,GS,有二义性。,分析 因为对文法的句子,iiiei,有如下两,棵不同的语法树与之对应，所以该文法,是二义的,第,66,页,/,共,70,页,本章小结,SiSeS|iS|i,句子,iiiei,对应下面两颗语法树：,S,S,i,e,S,i,S,i,i,S,i,S,i,S,i,e,S,i,第,67,页,/,共,70,页,本章小结,NSE|E,SSD|D,E0|2|4|6|8|10,D0|1|2|3|4|5|6|7|8|9,1.试证明文法,GN,有二义性。,2.此文法所描述的语言是什么？,3.试写出另一文法,G,使,L(G,)=L(G),且,G,是无二义性的。,例2 设有文法,GN:,第,68,页,/,共,70,页,本章小结,分析 因为对文法的句子10有两棵不同的语法树与之对应，所以该文法是二义的,N,E,S,0,D,1,N,E,0,1,NSE|E,SSD|D,E0|2|4|6|8|10,D0|1|2|3|4|5|6|7|8|9,第,69,页,/,共,70,页,本章小结,该文法所描述的语言是所有无符号偶数,的集合(可以0开头)。,改写后的文法,G,S,为:,NSE|E,SSD|D,E0|2|4|6|8,D0|1|2|3|4|5|6|7|8|9,NSE|E,SSD|D,E0|2|4|6|8|10,D0|1|2|3|4|5|6|7|8|9,第,70,页,/,共,70,页,