编译原理与实现02第2章文法和语言.ppt

第二章 文法和语言,编译过程的核心就是翻译，这是一个十分复杂的信息加工过程，其加工的对象是用某种高级语言编写的程序。对于一个英文翻译来说，首先必须对英文有很深的了解，掌握英文的语法和词汇，才能进行翻译。而编译程序的任务就是将高级语言编写的程序翻译成机器语言程序，因此，在学习和掌握编译技术之前，就需要对高级语言有深刻的了解。首先要了解如何确切地描述或定义一种程序设计语言，其次才能识别和分析这种语言。20世纪50年代，语言学家Noam Chomsky（乔姆斯基）提出了一个用来描述语言的数学系统，把用一组数学符号和规则来描述语言的方式叫做形式描述，而把能用数学符号和规则描述的语言称为形式语言。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。程序设计语言就是形式语言,2.1 字母表和符号串,介绍文法和语言之前，首先介绍符号、符号串等基本概念。任何一种语言都是由该语言的基本符号所组成的符号串集合的子集。例如，英语的基本符号有26个字母和一些标点符号，由这些基本符号所组成的各种可能序列的符号串构成一个无穷的集合，而英语就是这个集合的子集。同理，C语言的基本符号有if,while,for,字母、数字和+、-、（、）、=等分界符，由这些符号组成的各种可能序列的符号串构成一个无穷的集合，而C语言就是这个集合的子集。任何一个C语言程序都是定义在这个集合上的符号串，即任何一个C语言程序都是由这些基本符号所组成的序列。,字母表,“字母表”是元素的非空有穷集合。字母表中的每个元素称为“符号”，因此“字母表”也可称为“符号集”。典型的符号有字母、数字、各种标点符号和各种运算符。例如，集合a，b，c，+，*是一个含有5个符号的字母表，而字母表0，1只有两个符号。,符号串,“符号串”是由字母表上0个或多个符号所组成的任何有穷序列。例如有字母表a，b，c，+，*，则a,b,c,+,*,aa,ab,ac,a+,a*,ba,bb,bc,b+,b*,aaa,bbb等等都是该字母表上的符号串，而所有二进制数都是定义在字母表0，1上的符号串。要注意也是字母表上的符号串，它由0个符号组成。显然，一个字母表上的全部符号串所组成的集合是无穷的。,2.1.3 符号串及其集合的运算1,1.符号串的长度：指符号串x中所含符号的个数，记为|x|。如|abc|=3，|abc+*abc|=8，而|=02.符号串相等：若x、y是字母表上的两个符号串，那么当且仅当组成x的各符号与组成y的各符号依次相等时，则符号串x与符号串y相等，记作x=y。如：当x=abbc，y=abbc 时，则x=y；而当x=ab，y=ba 时，则xy3.符号串的前缀：指从符号串x的末尾删除0或多个符号后得到的符号串，如u、uni、university都是university的前缀。4.符号串的后缀：指从符号串x的开头删除0或多个符号后得到的符号串，如ty、sity、university都是university的后缀。,2.1.3 符号串及其集合的运算2,5.符号串的子串：指从符号串x的开头和末尾删除0或多个符号后得到的符号串，如ver是university的子串,符号串的前缀、后缀都是它的子串。6.符号串的连接：若x、y是两个符号串，则xy表示连接，是将符号串y连接在符号串x的后面。若x、y是字母表上的两个符号串，则xy也是字母表上的符号串。例如：x=ab，y=ba，那么 xy=abba注意：连接没有交换率，即 xy yx 而对于空串有 x=x=x,2.1.3 符号串及其集合的运算3,7.集合的乘积运算：令A、B为两个符号串集合，A和B的乘积AB定义为：AB=xy|x A，y B例如：A=a，b B=c，d，则AB=ac，ad，bc，bd 对于空集合有有：A=A=A8.符号串的幂运算：若x是符号串，则x的幂运算定义为：X0=,x1=x,x2=xx,，xn=xxx=xx n-1=x n-1 x,其中 n0例如：x=abc,x0=,x1=abc,x2=abcabc,2.1.3 符号串及其集合的运算4,9.集合的幂运算：设A为符号串集合，则A的幂运算定义为：A0=A1=A A2=AA An=AAA=AA n-1=A n-1 A，其中 n0,例如：A=a，b，则 A0=A1=a,bA2=aa,ab,ba,bb,2.1.3 符号串及其集合的运算4,10.集合的正闭包和集合的闭包：设A为一个集合，则集合A的正闭包用A+表示，定义为：A+=A1 A2.A n 集合A的闭包用A*表示，定义为：A*=A 0 A+例如：A=a，b，则A+=a,b,aa,ab,ba,bb,aaa,aab,A*=,a,b,aa,ab,ba,bb,aaa,aab,一个集合的闭包比正闭包多个。,2.2 文法,在学习英语时，我们知道句子由主语、谓语组成，主语由冠词、形容词及名词组成等等，这就是说明句子组成的规则。而在形式语言里，这种规则可采用“:=”、“:=”这种形式来表示。分析一个句子是否正确，就是根据这些规则进行的。文法实际上就是描述语言语法结构的形式规则。,2.2.1 文法形式定义1,在表示文法时，要说明语言的语法成分，句子中的符号以及语法结构。例如，能够描述句子“the monkey ate the banana”的文法如下：,这些规则说明句子由主语和谓语组成，主语由冠词和名词等等，而冠词由the构成，名词由banana或monkey构成。在这个文法里，一共有8条规则，每条规则中在:=左边的符号其着语法成分的作用，它们可用:=右边的符号代替。而像the、ate、banana这样的符号只在规则中:=的右边出现，这些符号不能用其它符号代替。,:=:=:=:=:=:=:=:=,2.2.1 文法形式定义2,文法的形式定义：文法可表示为一个四元组 G=（Vn，Vt，P，Z）Vn是一个非空有穷集合，该集合中的每个元素称为非终结符号。如上例中的符号、等等。Vt是一个非空有穷集合，该集合中的每个元素称为终结符号。如上例中的符号the、ate、banana等等都是终结符号。并且VtVn=，即Vt集合与Vn集合的交集为空。而Vt和Vn并集VtVn就是该文法的字汇表（即字汇表字母表）。P是一个非空的有穷集合，它的每个元素叫做产生式或规则。产生式的形式为：或:=是产生式的左部且不能为空，是产生式的右部，并且、（VtVn）*，“”或”“:=”含义相同，表示“定义为”或“由组成”。Z是Vn集合的一个特殊的非终结符号，称为文法的识别符号或开始符号。它至少必须在某个产生式的左部出现一次。就是上例文法的识别符号。,2.1 文法形式定义3,文法分4种类型（见2.13小节），程序设计语言文法主要为2型文法，这种文法也叫上下文无关文法，本书后面说的文法都是指这种文法。在上下文无关文法中，产生式的左部是一个非终结符号，而右部是由终结符号和非终结符号组成的有穷符号串。这样只要给出产生式集合，所有产生式的左部符号就构成了非终结符号集合Vn，而只出现在产生式右部的那些符号构成终结符号集合Vt，因此，在表示文法时只需给出规则集合并指定识别符号即可。为了进一步简化，在给出规则集时，可约定将左部符号为识别符号的规则作为规则集合的第一条规则，这样表示文法时只需给出规则的集合即可。显然，上例就是一个简化的文法表示。,2.1 文法形式定义4,例2.1，按文法形式定义表示上例文法。解：根据文法的形式定义，文法 G1=（Vn，Vt，P，Z）非终结符号集合:Vn=句子，主语，谓语，冠词，名词，动词，直接宾语终结符号集合:Vt=the，ate，banana，monkey 产生式集合P由下面8条规则组成:识别符号Z：,the ate banana monkey,2.1 文法形式定义5,例2.2，有如下简化表示文法，只给出规则集，写出该文法的终结符号集合、非终结符号集合和识别符号。,1.2.3.4.05.16.27.38.49.510.611.712.813.9,解：根据简化约定，可确定：非终结符号集合：Vn=,终结符号集合：Vt=0,1,2,3,4,5,6,7,8,9识别符号Z：,文法的EBNF表示,所谓文法的EBNF表示，就是在书写文法的规则时，可采用一些特殊的符号“|”、“”和“”、“”、“（”和“）”、“”和“”来表示文法，这些符号叫做元符号。其中“”和“”、“”、“（”和“）”、“”和“”这些元符号总是成对出现。下面介绍各种元符号的含义。,1.元符号“|”：表示“或”.对于具有相同左部的那些规则 如 1、n，可以缩写为:1|2|n例2.3，对例2.2文法的13条规则可缩写成：:=:=|:=0|1|2|3|4|5|6|7|8|9,文法的EBNF表示,2.元符号“”：用于括起由中文字组成的非终结符号或由多个字母组成的符号。如、等等。3.元符号“”和“”：表示可重复连接，tnm表示符号串t可重复连接n到m次，而t表示符号串t可重复连接0到无穷次。例如，13 与|相同 EE+T|T 与 ET+T 相同而字母打头、后面可跟数字或字母的不超过8个字符的标识符文法则为：|07,文法的EBNF表示,4.元符号“”和“”：表示括起的内容可有可无。如t表示符号串t可有可无。例如：IF THEN IF THEN ELSE 可写成：IF THEN ELSE 5.元符号“（”和“）”：表示括号内的成分优先。常用于在规则中提取公因子。例如，Uxy|xw|xz 可写成：Ux（y|w|z）从上述有关元符号的定义和例子可看出，这些元符号为表示文法提供了很大方便。,2.3 推导,给定了文法，就可以从文法的开始符号并根据文法规则进行推导。通过推导可产生文法定义的句子。例如，根据例2.1文法的规则，可从开始符号推出，又根据规则，可从推出，这个推导过程可表示成如下：=其中“=”表示一步推导,上述推导过程表示经过两步推导，从可推导出。,直接推导,假定G是一文法,是该文法的一个产生式，现有一含非终结符号的符号串xy，其中x和y是该文法的任意符号串(可为空),推导就是利用产生式将符号串xy中的非终结符号用替换，从而得到符号串xy。表示为：xy=xy其中“=”表示一步推导。我们称xy直接推导出xy,或xy直接产生xy。若从反方向看，则称xy直接归约到xy。,直接推导,例如有文法 1）:=2）:=|3）:=0|1|2|3|4|5|6|7|8|9对符号串利用规则1可直接推导出：=对符号串利用规则2可直接推导出：=对符号串利用规则3可直接推导出2：=2 将上述三个推导连接起来，可得如下推导过程：=2在这个推导过程中，直接推导出，直接推导出，直接推导出2。,推导,如果存在一直接推导序列0=2=n，其中n0,那么我们说 0产生n或n归约到 1,并记作0=+n,推导长度为n。如果有0=+n 或0=n,即n 0,则记作0=*n。例如，从开始，分别利用规则1、2、2、3、3，可产生如下推导过程：=2=23这个推导过程可记作：=+23，其推导长度n=5，表示产生23，或23归约到。而从到的推导，无须使用任何规则，可记作：=*，其推导长度n=0。,规范推导,规范推导也叫最右推导，即每步推导只变换最右边的非终结符号。其形式定义为：对于直接推导xy=xy来说，如果y只包含终结符号或为空符号串,那么就把这种推导称为规范推导或最右推导（如果只包含终结符号或为空符号串,则为最左推导），且记作:xUy=|=xuy,其中y Vt*。如果推导0=+n的每一步都是规范的,那么推导0=+n称为规范的,且记作:0=|=+n例如，有如下推导序列：=3=3=23该推导序列就是规范推导，且可记作：=|=+23,2.4 句型和句子,推导产生的结果可能是句型，也可能是句子。假设文法G的识别符号为Z，记为GZ，其字汇表VtVn，则句型、句子的定义如下：1.如果Z=*x,且xV*,则称x是文法GZ的一个句型。2.如果Z=+x,且xVt*,则称x是文法GZ的一个句子。,句型是从识别符号开始经过0步或多步推导出的可由终结符号和非终结符号组成的符号串。而句子是从文法的识别符号推导出来的完全由终结符号组成的符号串。句子是特殊的句型，是完全由终结符号组成的句型。从文法的开始符号利用规则进行推导，一旦推导出句子，推导过程就不能再继续进行，因为句子中没有非终结符号。假设符号串是某一推导的结果，那么，是句子的充分必要条件是从到的推导长度大于等于，即 Z=+x,而不可能是Z=*x。这是因为识别符号Z是非终结符号，而是终结符号串，显然，不可能与相等，所以不可能经过步推导就等于。,2.4 句型和句子,在句型中，有一类句型叫做规范句型，它是能用规范推导产生的句型。每一个句子都有一个规范推导,但并非每一个句型都有规范推导，只有那些能用规范推导产生的句型才是规范句型。例如，对于例2.3中的文法，有句型“2”,其推导过程如下:=2其中第步推导变换的不是最右边的非终结符号，不满足规范推导的要求，所以句型“2”不是规范句型。而对于句型“3”，其推导过程如下:=3=3其中的每一步推导都变换的是最右边的非终结符号，所以，句型“3”是规范句型。,2.5 语言,一个文法GZ所产生的所有句子的集合L(GZ),称为文法GZ所定义的语言,即:L(GZ)=x|x Vt*,且Z=+x 一个文法所定义的语言是该文法的终结符号集合Vt上的所有符号串组成的集合的一个子集,该子集中的每个符号串都可从识别符号开始经过至少一步推导出来，即:L(GZ)Vt*例如，对例2.1的文法G，其语言只有下面4个句子：the monkey ate the banana the banana ate the monkey the monkey ate the monkey the banana ate the banana而例2.3中的文法，其语言是所有无符号整数，句子是无穷的。文法和语言有如下关系：1)给定一个文法,就能从结构上唯一的确定其语言,即:GL(G)2)给定一种语言,能确定其文法,但不唯一,即:LG1 或G2 或。,2.5 语言,例例如，对例2.3的文法G，其语言为所有无符号整数组成的集合，即：L(G)=Vt+它是包括允许以“0”开头的所有正整数。例2.4，已知文法GZ为：1)ZaZb2)Zab 或写成 Z aZb|ab求该文法确定的语言。解：从识别符号开始推导，反复用规则1可得:Z=aZb=a2Zb2=an-1 Zbn-1最后用规则2可得:Z=aZb=a2Zb2=an-11 Zbn-1=anbn所以该文法确定的语言为：L(GZ)=(anbn|n1),2.5 语言,例2.5，已知语言为:L(G)=abna|n 1，构造产生该语言的文法。解：根据语言的形式，可构造其文法G为:ZaBaBBb|b还可以构造文法G1为:ZaBaBbB|b从例2.5可看出，G与G1是两个不同的文法，但它们都可以描述语言abna|n1。,如果两个不同的文法可描述相同的语言,那么我们称这两个文法为等价文法。例2.5的文法G和文法G1就是等价文法。等价文法的存在，对编译技术的实现有很大帮助，使我们能在不改变文法所确定的语言前提下，为了某种目的而改写文法。,2.6递归规则与递归文法,递归规则递归规则是指那些在规则的右部含有与规则左部相同符号的规则。例如：U:=xUy，右部含有与规则左部相同符号U，那么就是递归规则。如果这个相同的符号出现在右部的最左端，则为左递归规则。如 U:=Uy如果这个相同的符号出现在右部的最右端，则为右递归规则。如 U:=xU,给定了文法，就确定了语言。再看例2.1和例2.3中的文法，发现例2.1文法只产生两个句子，而例2.3的文法产生的句子却有无数个。句子的个数是有穷还是无穷取决于文法是否是递归的。,2.6.2递归文法,若文法中至少包含一条递归规则,则称文法是直接递归的。显然，例2.3中的文法就是直接递归文法。有些文法，表面看上去没有递归规则，但经过几步推导，也能造成文法的递归性，则称为间接递归。例如，有文法为:U:=Vx，V:=Uy|v 表面上看，该文法的每条规则都不是递归规则，但有推导过程U=Vx=Uyx，所以该文法为间接递归文法。对文法中的任一非终结符号,若能建立一个推导过程,推导所得的符号串中有出现了该非终结符号,则称文法是递归的;否则就是无递归的。递归文法使我们能用有穷的文法刻画无穷的语言。,2.6.2递归文法,例如，有文法GS:S:=aB|Bb，B:=a|b，该文法产生的语言为L(GS)=aa,ab,ba,bb，只有个句子，因为该文法不是递归的。例2.1的文法所描述的语言只有两个句子，也是因为它不是递归文法。而文法G有递归规则,属于递归文法，所以它所描述的语言为所有无符号整数，是无穷的。例2.6 判定如下文法所描述的语言是否是有穷的。ZaBaBbB|b解：因为文法中的第二条规则BbB|b是递归规则，所以该文法描述的语言是无穷的。该文法描述的语言为abna|n1。,2.7 短语、简单短语和句柄,短语、简单短语和句柄在分析中有着重要的作用，后面介绍自底向上的语法分析时就可看到如何找句柄是非常关键的。短语是句型的子串，是在句型的推导过程中能由某个非终结符号推导出的子串，而简单短语则是能由某个非终结符号直接推导出的子串。它们的形式定义如下：1.短语：设GZ是一文法,w=xuy是一句型,如果有 Z=*xUy 且U=+u,其中UVn,uV+，那么,我们称u是一个相对于非终结符号U的句型w的短语。2.简单短语：若有 Z=*xUy 且U=u，那么,我们称u是一个相对于非终结符号U的句型w的简单短语。3.句柄：任一句型的最左简单短语称为该句型句柄。,2.7 短语、简单短语和句柄,例2.7 对于文法G,确定句型1的短语、简单短语和句柄。解：首先构造句型1的推导过程如下：=11)由于=*,而=+1,对照定义，子串1是由非终结符号推出的，所以是相对的短语。2)由于=*,而=+数字串1,所以子串1是相对的短语。3)由于=*,而=1，且1是由非终结符号直接推出的，所以子串1是相对的短语,而且是简单短语。在句型1中,只有一个简单短语1,所以它就是该句型的句柄。,2.8 语法树,推导过程可用图来表示，这就是语法树，也叫推导树。语法树是一棵有序有向树，每个节点都有标记。根节点代表文法的识别符号；每个内部节点（非叶节点）表示一个非终结符号，其子节点由这个非终结符号在这次推导中所用产生式的右部各个符号代表的节点组成；每个末端节点（叶节点）代表终结符号或非终结符号，它们从左向右排列起来，构成句型。如果叶节点都是终结符号，则从左向右构成句子。推导过程不同，生成语法树的过程也不同，但最终生成的语法树是相同的。,例2.8 根据如下推导过程构造语法树。=3=3=23=23=123,解：构造语法树如图2.1所示。,数字串,图2.1 语法树,2.9 子树与短语,语法树的子树是由该树的某个节点（子树的根）连同它所有的后裔构成。子树与短语一一对应。要找一个句型的短语，可先画出该句型的语法树。若句型中某些符号按从左到右的顺序组成某个子树的末端节点，那么由这些末端节点组成的符号串，就是相对于子树根的短语。判明语法树中的每棵子树，那么每棵子树的末端节点自左向右组成的符号串，就是相对于子树根符号的短语。原则上语法树中有多少棵子树，就有多少个短语,例2.8 根据文法G，找句子123的短语、简单短语和句柄。解：首先画出产生句子123的语法树，见图2.1。该语法树共有7棵子树。子树1：树根，末端节点1、2、3，短语为123子树2：树根，末端节点1、2、3，短语为123子树3：树根，末端节点1、2，短语为12子树4：树根，末端节点1，短语为1子树5：树根，末端节点1，短语为1，且为简单短语、句柄子树6：树根，末端节点2，短语为2，且为简单短语子树7：树根，末端节点3，短语为3，且为简单短语,在这7个子树中，只有子树5、6、7的根节点与末端节点都是父子关系，所以这几个子树的末端节点形成的短语1、2、3都是简单短语。而子树5位于其中的最左端，所以短语1还是句柄。,2.10 由树构造推导过程,根据已有的语法树，即可从上而下、也可从下到上建立推导。如果按从上而下的方式建立推导，则从树根开始由上而下逐层地用子节点代替父节点。当一层中有两棵以上子树根时，原则上先选那一棵树根替换都可以，而每步都对最右边的树根符号替换，则构造出的推导是规范推导（最右推导）。我们还可以由下而上逐层地修剪子树末端节点来建立推导。当有两棵以上子树时，原则上修剪那一棵都可以，如果每次总是修剪最左边的子树，即相当于每步都对归约句型的句柄归约，则称为“最左归约”或“规范归约”。规范推导（最右推导）与规范归约（最左归约）互为逆过程。,例2.9，对图2.1所示的语法树，自底向上逐层地修剪子树末端节点来建立推导。解：语法树的末端节点形成的符号串为123，句柄 1，归约为数字句型23，句柄，归约为=3=3=23=23=123,2.11 文法的二义性,算术表达式的运算规则是乘除高于加减，if语句规定else就近配对，为什么呢？这是为了解决文法的二义性问题。前面我们介绍语法树时说过，推导过程不同，生成语法树的过程也不同，但最终生成的语法树是相同的，这是在文法没有二义的条件下才成立。如果一个文法所定义的句子中有某个句子或句型，它存在两棵不同的语法树，那么这个句子或句型是二义性的，该文法是二义性文法。,例如2.9，有文法GE：E=E+E|E*E|（E）|i，分析该文法是否为二义性文法。解：为了判断该文法是否为二义性文法，我们找一个句子i+i*i，如果能够构造出两个不同的语法树，则说明该文法是二义性文法。下面两个图是为句子i+i*i构造的两棵语法树，如图2.2(a)、(b)所示。由于这两棵语法树不同，所以可以肯定文法GE 是二义性文法。,2.11 文法的二义性,图2.2(a)语法树1 图2.2(b)语法树2,二义性产生的后果会导致分析结果不同，导致对句子的理解不同。在图2.2(a)语法树1中，根据规范归约构造的推导过程为：E=E+E=E+E*E=E+E*i=E+i*i=i+i*i在图2.2(b)语法树1中，根据规范归约构造的推导过程为：E=E*E=E*i=E+E*i=E+i*i=i+i*i由于图2.2(a)语法树1中的*先作为句柄归约，可理解成*优先于+进行运算，而图2.2(b)语法树2中的+先作为句柄归约，表示+优先于*进行运算。由于文法的二义性会造成不同的分析结果，所以算术表达式规定乘除高于加减，从而避免二义性。,2.11 文法的二义性,程序设计语言中的嵌套IF语句都要求ELSE与最近的IF配对，也是因为IF语句的文法存在二义性。例2.10，IF语句文法如下：=IFTHEN|IFTHENELSE|说明该文法是二义性文法。解：假设有一个IF语句嵌套的句型为：IFTHEN IFTHENELSE 根据文法可构造两棵语法树如图2.3(a)和图2.3(b)所示：,2.11 文法的二义性,图2.3(a)IF语句语法树1,图2.3(b)IF语句语法树2,由于这两棵语法树不同，所以该文法是二义性文法。图2.3(a)IF语句的语法树意味着ELSE和第2个THEN配对（就近配对），而图2.3(b)IF语句的语法树表示ELSE和第1个THEN配对。,2.11 文法的二义性,文法的二义性是不可判定的，即不存在一种算法，它能够在有限步内确切地判定一个文法是否是二义性的。但我们常常能找到一些句型，通过构造不同的语法树来判定文法的二义性，而且还能找到一些十分简单、并且不琐碎的条件，当文法满足这些条件时，就使我们确信文法是无二义性的。这些条件是无二义性的充分条件，不是必要条件。如在IF语句中，要求ELSE与最近的IF配对，在算术表达式中，规定乘除高于加减，就避免了其二义性。有时，我们还可以把一个二义性文法变换成一个等价的、无二义性文法。,例2.11，改写文法GE：E=E+E|E*E|（E）|i，使其无二义性。解：新添非终结符号T和F，将文法写成：E=T|E+T，T=F|T*F，F=(E)|i这样，就避免了二义性。用改写后的文法给出句i+i*i的语法树如图2.4所示。此时的语法树是唯一的。,图2.4 语法树,2.12 有关文法的实用限制,实用限制就是从实用的观点出发，对文法做一些必要的限制。首先，文法不能是二义性的，这是一种对文法的实用限制。另外，还有下面列出的一些限制条件：1)不能有U=U这样的有害规则。2)不能有多余规则：一是推导中始终用不到的规则。二是一旦使用某规则后无法推出终结符号的规则。检查有害规则比较容易，而要检查多余规则，则要检查文法中每一条规则左部的每个非终结符号U是否满足下述两个条件：1)U必须在某个句型中出现，即有：Z=*xUy2)必须能够从U推导出终结符号串，即U=+t，tVt*不满足这两个条件的规则就是多余规则。,2.12 有关文法的实用限制,例2.13，有文法：Z=Aa，A=Ca|Bb，B=Ba|a，C=Cb，D=b，去掉有害规则和多余规则。解：该文法中，由于非终结符号D不出现任何规则的右部且D不是开始符号，所以在句子的推导中不可能用到规则D=b，因此是多余规则，应该去掉。另外，规则C=Cb也是一条多余规则，因为一旦使用了这条规则以后，将使推导无穷地进行下去，即C=Cb=Cbb=Cbbb,无法推出终结符号串。而规则A=Ca因为会产生C，所以也要去掉。最后得到的文法为：Z=Aa A=Bb B=Ba|a从上例可看出，文法中有的多余规则对文法描述的语言集合不产生影响，如上例中的D=b规则，是名副其实的多余规则。而有的多余规则会导致不能最终产生终结符号串的错误，因此，检查并去掉这种多余规则也是必须的。,2.13文法和语言分类,著名的语言学家乔姆斯基在1956年对形式语言进行了定义。他把文法定义为四元组：G=（Vn，Vt，P，Z）其中：Vn为非终结符号集合，Vt为终结符号集合且VtV，P为有穷规则集合，Z识别符号，且ZVn。文法所描述的语言为：L（G）=x|xVt+，Z=+x根据文法中的规则的形式，可定义如下四类文法和相应的四种形式语言：,2.13文法和语言分类,1、0型文法若文法中有如下形式的规则：，其中 V+，V*，V=VnVt即规则左部可以是符号集合V上的符号序列但不能为空，而规则右部也是V上的符号序列，而且还可以是空。例如：aSbcAd 0型文法描述的语言为0型语言，用L0表示。,2、1型文法若文法中有如下形式的规则：Uu，其中 UVn，、V*，u V+，V=VnVt即规则左部可为符号序列，其中U为非终结符号且只有在左右为和的环境下U可变为u。因为规则中的和不发生变化，所以这种文法也叫上下文有关文法。例如：aUbaABBaab 1型文法描述的语言为1型语言，用L1表示。,2.13文法和语言分类,3、2型文法若文法中的规则都具有如下形式：Uu，其中 U Vn，u V*，V=V=VnVt2型文法中的规则左部必须是一个非终结符号，规则右部u是V上的符号序列。该文法相当于对1型文法中的规则形式加以限制，即要求和必须为空。2型文法也称作上下文无关文法，描述的语言为2型语言，用L2表示。2型文法是描述程序设计语言语法部分的主要文法。,2.13文法和语言分类,4、3型文法若文法中的规则都具有如下形式：Ua 或U=Wa（左线性）或 UaW（右线性）其中 U，W Vn，a Vt规则右部或是终结符号、或是非终结符号与终结符号。3型文法描述的语言为3型语言，用L3表示。高级程序设计语言的单词符号，如标识符、无符号整数等都是采用3型文法来描述的。例如，左线性3型文法：NN0|N1|N2|N3|N4|N5|N6|N7|N8|N9 N0|1|2|3|4|5|6|7|8|9 这个文法定义的语言为就是无符号整数。,在上述四类文法中，从0型到3型文法对规则的限制逐渐增加，产生的语言类却逐步缩小，即0型语言包含1型语言，1型语言包含2型语言，2型语言包含3型语言。因此，可以说3型文法是2型文法的特例，2型文法是1型文法的特例，1型文法又是0型文法的特例,习题 2,2.1 设字母表A=a，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+.2.2 令=a，b，c，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）32.3 设有文法GS：S=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。2.4 已知文法GZ：Z=U0V1、U=Z11、V=Z00,请写出全部由此文法描述的只含有四个符号的句子。2.5 已知文法GS：S=AB A=aA B=bBcbc,写出该文法描述的语言。2.6 已知文法E=TE+TE-T、T=FT*FT/F、F=(E)i，写出该文法的开始符号、终结符号集合VT、非终结符号集合VN、2.7 对2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。2.8 设有文法GS：S=S*S|S+S|(S)|a，该文法是二义性文法吗？2.9 写一文法，使其语言是奇正整数集合。2.10给出语言anbm|n,m1的文法。,