形式语言简介

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

2、)该语言所包含的该语言所包含的所有句子所有句子。l这是这是形式语言形式语言所研究的问题。所研究的问题。l接收一个语言，目的就是使用某种接收一个语言，目的就是使用某种自自动机模型动机模型来来接收接收句子，该模型所接收句子，该模型所接收的所有句子，也形成一个语言。的所有句子，也形成一个语言。l这是这是自动机自动机所研究的问题。所研究的问题。 l本章介绍本章介绍形式语言形式语言的基本内容。的基本内容。语言的形式定义语言的形式定义l设设 是一个是一个字母表字母表， l l * *, , l l称为称为字母表字母表 上上的一个的一个语言语言, , w w l l, w, w称为语言称为语言l l的一个的

3、一个句子句子。2.1 例子语言例子语言l括号匹配串的语言。括号匹配串的语言。 该语言是指所有的左括号和右括号相该语言是指所有的左括号和右括号相匹配的串的集合；匹配的串的集合； ( )，( )，( )( )等等都是该语言的句子等等都是该语言的句子 )( ，( )等等不是该语言的句子。等等不是该语言的句子。 l如何如何产生产生这个语言呢？这个语言呢？ 即如何即如何产生产生该语言所有句子呢？该语言所有句子呢？l实际上，就是需要给出语言中句子的实际上，就是需要给出语言中句子的构造（形成）规则构造（形成）规则。l递归定义递归定义提供了语言的良好的定义方提供了语言的良好的定义方式，使得语言中的句子的构造规

4、律较式，使得语言中的句子的构造规律较明显。明显。l可以使用多种方法可以使用多种方法描述描述构造规则。构造规则。l自然语言自然语言的描述方式，采用如下的的描述方式，采用如下的 递归规则：递归规则：( )是该语言的最基本的句子；是该语言的最基本的句子；若若s是句子是句子,则则(s)是句子；是句子；若若s是句子是句子,则则ss是句子；是句子；l这些规则称为这些规则称为形成规则形成规则，根据这些规则，根据这些规则，可以可以 (1)产生该语言的任意的句子；产生该语言的任意的句子； (2)判断某个判断某个串串是否是该语言的句子。是否是该语言的句子。例如l可以产生句子可以产生句子（）（） 而推断串而推断串

5、（）（） 不是句子。不是句子。l规则规则(的个数的个数)是有限的，但可以产生无是有限的，但可以产生无限个句子和长度无限的句子；限个句子和长度无限的句子；l因为规则是因为规则是递归递归的。的。bnf的描述方式的描述方式l巴科斯和诺尔采用的巴科斯和诺尔采用的巴科斯巴科斯-诺尔范式（诺尔范式（bnf-backus-naur form）描述规则描述规则：l:= ( )l:=()l:= l使用尖括号使用尖括号“”包括起来的部分，作包括起来的部分，作为一个整体来看待，表示某个语法成分为一个整体来看待，表示某个语法成分 需要使用字母表中的字母来定义其构成需要使用字母表中的字母来定义其构成l符号符号“:=”是

6、是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是该语言

9、的基本的句子；是该语言的基本的句子；若若s是句子是句子,则则00s是句子。是句子。 形式化的描述方式：形式化的描述方式： s00 s00s 问题：问题：将产生式将产生式sss换成换成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/ 四个产生式四个产生式的左边是相同的符号，可以合并为的左边是相同的符号，可以合并为 a+|-|*|/ +、-、*、/ 称为称为a的的侯选式侯选式。 e i eeae e(e)也可以记为：

11、也可以记为： 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)代表的是带小括号的表达式。代表的是带小括号的表达式。表示：先算因子，再表示：先算因子，再* *、/ /，最后，最后+ +、- -。 如果使用如果使用% %代表模运算代表模运算( (即取余数运算即取余数运算) )、使用使用 代表指数运算，则有代表指数运算，则有 e

12、e+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|t u|v|w|x|y|zd0|1|2|3|4|5|6|7|8|9思考：上例是从标识符的上例是从

13、标识符的形成角度形成角度思考问题。思考问题。从标识符的从标识符的定义定义角度考虑，则？角度考虑，则？注意 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-42-4c c语言中简单变量的说明语句的定义。语言中简单变量的说明语句的定义。

14、c c语言中的说明语句形式为：语言中的说明语句形式为： type type 变量名表；变量名表； type type 变量名表；变量名表； type type 变量名表；变量名表；产生式为：产生式为： ssssss|p|p pt v pt v； tint|char|floattint|char|float v vv,vv,v|i |i il|il|id l d思考pascalpascal语言的简单变量的说明语句的形成。语言的简单变量的说明语句的形成。 var 变量名表变量名表: type; 变量名表变量名表: type ; 变量名表变量名表: type; 2.2 文法和语言的关系文法和语言的关

15、系语言的定义语言的定义文法的定义文法的定义文法与语言的关系文法与语言的关系再次强调：再次强调： 语言就是字母表上的字符串语言就是字母表上的字符串组成的一个集合。组成的一个集合。 语言中的字符串称为语言中的字符串称为句子句子。 文法的作用就是产生一个语言。文法的作用就是产生一个语言。 有穷语言的表示较容易。有穷语言的表示较容易。 即使语言中的句子的组成没有什即使语言中的句子的组成没有什么规律，也可以使用么规律，也可以使用枚举枚举的方式列的方式列出语言中的所有句子。出语言中的所有句子。 对于对于无穷语言无穷语言，需要使用有穷描述的，需要使用有穷描述的方式表达。方式表达。 需要从语言的句子的一般构成

16、规律去需要从语言的句子的一般构成规律去考虑问题。考虑问题。 从语言的从语言的有穷描述有穷描述来表达语言的方法来表达语言的方法对对大多数语言大多数语言是有效的。是有效的。 在（使用计算机）判断一个字符在（使用计算机）判断一个字符串是否是某个语言的句子时串是否是某个语言的句子时( (语法语法分析分析) ) 从句子和语言的从句子和语言的结构特征结构特征上着手上着手是非常重要的。是非常重要的。 对于语言，可以在字母表上，按照一对于语言，可以在字母表上，按照一定的构成规则，根据语言的结构特点，定的构成规则，根据语言的结构特点，可以定义一个产生该语言的可以定义一个产生该语言的文法文法。 使用使用文法文法作

17、为相应语言的有穷描述，作为相应语言的有穷描述，不仅可以描述出语言的不仅可以描述出语言的结构特征结构特征，而且，而且可以可以产生产生这个语言的这个语言的所有句子所有句子。定义定义2-1 短语结构文法短语结构文法(文法文法)的定义的定义文法文法g是一个四元式，是一个四元式， g=(，v，s，p) 是一个有限字符的集合是一个有限字符的集合(字母表字母表)，它的，它的元素称为字母或者终结符；元素称为字母或者终结符； v是一个有限字符的集合是一个有限字符的集合-非终结符集合，非终结符集合，它的元素称为变量或者非终结符；它的元素称为变量或者非终结符；短语结构文法短语结构文法(文法文法)的定义的定义 sv，

18、称为文法的开始符号；，称为文法的开始符号； p是有序偶对是有序偶对(，)的集合，其中的集合，其中是集是集合合(uv)上的字符串，但至少包含一个上的字符串，但至少包含一个非终结符；非终结符；是集合是集合(uv)*的元素。的元素。 一般，将有序偶对一般，将有序偶对(，)记为记为，称，称为产生式；为产生式； 如果有如果有，称之为空串产生式或者，称之为空串产生式或者产生式。产生式。 如果如果有有abab，称之为单产生式。，称之为单产生式。 一个产生式的左边可能不只一个符号；一个产生式的左边可能不只一个符号； 第一个产生式的左边只能有一个符号，第一个产生式的左边只能有一个符号，就是就是开始符号开始符号s

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

20、串 = pvr ，=pur(p和和r可能同时为可能同时为) 而而vu是文法是文法g的一个产生式的一个产生式,则称则称可以可以直接推导出直接推导出 ， 记为记为= ，既，既 pvr =pur。推导的实质推导的实质 产生式的产生式的右边右边替换替换产生式的产生式的左边左边 非终结符非终结符代表在推导的过程中可以被代表在推导的过程中可以被替代的符号，替代的符号， 终结符终结符代表在推导的过程中不可以被代表在推导的过程中不可以被替代的符号。替代的符号。 推导推导的的逆逆过程称为过程称为归约归约。 与与pvr =pur对应，称串对应，称串pur可以直可以直接归约成串接归约成串pvr 记为记为pvr +z

21、 表示表示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 一定都成立吗一定都成立吗？最左推导和最右推导最左推导和最右推导 如果在推导的过程中，如果在推导的过程中，每一步每一步都都是将推导产生的串的是将推导产生的串的最左边最左边的非终的非终结符代替掉结符代替掉-最左推导最左推导

22、 如果每一步都是将推导产生的串如果每一步都是将推导产生的串的最右边的非终结符代替掉的最右边的非终结符代替掉-最右最右推导推导(规范推导规范推导)， 当然，还有其它方式的推导过程当然，还有其它方式的推导过程（例如混合）（例如混合） 而而最左推导最左推导和和最右推导最右推导是比较常用是比较常用的推导方式。的推导方式。句型和句子 对于文法对于文法g，如果，如果s=*，则称，则称是文法的一个是文法的一个句型句型， 若若 * *, , 称为称为句子句子。定义定义2-3 语言的定义语言的定义 给定文法给定文法g，有开始符号，有开始符号s，则把，则把s可可以推导出所有句子的集合，称为由文法以推导出所有句子的

23、集合，称为由文法产生的语言，记为产生的语言，记为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)约定：约定： 第一个产生式左边的符号，就是开第一个产生式左边的符号，就是开始符号（始符号（可以不是可以不是s）； 大写的英文字母代表非终结符大写的英文字母代表非终结符。 对于文

24、法（对于文法（g），只需给出该文法的），只需给出该文法的所有产生式即可。所有产生式即可。产生括号匹配语言的文法可以写成产生括号匹配语言的文法可以写成 s( ) s(s) sss 还可以再简单写成还可以再简单写成 s( )|(s)|ss 文法和语言的文法和语言的3类问题类问题 已知已知文法文法,得到该文法产生的得到该文法产生的语言语言 已知已知语言语言,构造产生该语言的构造产生该语言的某个某个文法文法 判断判断一个语言是否由某一个文法产生一个语言是否由某一个文法产生关系关系1： 文法文法 sasa|bsb|c| 产生的语言是什么？产生的语言是什么？ s能够产生的所有句子，需要考能够产生的所有句子

25、，需要考虑虑3个产生式个产生式所有可能使用情况所有可能使用情况 注意注意对称性对称性关系关系2：构造产生语言构造产生语言l的文法。的文法。 l= wwt|wa,b,c+其中：其中：wt是是w的逆（反序）的逆（反序）思考：思考：产生下列语言的文法：产生下列语言的文法： l1=anbn|n0 l2=anbn|n0关系关系3： 文法文法 s0b|1a a0|0s|1aa b1|1s|0bb是否产生的语言是否产生的语言l： l=|0,1+， 且且中有中有相同多相同多的的0和和1？注意： 一个语言一个语言可以可以由多个不同的文由多个不同的文法产生。法产生。 一个文法一个文法只能只能产生一个语言。产生一个

26、语言。例例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相同相同。 2.3chomsky对文法的分类对文法的分类 chomsky chomsky对文法进行了分类；对文法进行了分类； 对语言的分类，是根据产生语言的对语言的分类，是根据产生语言的文法的分类进行的文法的分类进行的0型文法 对于

27、一般的短语结构文法对于一般的短语结构文法(psg) g=(，v，s，p) g称为称为0型文法，对应的型文法，对应的l(g)称为称为0型语言或者短语结构语言型语言或者短语结构语言(psl)、递归可枚举集递归可枚举集。1型文法 如果对于任意如果对于任意p，均有，均有| | |成立，则称成立，则称g为为1型文法，或型文法，或上下文相关文法上下文相关文法(csg)。 对应的对应的l(g)称为称为1型语言或者上型语言或者上下文相关语言下文相关语言(csl)。1型文法1型文法产生式的标准形式为：型文法产生式的标准形式为： yazyz其中：其中：av； y,z(v)*， (v)+；1型文法 可以证明，任意的

28、可以证明，任意的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型语言或型语言或 右线性

29、语右线性语言言rll或或 正则语言正则语言rl。 四类文法和对应的四类四类文法和对应的四类语言语言之间是之间是真包含真包含关系。关系。 思考思考 如果文法如果文法g有有产生式，则产生式，则g g是是 型文法型文法? ?文法分类判断方法：文法分类判断方法： 文法文法g=(，v，s，p)，则，则 1) g是短语结构文法；是短语结构文法； 2) 如果文法如果文法g的所有产生式的左的所有产生式的左边边长度长度小于等于右边长度部分，小于等于右边长度部分，那么那么g是是上下文相关文法上下文相关文法； 3) 如果上下文相关文法如果上下文相关文法g的所有产生的所有产生式的左边都是式的左边都是一个非终结符一个非

30、终结符，那么，那么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

31、。 形如形如的产生式称为空产生式，的产生式称为空产生式，也可称为也可称为产生式产生式。 csg、cfg和和rg，都不能含有，都不能含有空产生式，所以任何空产生式，所以任何csl、cfl和和rl中都不包含中都不包含(空句子空句子)。 如果允许在如果允许在csg、cfg和和rg中中含有含有空产生式空产生式， 也就允许也就允许csl、cfl和和rl中包含中包含空句子空句子。 一般地，如果语言一般地，如果语言l没有空句子，则没有空句子，则 文法中增加产生式文法中增加产生式 s 就可以产生空句子。就可以产生空句子。文法文法扩充分类扩充分类： 设文法设文法g=(，v，s，p) 如果如果s不出现在任何产生式

32、的右不出现在任何产生式的右部部，则，则(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+bg：sab|as|l(g)=a+b, , a+增加增加了空句子了空句子，但，但多多产生句子产生句子a+定理2-1 文法文法g=(，v

33、，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 思考 文法的文法的

34、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中

35、产生式的右部中产生式的右部 增加的增加的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，则存在一个，则存

36、在一个 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。 除了生成空句子除了生成空句子外，空产生式可外，空产生式可以不用于其他句子的推导中。以不用于其他句子的推导中。 空句子空句子在一个语言中的存在并不在一个语言中的存在并不影响该语言的有穷描述。影响该语言的有穷描述。 如果

37、如果允许允许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文法产生语言文法产生语言例例 文法文法 s0s s0产生语言产生语言l=0n|n0分析 如果开始使用第如果开始使用第2个产生式个产生式s0，则，则s=0，就不能再往下进

38、行推导了。，就不能再往下进行推导了。 产生产生基本句子基本句子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 则称为则称为直接递归直接递归的非终结符。的非终结

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

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

41、关文法文法g g有有ss，则则 该该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 这对于任何这

42、对于任何n1n1都是成立的；都是成立的；总之，该文法产生语言总之，该文法产生语言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 sb

43、sb sbsb思考(1)(1)文法文法 sasasasa sbsb sbsb 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|n=0=0。一般l对 任 意 的对 任 意 的 a a , , b b + +， 可 以 使 用， 可 以 使

44、 用aab|aabaab|aab来产生来产生 a an nb bn n|n|n00；l对 任 意 的对 任 意 的 a , ba , b + +， 可 以 使 用， 可 以 使 用aa|b|aa|baaa|b|aa|ba来产生来产生aa，bb+ +；l对任意的对任意的aa+ +，可以使用，可以使用aa|aaaa|aa来产生来产生aan n|n|n00；l对任意的对任意的a a，bb+ +，可以使用，可以使用 aaaa|babaaaa|bab来产生来产生 w wa aw wt t| |w wa,ba,b + + 注意：注意：l不能使用不能使用 aaaa2 2l代表代表 aaaaaal不能使用不能

45、使用 aaaan n(n1) (n1) 或或 aaaa + +l来代表来代表 a a可以产生任意多个可以产生任意多个a a。思考：字母表为思考：字母表为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个个数字符号组成的，但不允许以数字符号组成的

46、，但不允许以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|8m|9m例2-11构造文法构造文法g g，产生语言，产生语言w|ww|w是实数是实数 略。略。例2-12 s0b|1a s0b|1a a0|0s|1aa a0|0s|1aa b1|1s|0bb b1|1s|0bb证明：证明：l(g)=|0l(g)=|0，11+ +，且，且中中有相同多的有相同多的0 0和和11。l证明提示：证明提示： 使用数学归纳

47、法（句子长度）使用数学归纳法（句子长度）l证明过程证明过程 略。略。根据下推自动机根据下推自动机00分析分析 所有产生式的的使用情况所有产生式的的使用情况: 顺序和次数顺序和次数思考：思考： 上下文相关上下文相关上述文法的后上述文法的后3 3个产生式个产生式 bbbbbbbb bcbc bcbc cccc cccc是否可以改为是否可以改为 bb ccbb cc上例还可以简化为：上例还可以简化为： sabc|asbsabc|asbc c cbbc cbbc bbbb bbbb 文法的产生式的左边可以有多个符号文法的产生式的左边可以有多个符号思考：思考：补充文法g使得使得l(g)= aan nb

48、bn nc cn n|n|n00 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=12.5 推导树推导树对于上下文无关文法，对于上下文无关文法， 利用推导树也可以表示句型的产利用推导树也可以表示句型的产生过程。生过程。例-16 s0b|1a a0|0s|1aa b1|1s|0bb对于串对于串0011的产生过程：的产生过程：推导过程推导过程最左推导：最左推导： s=0b=00bb=001b=0011 最右推导：最右推导： s=0b=00bb=00b1=00

49、11推导树表示推导推导树表示推导 s s 0 b 0 b 0 b b 0 b b 1 1 1 1无用非终结符无用非终结符一个无关文法一个无关文法g,av 如果如果a不出现在任何形如不出现在任何形如 s=*uav=+uwv的推导之中的推导之中-a为为无用非终结符无用非终结符。其中：其中：u ，w ，v *。有用非终结符有用非终结符a，必须同时满足，必须同时满足:(1) a必须出现在某个句型中；必须出现在某个句型中；(2)从从a开始，能够产生终结符号串开始，能够产生终结符号串无用的产生式无用的产生式 如果一个产生式如果一个产生式( (产生式的左边产生式的左边或右边或右边) )包含有无用的非终结符，

50、包含有无用的非终结符，则该产生式就是则该产生式就是无用的产生式无用的产生式。 应该将无用的产生式应该将无用的产生式删除删除。思考思考如果文法如果文法g的开始符号的开始符号s是无用的非终是无用的非终结符号，则结符号，则l(g)=?思考判断判断a是有用的非终结符号的算法。是有用的非终结符号的算法。 请参见参考文献请参见参考文献 形式语言与自动机理论形式语言与自动机理论 （蒋宗礼蒋宗礼 姜守旭姜守旭 清华大学出版社）清华大学出版社）2.6 空串定理空串定理 上下文无关文法上下文无关文法g ，存在一般的空，存在一般的空串产生式串产生式a，则存在另一个上下文，则存在另一个上下文无关文法无关文法g1，使得

51、：，使得：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共有

52、共有2k个。个。 最后，去掉所有的空串产生式和最后，去掉所有的空串产生式和无用的产生式无用的产生式就得到就得到g1。 考虑考虑g产生句型产生句型的推导树的推导树t: 若若的推导中使用了空串产生式，则的推导中使用了空串产生式，则树树t中有以中有以为标志的叶节点，为标志的叶节点， 删除删除树树t中的所有产生中的所有产生的的子树子树，得到，得到树树t1，而它刚好是文法，而它刚好是文法g1产生串产生串的的推导树，所以，推导树，所以，l(g)=l(g1)。例文法：文法： 改造成等价的改造成等价的g：sabcd sacdcrs csb aaaa dddd sdr sd 证明（3） 假设假设l(g)，则要增

53、加新的开始，则要增加新的开始符号符号s和两个产生式和两个产生式 ss， s；再消除其余的空；再消除其余的空串产生式，即可。串产生式，即可。2.7 消除左递归消除左递归l在在某些情况某些情况下下,需要消除一个无关文法需要消除一个无关文法中的中的左递归左递归。l递归的作用是产生无穷的语言，消除递归的作用是产生无穷的语言，消除左递归，只是将左递归，只是将左递归左递归改造为改造为右递归右递归。l左递归包括左递归包括直接直接的和的和间接间接的左递归。的左递归。2.7.1 消除直接左递归消除直接左递归l直接左递归的产生式形式为直接左递归的产生式形式为 aav 其中：其中：av，v(uv)+。l递归的产生式

54、可以产生串递归的产生式可以产生串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)(v1|v2|

55、vn)*l增加一个新的非终结符增加一个新的非终结符b，构造，构造无左递归文法：无左递归文法：aw1b|w2b|wmb|w1|w2|wmbv1b|v2b|vnb|v2|v2|vnl某些文法可能没有直接左递归，某些文法可能没有直接左递归，但可能会有但可能会有间接左递归间接左递归。 saa asb|b2.7.2 消除间接左递归（消除间接左递归（自学自学）lg是一个上下文无关文法，首先是一个上下文无关文法，首先使用空串定理；然后将文法使用空串定理；然后将文法g中中的所有非终结符按的所有非终结符按任一顺序排列任一顺序排列为为a1，a2，an，根据下列，根据下列算算法法消除可能存在的间接左递归。消除可能存

56、在的间接左递归。lfor i：=1 to n do lbeginl for j：=1 to i-1 do l beginl 将将ai ajw的产生式的产生式改写改写为：为：l aiv1w|v2w|vkw ；l (v1，v2，vk是是aj的侯选式的侯选式)l endl 消除消除ai产生式的直接左递归；产生式的直接左递归； l endl最后，删除最后，删除无用无用的产生式，就可的产生式，就可以得到没有间接左递归的文法。以得到没有间接左递归的文法。l该算法思想是将推导过程中可能该算法思想是将推导过程中可能出现的左递归，在文法的产生式出现的左递归，在文法的产生式中就中就体现体现出来，产生式的改写实出来

57、，产生式的改写实际上是推导的体现际上是推导的体现-用用aj的侯选的侯选式将式将aj代替代替掉。掉。l为方便实现，将上述算法进行改为方便实现，将上述算法进行改写。写。lg是一个上下文无关文法，将是一个上下文无关文法，将文法文法g中的所有非终结符按任中的所有非终结符按任一给定的顺序排列为一给定的顺序排列为la1，a2，anl那么，文法的每个产生式是那么，文法的每个产生式是aiajw的形式（对于的形式（对于aiaw形形式的产生式，不用考虑，因为它式的产生式，不用考虑，因为它不会导致左递归的出现）不会导致左递归的出现）.l而而i和和j的的大小关系大小关系只可能有只可能有3种情种情况：况：laiajwl

58、 ij 称该产生式是称该产生式是向下向下的；这类的；这类产生式需要产生式需要替代替代，用，用aj的侯选式的侯选式将将aj替掉，若出现了直接左递归，替掉，若出现了直接左递归，还需要将直接左递归还需要将直接左递归消除消除；l首先考虑非终结符首先考虑非终结符a1：la1ajwl 1j 产生式是向上的产生式是向上的l 1=j 该产生式是直接左递归的；该产生式是直接左递归的；消除直接左递归消除直接左递归l对于非终结符对于非终结符a2:la2ajw 2j 该产生式是向下的；这类产生该产生式是向下的；这类产生式需要替代，式需要替代，ll对于非终结符对于非终结符an：l anajw n=j 消除直接左递归；消

59、除直接左递归； nj 向下的；这类产生式需要需要替代，向下的；这类产生式需要需要替代，用用aj的侯选将的侯选将aj替换掉，若出现了直接左替换掉，若出现了直接左递归，还需要将直接左递归消除；递归，还需要将直接左递归消除；l最后，删除多余的产生式，得到最后，删除多余的产生式，得到的文法就的文法就没有了左递归没有了左递归，包括直，包括直接和间接的左递归。接和间接的左递归。2.8 上下文无关文法的另一种表示上下文无关文法的另一种表示l文法存在另外一种表示方法：文法存在另外一种表示方法： 使用使用表示表示* ； 使用使用表示表示的出现可有可无的出现可有可无(等等价于价于)l左递归的产生式左递归的产生式

60、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|92.9 语言之间的运算及运算封闭性语言之间的运算及运算封闭性 l对对简单语言简单语言进行语言的进行语言的运算，运算