有限自动机理论02章形式语言

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如何如何产生产生这个语言呢？这个语言呢？ 即如何即如何

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

5、，可以，可以 产生该语言的任意的句子；产生该语言的任意的句子； 判断某个判断某个串串是否是该语言的句子是否是该语言的句子- 语法分析语法分析。例如l可以产生句子可以产生句子（）（） 而推断串而推断串 （）（） 不是句子。不是句子。l规则规则(的个数的个数)是有限的，但可以产生是有限的，但可以产生无无限个句子限个句子、甚至、甚至长度无限的句子长度无限的句子l因为规则是因为规则是递归递归的。的。BNF的描述方式的描述方式l巴科斯和诺尔采用的巴科斯和诺尔采用的巴科斯巴科斯-诺尔范式诺尔范式(BNF-Backus-Naur Form)描述规则描述规则：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) =( )( ) =( )(

8、 )S S) ) = ( )( )( ) = ( )( )( ) 产生式的个数是有限的，规则是递归产生式的个数是有限的，规则是递归的，所有的的，所有的小括号匹配的串小括号匹配的串，都可以由，都可以由产生式产生；产生式产生； 它们组成的集合就称为一个语言。它们组成的集合就称为一个语言。lS称为称为非终结符非终结符，在推导过程中，可以被，在推导过程中，可以被代替的符号。代替的符号。l(和和)称为称为终结符终结符，在推导过程中，不可以，在推导过程中，不可以被代替的符号。被代替的符号。l 是产生式系统的是产生式系统的元符号元符号，不属于终结，不属于终结符，也不属于非终结符。符，也不属于非终结符。例例2

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

10、设计语言中的算术表达式的形成规则成规则自然语言的描述方式自然语言的描述方式单个变量是最基本的单个变量是最基本的句子句子；若若E是一个是一个句子句子，则，则EAE是一个是一个句子句子（其中（其中A代表运算符代表运算符+、-、*、/）若若E是一个是一个句子句子，则，则(E)是是句子句子；形式语言的描述方式形式语言的描述方式 E i （i代表单个变量）代表单个变量） EEAE E(E) A+ A- A* A/思考：思考：字母表为？字母表为？ 若以若以A开始推导，则产生？开始推导，则产生？其中其中 ： A+，A-，A*，A/ 四个产生式四个产生式的左边是相同的符号，可以合并为的左边是相同的符号，可以合

11、并为 A+|-|*|/ +、-、*、/ 称为称为A的的侯选式侯选式。 E i EEAE E(E)也可以记为：也可以记为： E i|EAE|(E)注意：注意： 这组产生式这组产生式没有表示出运算符的没有表示出运算符的优先级优先级。表示出运算符的优先级的产生式：表示出运算符的优先级的产生式： EE+T|E-T|T TT*F|T/F|F F(E)|il其中：其中：E E代表表达式，代表表达式，T T代表项，代表项，F F代表因子代表因子(E)(E)代表的是带小括号的表达式代表的是带小括号的表达式表示：先因子，再表示：先因子，再* *、/ /，最后，最后+ +、- - 如果使用如果使用% %代表模运算

12、代表模运算( (即取余数运算即取余数运算) )、使用使用 代表指数运算，则有代表指数运算，则有 EE+T|E-T|TEE+T|E-T|T TT TT* *F|T/F|T%F|AF|T/F|T%F|A AFA|FAFA|F F(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

13、|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不能简写为不能简写为 D0|9将I的定义加入到表达式中： EE+T|E-T|T TT*F |T/F|F F (E)|I IL|IL|ID L D思考思考: 其他类型的表达式（如关系表达式等）其他类型的表达式（如关系表达式等）的定义：的定义：、=、= 标识符标识符(以以下划线下划线或字母开头的字母、下或字母开头的字母、下划线和数字的串划线和数字的串)的产生

14、。的产生。例例2-42-4C C语言中简单变量的说明语句的定义。语言中简单变量的说明语句的定义。 C C语言中的说明语句形式为：语言中的说明语句形式为： TYPE TYPE 变量名表；变量名表； TYPE TYPE 变量名表；变量名表； TYPE TYPE 变量名表；变量名表；产生式为：产生式为：SSSSSS|P|PPT VPT V；Tint|char|float|double|Tint|char|float|double|VVV,VV,V|I |I 用户定义类型用户定义类型 IL|IL|ID L D思考PASCALPASCAL语言的简单变量的说明语句的形成。语言的简单变量的说明语句的形成。

15、VAR 变量名表变量名表: TYPE; 变量名表变量名表: TYPE ; 变量名表变量名表: TYPE; 2.2 文法和语言的关系文法和语言的关系语言的定义语言的定义文法的定义文法的定义文法与语言的关系文法与语言的关系 对于语言，在字母表上，按照一定的对于语言，在字母表上，按照一定的构成规则，根据语言句子的结构特点，构成规则，根据语言句子的结构特点，可以定义一个产生该语言的可以定义一个产生该语言的文法文法。 使用使用文法文法作为语言的有穷描述，不仅作为语言的有穷描述，不仅可以描述出语言的可以描述出语言的结构特征结构特征，而且可以，而且可以产生产生这个语言的这个语言的所有句子所有句子。定义定义2

16、-1 短语结构文法短语结构文法(文法文法)的定义的定义文法文法G是一个四元式，是一个四元式， G=(，V，S，P) 是有限字符的集合是有限字符的集合(字母表字母表)， 元素元素称为字母或者称为字母或者终结符终结符； V是有限字符的集合是有限字符的集合-非终结符集合，非终结符集合，元素称为变量或者元素称为变量或者非终结符非终结符；短语结构文法短语结构文法(文法文法)的定义的定义 SV，称为文法的开始符号；，称为文法的开始符号； P是有序偶对是有序偶对(，)的集合：的集合：是集合是集合(V)上的字符串，至少包含一个非上的字符串，至少包含一个非终结符终结符；是集合是集合(V)*的元素的元素 一般，将

17、有序偶对一般，将有序偶对(，)记为记为 称为产生式；称为产生式； 如果有如果有，称之为，称之为空串产生式空串产生式或者或者产生式。产生式。 如果有如果有ABAB，称之为，称之为单产生式单产生式。 一个产生式的左边可以是串；一个产生式的左边可以是串； 第一个产生式的左边只能有一个符号，第一个产生式的左边只能有一个符号，就是就是开始符号开始符号S。文法文法的作用就是产生一个的作用就是产生一个语言语言。约定：如果没有特别说明约定：如果没有特别说明,则则 第一个产生式左边的符号，就是开始符第一个产生式左边的符号，就是开始符号，号，可以不为可以不为S； 大写的英文字母代表非终结符；大写的英文字母代表非终

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

19、r对应，串对应，串pur可以直接可以直接归约成串归约成串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=*，则称，则称是文法的一个是文法的一个句型句型 进一步进

20、一步 ，若，若 * *, , 称为称为句子句子定义定义2-3 语言的定义语言的定义 给定文法给定文法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=

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

22、一个文法是否由产生某个语言一个文法是否由产生某个语言 第一类问题第一类问题 文法文法 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产生的语言是否为产生的语言是否为

23、L： L=|0,1+， 且且中有中有相同多相同多的的0和和1？第三类问题还包括第三类问题还包括l判断判断一个语言是否由某个文法产生。一个语言是否由某个文法产生。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是是等价等价的

24、文法。的文法。 L(G1)= L(G2)注意区别：文法文法G1G1和和G2G2等价等价文法文法G1G1和和G2G2相同相同 文法等价的证明文法等价的证明l如何证明两个文法等价？如何证明两个文法等价？2.3Chomsky对文法、语言分类对文法、语言分类 Chomsky Chomsky对文法进行了分类；对文法进行了分类； 语言的分类，是根据产生该语语言的分类，是根据产生该语言文法的类别进行分类的言文法的类别进行分类的0型文法 对于一般的短语结构文法对于一般的短语结构文法(PSG) G=(，V，S，P) G称为称为0型文法，对应的型文法，对应的L(G)称为称为0型语言或者短语结构语言型语言或者短语结

25、构语言(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型型

26、文法，或文法，或上下文无关文法上下文无关文法(CFG) 对应的对应的L(G)称为称为2型语言或者型语言或者上下上下文无关语言文无关语言(CFL)。3型文法 如果对于任意如果对于任意P，具有形式，具有形式 Aw，AwB其中，其中，A，BV，w+ 则称则称G为为3型文法，或右线性文法型文法，或右线性文法 RLG，也可称为，也可称为正则文法正则文法RG。 对应的对应的L(G)称为称为3型语言型语言 或或 右线性语言右线性语言RLL或或 正则语言正则语言RL。 四类文法和对应的四类四类文法和对应的四类语言语言之间是之间是真包含真包含关系。关系。 思考思考 如果文法如果文法G有有产生式，则产生式，则G

27、G是是 型文法型文法? ?文法分类判断方法：文法分类判断方法： 文法文法G=(，V，S，P)，则，则 1) G是短语结构文法；是短语结构文法； 2) 如果文法如果文法G的所有产生式的左的所有产生式的左边边长度长度小于等于右边长度部分，小于等于右边长度部分，那么那么G是是上下文相关文法上下文相关文法； 3) 如果上下文相关文法如果上下文相关文法G的所有产的所有产生式的左边都是生式的左边都是一个非终结符一个非终结符， 那么那么G是是上下文无关文法上下文无关文法； 4) 如果如果上下文无关文法上下文无关文法G的所有产的所有产生式右边最多只有一个非终结符生式右边最多只有一个非终结符 且该非终结符号只能

28、出现在最右且该非终结符号只能出现在最右边，那么边，那么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中都

29、不包含中都不包含(空句子空句子)。 如果允许在如果允许在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

30、) 是是CFL。 (1) 若若G是是RG G=(，V，S，PS) 仍然仍然为为RG； L(G) 是是RL。思考思考 为什么要有条件为什么要有条件 S不出现在任何产生式的右部？不出现在任何产生式的右部？设正则文法设正则文法RG：Sab|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构

31、造构造满足条件的满足条件的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的的作用作用是什么？是什么？ 仅仅负责推导的开始；仅仅负责推导的开始； 不能够作为不能够作为一般非终结符一般非终结符使用使用下列命题成立 有语言有

32、语言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，不可能被使用到任不可能被使用到任何非空句子的推导中，则何非空句子

33、的推导中，则 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。

34、如果L 设设S不出现在不出现在G的产生式的右部。的产生式的右部。 构造构造 =(,V,S,P-S)， G 也是也是CSG。 S不出现在不出现在G产生式的右部产生式的右部 去掉去掉S,则则不影响不影响任何非空任何非空句子句子的推导的推导， L(G )=L(G)-。 L(G )是是CSL。 除了生成空句子除了生成空句子外，空产生式可外，空产生式可以不用于其他句子的推导中。以不用于其他句子的推导中。 空句子空句子在一个语言中的存在并不在一个语言中的存在并不影响该语言的有穷描述。影响该语言的有穷描述。文法可以包含一般的空串产生式，文法可以包含一般的空串产生式，属于属于0型文法。型文法。 L(G)=w|

35、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都是成立的；都是成立的； 总之，该

36、文法产生语言总之，该文法产生语言L=0n|n0。定义定义2-7 递归文法递归文法 一个一个上下文无关文法上下文无关文法G，AV 如果如果 A =+A ，则该文法称为，则该文法称为递归递归的文法；的文法；(A:递归递归非终结符非终结符) 递归分为递归分为直接直接和和间接间接递归。递归。 若若A =A 则称为则称为直接递归直接递归的非终结符。的非终结符。 直接递归直接递归可以从可以从产生式产生式判断。判断。 间接递归间接递归需要根据需要根据推导推导过程才能进行过程才能进行判断。判断。思考思考 是否可以将间接递归是否可以将间接递归转换转换为直接为直接递归？递归？ 如何如何进行进行转换？转换？ 基本思

37、路：基本思路： 将推导过程直接反映在产生式中将推导过程直接反映在产生式中 方法：方法： 代入法代入法 一个一个上下文无关上下文无关文法的产生式的文法的产生式的个数总是有限的。个数总是有限的。 如果该文法是如果该文法是递归文法递归文法，则该文，则该文法就能够产生一个法就能够产生一个无穷语言无穷语言。 若一个若一个上下文无关上下文无关文法文法不是递归不是递归的文法，则的文法，则 该文法产生该文法产生有穷语言有穷语言。注意 特殊形式的产生式特殊形式的产生式 AA 是递归的，可以反复利用任意多次，是递归的，可以反复利用任意多次，但对于无穷语言的产生，没有任何作用但对于无穷语言的产生，没有任何作用定义定

38、义2-8 空串产生式的定义空串产生式的定义 形如形如A的产生式，称为的产生式，称为上下文上下文无关无关文法的空串产生式，或文法的空串产生式，或产生产生式；式； 空串产生式的作用就是在推导的空串产生式的作用就是在推导的过程中，对于某个句型，省略掉能过程中，对于某个句型，省略掉能够产生够产生的非终结符号。的非终结符号。 若某个若某个上下文无关上下文无关文法文法G G有有SS，则则 该该L(G)L(G)一定包含空句子一定包含空句子例文法文法 S0SS0S S S该文法产生语言该文法产生语言L=0L=0n n|n0|n0思考：思考： 该文法是该文法是 ？型文法？型文法分析 如果开始使用第如果开始使用第

39、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都是成立的；都是成立的；总之，该文法产生语言总之，该文法产生语言L=0L=0n n|n0|n0例 文法文法 SaSb Sab产生语言产生语言 L=anbn|n0例文法文法 SaS SbS S产生语言产生语言 L=a，b*例 字母表字母表a

40、a，bb上所有对称的上所有对称的非空串非空串组组成的语言成的语言( (没有中心点没有中心点) ) 构造文法产生该语言构造文法产生该语言分析 aa aa和和bbbb是最基本的句子。是最基本的句子。 如果如果S S是句子，则是句子，则aSaaSa和和bSbbSb是句子是句子得到文法：得到文法： SaaSaa Sbb Sbb SaSa SaSa SbSb SbSb思考(1)(1)文法文法 SaSaSaSa SbSb SbSb Sa Sa Sb Sb产生的语言是什么？产生的语言是什么？思考(2)(2)文法文法 SaSaSaSa SbSb SbSb S S产生的语言是什么？产生的语言是什么？练习：构造文

41、法，产生(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 a, ,bb+ +l使用使用 Aab|aAb Aab|aAb 产生产生 a an nb bn n|n0|n0l使用使用 Aa|b|aA|bA Aa|b|aA|bA 产生产生 aa，bb+ +l使用使用 Aa|aA Aa|aA 产生产生 aa+ + 一般 对任意的a,b+ +l使用使用 A A|aAb|aAb 产生产生 a an nb bn

42、 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思考：字母表为思考：字母表为0，1语言的特性及产生语言的文法语言的特性及产生语言的文法 (1) x | x=xT , x (2)

43、 x| x=xT , x + (3) xxT | x + (4) xxT | x * (5) x0 xT | x + (6) xwxT | x, w + (7) xxTw | x, w + 构造文法产生所有的产生所有的无符号整数无符号整数。 无符号整数是由无符号整数是由00，1,91,9中的中的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|2M|3M|4M|5M|6M|7M|8

44、M|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分析分析 所有产生式的所有使用情况所有产生式的所有使用情况: 顺序和次数顺序和次数思考：思考： 上下文相关上下文相关上述文法的后上述文法的后3 3个产生式

45、个产生式 bBbbbBbb bCbc bCbc cCcc cCcc是否可以改为是否可以改为 Bb CcBb Cc 上例还可以简化为：上例还可以简化为：Sabc|aSBSabc|aSBc c cBBc cBBc aBab aBab 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

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

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

48、程：推导过程推导过程最左推导：最左推导： 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，

49、且，且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: 若若的推导中使用了空串产生式，

50、则的推导中使用了空串产生式，则树树T中有以中有以为标志的叶节点，为标志的叶节点， 删除删除树树T中的所有产生中的所有产生的的子树子树，得到，得到树树T1，而它刚好是文法，而它刚好是文法G1产生串产生串的推的推导树，所以，导树，所以，L(G)=L(G1)。例文法：文法： 改造成等价的改造成等价的G：SABCD SACDCRS CRSB CSAa AaDd DdR|r SdSd 证明（3） 假设假设L(G)，则要增加新的开始，则要增加新的开始符号符号S1和两个产生式和两个产生式 S1S， S1；再消除其余的空；再消除其余的空串产生式，即可。串产生式，即可。2.8 消除左递归消除左递归l上下文无关文

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

52、V)+l递归的产生式可以产生串递归的产生式可以产生串v的任意次的任意次连接连接l假设文法假设文法G的产生式形式为：的产生式形式为： AAv|wl其中其中: v,w(UV)+ 且且w不包含不包含Al对于对于A，有，有 A=*wv*l增加增加B V，构造无左递归文法：，构造无左递归文法： AwB|w BvB|v 右递归右递归则则 A=*wv*或 （编译采用的方式） AwB BvB|实际上，消除了实际上，消除了产生式，就得产生式，就得 AwB|w BvB|vl一般地，产生式的形式为：一般地，产生式的形式为： AAv1|Av2|Avn|w1|w2|wml对于对于A，有，有 A=*(w1|w2|wm)(

53、v1|v2|vn)*l增加一个新的非终结符增加一个新的非终结符B，构造，构造无左递归文法：无左递归文法：Aw1B|w2B|wmB|w1|w2|wmBv1B|v2B|vnB|v2|v2|vnl某些文法可能没有直接左递归，某些文法可能没有直接左递归，但可能会有但可能会有间接左递归间接左递归。 SAa ASb|b2.8.2 消除间接左递归（消除间接左递归（自学自学）lG是一个上下文无关文法，首先是一个上下文无关文法，首先使用空串定理；然后将文法使用空串定理；然后将文法G中中的所有非终结符按的所有非终结符按任一顺序排列任一顺序排列为为A1，A2，An，根据下列，根据下列算算法法消除可能存在的间接左递归

54、。消除可能存在的间接左递归。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产生式的直接左递归；产生式的直接左递归； endl最后，删除最后，删除无用无用的产生式，就可的产生式，就可以得到没有间接左递归的文法。以得到没有间接左递归的文法。l该算法思想是将推导过程中可能该算法思想是将推导过程中可能出现的左递归，在文法的产生式出现的左递归，在文法的产生式中就中就体现体现出来，产生式的改写实出来，产生式的改

55、写实际上是推导的体现际上是推导的体现-用用Aj的侯选的侯选式将式将Aj代替代替掉。掉。l为方便实现，将算法进行改写。为方便实现，将算法进行改写。lG是一个上下文无关文法，将是一个上下文无关文法，将文法文法G中的所有非终结符按任中的所有非终结符按任一给定的顺序排列为一给定的顺序排列为lA1，A2，Anl那么，文法的每个产生式是那么，文法的每个产生式是AiAjw的形式（对于的形式（对于Aiaw形形式的产生式，不用考虑，因为它式的产生式，不用考虑，因为它不会导致左递归的出现）不会导致左递归的出现）.l而而i和和j的的大小关系大小关系只可能有只可能有3种情种情况：况：lAiAjwl ij 称该产生式是

56、称该产生式是向下向下的；这类的；这类产生式需要产生式需要替代替代，用，用Aj的侯选式的侯选式将将Aj替掉，若出现了直接左递归，替掉，若出现了直接左递归，还需要将直接左递归还需要将直接左递归消除消除；l首先考虑非终结符首先考虑非终结符A1：lA1Ajwl 1j 产生式是向上的产生式是向上的l 1=j 该产生式是直接左递归的；该产生式是直接左递归的；消除直接左递归消除直接左递归l对于非终结符对于非终结符A2:lA2Ajw 2j 该产生式是向下的；这类产生该产生式是向下的；这类产生式需要替代，式需要替代，ll对于非终结符对于非终结符An：l AnAjw n=j 消除直接左递归；消除直接左递归； nj

57、 向下的；这类产生式需要需要替代，向下的；这类产生式需要需要替代，用用Aj的侯选将的侯选将Aj替换掉，若出现了直接左替换掉，若出现了直接左递归，还需要将直接左递归消除；递归，还需要将直接左递归消除；l最后，删除多余的产生式，得到最后，删除多余的产生式，得到的文法就的文法就没有了左递归没有了左递归，包括直，包括直接和间接的左递归。接和间接的左递归。2.9 上下文无关文法的另一种表示上下文无关文法的另一种表示l为提高语法分析的为提高语法分析的效率效率l文法存在另外一种表示方法：文法存在另外一种表示方法： 使用使用表示表示* 使用使用表示表示的出现可有可无的出现可有可无 (等价于等价于) 还增加元符

58、号还增加元符号（、）l左递归的产生式左递归的产生式 Aa|b|Awl改写成改写成 A(a|b)wl右递归的产生式右递归的产生式 Aa|b|wAl改写成：改写成： 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|DLa|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可以对应可以对应whilewhile语句语句2.10 语言之间的运

59、算及运算封闭性语言之间的运算及运算封闭性 l对对简单语言简单语言进行语言的进行语言的运算，运算，可可以产生以产生复杂语言复杂语言。语言对运算的封闭性 如果任意的、属于某一如果任意的、属于某一语言类语言类的的语言在某一语言在某一特定运算特定运算下所得到的语下所得到的语言仍然是言仍然是同类同类语言语言: 该该语言类语言类对该运算具有对该运算具有封闭性封闭性有效封闭性 根据多个语言的根据多个语言的(文法文法)描述描述, 若可以构造出若可以构造出给定运算给定运算下所获得下所获得的的同类语言同类语言的的(文法文法)描述描述 此语言类对该运算是此语言类对该运算是有效封闭有效封闭的的(有效封闭性有效封闭性)

60、。问题本质问题本质:文法的构造文法的构造存在文法存在文法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或者