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

《有限自动机理论-2章形式语言.ppt》由会员分享，可在线阅读，更多相关《有限自动机理论-2章形式语言.ppt（325页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 形式语言简介形式语言简介 形式语言和自动机理论中的形式语言和自动机理论中的语言语言是是一个宽泛的概念。一个宽泛的概念。一个字母表上的一个字母表上的语言语言就是该就是该字母表字母表的某些的某些字符串字符串的的集合集合。语言中的字符串称为该语言的语言中的字符串称为该语言的句子句子l语言的的定义可以从两个方面进行：语言的的定义可以从两个方面进行：）从）从产生产生语言的角度；语言的角度；）从）从接收接收(或或识别识别)语言的角度。语言的角度。l产生语言产生语言 根据语言中的根据语言中的基本句子基本句子和其他句子的和其他句子的形成规则形成规则，得到，得到(产生产生)该语言所包含的该语言所包

2、含的所有句子所有句子。l 形式语言形式语言所研究的问题。所研究的问题。l接收一个语言接收一个语言 使用某种使用某种自动机模型自动机模型来来接收接收字符串，字符串，该模型所接收的所有字符串，也形成一该模型所接收的所有字符串，也形成一个语言。个语言。l 自动机自动机所研究的问题。所研究的问题。统一的理论 形式语言与自动机作为统一的理论形式语言与自动机作为统一的理论,实际上包括实际上包括3个方面的内容个方面的内容:1)形式语言形式语言理论理论(产生语言产生语言)2)自动机自动机理论理论(接收语言接收语言)3)形式语言与自动机的形式语言与自动机的等价性等价性理论理论l本章介绍本章介绍形式语言形式语言的

3、基本内容。的基本内容。语言的形式定义语言的形式定义l设设 是一个是一个字母表字母表，L L *,L L称为称为字母表字母表 上上的一个的一个语言语言,w w L,wL,w称为语言称为语言L L的一个的一个句子句子。2.1 例子语言例子语言l括号匹配串的语言。括号匹配串的语言。该语言是指所有的左括号和右括号相匹该语言是指所有的左括号和右括号相匹配的串的集合；配的串的集合；()，()，()()等等都是该语言的句子等等都是该语言的句子 )(，()等等不是该语言的句子。等等不是该语言的句子。l如何如何产生产生这个语言呢？这个语言呢？即如何即如何产生产生该语言所有句子呢？该语言所有句子呢？l实际上，就是

4、需要给出语言中句子的实际上，就是需要给出语言中句子的构造（形成）规则构造（形成）规则。l递归方法递归方法提供了语言的良好的定义方提供了语言的良好的定义方式：语言中的句子的构造规律较明显式：语言中的句子的构造规律较明显l可以使用多种方法可以使用多种方法描述描述构造规则。构造规则。l自然语言自然语言的描述方式，采用如下的的描述方式，采用如下的 递归规则：递归规则：()是该语言的最基本的句子；是该语言的最基本的句子；若若S是句子是句子,则则(S)是句子；是句子；若若S是句子是句子,则则SS是句子；是句子；l这些规则称为这些规则称为形成规则形成规则，根据这些，根据这些规则，可以规则，可以 产生该语言的

5、任意的句子；产生该语言的任意的句子；判断某个判断某个串串是否是该语言的句子是否是该语言的句子-语法分析语法分析。例如l可以产生句子可以产生句子（）（）而推断串而推断串 （）（）不是句子。不是句子。l规则规则(的个数的个数)是有限的，但可以产生是有限的，但可以产生无无限个句子限个句子、甚至、甚至长度无限的句子长度无限的句子l因为规则是因为规则是递归递归的。的。BNF的描述方式的描述方式l巴巴科科斯斯和和诺诺尔尔采采用用的的巴巴科科斯斯-诺诺尔尔范范式式(BNF-Backus-NaurForm)描述规则描述规则：l:=()l:=()l:=l使使用用尖尖括括号号“”包包括括起起来来的的部部分分，作为

6、一个整体来看待，表示某个语法成分作为一个整体来看待，表示某个语法成分 需要使用字母表中的字母来定义其构成需要使用字母表中的字母来定义其构成l符符号号“:=”是是BNF本本身身的的符符号号（元元符符号号），代表代表“定义为定义为”或或“是是”。l符号符号“(”和和“)”是字母表的元素。是字母表的元素。lChomsky采采用用的的符符号号化化(形形式式化化)的的描描述述方式，运用规则（称为方式，运用规则（称为产生式产生式）：）：S()S(S)SSS “”代表代表“定义为定义为”或者或者“是是”，它的左边和右边分别称为该产生式的它的左边和右边分别称为该产生式的左边左边和和右边右边根据产生式 可以生成

7、任意句子；可以生成任意句子；可以判断一个串是否为句子可以判断一个串是否为句子产生句子的过程 从从S开始，可以反复利用产生式的右开始，可以反复利用产生式的右边边代替代替产生式的左边（产生式的左边（推导过程推导过程），），最终可以产生括号匹配的的句子。最终可以产生括号匹配的的句子。例例:句子()()()()()()的推导过程的推导过程 S=S SS S=(=(S S)S)S=()=()S S=()(=()(S S)=()(=()(S SS)S)=()()=()()S S)=()()()=()()()产生式的个数是有限的，规则是递归产生式的个数是有限的，规则是递归的，所有的的，所有的小括号匹配的串小

8、括号匹配的串，都可以由，都可以由产生式产生；产生式产生；它们组成的集合就称为一个语言。它们组成的集合就称为一个语言。lS称为称为非终结符非终结符，在推导过程中，可以被，在推导过程中，可以被代替的符号。代替的符号。l(和和)称为称为终结符终结符，在推导过程中，不可以，在推导过程中，不可以被代替的符号。被代替的符号。l 是产生式系统的是产生式系统的元符号元符号，不属于非终，不属于非终结符，也不属于非终结符。结符，也不属于非终结符。例例2-1：由偶数个：由偶数个0组成的串的语言。组成的串的语言。规则的自然语言描述方式：规则的自然语言描述方式：00是该语言的基本的句子；是该语言的基本的句子；若若S是句

9、子是句子,则则00S是句子。是句子。形式化的描述方式：形式化的描述方式：S00 S00S 问题：问题：将产生式将产生式S00S换成换成S0S0或或SS00或或SSS是否还产生相同的语言？是否还产生相同的语言？结论：结论：一个语言，可以使用不同的产生式组一个语言，可以使用不同的产生式组合来产生。合来产生。考虑由奇数个由奇数个1组成串的语言（产生规则）组成串的语言（产生规则）例2-2 高高级级程程序序设设计计语语言言中中的的算算术术表表达达式式(的的语言语言)的产生。的产生。自然语言的描述方式自然语言的描述方式单个变量是最基本的单个变量是最基本的句子句子；若若E是是一一个个句句子子，则则EAE是是

10、一一个个句句子子（其中（其中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)注意：注意：这组产生式这组产生式没有表示出运算

11、符的没有表示出运算符的优先级优先级。表示出运算符的优先级的产生式：表示出运算符的优先级的产生式：EE+T|E-T|T TT*F|T/F|F F(E)|il其中：其中：E E代表表达式，代表表达式，T T代表项，代表项，F F代表因子代表因子(E)(E)代表的是带小括号的表达式代表的是带小括号的表达式表示：先因子，再表示：先因子，再*、/，最后，最后+、-如如果果使使用用%代代表表模模运运算算(即即取取余余数数运运算算)、使用使用 代表指数运算，则有代表指数运算，则有 EE+T|E-T|TEE+T|E-T|T TT*F|T/F|T%F|A TT*F|T/F|T%F|A AFA|FAFA|F F(

12、E)|i F(E)|i注意需要考虑需要考虑 运算的运算的结合性结合性：是右结合的。是右结合的。例2-3 标识符标识符(以字母开头的字母、数字的以字母开头的字母、数字的串串)的产生的产生(仅考虑小写字母仅考虑小写字母)。从标识符的形成角度考虑从标识符的形成角度考虑ILIILIIDLa|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t u|v|w|x|y|zD0|1|2|3|4|5|6|7|8|9思考：上例是从标识符的上例是从标识符的形成角度形成角度思考问题。思考问题。从标识符的从标识符的定义定义角度考虑，则？角度考虑，则？注意 D0|1|2|3|4|5|6|7|8|9不

13、能简写为不能简写为 D0|9将I的定义加入到表达式中：EE+T|E-T|T TT*F|T/F|F F(E)|I IL|IL|ID L D思考思考:其他类型的表达式（如关系表达式等）其他类型的表达式（如关系表达式等）的定义：的定义：、=、=标识符标识符(以以下划线下划线或字母开头的字母、下或字母开头的字母、下划线和数字的串划线和数字的串)的产生。的产生。例例2-42-4C C语言中简单变量的说明语句的定义。语言中简单变量的说明语句的定义。C C语言中的说明语句形式为：语言中的说明语句形式为：TYPE TYPE 变量名表；变量名表；TYPE TYPE 变量名表；变量名表；TYPE TYPE 变量名

14、表；变量名表；产生式为：产生式为：SSSSSS|P|PPT VPT V；Tint|char|float|double|Tint|char|float|double|VVV,VV,V|I|I 用户定义类型用户定义类型 IL|IL|ID L D思考PASCALPASCAL语言的简单变量的说明语句的形成。语言的简单变量的说明语句的形成。VAR变量名表变量名表:TYPE;变量名表变量名表:TYPE;变量名表变量名表:TYPE;2.2 文法和语言的关系文法和语言的关系语言的定义语言的定义文法的定义文法的定义文法与语言的关系文法与语言的关系 对对于于语语言言，在在字字母母表表上上，按按照照一一定定的的构构

15、成成规规则则，根根据据语语言言句句子子的的结结构构特特点点，可以定义一个产生该语言的可以定义一个产生该语言的文法文法。使使用用文文法法作作为为语语言言的的有有穷穷描描述述，不不仅仅可可以以描描述述出出语语言言的的结结构构特特征征，而而且且可可以以产生产生这个语言的这个语言的所有句子所有句子。定义定义2-1 短语结构文法短语结构文法(文法文法)的定义的定义文法文法G是一个四元式，是一个四元式，G=(，V，S，P)是是有有限限字字符符的的集集合合(字字母母表表)，元元素素称为字母或者称为字母或者终结符终结符；V是是有有限限字字符符的的集集合合-非非终终结结符符集集合合，元素称为变量或者元素称为变量

16、或者非终结符非终结符；短语结构文法短语结构文法(文法文法)的定义的定义 S V，称为文法的开始符号；，称为文法的开始符号；P是是有有序序偶偶对对(，)的的集集合合：是是集集合合(V)上上的的字字符符串串，至至少少包包含含一一个个非非终结符终结符；是集合是集合(V)*的元素的元素 一般，将有序偶对一般，将有序偶对(，)记为记为 称为产生式；称为产生式；如果有如果有，称之为，称之为空串产生式空串产生式或者或者产生式。产生式。如果有如果有ABAB，称之为，称之为单产生式单产生式。一个产生式的左边可能不只一个符号；一个产生式的左边可能不只一个符号；第一个产生式的左边只能有一个符号，第一个产生式的左边只

17、能有一个符号，就是就是开始符号开始符号S。文法文法的作用就是产生一个的作用就是产生一个语言语言。约定：如果没有特别说明约定：如果没有特别说明,则则 第一个产生式左边的符号，就是开始符第一个产生式左边的符号，就是开始符号，号，可以不为可以不为S；大写的英文字母代表非终结符；大写的英文字母代表非终结符；小写的英文字母小写的英文字母a，b，c，d，e和数字和数字代表终结符；代表终结符；约定：如果没有特别说明约定：如果没有特别说明,则则 小写的英文字母小写的英文字母u，v，w，x，y，z代代表终结符串；表终结符串；小写的希腊字母小写的希腊字母，、代表非终结符代表非终结符和终结符串；和终结符串；推导（派

18、生）的定义推导（派生）的定义2-2 文法文法G，和和是集合是集合(VV)上的串上的串=pvr，=pur(p和和r可能同时为可能同时为)而而vu是文法是文法G的一个产生式的一个产生式,则称则称直接推导出直接推导出 记为记为=，即，即 pvr=pur 推导的实质推导的实质 产生式的产生式的右边右边替换替换产生式的产生式的左边左边 非终结符非终结符代表在推导的过程中可以被代表在推导的过程中可以被替代的符号，替代的符号，终结符终结符代表在推导的过程中不可以被代表在推导的过程中不可以被替代的符号。替代的符号。推导推导的的逆逆过程称为过程称为归约归约。与与pvr=pur对应，串对应，串pur可以直接可以直

19、接归约成串归约成串pvr 记为记为pvr+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 语言的定义语言的

20、定义 给定文法给定文法G，有开始符号，有开始符号S 把把S可以推导出的所有句子的集合可以推导出的所有句子的集合 称为由文法产生的语言，记为称为由文法产生的语言，记为L(G)L(G)=|S=*，且且*例l文法文法 G=(,),S,S,S(),S(S),SSS)产生语言产生语言 L(G)=w|w是括号匹配的串是括号匹配的串注意注意:文法文法G产生语言产生语言L，必须满足：，必须满足：G推导产生的所有句子都在推导产生的所有句子都在L中中L的任意句子都可以由的任意句子都可以由G推导产生推导产生对于文法对于文法G=(，V，S，P)约定：约定：第一个产生式左边的符号，就是开第一个产生式左边的符号，就是开始

21、符号（始符号（可以不是可以不是S）；大写的英文字母代表非终结符大写的英文字母代表非终结符。对于文法（对于文法（G），只需给出该文法的），只需给出该文法的所有产生式即可。所有产生式即可。产生括号匹配语言的文法可以写成产生括号匹配语言的文法可以写成 S()S(S)SSS 还可以再简写成还可以再简写成 S()|(S)|SS 文法和语言的文法和语言的3类问题类问题已知已知文法文法得到该文法产生的得到该文法产生的语言语言已知已知语言语言构造产生该语言的构造产生该语言的某个某个文法文法判断判断一个语言是否由某一个文法产生一个语言是否由某一个文法产生第一类问题第一类问题文法文法SaSa|bSb|c产生的语言

22、是什么？产生的语言是什么？需需要要考考虑虑所所有有产产生生式式的的所所有有可可能能使用情况使用情况（包括顺序和次数）（包括顺序和次数）第二类问题第二类问题构造产生语言构造产生语言L的文法。的文法。L=wwT|wa,b,c+其中：其中：wT是是w的逆（反序）的逆（反序）思考：思考：产生下列语言的文法：产生下列语言的文法：L1=anbn|n0L2=anbn|n 0第三类问题第三类问题文法文法S0B|1AA0|0S|1AAB1|1S|0BB产生的语言是否为产生的语言是否为L：L=|0,1+，且且中有中有相同多相同多的的0和和1？第三类问题还包括第三类问题还包括l判断一个语言是否由某个文法产生。判断一

23、个语言是否由某个文法产生。l证明一个语言由某一个文法产生。证明一个语言由某一个文法产生。注意：一个语言一个语言可以可以由多个不同的文由多个不同的文法产生。法产生。一个文法一个文法只能只能产生一个语言。产生一个语言。例例2-5 G1：S0|1|00|11 G2：SA|B|AA|BB A0 B1L(G1)=L(G2)=0,1,00,11文法等价文法等价 如果文法如果文法G1和文法和文法G2产生同一产生同一个语言，则称文法个语言，则称文法G1和和G2是是等价等价的文法。的文法。L(G1)=L(G2)注意区别：文法文法G1G1和和G2G2等价等价文法文法G1G1和和G2G2相同相同 文法等价的证明文法

24、等价的证明l如何证明两个文法等价？如何证明两个文法等价？2.3Chomsky对文法、语言分类对文法、语言分类 Chomsky Chomsky对文法进行了分类；对文法进行了分类；语语言言的的分分类类，是是根根据据产产生生该该语语言文法的类别进行分类的言文法的类别进行分类的0型文法 对于一般的短语结构文法对于一般的短语结构文法(PSG)G=(，V，S，P)G称为称为0型文法，对应的型文法，对应的L(G)称为称为0型语言或者短语结构语言型语言或者短语结构语言(PSL)、递归可枚举集递归可枚举集。1型文法 如果对于任意如果对于任意P，均有，均有|成立，则称成立，则称G为为1型文法，型文法，或或上下文相

25、关文法上下文相关文法(CSG)。对应的对应的L(G)称为称为1型语言或者型语言或者上上下文相关语言下文相关语言(CSL)。1型文法产生式的标准形式产生式的标准形式 yAzyz其中：其中：A V；y,z(V)*(V)+1型文法 可以证明：可以证明：任意的任意的1型文法，都可以改造为型文法，都可以改造为1型文法的标准形式。型文法的标准形式。2型文法 如果对于任意如果对于任意P，均有，均有|且且 V成立，则称成立，则称G为为2型型文法，或文法，或上下文无关文法上下文无关文法(CFG)对应的对应的L(G)称为称为2型语言或者型语言或者上下上下文无关语言文无关语言(CFL)。3型文法 如果对于任意如果对

26、于任意P，具有形式，具有形式 Aw，AwB其中，其中，A，B V，w+则称则称G为为3型文法，或右线性文法型文法，或右线性文法 RLG，也可称为，也可称为正则文法正则文法RG。对应的对应的L(G)称为称为3型语言型语言 或或 右线性语言右线性语言RLL或或 正则语言正则语言RL。四类文法和对应的四类四类文法和对应的四类语言语言之间是之间是真包含真包含关系。关系。思考思考 如果文法如果文法G有有产生式，则产生式，则G G是是 型文法型文法?文法分类判断方法：文法分类判断方法：文法文法G=(，V，S，P)，则，则 1)G是短语结构文法；是短语结构文法；2)如果文法如果文法G的所有产生式的左的所有产

27、生式的左边边长度长度小于等于右边长度部分，小于等于右边长度部分，那么那么G是是上下文相关文法上下文相关文法；3)如果上下文相关文法如果上下文相关文法G的所有产的所有产生式的左边都是生式的左边都是一个非终结符一个非终结符，那么那么G是是上下文无关文法上下文无关文法；4)如果如果上下文无关文法上下文无关文法G的所有产的所有产生式右边最多只有一个非终结符生式右边最多只有一个非终结符 且该非终结符号只能出现在最右且该非终结符号只能出现在最右边，那么边，那么G是是正则文法正则文法。文法文法G:S01|101S是是RG，CFG，CSG和和PSG文法文法G：SAaS|AS Aa|b|c|d是是CFG，CSG

28、和和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没有空句子，则没有空句

29、子，则 文法中增加产生式文法中增加产生式 S 就可以直接产生空句子。就可以直接产生空句子。文法文法扩充分类扩充分类：设文法设文法G=(，V，S，P)如果如果S不出现在任何不出现在任何产生式的右产生式的右部部，则，则(1)若若G是是CSG G=(，V，S，P S)仍然仍然为为CSG；L(G)是是CSL。(1)若若G是是CFG G=(，V，S，P S)仍然仍然为为CFG；L(G)是是CFL。(1)若若G是是RG G=(，V，S，P S)仍然仍然为为RG；L(G)是是RL。思考思考 为什么要有条件为什么要有条件 S不出现在任何产生式的右部？不出现在任何产生式的右部？设正则文法设正则文法RG：Sab|

30、aS，则，则 L(G)=a+bG：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=(，V S,S,P)其中其中P=P S|S P G 与与G有相同的类型。有相同的类型。G与G等价 即证明即证明L(G)=L(G)需要证明需要证明 L(G)L(G)L(G)L(G)

31、特殊情况特殊情况 如果如果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，则存在一

32、个，则存在一个 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，则，则

33、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。除了生成空句子除了生成空句子外，空产生式可外，空产生式

34、可以不用于其他句子的推导中。以不用于其他句子的推导中。空句子空句子在一个语言中的存在并不在一个语言中的存在并不影响该语言的有穷描述。影响该语言的有穷描述。文法可以包含一般的空串产生式，文法可以包含一般的空串产生式，属于属于0型文法。型文法。L(G)=w|w 0,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，就不能再往下进行推

35、导了。，就不能再往下进行推导了。产生产生基本句子基本句子0；若使用产生式若使用产生式S0S，n-1次后，则次后，则 S=0S=00S=000S=+0n-1S使用使用S0，则，则S=+0n 这对于任何这对于任何n1都是成立的；都是成立的；总之，该文法产生语言总之，该文法产生语言L=0n|n0。定义定义2-7 递归文法递归文法 一个一个上下文无关文法上下文无关文法G，A V 如如果果 A=+A，则则该该文文法法称称为为递递归归的文法；的文法；(A:递归递归非终结符非终结符)递归分为递归分为直接直接和和间接间接递归。递归。若若A=A 则称为则称为直接递归直接递归的非终结符。的非终结符。直接递归直接递

36、归可以从可以从产生式产生式判断。判断。间间接接递递归归需需要要根根据据推推导导过过程程才才能能进进行行判断。判断。思考思考 是否可以将间接递归是否可以将间接递归转换转换为直接为直接递归？递归？如何如何进行进行转换？转换？基本思路：基本思路：将推导过程直接反映在产生式中将推导过程直接反映在产生式中 方法：方法：代入法代入法 一个一个上下文无关上下文无关文法的产生式的文法的产生式的个数总是有限的。个数总是有限的。如果该文法是如果该文法是递归文法递归文法，则该文，则该文法就能够产生一个法就能够产生一个无穷语言无穷语言。若若一一个个上上下下文文无无关关文文法法不不是是递递归归的文法，则的文法，则 该文

37、法产生该文法产生有穷语言有穷语言。注意 特殊形式的产生式特殊形式的产生式 AA 是递归的，可以反复利用任意多次，是递归的，可以反复利用任意多次，但对于无穷语言的产生，没有任何作用但对于无穷语言的产生，没有任何作用定义定义2-8 空串产生式的定义空串产生式的定义 形如形如A的产生式，称为的产生式，称为上下文上下文无关无关文法的空串产生式，或文法的空串产生式，或产生产生式；式；空串产生式的作用就是在推导的空串产生式的作用就是在推导的过程中，对于某个句型，省略掉能过程中，对于某个句型，省略掉能够产生够产生的非终结符号。的非终结符号。若若某某个个上上下下文文无无关关文文法法G G有有SS，则，则 该该

38、L(G)L(G)一定包含空句子一定包含空句子例文法文法 S0SS0S S S该文法产生语言该文法产生语言L=0L=0n n|n0|n0思考：思考：该文法是该文法是？型文法？型文法分析 如如果果开开始始使使用用第第2 2个个产产生生式式SS，则则S=S=，就不能再往下进行推导了，就不能再往下进行推导了，则产生空句子则产生空句子；如果开始使用产生式如果开始使用产生式S0SS0S，n n次后，次后，S=0S=00S=000S=S=0S=00S=000S=+0 0n nS S 最后，使用最后，使用SS，则，则S=S=+0 0n n 这对于任何这对于任何n1n1都是成立的；都是成立的；总之，该文法产生语

39、言总之，该文法产生语言L=0L=0n n|n0|n0例 文法文法 SaSb Sab产生语言产生语言 L=anbn|n0例文法文法 SaS SbS S产生语言产生语言 L=a，b*例 字字母母表表aa，bb上上所所有有对对称称的的非非空空串串组组成的语言成的语言(没有中心点没有中心点)构造文法产生该语言构造文法产生该语言分析 aa aa和和bbbb是最基本的句子。是最基本的句子。如果如果S S是句子，则是句子，则aSaaSa和和bSbbSb是句子是句子得到文法：得到文法：SaaSaa Sbb Sbb SaSa SaSa SbSb SbSb思考(1)(1)文法文法 SaSaSaSa SbSb Sb

40、Sb Sa Sa Sb Sb产生的语言是什么？产生的语言是什么？思考(2)(2)文法文法 SaSaSaSa SbSb SbSb S S产生的语言是什么？产生的语言是什么？练习：构造文法，产生(1)(1)字字母母表表aa，bb上上所所有有对对称称的的非非空空串串组成的语言。组成的语言。(2)L=wdw(2)L=wdwT T|wa,b,c|wa,b,c+(3)L=a(3)L=an nb bn n|n=0|n=0一般 对任意的a,b+l使用使用 Aab|aAb Aab|aAb 产生产生 a an nb bn n|n0|n0l使用使用 Aa|b|aA|bA Aa|b|aA|bA 产生产生 aa，bb+

41、l使用使用 Aa|aA Aa|aA 产生产生 aa+一般 对任意的a,b+l使用使用 A A|aAb|aAb 产生产生 a an nb bn n|n=0|n=0l使用使用 AA|aA|bA|aA|bA 产生产生 aa，bb*l使用使用 A A|aA|aA 产生产生 aa*一般 对任意的a,b+l 使用使用 AaAa|bAbAaAa|bAb产生产生 w wA Aw wT T|w wa,ba,b+注意：注意：l不能使用不能使用 AaAa2 2l代表代表 AaaAaal不能使用不能使用 AaAan n(n1)(n1)或或 AaAa+l代表代表 A A可以产生多个可以产生多个a a思考：字母表为思考：

42、字母表为0，1语言的特性及产生语言的文法语言的特性及产生语言的文法 (1)x|x=xT,x (2)x|x=xT,x +(3)xxT|x +(4)xxT|x *(5)x0 xT|x +(6)xwxT|x,w +(7)xxTw|x,w +构造文法产生所有的产生所有的无符号整数无符号整数。无符号整数是由无符号整数是由00，1,1,99中的中的1010个个数字符号组成的，但不允许以数字符号组成的，但不允许以0 0开始。开始。NAM|NAM|0 0 A1|2|3|4|5|6|7|8|9 A1|2|3|4|5|6|7|8|9 M|0M|1M|2M|3M|4M|5M|6M|7M|8M|9M M|0M|1M|

43、2M|3M|4M|5M|6M|7M|8M|9M例例产生语言产生语言|0，1*，且，且中有中有相同多的相同多的0和和1的文法为：的文法为：S0AS|1BS|A1|0AA B0|1BB或 SS0S1S|S1S0S|例例2-13 2-13 文法文法SaSBC SaSBC SaBC SaBC CBBC CBBC aBab aBab bBbb bBbb bCbc bCbc cCcc cCcc 产生的语言为产生的语言为 L(G)=aL(G)=an nb bn nc cn n|n0|n0分析分析 所有产生式的所有使用情况所有产生式的所有使用情况:顺序和次数顺序和次数思考：思考：上下文相关上下文相关上述文法的

44、后上述文法的后3 3个产生式个产生式 bBbbbBbb bCbc bCbc cCcc cCcc是否可以改为是否可以改为 Bb CcBb Cc上例还可以简化为：上例还可以简化为：Sabc|aSBSabc|aSBc c cBBc cBBc bBbb bBbb 文法的产生式的左边可以有多个符号文法的产生式的左边可以有多个符号思考：思考：补充文法G使得使得 L(G)=aan nb bn nc cn n|n0|n0 SaB SaBS Sc c SaBc SaBc Ba?Ba?练习：练习：构造文法G，使得 L(G)=anb2n|n=1 L(G)=am+1b2m+1|m=0 L(G)=anb2n-1|n=1

45、2.5无用非终结符无用非终结符一个无关文法一个无关文法G,A V 如果如果A不出现在任何形如不出现在任何形如 S=*uAv=+uwv的推导之中的推导之中-A为为无用非终结符无用非终结符其中：其中：u，w，v *有用非终结符有用非终结符A，必须同时满足，必须同时满足:(1)A必须出现在某个句型中必须出现在某个句型中(2)从从A开开始始，能能够够产产生生终终结结符符串串（包括（包括）无用的产生式无用的产生式 如如果果一一个个产产生生式式(产产生生式式的的左左边边或或右右边边)包包含含有有无无用用的的非非终终结结符符，则该产生式就是则该产生式就是无用的产生式无用的产生式。应该将无用的产生式应该将无用

46、的产生式删除删除。思考思考如果文法如果文法G的开始符号的开始符号S是无用的非终是无用的非终结符号，则结符号，则L(G)=?思考判断判断A是有用的非终结符号的算法。是有用的非终结符号的算法。请参见参考文献请参见参考文献 形式语言与自动机理论形式语言与自动机理论 （蒋宗礼蒋宗礼 姜守旭姜守旭 清华大学出版社）清华大学出版社）2.6 推导树推导树对于上下文无关文法，对于上下文无关文法，利利用用推推导导树树也也可可以以表表示示句句子子（或或 句型）的产生过程。句型）的产生过程。例-16 S0B|1A A0|0S|1AA B1|1S|0BB对于串对于串0011的产生过程：的产生过程：推导过程推导过程最左

47、推导：最左推导：S=0B=00BB=001B=0011 最右推导：最右推导：S=0B=00BB=00B1=0011推导树表示推导推导树表示推导 S S 0 B 0 B 0 B B 0 B B 1 1 1 12.7 空串定理空串定理 上下文无关文法上下文无关文法G，存在一般的空，存在一般的空串产生式串产生式A，则存在另一个上下文，则存在另一个上下文无关文法无关文法G1，使得：，使得：L(G)=L(G1)；若若 L(G)，则，则G1中没有任何中没有任何空串空串产生式产生式（S1就是就是S）；）；若若 L(G)，则，则G1中仅有一个空串产中仅有一个空串产生式生式S1，且，且S1不出现在不出现在G1的

48、产生的产生式的右边。式的右边。证明（2）因为因为 L(G)，对于任意，对于任意C V，考，考虑它的任意产生式虑它的任意产生式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中有

49、以中有以为标志的叶节点，为标志的叶节点，删除删除树树T中的所有产生中的所有产生的的子树子树，得到，得到树树T1，而它刚好是文法，而它刚好是文法G1产生串产生串的的推导树，所以，推导树，所以，L(G)=L(G1)。例文法：文法：改造成等价的改造成等价的G：SABCD SACDCRS CSB AaAa DdDd SdR Sd 证明（3）假设假设 L(G)，则要增加新的开始，则要增加新的开始符号符号S1和两个产生式和两个产生式 S1S，S1；再消除其余的；再消除其余的空串产生式，即可。空串产生式，即可。2.8 消除左递归消除左递归l上下文无关文法上下文无关文法G，如果存在，如果存在 A=+Al则则A

50、称为左递归的非终结符。称为左递归的非终结符。l如果有如果有 A=Al则则A称为直接左递归的非终结符。称为直接左递归的非终结符。l在在某些情况某些情况下下,需要消除一个无关文法需要消除一个无关文法中的中的左递归左递归。l递归的作用是产生无穷的语言，消除递归的作用是产生无穷的语言，消除左递归，只是将左递归，只是将左递归左递归改造为改造为右递归右递归。l左递归包括左递归包括直接直接的和的和间接间接的左递归。的左递归。2.8.1 消除直接左递归消除直接左递归l直接左递归的产生式形式为直接左递归的产生式形式为 AAv 其中：其中：A V，v(UV)+l递归的产生式可以产生串递归的产生式可以产生串v的任意