有限自动机理论-2章形式语言.ppt

第二章 形式语言简介,形式语言和自动机理论中的语言是一个宽泛的概念。 一个字母表上的语言就是该字母表的某些字符串的集合。 语言中的字符串称为该语言的句子,语言的的定义可以从两个方面进行： ）从产生语言的角度； ）从接收(或识别)语言的角度。,产生语言 根据语言中的基本句子和其他句子的形成规则，得到(产生)该语言所包含的所有句子。 形式语言所研究的问题。,接收一个语言 使用某种自动机模型来接收字符串，该模型所接收的所有字符串，也形成一个语言。 自动机所研究的问题。,统一的理论,形式语言与自动机作为统一的理论,实际上包括3个方面的内容: 1) 形式语言理论(产生语言) 2) 自动机理论(接收语言) 3) 形式语言与自动机的等价性理论,本章介绍形式语言的基本内容。,语言的形式定义,设是一个字母表， L*, L称为字母表上的一个语言, wL, w称为语言L的一个句子。,2.1 例子语言,括号匹配串的语言。 该语言是指所有的左括号和右括号相匹配的串的集合； ( )，( )，( )( )等等都是该语言的句子 )( ，( )等等不是该语言的句子。,如何产生这个语言呢？ 即如何产生该语言所有句子呢？,实际上，就是需要给出语言中句子的构造（形成）规则。 递归方法提供了语言的良好的定义方式：语言中的句子的构造规律较明显 可以使用多种方法描述构造规则。,自然语言的描述方式，采用如下的 递归规则： ( )是该语言的最基本的句子； 若S是句子,则(S)是句子； 若S是句子,则SS是句子；,这些规则称为形成规则，根据这些规则，可以 产生该语言的任意的句子； 判断某个串是否是该语言的句子- 语法分析。,例如,可以产生句子（） 而推断串 （） 不是句子。,规则(的个数)是有限的，但可以产生无限个句子、甚至长度无限的句子 因为规则是递归的。,BNF的描述方式,巴科斯和诺尔采用的巴科斯-诺尔范式(BNF-Backus-Naur Form)描述规则： := ( ) :=() :=,使用尖括号“”包括起来的部分，作为一个整体来看待，表示某个语法成分 需要使用字母表中的字母来定义其构成 符号“:=”是BNF本身的符号（元符号），代表“定义为”或“是”。 符号“( ”和“ )”是字母表的元素。,Chomsky采用的符号化(形式化)的描述方式，运用规则（称为产生式）： S( ) S(S) SSS,“”代表“定义为”或者“是” ， 它的左边和右边分别称为该产生式的左边和右边,根据产生式,可以生成任意句子； 可以判断一个串是否为句子,产生句子的过程,从S开始，可以反复利用产生式的右边代替产生式的左边（推导过程）， 最终可以产生括号匹配的的句子。,例:句子( )( )( )的推导过程,S =SS =(S)S =( )S =( )(S) =( )(SS) =( )( )S) = ( )( )( ),产生式的个数是有限的，规则是递归的，所有的小括号匹配的串，都可以由产生式产生； 它们组成的集合就称为一个语言。,S称为非终结符，在推导过程中，可以被代替的符号。 (和)称为终结符，在推导过程中，不可以被代替的符号。 是产生式系统的元符号，不属于非终结符，也不属于非终结符。,例2-1：由偶数个0组成的串的语言。 规则的自然语言描述方式： 00是该语言的基本的句子； 若S是句子,则00S是句子。,形式化的描述方式： S00 S00S,问题：,将产生式S00S换成 S0S0或SS00或SSS 是否还产生相同的语言？,结论：,一个语言，可以使用不同的产生式组合来产生。,考虑,由奇数个1组成串的语言（产生规则）,例2-2,高级程序设计语言中的算术表达式(的语言)的产生。,自然语言的描述方式,单个变量是最基本的句子； 若E是一个句子，则EAE是一个句子（其中A代表运算符+、-、*、/） 若E是一个句子，则(E)是句子；,形式语言的描述方式, E i （i代表单个变量） EEAE E(E) A+ A- A* A/,思考：,字母表为？ 若以A开始推导，则产生？,其中 ： A+，A-，A*，A/ 四个产生式的左边是相同的符号，可以合并为 A+|-|*|/ +、-、*、/ 称为A的侯选式。,E i EEAE E(E) 也可以记为： E i|EAE|(E),注意：,这组产生式 没有表示出运算符的优先级。,表示出运算符的优先级的产生式： EE+T|E-T|T TT*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,标识符(以字母开头的字母、数字的串)的产生(仅考虑小写字母)。,从标识符的形成角度考虑,IL IIL IID 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 IL|IL|ID L D,思考:,其他类型的表达式（如关系表达式等）的定义：、=、= 标识符(以下划线或字母开头的字母、下划线和数字的串)的产生。,例2-4,C语言中简单变量的说明语句的定义。 C语言中的说明语句形式为： TYPE 变量名表； TYPE 变量名表； TYPE 变量名表；,产生式为：,SSS|P PT V； Tint|char|float|double| VV,V|I,用户定义类型,IL|IL|ID L D,思考,PASCAL语言的简单变量的说明语句的形成。 VAR 变量名表: TYPE; 变量名表: TYPE ; 变量名表: TYPE;,2.2 文法和语言的关系,语言的定义 文法的定义 文法与语言的关系,对于语言，在字母表上，按照一定的构成规则，根据语言句子的结构特点，可以定义一个产生该语言的文法。 使用文法作为语言的有穷描述，不仅可以描述出语言的结构特征，而且可以产生这个语言的所有句子。,定义2-1 短语结构文法(文法)的定义,文法G是一个四元式， G=(，V，S，P) 是有限字符的集合(字母表)， 元素称为字母或者终结符； V是有限字符的集合-非终结符集合，元素称为变量或者非终结符；,短语结构文法(文法)的定义,SV，称为文法的开始符号； P是有序偶对(，)的集合：是集合(V)上的字符串，至少包含一个非终结符；是集合(V)*的元素 一般，将有序偶对(，)记为 称为产生式；,如果有，称之为空串产生式或者产生式。 如果有AB，称之为单产生式。,一个产生式的左边可能不只一个符号； 第一个产生式的左边只能有一个符号，就是开始符号S。,文法的作用就是产生一个语言。,约定：如果没有特别说明,则,第一个产生式左边的符号，就是开始符号，可以不为S； 大写的英文字母代表非终结符； 小写的英文字母a，b，c，d，e和数字代表终结符；,约定：如果没有特别说明,则,小写的英文字母u，v，w，x，y，z代表终结符串； 小写的希腊字母，、 代表非终结符和终结符串；,推导（派生）的定义2-2,文法G，和是集合(V)上的串 = pvr ，=pur(p和r可能同时为) 而vu是文法G的一个产生式, 则称直接推导出 记为= ，即 pvr =pur,推导的实质 产生式的右边替换产生式的左边,非终结符代表在推导的过程中可以被替代的符号， 终结符代表在推导的过程中不可以被替代的符号。,推导的逆过程称为归约。 与pvr =pur对应，串pur可以直接归约成串pvr 记为pvr =pur,多步推导（至少一步）,y=+z 表示y可以经过多步推导出z，即 存在串的序列1，2，3 ，n ； 有y=1 ，z= n ， 且i=i+1；对所有ni=1,任意步推导(包括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类问题,已知文法 得到该文法产生的语言 已知语言 构造产生该语言的某个文法 判断一个语言是否由某一个文法产生,第一类问题,文法 SaSa|bSb|c 产生的语言是什么？ 需要考虑所有产生式的所有可能使用情况（包括顺序和次数）,第二类问题,构造产生语言L的文法。 L= wwT|wa,b,c+ 其中：wT是w的逆（反序）,思考：,产生下列语言的文法： L1=anbn|n0 L2=anbn|n0,第三类问题,文法 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型文法产生式的标准形式,yAzyz 其中：AV； y,z(V)* (V)+,1型文法,可以证明： 任意的1型文法，都可以改造为1型文法的标准形式。,2型文法,如果对于任意P，均有|且V成立，则称G为2型文法，或上下文无关文法(CFG) 对应的L(G)称为2型语言或者上下文无关语言(CFL)。,3型文法,如果对于任意P，具有形式 Aw，AwB 其中，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，PS) 仍然为CSG； L(G) 是CSL。,(1) 若G是CFG G=(，V，S，PS) 仍然为CFG； L(G) 是CFL。,(1) 若G是RG G=(，V，S，PS) 仍然为RG； L(G) 是RL。,思考,为什么要有条件 S不出现在任何产生式的右部？,设正则文法RG：Sab|aS，则 L(G)=a+b G：Sab|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=PS|SP 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,PS) 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。,除了生成空句子外，空产生式可以不用于其他句子的推导中。 空句子在一个语言中的存在并不影响该语言的有穷描述。,文法可以包含一般的空串产生式， 属于0型文法。,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文法产生语言,例 文法 S0S S0 产生语言L=0n|n0,分析,如果开始使用第2个产生式S0，则S=0，就不能再往下进行推导了。 产生基本句子0；,若使用产生式S0S，n-1次后，则 S=0S=00S=000S=+0n-1S 使用S0，则S=+0n 这对于任何n1都是成立的； 总之，该文法产生语言L=0n|n0。,定义2-7 递归文法,一个上下文无关文法G，AV 如果 A =+A ，则该文法称为递归的文法；(A:递归非终结符) 递归分为直接和间接递归。 若A =A 则称为直接递归的非终结符。,直接递归可以从产生式判断。 间接递归需要根据推导过程才能进行判断。,思考,是否可以将间接递归转换为直接递归？ 如何进行转换？,基本思路： 将推导过程直接反映在产生式中 方法： 代入法,一个上下文无关文法的产生式的个数总是有限的。 如果该文法是递归文法，则该文法就能够产生一个无穷语言。,若一个上下文无关文法不是递归的文法，则 该文法产生有穷语言。,注意,特殊形式的产生式 AA 是递归的，可以反复利用任意多次， 但对于无穷语言的产生，没有任何作用,定义2-8 空串产生式的定义,形如A的产生式，称为上下文无关文法的空串产生式，或产生式； 空串产生式的作用就是在推导的过程中，对于某个句型，省略掉能够产生的非终结符号。,若某个上下文无关文法G有S，则 该L(G)一定包含空句子,例,文法 S0S S 该文法产生语言L=0n|n0 思考： 该文法是 ？型文法,分析,如果开始使用第2个产生式S，则S=，就不能再往下进行推导了， 则产生空句子；,如果开始使用产生式S0S，n次后， S=0S=00S=000S=+0nS 最后，使用S，则S=+0n 这对于任何n1都是成立的； 总之，该文法产生语言L=0n|n0,例,文法 SaSb Sab 产生语言 L=anbn|n0,例,文法 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=wdwT|wa,b,c+ (3) L=anbn|n=0,一般 对任意的a,b+,使用 Aab|aAb 产生 anbn|n0 使用 Aa|b|aA|bA 产生 a，b+ 使用 Aa|aA 产生 a+,一般 对任意的a,b+,使用 A|aAb 产生 anbn|n=0 使用 A|aA|bA 产生 a，b* 使用 A|aA 产生 a*,一般 对任意的a,b+,使用 AaAa|bAb 产生 wAwT|wa,b+,注意：,不能使用 Aa2 代表 Aaa,不能使用 Aan(n1) 或 Aa+ 代表 A可以产生多个a,思考：字母表为0，1,语言的特性及产生语言的文法 (1) x | x=xT , x (2) x| x=xT , x + (3) xxT | x + (4) xxT | x *,(5) x0xT | x + (6) xwxT | x, w + (7) xxTw | 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,例,产生语言 |0，1*，且中有相同多的0和1的文法为： S0AS|1BS| A1|0AA B0|1BB,或,SS0S1S|S1S0S|,例2-13 文法,SaSBC SaBC CBBC aBab bBbb bCbc cCcc ,产生的语言为 L(G)=anbncn|n0,分析,所有产生式的所有使用情况: 顺序和次数,思考： 上下文相关,上述文法的后3个产生式 bBbb bCbc cCcc 是否可以改为 Bb Cc,上例还可以简化为： Sabc|aSBc cBBc bBbb,文法的产生式的左边可以有多个符号,思考：补充文法G,使得 L(G)= anbncn|n0 SaBSc SaBc Ba? ,练习：构造文法G，使得,L(G)=anb2n|n=1 L(G)=am+1b2m+1|m=0 L(G)=anb2n-1|n=1,2.5无用非终结符,一个无关文法G,AV 如果A不出现在任何形如 S=*uAv=+uwv 的推导之中-A为无用非终结符 其中：u ，w ，v *,有用非终结符A，必须同时满足: (1) A必须出现在某个句型中 (2)从A开始，能够产生终结符串（包括）,无用的产生式,如果一个产生式(产生式的左边或右边)包含有无用的非终结符，则该产生式就是无用的产生式。 应该将无用的产生式删除。,思考,如果文法G的开始符号S是无用的非终结符号，则 L(G)=?,思考,判断A是有用的非终结符号的算法。 请参见参考文献 形式语言与自动机理论 （蒋宗礼 姜守旭 清华大学出版社）,2.6 推导树,对于上下文无关文法， 利用推导树也可以表示句子（或 句型）的产生过程。,例-16,S0B|1A A0|0S|1AA B1|1S|0BB 对于串0011的产生过程：,推导过程,最左推导： S=0B=00BB=001B=0011 最右推导： S=0B=00BB=00B1=0011,推导树表示推导,S 0 B 0 B B 1 1,2.7 空串定理,上下文无关文法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中非终结符分为A1，A2，Ak，B1，B2，Bj， 对于Ai， 有 Ai 1ik,将Cw改造为Cw w是通过0步，1步，k步删除w中的Ai而得到的，w共有2k个。 最后，去掉所有的空串产生式和无用的产生式就得到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)，则要增加新的开始符号S1和两个产生式 S1S， S1；再消除其余的空串产生式，即可。,2.8 消除左递归,上下文无关文法G，如果存在 A =+A 则A称为左递归的非终结符。 如果有 A =A 则A称为直接左递归的非终结符。,在某些情况下,需要消除一个无关文法中的左递归。 递归的作用是产生无穷的语言，消除左递归，只是将左递归改造为右递归。 左递归包括直接的和间接的左递归。,2.8.1 消除直接左递归,直接左递归的产生式形式为 AAv 其中：AV，v(UV)+ 递归的产生式可以产生串v的任意次连接,假设文法G的产生式形式为： AAv|w 其中: v,w(UV)+ 且w不包含A 对于A，有 A=*wv*,增加B V，构造无左递归文法： AwB|w BvB|v 右递归 则 A=*wv*,或 （编译采用的文法）,AwB BvB| 实际上，消除了产生式，就得 AwB|w BvB|v,一般地，产生式的形式为： AAv1|Av2|Avn|w1|w2|wm 对于A，有 A=*(w1|w2|wm)(v1|v2|vn)*,增加一个新的非终结符B，构造无左递归文法： Aw1B|w2B|wmB|w1|w2|wm Bv1B|v2B|vnB|v2|v2|vn,某些文法可能没有直接左递归，但可能会有间接左递归。 SAa ASb|b,2.8.2 消除间接左递归（自学）,G是一个上下文无关文法，首先使用空串定理；然后将文法G中的所有非终结符按任一顺序排列为A1，A2，An，根据下列算法消除可能存在的间接左递归。,for i：=1 to n do begin for j：=1 to i-1 do begin 将Ai Ajw的产生式改写为： Aiv1w|v2w|vkw ； (v1，v2，vk是Aj的侯选式) end 消除Ai产生式的直接左递归； end,最后，删除无用的产生式，就可以得到没有间接左递归的文法。,该算法思想是将推导过程中可能出现的左递归，在文法的产生式中就体现出来，产生式的改写实际上是推导的体现-用Aj的侯选式将Aj代替掉。,为方便实现，将算法进行改写。,G是一个上下文无关文法，将文法G中的所有非终结符按任一给定的顺序排列为 A1，A2，An,那么，文法的每个产生式是AiAjw的形式（对于Aiaw形式的产生式，不用考虑，因为它不会导致左递归的出现）. 而i和j的大小关系只可能有3种情况：,AiAjw ij 称该产生式是向上的，这类产生式不用替代。 i=j 该产生式是直接左递归的；消除直接左递归。,ij 称该产生式是向下的；这类产生式需要替代，用Aj的侯选式将Aj替掉，若出现了直接左递归，还需要将直接左递归消除；,首先考虑非终结符A1： A1Ajw 1j 产生式是向上的 1=j 该产生式是直接左递归的；消除直接左递归,对于非终结符A2: A2Ajw 2j 该产生式是向下的；这类产生式需要替代，,对于非终结符An： AnAjw n=j 消除直接左递归； nj 向下的；这类产生式需要需要替代，用Aj的侯选将Aj替换掉，若出现了直接左递归，还需要将直接左递归消除；,最后，删除多余的产生式，得到的文法就没有了左递归，包括直接和间接的左递归。,2.9 上下文无关文法的另一种表示,为提高语法分析的效率 文法存在另外一种表示方法： 使用表示* 使用表示的出现可有可无 (等价于) 还增加元符号（、）,左递归的产生式 Aa|b|Aw 改写成 A(a|b)w,右递归的产生式 Aa|b|wA 改写成： Aw(a|b),例2-18 标识符可定义为,IL IIL IID 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,改写成,ILL|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,可以对应while语句,2.10 语言之间的运算及运算封闭性,对简单语言进行语言的运算，可以产生复杂语言。,语言对运算的封闭性,如果任意的、属于某一语言类的语言在某一特定运算下所得到的语言仍然是同类语言: 该语言类对该运算具有封闭性,有效封闭性,根据多个语言的(文法)描述, 若可以构造出给定运算下所获得的同类语言的(文法)描述 此语言类对该运算是有效封闭的(有效封闭性)。,问题本质:文法的构造,存在文法G1和G2 L1=L(G1) L2=L(G2) 需要构造文法G，使得 L(G)是对L1和L2进行某种运算后得到的语言。,语言的有效封闭性可以 证明某些语言属于某类语言， 基于简单语言构造复杂的同类语言。,2.10.1 语言之间的基本运算,若语言L1和L2是字母表1和 2上的两个语言，定义 语言L1和L2的联合运算为： L1UL2=w|wL1或者wL2,思考,新语言的字母表是？,连接,语言L1和L2的连接运算为： L1L2= w|w=w1w2，w1L1，w2L2,迭代,语言L1的迭代运算(或星运算、闭包运算)为： L1*=w| w= w1w2wm， wiL1，m0 =L1n 对n0,注意,语言L1=an|n0，L2=bn|n0， 则 L1L2是 anbm|n,m0 而不是 anbn|n0,定理2-7,i (i=0，1，2，3)型语言 对联合，连接和迭代运算有效封闭,证明：,设参加运算的语言L1和L2分别是字母表1和 2上的语言,产生L1的文法 G1=（1，V1，S1，P1） 产生L2的文法 G2=（2，V2，S2，P2） 即L1=L(G1)；L2=L(G2),假定,12= V1V2= SV1 SV2,设置,=12 V=V1V2S,联合运算,构造 G3=（，V，S，P3） 其中: P3=SS1USS2UP1UP2,联合运算,对于i=0，1，2 若G1和G2是i型文法，则G3依然。 显然，L(G3)=L(G1)UL(G2)， 0、1、2型语言类对于联合封闭。,联合运算,若G1和G2是3型文法，G3 ? 构造文法G4=（，V，S，P4） 其中P4为： S |S1 在P1中U S |S2 在P2中UP1U P2,联合运算,则G4是RG，且L(G4)=L(G1)UL(G2)。 所以3型语言对于联合封闭。,联合运算,实际上，G4的构造方法也适合于 0、1、2型文法。,思考,特殊性与一般性,连接运算,构造G5=（，V，S，P5） 其中P5= SS1S2 U P1 U P2 对于i=0，1，2 若G1和G2是i型文法，则G5依然,连接运算,S1=*w1 L1 S2=*w2 L2 则 S=S1S2=* w1w2 则 L(G5)=L(G1)L(G2)； 0、1、2型语言对连接封闭。,连接运算,对于3型文法：SS1S2 ？ 构造G6=(，V1UV2，S1，P6 ) 其中P6为： AwB| AwB在P1中 AwS2 |Aw在P1中 P2,连接运算,将P1每个形如Aw的产生式改写为 AwS2 则从S1=+ r1r2rkA =r1r2rkwS2=+w1w2 其中，r1r2rkw L1,连接运算,L(G6)=L(G1)L(G2) 3型语言对连接封闭。 注意：若P1中有一般空串产生式，则要先消除空串产生式 问题：若有S1 ？,连接运算,若G1和G2是0型或1型文法， 而 12（包括1=2 ） 则 文法G5可能会有问题。,连接运算,文法G1：S1b 文法G2：S2c|bA|A A a bAbb 则L(G1)=b，L(G2)=c,a,ba,bb L(G1)L(G2)=bc,ba,bba,bbb,连接运算的问题,存在推导： S=S1S2=bS2=bA = bb 产生了句子bb 但是 bb 不是语言L(G1)和L(G2)的连接后的句子,思考,产生问题的原因是？,该问题产生的原因是S1和S2产生的串发生了串道(cross)。 即文法G1可能将S2产生句型的子串作为下文，文法G2可能将S1产生句型的子串作为上文。,思考,串道是终结符号还是非终结符号？ 终结符号 解决串道问题的方法 将两个文法的终结符号变换为不一致的描述,连接运算,解决串道问题，将复制为和 令 =x|x =x|x,连接运算,将P1中的x用x代替,得到P 将P2中的x用x代替,得到P,连接运算,构造G7=(,V U U,S，P7) 其中P7为： SS1S2 U PU P U xx|xUxx |x 则L(G7)=L(G1)L(G2),文法G1：S1b 文法G2：S2c|bA|A Aa bAbb P7 为 SS1S2 S1b S2c|bA|A Aa bA bb bb a a cc bb,S=S1S2 =b S2 = b A = ? =bS2 =?,思考：,若12= 是否有串道的可能 ？ 若12 是否可以简化P和P ？,迭代运算（一元运算）,基本思路： 空句子, 迭代 若S|S1S S 在产生式右边，封闭性存在问题,迭代运算,考虑文法 S|S SS1|S1S 则S推导出和S1n(n1),迭代运算,构造G8=(，V1US，S，S，P8) 其中P8为： S|S USS1|S1S UP1,迭代运算,若G1是2型文法，则G8也是2型文法； 且 S=*L(G1)* 所以2型语言对迭代封闭。,若G1是0、1型文法， 文法G8可能也会有串道问题。 如 S1abS1|S1a bS1bb S1ac,迭代运算,消除G1中的空串产生式 将1复制为和 将V1复制为V和V,构造P和P,将P1中的x用x代替 将P1中的A用A代替 得到P 将P2中的x用x代替 将P2中的A用A代替 得到P,构造,G= (,V U U S-S1,S,P) 并 将S1改写S G= (,VUU S-S1,S,P) 并 将S1改写S,迭代运算,构造G9=(, VU V UU U S,S,S, S1，S2, S，P9),其中P9为： S|S1|S2 U S1S|SS2 U S2S | S S1 UPUP U xx|xUxx |x 注意:原来的S1改写为S和 S ,为避免串道，需要S和 S 交替出现，有两种可能： S1推导出S S S S S S 或 S S S S S S2推导出S S S S S S 或 S S S S S ,迭代运算,则L(G9)=L(G1)*；所以0型和1型语言对迭代封闭。,迭代运算,对于3型文法，引入新的开始符号S和S来产生空串（若在P1中有S1，则删除S1） 增加Sr (S1r 在P1中) 以便开始推导(r=wB 或 r=w),迭代运算,对于每个形如Aw的产生式，增加 AwS1（不删除Aw） 从S开始，可以推导出句型 r1r2rkA 其中：r1，r2，rk L1,可以在推导出r1r2rkw时停止， 也可以从r1r2rkwS1开始推导出另一个更长的串， 直至L(G1)*,迭代运算,G1是3型文法，构造 G10=（，V1US，S，P10） 其中P10为：,迭代运算,S U (P1 - S1 ) U Sr | S1r在P1中 U AwS1|若Aw(包括Sw) G10也是RG，且L(G10)=L(G1)*；所以3型语言对迭代封闭。,结论,不论字母表 12 或 12（包括1=2 ） 四类语言对联合、连接和迭代运算是有效封闭的。,2.10.3 语言之间的其他运算,定理2-8 正则语言对于补和交运算是封闭的。 该定理的证明需要使用自动机的知识，留待今后证明。,定理2-9,上下文无关语言对于补和交运算不是封闭的。,证明：举一个反例即可,上下文无关语言 L1=anbncm|n,m0 上下文无关语言 L2=aibkck|i,k0,它们的交集为L=anbncn|n0 不是上下文无关语言（是一个上下文相关语言）。,语言，还有一个有用的运算置换。,定义2-15 (上下文无关)置换,一个映射g为置换映射： X*Y* (X和Y当作字母表) 若 g()=，且对n1； g(w1w2wn)=g(w1)g(w2)g(wn) 其中 g(wi)=yY* 或 g(wi)=y1 ,y2 ， yiY*,特别地，若g(wi)=yY* 则g称为同态。 同态可以映射为或者是一个串 若|y|=1 同态仅仅只改变了成分的名字,g(L),若L是字母表上的一个语言，则 g(L)=Ug(w) 其中wL,例,=a，b，g(a)=0*，g(b)=1 若语言L=aba*，则 g(L) =0*10*,g(a*) = g()Ug(a)Ug(aa)U Ug(aa)=(g(a)* g(L*)= (g(L)*,定理2-10,上下文无关语言对于置换映射是有效封闭的。,证明：,2型文法G=(,V,S,P)产生语言L g是一个置换映射： g(xi)=Lxi 其中，xi,构造，将文法G改造为 G=(Y，V U ，S，P) 将G产生式中的终结符x替换为x 增加产生式，使得每个 x=+ Lxi 得到P,若文法G产生句子x1x2xn 则文法G产生句型x1x2xn 再得到句子Lx1Lx2Lxn 所以文法G产生语言g(L)，也是上下文无关的语言。,文法G:S aSb|ab L(G)=anbn 若 g(a)=0*，g(b)=1 构造文法：S aS b |ab a |0 a b 1 产生语言0*1+,定理2-11,3型语言对于置换映射是封闭的。 证明： 略。,2.11 正则表达式和正则集,有效自动化是计算学科的重点问题 有效自动化的基础： 对问题恰当的形式化描述,可以使用正则表达式来表示正则的语言,优势,这种表达形式还更接近语言的集合表示和语言的计算机表示。 语言的集合表示形式使得更容易理解和使用； 而适合计算机的表示形式又使得它更容易被计算机系统处理。,本