有限自动机理论CH2.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 形式语言简介,形式语言和自动机理论中的,语言,是一个广泛的概念。,一个字母表上的,语言,就是该,字母表,的某些,字符串,的,集合,。,语言中的字符串称为该语言的,句子,语言的的定义可以从两个方面进行：,）从,产生,语言的角度；,）从,接收,(,或,识别,),语言的角度。,产生一个语言，目的就是根据语言中的,基本句子,和句子的,形成规则,，得到,(,产生,),该语言所包含的,所有句子,。,这是,形式语言,所研究的问题。,接收一个语言，目的就是使用某种,自动机模型,来,接收,句子，该模型所接收的所有句子，也形成一个语言。,这是,自动机,所研究的问题。,本章介绍,形式语言,的基本内容。,语言的形式定义,设,是一个,字母表,，,L,*,L,称为,字母表上,的一个,语言,wL,w,称为语言,L,的一个,句子,。,2.1,例子语言,括号匹配串的语言。,该语言是指所有的左括号和右括号相匹配的串的集合；,(),，,(),，,()(),等等都是该语言的句子,)(,，,(),等等不是该语言的句子。,如何,产生,这个语言呢？,即如何,产生,该语言所有句子呢？,实际上，就是需要给出语言中句子的,构造（形成）规则,。,递归定义,提供了语言的良好的定义方式，使得语言中的句子的构造规律较明显。,可以使用多种方法,描述,构造规则。,自然语言,的描述方式，采用如下的,递归规则：,(),是该语言的最基本的句子；,若,S,是句子,则,(S),是句子；,若,S,是句子,则,SS,是句子；,这些规则称为,形成规则,，根据这些规则，可以,(1),产生该语言的任意的句子；,(2),判断某个,串,是否是该语言的句子。,例如,可以产生句子,（）,而推断串,（）,不是句子。,规则,(,的个数,),是有限的，但可以产生无限个句子和长度无限的句子；,因为规则是,递归,的。,BNF,的描述方式,巴科斯和诺尔采用的,巴科斯,-,诺尔范式（,BNF,-Backus-Naur Form,）,描述规则,：,:=,(),:=,(,),:=,使用尖括号“,”,包括起来的部分，作为一个整体来看待，表示某个语法成分,需要使用字母表中的字母来定义其构成,符号“,:=,”,是,BNF,本身的符号（元符号），代表“,定义为,”或“,是,”。,符号“,(,”,和“,),”,是字母表的元素。,Chomsky,采用的符号化,(,形式化,),的描述方式，运用如下的规则（这些规则被称为,产生式,）：,S(),S(S),SSS,“,”代表“定义为”或者“是”，,它的左边和右边分别称为该产生式的,左边,和,右边,根据,产生式,可以生成任意句子；,可以判断一个串是否为句子,(,语法分析,),产生句子的过程,从,S,开始，利用产生式的右边,代替,产生式的左边称之为,推导过程,）,进行多次推导，可以得到括号匹配的的句子。,例,:,句子,(),(,()(),),的推导过程,S,=,S,S,=(,S,)S,=(),S,=()(,S,),=()(,S,S),=()(),S,),=()()(),产生式的个数是有限的，规则是递归的，因而所有的小括号匹配的串，都可以由产生式产生；,它们组成的集合就称为一个语言。,S,称为,非终结符,，在推导过程中，可以被代替的符号。,(,和,),称为,终结符,，在推导过程中，不可以被代替的符号。,是产生式系统的,元符号,，不属于非终结符，也不属于非终结符。,例,2-1,：由偶数个,0,组成的串的语言。,规则的自然语言描述方式00,是该语言的基本的句子；,若,S,是句子,则,00S,是句子。,形式化的描述方式：,S00,S00S,问题：,将产生式,SSS,换成,S0S0,或,SS00,或,SSS,是否还产生相同的语言？,结论：,一个语言，可以使用不同的产生式组合来产生。,考虑,由奇数个,1,组成串的语言（产生规则）,例,2-2,高级程序设计语言中的算术表达式,(,的语言,),的产生。,自然语言的描述方式,单个变量是最基本的,句子,；,若,E,是一个,句子,，则,E,A,E,是一个,句子,（其中,A,代表运算符,+,、,-,、*、,/,）,若,E,是一个,句子,，则,(,E),是,句子,；,形式语言的描述方式,E i,（,i,代表单个变量）,E,EAE,E(E),A+A-,A*A/,思考：,字母表为？,若以,A,开始推导，则产生？,其中：,A+,，,A-,，,A*,，,A/,四个产生式的左边是相同的符号，可以合并为,A+|-|*|/,+,、,-,、*、,/,称为,A,的,侯选式,。,E i,EEAE,E(E),也可以记为：,E,i|EAE|(E,),注意：,这组产生式,没有表示出运算符的,优先级,。,表示出运算符的优先级的产生式：,E,E+T|E-T|T,T,T*F|T/F|F,F,(E)|i,其中：,E,代表表达式，,T,代表项，,F,代表因子,(E),代表的是带小括号的表达式。,表示：先算因子，再/,，最后,+,、,-,。,如果使用,%,代表模运算,(,即取余数运算,),、使用,代表指数运算，则有,EE+T|E-T|T,TT*F|T/F|T%F|A,AFA|F,F(E)|i,注意,需要考虑,运算的,结合性,：,是右结合的。,例,2-3,标识符,(,以字母开头的字母、数字的串,),的产生,(,仅考虑小写字母,),。,从标识符的形成角度考虑,I,L,I,IL,I,ID,La|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t,u|v|w|x|y|z,D0|1|2|3|4|5|6|7|8|9,思考：,上例是从标识符的,形成角度,思考问题。,从标识符的,定义,角度考虑，则？,注意,D0|1|2|3|4|5|6|7|8|9,不能简写为,D0,|,|,9,将,I,的定义加入到表达式中：,EE+T|E-T|T,TT*F|T/F|F,F(E)|,I,I,L|IL|ID,L,D,思考,:,其他类型的表达式（如关系表达式等）的定义：,、,、,=,、,、,=,标识符,(,以,下划线,或字母开头的字母、下划线和数字的串,),的产生。,例,2-4,C,语言中简单变量的说明语句的定义。,C,语言中的说明语句形式为：,TYPE,变量名表；,TYPE,变量名表；,TYPE,变量名表；,产生式为：,S,SS,|P,PT V,；,Tint|char|float,V,V,V,|I,IL|IL|ID,L,D,思考,PASCAL,语言的简单变量的说明语句的形成。,VAR,变量名表,:TYPE;,变量名表,:TYPE;,变量名表,:TYPE;,2.2,文法和语言的关系,语言的定义,文法的定义,文法与语言的关系,再次强调：,语言就是字母表上的字符串组成的一个集合。,语言中的字符串称为,句子,。,文法的作用就是产生一个语言。,有穷语言的表示较容易。,即使语言中的句子的组成没有什么规律，也可以使用,枚举,的方式列出语言中的所有句子。,对于,无穷语言,，需要使用有穷描述的方式表达。,需要从语言的句子的一般构成规律去考虑问题。,从语言的,有穷描述,来表达语言的方法对,大多数语言,是有效的。,在（使用计算机）判断一个字符串是否是某个语言的句子时,(,语法分析,),从句子和语言的,结构特征,上着手是非常重要的。,对于语言，可以在字母表上，按照一定的构成规则，根据语言的结构特点，可以定义一个产生该语言的,文法,。,使用,文法,作为相应语言的有穷描述，不仅可以描述出语言的,结构特征,，而且可以,产生,这个语言的,所有句子,。,定义,2-1,短语结构文法,(,文法,),的定义,文法,G,是一个四元式，,G=(,，,V,，,S,，,P),是一个有限字符的集合,(,字母表,),，它的元素称为字母或者终结符；,V,是一个有限字符的集合,-,非终结符集合，它的元素称为变量或者非终结符；,短语结构文法,(,文法,),的定义,S,V,，,称为文法的开始符号；,P,是有序偶对,(,，,),的集合，其中,是集合,(UV),上的字符串，但至少包含一个非终结符；,是集合,(UV),*,的元素。,一般，将有序偶对,(,，,),记为,，,称为产生式；,如果有,，,称之为空串产生式或者,产生式。,如果,有,AB,，,称之为单产生式。,一个产生式的左边可能不只一个符号；,第一个产生式的左边只能有一个符号，就是,开始符号,S,。,文法,的作用就是产生一个,语言,。,约定：如果没有特别说明,则,第一个产生式左边的符号，就是开始符号，,可以不为,S,；,大写的英文字母代表非终结符；,小写的英文字母,a,，b,，,c,，,d,，,e,和数字代表终结符；,小写的英文字母,u,，,v,，,w,，,x,，,y,，,z,代表 终结符串；,小写的希腊字母,，,代表非终结符和终结符串；,推导（派生）的定义,2-2,文法,G,，,和,是集合,(UV),上的串,=,p,v,r,，,=,p,u,r(p,和,r,可能同时为,),而,vu,是文法,G,的一个产生式,则称,可以直接推导出,，,记为,=,，既,p,v,r,=,p,u,r,。,推导的实质,产生式的,右边,替换,产生式的,左边,非终结符,代表在推导的过程中可以被替代的符号，,终结符,代表在推导的过程中不可以被替代的符号。,推导,的,逆,过程称为,归约,。,与,pvr,=,pur,对应，称串,pur,可以直接归约成串,pvr,记为,p,v,r,+,z,表示,y,可以经过,多步,推导出,z,，即,存在串的序列,1,，,2,，,3,，,，,n,；,有,y=,1,，,z=,n,，,且,i,=,i+1,；对所有,ni1,。,任意步推导,(,包括,0,步,),y,=*,z,表示,y,可以经过,任意步,推导出,z,，即,y=z,；或者,y=,+,z,。,思考：,对于任意文法,G,：,S,=,*,S,S,=,+,S,一定都成立吗,？,最左推导和最右推导,如果在推导的过程中，,每一步,都是将推导产生的串的,最左边,的非终结符代替掉,-,最左推导,如果每一步都是将推导产生的串的最右边的非终结符代替掉,-,最右推导,(,规范推导,),，,当然，还有其它方式的推导过程（例如混合）,而,最左推导,和,最右推导,是比较常用的推导方式。,句型和句子,对于文法,G,，,如果,S=,*,，,则称,是文法的一个,句型,，,若,*,称为,句子,。,定义,2-3,语言的定义,给定文法,G,，,有开始符号,S,，,则把,S,可以推导出所有句子的集合，称为由文法产生的语言，记为,L(G),，,即,L(G)=|S,=,*,，,且,*,例,文法,G=(,(,),S,S,S(),S(S),SSS,),产生语言,L(G)=,w|w,是括号匹配的串,注意,:,文法,G,产生语言,L,，必须：,G,推导产生的所有,句子,都在,L,中,L,的任意一个,句子,都可以由,G,产生,对于文法,G=(,，,V,，,S,，,P),约定：,第一个产生式左边的符号，就是开始符号（,可以不是,S,）,；,大写的英文字母代表非终结符,。,对于文法（,G,），只需给出该文法的所有产生式即可。,产生括号匹配语言的文法可以写成,S,(,),S(S),SSS,还可以再简单写成,S(),|,(S),|,SS,文法和语言的,3,类问题,已知,文法,得到该文法产生的,语言,已知,语言,构造产生该语言的,某个,文法,判断,一个语言是否由某一个文法产生,关系,1,：,文法,SaSa|bSb|c|,产生的语言是什么S,能够产生的所有句子，需要考虑,3,个产生式,所有可能使用情况,注意,对称性,关系,2,：,构造产生语言,L,的文法。,L=,ww,T,|wa,b,c,+,其中：,w,T,是,w,的逆（反序）,思考：,产生下列语言的文法：,L,1,=,a,n,b,n,|n,0,L,2,=a,n,b,n,|n,0,关系,3,：,文法,S0B|1A,A0|0S|1AA,B1|1S|0BB,是否产生的语言,L,：,L=|,0,1,+,，,且,中有,相同多,的,0,和,1,？,注意：,一个语言,可以,由多个不同的文法产生。,一个文法,只能,产生一个语言。,例,2-5,G1,：,S0|1|00|11,G2,：,SA|B|AA|BB,A0,B1,L(G1)=L(G2)=0,1,00,11,文法等价,如果文法,G1,和文法,G2,产生同一个语言，则称文法,G1,和,G2,是,等价,的文法。,L(G1)=L(G2),注意区别：,文法,G1,和,G2,等价,文法,G1,和,G2,相同,。,2.3Chomsky,对文法的分类,Chomsky,对文法进行了分类；,对语言的分类，是根据产生语言的文法的分类进行的,0,型文法,对于一般的短语结构文法,(,PSG,),G=(,，,V,，,S,，,P),G,称为,0,型文法，对应的,L(G),称为,0,型语言或者短语结构语言,(,PSL,),、,递归可枚举集,。,1,型文法,如果对于任意,P,，均有,|,|,|,成立，则称,G,为,1,型文法，或,上下文相关文法,(,CSG,),。,对应的,L(G),称为,1,型语言或者上下文相关语言,(,CSL,),。,1,型文法,1,型文法产生式的标准形式为：,y,A,zy,z,其中：,AV,；,y,z(V,),*,，,(V,),+,；,1,型文法,可以证明，任意的,1,型文法，都可以改造为,1,型文法的标准形式。,2,型文法,如果对于任意,P,，均有,|,|,|,且,V,成立，则称,G,为,2,型文法，或,上下文无关文法,(,CFG,),对应的,L(G),称为,2,型语言或者上下文无关语言,(,CFL,),。,3,型文法如果对于任意,P,，具有形式,A,w,，,A,wB,其中，,A,，,BV,，,w,+,则称,G,为,3,型文法，或右线性文法,RLG,，也可称为,正则文法,RG,。,对应的,L(G),称为,3,型语言或 右线性语言,RLL,或 正则语言,RL,。,四类文法和对应的四类,语言,之间是,真包含,关系。,思考,如果文法,G,有,产生式，则,G,是,型文法,?,文法分类判断方法：,文法,G=(,，,V,，,S,，,P),，则,1)G,是短语结构文法；,2),如果文法,G,的所有产生式的左边,长度,小于等于右边长度部分，那么,G,是,上下文相关文法,；,3),如果上下文相关文法,G,的所有产生式的左边都是,一个非终结符,，那么,G,是,上下文无关文法,；,4),如果,上下文无关文法,G,的所有产生式的右边最多只有一个非终结符,且该非终结符号只能出现在最右边，那么,G,是,正则文法,。,文法,G:,S01|101S,是,RG,，,CFG,，,CSG,和,PSG,文法,G,：,SAaS|AS,Aa|b|c|d,是,CFG,，,CSG,和,PSG,，但不是,RG,。,文法,G,SaB,aBab,是,CSG,和,PSG,，但不是,CFG,和,RG,。,文法,G,S,aB,aBab,aBa,是,PSG,，但不是,CFG,、,RG,和,CSG,。,形如,的产生式称为空产生式，也可称为,产生式,。,CSG,、,CFG,和,RG,，都不能含有空产生式，所以任何,CSL,、,CFL,和,RL,中都不包含,(,空句子,),。,如果允许在,CSG,、,CFG,和,RG,中含有,空产生式,，,也就允许,CSL,、,CFL,和,RL,中包含,空句子,。,一般地，如果语言,L,没有空句子，则,文法中增加产生式,S,就可以产生空句子。,文法,扩充分类,：,设文法,G=(,，,V,，,S,，,P),如果,S,不出现在任何产生式的右部,，则,(1),若,G,是,CSG,G,=(,，,V,，,S,，,P,S,),仍然,为,CSG,；,L(G,),是,CSL,。,(1),若,G,是,CFG,G,=(,，,V,，,SP,S,),仍然,为,CFG,；,L(G,),是,CFL,。,(1),若,G,是,RG,G,=(,，,V,，,S,，,P,S,),仍然,为,RG,；,L(G,),是,RL,。,思考,为什么要有条件,S,不出现在任何产生式的右部？,设正则文法,RG,：,S,ab|aS,，则,L(G)=,a,+,b,G,：,S,ab|aS|,L(G)=,a,+,b,a,+,增加,了空句子,，但,多,产生句子,a,+,定理,2-1,文法,G=(,，,V,，,S,，,P,),，,存在与,G,同类型的文法,G,=(,V,S,P,),，使得,L(G)=L(G,),且,S,不出现,在,G,的任何产生式,右部,证明：,先根据,G,构造,满足条件的,G,，然后证明两者,等价,。,构造,G,=(,，,VS,S,P,),其中,P,=P,S,|S,P,G,与,G,有相同的类型。,G,与,G,等价,即证明,L(G)=L(G,),需要证明,L(G),L(G,),L(G,),L(G),特殊情况,如果,S,不出现在,P,中任何产生式的右边，则,G=G,思考,文法的,S,不出现在产生式的右部,那么，,S,的,作用,是什么？,下列命题成立,有语言,L,，设置,L,=,L,(1),若,L,是,CSL,，则,L,仍然是,CSL,。,(2),若,L,是,CFL,，则,L,仍然是,CFL,。,(3),若,L,是,RL,，则,L,仍然是RL,。,证明：,证明第,(1),个命题，,(2)(3),同理可证。,证明,设,L,是,CSL,，则存在一个,CSG=(,，,V,，,S,，,P),使得,L(G)=L,。,设,S,不出现在,G,的产生式右部。,构造,G,=(,V,S,P,S,),G,也是,CSG,。,S,不出现在,G,中产生式的右部,增加的,S,，,不可能出现在非空句子的推导中，则,L(G,)=,L(G),L(G,),是,CSL,。,结论,增加空句子不影响语言的类型。,同理,删除空句子也不影响语言的类型。,下列命题成立,有语言,L,，,L,=,L-,(1),若,L,是,CSL,，则,L,仍然是,CSL,。,(2),若,L,是CFL,，则,L,仍然是,CFL,。,(3),若,L,是,RL,，则,L,仍然是,RL,。,证明：,证明第,(1),个命题，,(2)(3),同理可证。,证明,设,L,是,CSL,，则存在一个,CSG=(,，,V,，,S,，,P),使得,L(G)=L,。,如果,L,L-=L,L-,是,CSL,。,如果,L,设,S,不出现在,G,的产生式的右部。,构造,=(,V,S,P,-,S,),，,G,也是,CSG,。,S,不出现在,G,产生式的右部,去掉,S,则,不影响,任何非空,句子的推导,，,L(G,)=L(G)-,。,L(G,),是,CSL,。,除了生成空句子,外，空产生式可以不用于其他句子的推导中空句子,在一个语言中的存在并不影响该语言的有穷描述。,如果,允许,CSG,CFG,RG,包含一般的,-,产生式,1),可能,对问题的处理提供方便。,2),编译理论中,(,无回溯的,),自上而下分析法,需要,一般的,-,产生式。,L(G)=w|w0,1,+,且,w,以,0,开始,G,可以为：,S0|0A,A0|1|0A|1A,其中：,A,产生,0,1,+,或,S,？,A|0A|1A,其中：,A,产生,0,1,*,2.4,文法产生语言,例,文法,S,0,S,S0,产生语言,L=,0,n,|n0,分析,如果开始使用第,2,个产生式,S0,，则,S=0,，,就不能再往下进行推导了。,产生,基本句子0,；,若使用产生式,S0S,，,n-1,次后，则,S=0S=00S=000S=,+,0,n-1,S,使用,S0,，则,S=,+,0,n,这对于任何,n1,都是成立的；,总之，该文法产生语言,L=,0,n,|n,0,。,定义,2-7,递归文法,一个,上下文无关文法,G,，,AV,如果,A,=,+,A,，,则该文法称为,递归,的文法；,(A:,递归,非终结符,),递归分为,直接,和,间接,递归。,若,A,=,A,则称为,直接递归,的非终结符。,直接递归,可以从,产生式,判断。,间接递归,需要根据,推导,过程才能进行判断。,思考,是否可以将间接递归,转换,为直接递归？,如何,进行,转换？,基本思路：,将推导过程直接反映在产生式中,方法：,代入法,一个,上下文无关,文法的产生式的个数总是有限的。,如果该文法是,递归文法,，则该文法就能够产生一个,无穷语言,。,若一个,上下文无关,文法,不是递归,的文法，则,该文法产生,有穷语言,。,注意,特殊形式的产生式,AA,是递归的，可以反复利用任意多次，,但对于无穷语言的产生，没有任何作用,定义,2-8,空串产生式的定义,形如,A,的产生式，称为,上下文无关,文法的空串产生式，或,产生式；,空串产生式的作用就是在推导的过程中，对于某个句型，省略掉能够产生,的非终结符号。,若某个,上下文无关,文法,G,有,S,，则,该,L(G),一定包含空句子,例文法,S0S,S,该文法产生语言,L=0,n,|n0,。,思考：该文法是？型文法,分析,如果开始使用第,2,个产生式,S,，则,S=,，,就不能再往下进行推导了，,则产生空句子,；,如果开始使用产生式,S0S,，,n,次后，,S=0S=00S=000S=,+,0,n,S,最后，使用,S,，则,S=,+,0,n,这对于任何,n1,都是成立的；,总之，该文法产生语言,L=0,n,|n0,例,文法,SaSb,Sab,产生语言,L=,a,n,b,n,|n,0,例,文法,SaS,SbS,S,产生语言,L=a,，,b*,例,字母表,a,，,b,上所有对称的,非空串,组成的语言,(,没有中心点,),构造文法产生该语言,分析,aa,和,bb,是最基本的句子。,如果,S,是句子，则,aSa,和,bSb,是句子,得到文法：,Saa,Sbb,SaSa,SbSb,思考,(1),文法,SaSa,SbSb,Sa,Sb,产生的语言是什么？,思考,(2),文法,SaSa,SbSb,S,产生的语言是什么？,练习：,构造文法，产生,(1),字母表,a,，,b,上所有对称的,非空串,组成的语言。,(2)L=,wdw,T,|wa,b,c,+,。,(3)L=,a,n,b,n,|n,=0,。,一般,对任意的,a,b,+,，,可以使用,Aab|aAb,来产生,a,n,b,n,|n,0,；,对任意的,a,b,+,，可以使用,Aa|b|aA|bA,来产生,a,，,b,+,；,对任意的,a,+,，可以使用,Aa|aA,来产生,a,n,|n,0,；,对任意的,a,，,b,+,，,可以使用,AaAa|bAb,来产生,w,A,w,T,|,w,a,b,+,注意：,不能使用,Aa,2,代表,Aaa,不能使用,Aa,n,(n1),或,Aa,+,来代表,A,可以产生任意多个,a,。,思考：字母表为,0,，,1,语言的特性及产生语言的文法,(1),x|x=,x,T,x,(2)x|x=,x,T,x,+,(3),xx,T,|,x,+,(4),xx,T,|,x,*,(5),x0 x,T,|,x,+,(6)xwx,T,|,x,w,+,(7)xx,T,w|,x,w,+,构造文法,产生所有的,无符号整数,。,无符号整数是由,0,，,1,9,中的,10,个数字符号组成的，但不允许以,0,开始。,NAM|,0,A1|2|3|4|5|6|7|8|9,M|0M|1M|2M|3M|4M|5M|6M|7M|8M|9M,例,2-11,构造文法,G,，,产生语言,w|w,是实数,略。,例,2-12,S0B|1A,A0|0S|1AA,B1|1S|0BB,证明：,L(G)=|0,，,1,+,，且,中有相同多的,0,和,1,。,证明提示：,使用数学归纳法（句子长度）,证明过程 略。,根据下推自动机,0,分析,所有产生式的的使用情况,:,顺序和次数,思考：,上下文相关,上述文法的后,3,个产生式,bBbb,bCbc,cCcc,是否可以改为,Bb,Cc,上例还可以简化为：,Sabc|aSB,c,cBBc,bBbb,文法的产生式的左边可以有多个符号,思考：,补充文法,G,使得,L(G)=,a,n,b,n,c,n,|n,0,SaB,S,c,SaBc,Ba,?,练习：,构造文法,G,，使得,L(G)=,a,n,b,2n,|n=1,L(G)=,a,m+1,b,2m+1,|m=0,L(G,)=a,n,b,2n-1,|n=1,2.5,推导树,对于上下文无关文法，,利用推导树也可以表示句型的产生过程。,例,-16,S0B|1A,A0|0S|1AA,B1|1S|0BB,对于串,0011,的产生过程：,推导过程,最左推导：,S=0,B,=00,B,B=001,B,=0011,最右推导：,S=0,B,=00B,B,=00,B,1=0011,推导树表示推导,S,0 B,0 B B,1 1,无用非终结符,一个无关文法,G,AV,如果,A,不出现在任何形如,S=,*,uAv,=,+,uwv,的推导之中,-A,为,无用非终结符,。,其中：,u,，,w,，,v,*,。,有用非终结符,A,，必须同时满足,:,(1)A,必须出现在某个句型中；,(2),从,A,开始，能够产生终结符号串,无用的产生式,如果一个产生式,(,产生式的左边或右边,),包含有无用的非终结符，则该产生式就是,无用的产生式,。,应该将无用的产生式,删除,。,思考,如果文法,G,的开始符号,S,是无用的非终结符号，则,L,(G)=?,思考,判断,A,是有用的非终结符号的算法。,请参见参考文献,形式语言与自动机理论,（,蒋宗礼,姜守旭 清华大学出版社）,2.6,空串定理,上下文无关文法,G,，存在一般的空串产生式,A,，则存在另一个上下文无关文法,G1,，,使得：,L(G)=L(G1),；,若,L(G,),，则,G1,中没有任何,空串产生式,（,S1,就是,S,）；,若,L(G,),，则,G1,中仅有一个空串产生式,S1,，且,S1,不出现在,G1,的产生式的右边。,证明（,2,）,因为,L(G,),，,对于任意,CV,，,考虑它的任意产生式,Cw,（,w,不为空串,），,w,中非终结符分为,A,1,，,A,2,，,A,k,，,B,1,，,B,2,，,B,j,，,对于,A,i,，,有,A,i,1ik,将,Cw,改造为,Cw,w,是通过,0,步，,1,步，,k,步,删除,w,中的,A,i,而得到的，,w,共有,2,k,个。,最后，去掉所有的空串产生式和,无用的产生式,就得到,G1,。,考虑,G,产生句型,的推导树,T:,若,的推导中使用了空串产生式，则树,T,中有以,为标志的叶节点，,删除,树,T,中的所有产生,的,子树,，得到树,T1,，,而它刚好是文法,G1,产生串,的推导树，所以，,L(G)=L(G1),。,例,文法：,改造成等价的,G,：,SABCD SACD,CRS CS,B Aa,Aa Dd,Dd Sd,R,Sd,证明（,3,）,假设,L(G),，,则要增加新的开始符号,S,和两个产生式,SS,，,S,；,再消除其余的空串产生式，即可。,2.7,消除左递归,在,某些情况,下,需要消除一个无关文法中的,左递归,。,递归的作用是产生无穷的语言，消除左递归，只是将,左递归,改造为,右递归,。,左递归包括,直接,的和,间接,的左递归。,2.7.1,消除直接左递归,直接左递归的产生式形式为,AAv,其中：,AV,，,v(UV),+,。,递归的产生式可以产生串,v,的任意次连接。,假设文法,G,的产生式形式为：,AAv|w,其中,:,v,w(UV,),+,，,且,w,不包含,A,对于,A,，有,A=*,wv,*,增加,B,V,，构造无左递归文法：,AwB|w,B,v,B,|v,右递归,则,A=*,wv,*,或（编译采用的文法）,AwB,BvB|,实际上，消除了,产生式，就得,AwB|w,BvB|v,一般地，产生式的形式为：,AAv,1,|Av,2,|Av,n,|w,1,|w,2,|w,m,对于,A,，有,A=*(w,1,|w,2,|w,m,)(v,1,|v,2,|,v,n,)*,增加一个新的非终结符,B,，,构造无左递归文法：,Aw,1,B|w,2,B|w,mB|w,1,|w,2,|w,m,Bv,1,B|v,2,B|v,n,B|v,2,|v,2,|,v,n,某些文法可能没有直接左递归，但可能会有,间接左递归,。,SAa,ASb|b,2.7.2,消除间接左递归（,自学,）,G,是一个上下文无关文法，首先使用空串定理；然后将文法,G,中的所有非终结符按,任一顺序排列,为,A1,，,A2,，,An,，,根据下列,算法,消除可能存在的间接左递归。,for i,：,=1 to n do,begin,for j,：,=1 to i-1 do,begin,将,A,i,A,j,w,的产生式,改写,为：,A,i,v,1,w|v,2,w|,v,k,w,；,(v,1,v,2,，,，,v,k,是,Aj,的侯选式,),end,消除,A,i,产生式的直接左递归；,end,最后，删除,无用,的产生式，就可以得到没有间接左递归的文法。,该算法思想是将推导过程中可能出现的左递归，在文法的产生式中就,体现,出来，产生式的改写实际上是推导的体现,-,用,A,j,的侯选式将,A,j,代替,掉。,为方便实现，将上述算法进行改写。,G,是一个上下文无关文法，将文法,G,中的所有非终结符按任一给定的顺序排列为,A,1,，,A,2,，,A,n,那么，文法的每个产生式是,A,i,A,j,w,的形式（对于,A,i,aw,形式的产生式，不用考虑，因为它不会导致左递归的出现）,.,而,i,和,j,的,大小关系,只可能有,3,种情况：,A,i,A,j,w,ij,称该产生式是,向下,的；这类产生式需要,替代,，用,A,j,的侯选式将,A,j,替掉，若出现了直接左递归，还需要将直接左递归,消除,；,首先考虑非终结符,A,1,：,A,1,A,j,w,1j,产生式是向上的,1=j,该产生式是直接左递归的；消除直接左递归,对于非终结符,A,2,:,A,2,A,j,w,2j,该产生式是向下的；这类产生式需要替代，,对于非终结符,A,n,：,A,n,A,j,w,n=j,消除直接左递归；,nj,向下的；这类产生式需要需要替代，用,A,j,的侯选将,A,j,替换掉，若出现了直接左递归，还需要将直接左递归消除；,最后，删除多余的产生式，得到的文法就,没有了左递归,，包括直接和间接的左递归。,2.8,上下文无关文法的另一种表示,文法存在另外一种表示方法：,使用,表示,*,；,使用,表示,的出现可有可无,(,等价于,),左递归的产生式,Aa|b|Aw,改写成,A(a|b)w,右左递归的产生式,Aa|b|wA,改写成：,Aw(a|b,),例,2-18,标识符可定义为,IL,I,I,L,I,I,D,La|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r,|,s|t|u|v|w|x|y|z,D0|1|2|3|4|5|6|7|8|9,改写成,IL,L|D,La|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z,D0|1|2|3|4|5|6|7|8|9,2.9,语言之间的运算及运算封闭性,对,简单语言,进行语言的,运算，,可以产生,复杂语言,。,语言对运算的封闭性,如果任意的、属于某一,语言类,的语言在某一,特定运算,下所得到的语言仍然是,同类,语言,:,该,语言类,对此运算具有,封闭性,有效封闭性,根据多个语言的,(,文法,),描述,若可以构造出,给定运算,下所获得的,同类语言,的,(,文法,),描述,此语言类对该运算是,有效封闭,的,(,有效封闭性,),。,问题本质,存在文法,G,1,和,G,2,L,1,=L(,G1,),；,L,2,=L(,G,2,),需要,构造文法,G,，使得,L,(G),是对,L,1,和,L,2,是进行,某种运算,后得到的语言。,语言的有效封闭性可以,证明,某些语言属于某类语言，,从简单语言,构造,复杂的,同类,语言。,2.9.1,语言之间的基本运算,若语言,L,1,和,L,2,是字母表,1,和,2,上的两个语言，定义,语言,L,1,和,L,2,的,联合,运算为：,L,1,UL,2,=w|wL,1,或者,wL,2,思考,新语言的,字母表,是,？,连接,语言,L,1,和,L,2,的,连接,运算为：,L,1,L,2,=,w|w,=w,1,w,2,，,w,1,L,1,，,w,2,L,2迭代,语言,L,1,的,迭代,运算,(,或星运算，闭包运算,),为：,L,1,*=w|w=w,1,w,2,w,m,，,w,i,L,1,，,m0,=,L,1,n,对,n0,注意,语言,L,1,=a,n,|n0,，,L,2,=,b,n,|n,0,，,则,L,1,L,2,是,a,n,b,m,|n,m,0,而不是,a,n,b,n,|n,0,定理,2-7,i,(,i=0,，,1,，,2,，,3,),型语言,对,联合,，,连接,和,迭代,运算,有效,封闭,证明：,设参加运算的语言,L,1,和,L,2,分别是,字母表,1,和,2,上的语言。,产生,L,1,的文法,G,1,=,（,1,，,V,1,，,S,1P,1,）,产生,L,2,的文法,G,2,=,（,2,，,V,2,，,S,2,，,P,2,）,即,L,1,=L(G,1,),；,L,2,=L(G,2,),假定,1,2,=,V,1,V,2,=,S,V,1,S,V,2,设置,=,1,2,V=V,1,U,V,2,U,S,联合,运算,构造,G,3,=,（，,V,，,S,，,P,3,）,其中,:,P,3,=,SS,1,U,SS,2,U,P,1,U,P,2,联合运算,对于,i=0,，,1,，,2,若,G,1,和,G,2,是,i,型文法，则,G,3,依然。,显然,，,L(G,3,)=L(G,1,)UL(G,2,),，,0,、,1,、,2,型语言类对于联合封闭。,联合运算,若,G,1,和,G,2,是,3,型文法，,G,3,?,构造文法,G,4,=,（，,V,，,S,，,P,4,）,其中,P,4,为：,Sw,1,|,S,1,w,1,在,P,1,中,U,Sw,2,|,S,2,w,2,在,P,2,中,UP,1,U P,2,联合运算,则,G,4,是,RG,，且,L(G,4,)=L(G,1,),U,L(G,2,),。,所以,3,型语言对于联合封闭。,联合运算,实际上，,G,4,的构造方法也适合于,0,、,1,、,2,型文法。,思考,特殊性与一般性,连接运算,构造,G,5,=,（，,V,，,S,，,P,5,）,其中,P,5,=,SS,1,S,2,U P1,U P,2,对于,i=0,，,1,，,2,若,G,1,和,G,2,是,i,型文法，则,G,5,依然,连接运算,S,1,=*w,1,L,1,S,2,=*w,2,L,2,则,S=S,1,S,2,=*w,1,w,2,则,L(G,5,)=L(G,1,)L(G,2,),；,0,、,1,、,2,型语言对连接封闭。,连接运算,对于,3,型文法：,SS,1,S,2,？,构造,G,6,=(,，,V,1,U,V,2,，,S,1,，,P,6,),其中,P,6,为：,A,w,S,2,|Aw,在,P,1,中,-,Aw,U P,1,U P,2,连接运算,将每个形如,Aw,的产生式，,改写,为,Aw,S,2,则从,S1,=,+,r,1,r,2,r,k,A,=,r,1,r,2,r,k,w,S,2,=,其中，,r,1,r,2,r,k,w,L,1,连接运算,L(G,6,)=L(G,1,)L(G,2,),；,3,型语言对连接封闭。,注意：若,P,1,中有空串产生式，则要先消除,空串产生式,连接运算,若,G,1,和,G,2,是,0,型或,1,型,文法，,而,1,2,（包括,1,=,2,）,则 文法,G,5,可能,会有,问题,。,连接运算,文法,G,1,：,S,1,b,文法,G,2,：,S,2,c|bA|A,A a,bAbb,则,L(G,1,)=b,，,L(G,2,)=,c,a,ba,bb,L(G,1,)L(G,2