编译原理my第二章2010.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二章 前后文无关文法和语言,编译工作首先需要解决：,如何描述或定义一种程序设计语言,如何识别或分析这种程序设计语言,上世纪,50,年代，,N.Chomsky,对语言描述提出探讨，建立了四类,文法的数学模型,。,形式描述,：用一组数学符号和规则来描述语言的方式。,形式语言,：形式描述所用的数学符号和规则。,2.1,文法及语言的表示,什么是语言？,某字母表上符号串的集合。,语言的表示方法或定义方法：,1.,枚举法,2.,规则法,3.,自动机（算法,/,过程）,2.2,文法和语言的定义,2.2.1,基本概念和术语,1,）,字母表：,由若干元素组成的有限非空集合，其中每一元,素称为符号。,2,）,符号串：,用字母表中的符号组成的任何有限序列。,符号串的长度：,符号串中所含有符号的个数。,空符号串,：,|=0.,3,）,符号串的前缀、后缀与子串,:,（真前,(,后,),缀,:,）,4,）,符号串的连接和方幂,:,（,是连接操作的单位元素）,5,）,符号串集合的和与积,:,A+B=,w|wA,或,wB,AB=,xy|xA,且,yB,6,）,符号串集合的方幂和闭包,:,（正闭包、自反传递闭包）,2.2.2,文法和语言的形式定义,产生语言就是制定出有限个规则（文法），借助于它们，就能产生出此语言的全部句子。,产生语言的规则中的一系列需定义的语法范畴的名字称为,非终结符号,，其集合记为,v,N,规则中不需进一步定义的基本符号称为,终结符号,，其集合记为,v,T,非终结符中最终需要定义的那个为推导句子开始的语法范畴，被称为,开始符号或识别符号,，记作,S,每一规则是用,:=,或,连接起来的有序对，亦称,产生式,，用,P,表示,:=,:=the,:=,:=,:=monkey,:=banana,:=ate,:=has,:=the,:=a,the monkey ate a banana,定义,2.1,前后文无关文法,定义,2.2,直接推导,定义,2.3,推导,定义,2.4,句型和句子,定义,2.5,语言,定义,2.6,直接递归、递归、递归文法,定义,2.7,文法等价,L(G,1,)=L(G,2,),引理,2.1,2.3,句型的分析,句型的分析,是指构造一种算法，用以判断所给符号串是否为某一文法的句型,(,或句子,),。,分,两类方法,：自顶向下分析；自底向上分析,2.3.1,规范推导和规范归约,最左,(,右,),推导,：对一个推导序列中的每一直接推导，被替换的总是当前符号串中的最左,(,右,),非终结符号。,左,(,右,),句型,：能由最左,(,右,),推导推出的句型。,把最右推导称为,规范推导,，右句型为,规范句型,。,当有非终结符由多个候选式定义时，将成为带,回溯,的自顶向下分析。,问题：如何选用侯选式？,最右,(,左,),推导的,逆过程,是最左,(,右,),归约。最左归约为,规范归约,。,问题：对于规范归约的每一步，如何确定应被归约的最左子串？,2.3.2,语法树和二义性,引入,语法树,（推导树）更直观、更清晰地描述一句型或句子的语法结构,.,树的性质,：,子树,：由某结点连同其所有后继组成的部分。,直接子树,：只有直接后继，而无更远的后继的子树（树高为,1,）。,文法,G=(V,N,V,T,P,S),的,推导树满足以下条件,:,（,1,）每一结点均有一标记，此标记为,V,N,V,T,中的一个符号。,（,2,）树的根结点标记为文法的开始符号,S,。,（,3,）若一结点至少有一个直接后继，则此结点上的标记为,V,N,中的一个符号。,（,4,）若一个以,A,为标记的结点有,K,个直接后继，且按从左至右的顺序，标记,为,x,1,、,x,2,、,、,x,k,，则,A,x,1,x,2,x,k,必是,G,的一个产生式。,语法树与推导序列间为,1,对多的关系,，但一语法树只对应于唯一的最左推导和最右推导。,L(G),的某个句子,(,句型,),可能对应不只一个最左推导和最右推导，称这样的文法,G,为,二义性文法,。,如果一文法所产生的每一个句子都仅有一棵语法树，则称此文法为,无二义性,的。,任给的前后文无关文法是否具有二义性是不可判定的。,但对某些具体文法可判断其二义性或无二义性。,如,LL(1),等文法。,另存在一些检查文法二义性的充分条件。,如含有既是左递归又是右递归非终结符的文法必是二义性文法。,先天二义性语言,：用于定义语言的一切文法都是二义性的。,2.3.3,短语和句柄,对于句型,的一棵语法树，如果它的一棵子树的根结点标记为,A,，若此子树的末端结点标记自左至右排列起来所形成的符号串为,，则,是句型,相对于,A,的一个,短语,；如果此子树为一棵直接子树，则,是句型,相对于产生式,A,的,直接短语,。,定义,2.8,短语和直接短语的形式定义,定义,2.9,句柄的定义,对于无二义性文法，可保证句柄的唯一性。,2.4,文法的化简和改造,2.4.1,无用符号和无用产生式的删除,有用符号的条件,：文法,G,中的有用符号,XV,至少出现在一个句子的推导过程中。,无用产生式,：左部或右部含有无用符号的产生式。,（应消去不能推出结论符号的产生式）,已化简的文法,：不含有形如,AA,和不含有无用符号及无用产生式的文法。（注：对形如,AA,的产生式，无论,A,是否有用，都应删去。）,例题：化简文法,G=(S,，,U,，,V,，,W,，,a,，,b,，,c,，,P,，,S),其中，,P,由如下产生式组成,SaS,SW SU,Ua,VbV,Vac,WaW,答案：与,G,等价但不含无用符号及无用产生式的文法为：,G1=(S,，,U,，,a,，,P1,，,S),其中,P1,由下列产生式组成：,SaS,SU,Ua,2.4.2,产生式的消除,产生式是指右部为一空符号串,的产生式。,A,（,AV,N,）,2.4.3,单产生式的消除,单产生式是指右部只含一个非终结符的产生式。,AB,（,A,BV,N,）,2.5,文法和语言的,Chomsky,分类,1.,文法的每个产生式,中：若,+,，,*,则称,G,为,0,型文法或短语结构文法,(PSG),。,2.,若,0,型文法,G,中所有产生式具有,1,A,2,1,2,的形式，其中,1,，,2,V*,，,AV,N,，,V,+,。,另一等价定义是：,一,0,型文法的每一产生式,满足,|,|,|,，,，,V,+,（允许,S,产生式作为唯一的例外包含在,1,型文法中）。,则称,G,为,1,型文法或前后文有关文法,(CSG),。,3.,若,1,型文法,G,中的每一产生式,A,满足,AV,N,，,V,+,形式，,则称,G,为,2,型文法或前后文无关文法,(CFG).,4.,若,2,型文法,G,中仅含有形如,AaB,或,Aa,的产生式，其中,A,B V,N,，,aV,T,，则称,G,为右线性文法。若,G,中仅含有形如,ABa,或,Aa,的,产生式，则称,G,为左线性文法。二者统称为,3,型文法或正规文法。,5.,四类基本文法的关系：,作业,P38,习题,2-1,2-2(1)(3)(5),2-3(1)(3)(5),2-6,2-7(1)(2),2-10,2-11(1)(2),2-13(1)(3),