编译原理-蒋立源第2章文法和语言.ppt

第二章 文法和语言,编译过程的核心就是翻译，就是把一种语言翻译成为另一种语言，与自然语言的翻译类似，只不过其工作对象是某种程序设计语言。 两个重要的前提： 1）描述和定义程序设计语言 2）识别或分析这种语言 20世纪50年代，语言学家Noam Chomsky（乔姆斯基）提出了一个用来描述语言的数学系统，把用一组数学符号和规则来描述语言的方式叫做形式描述，而把能用数学符号和规则描述的语言称为形式语言。 这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。程序设计语言就是形式语言。,2.1 文法及语言的表示,如何来描述一种语言？ 1）当一个语言仅含有有限个句子时，可采用枚举法来表示这种语言。 对于无限的语言寻找出有限的表示，有两种途径： 2）生成方式（文法）：制定有限条规则，用来生成所要描述的语言中的全部句子。 3）识别方式（自动机）：建立一种装置（更确切的说，是构造一种算法或过程），此装置以某一字母表上的所有符号串作为输入，并识别这些符号串，当一个符号串是此字母表上某给定语言中的句子时，就接受它，反之，则拒绝接受。,语言的定义： Webster定义：为相当大地区的公众所懂得并使用的“话”，以及组成这些“话”的方法的统一体。 另一种定义：某一字母表上符号串（句子）的集合,一种精确化的语言的要求： （1）为所定义语言中的句子提供一种结构性的描述 （2）提供一种手段，准确地判别什么是该语言的正确句子，而什么又不是,2.2.1基本概念和术语,字母表：元素的非空有穷集合。字母表中的每个元素称为“符号”，因此“字母表”也可称为“符号集”。典型的符号有字母、数字、各种标点符号和各种运算符。 例如，集合a，b，c，+，*是一个含有5个符号的字母表，而字母表0，1只有2个符号。 符号串：由字母表上0个或多个符号所组成的任何有穷序列。特别地，把不包含任何符号的符号串称为空符号串。 例如有字母表a，b，c，+，*，则a,b,c,+,*,aa,ab,ac,a+,a*,ba,bb,bc,b+,b*,aaa,bbb等等都是该字母表上的符号串。 而所有二进制数都是定义在字母表0，1上的符号串。 显然，一个字母表上的全部符号串所组成的集合是无穷的。,2.2 文法和语言的定义,符号串及其集合的运算1,1.符号串的长度：指符号串x中所含符号的个数，记为|x|。 如：|abc|=3，|abc+*abc|=8，|=？ 2. 符号串的前缀：指从符号串x的末尾删除0或多个符号后得到的符号串，如 、 a、ab、abc都是abc的前缀。 符号串的后缀：指从符号串x的开头删除0或多个符号后得到的符号串，如 、 c、bc、abc都是abc的后缀。 符号串的子串：指从符号串x的开头和末尾删除0或多个符号后得到的符号串，如abc的子串？ 符号串的前缀、后缀都是它的子串。, 、 a 、b 、c 、ab 、bc 、abc,|=0,符号串及其集合的运算2,3.符号串的连接：若x、y是两个符号串，则xy表示连接，是将符号串y连接在符号串x的后面。若x、y是字母表上的两个符号串，则xy也是字母表上的符号串。 如： x=ab，y=ba，那么 xy=abba 注意：连接没有交换律，即 xy yx 对于空串有 x=x =x 符号串的方幂：一个符号串x与其自身的n-1次连接称为x的n次方幂，即： X0=, x1=x , x2=xx ,，xn=xxx=xxn-1=xn-1x 如：x=abc, x0= , x1=abc, x2=abcabc,符号串及其集合的运算3,4.符号串集合的乘积：令A、B为两个符号串集合，A和B的乘积AB定义为： AB=xy|x A ，y B 例如：A=a，b B=c，d，则AB=ac，ad，bc，bd 对于有： A=A =A 符号串集合的方幂：设A为符号串集合，则A的方幂定义为： A0=，A1=A，A2=AAAn=AAA=AAn-1 =An-1A 例如：A=a，b，c A0= A1=a，b，c A2=AA=aa ，ab ，ac ，ba ，bb ，bc ，ca ，cb ，cc,符号串及其集合的运算4,5.符号串集合的闭包：设A为一个集合，则集合A的正闭包用A+表示，定义为： A+ =A1 A2 . A n 集合A的闭包用A*表示，定义为： A* =A 0 A+ 例如：A =a，b ，c 则A+ =a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab, A* =,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab, 可见，字母表A的正闭包A+就是由A中字母所构成的一切符号串的集合，而A*仅比A+多个。,2.2.2 文法和语言的形式定义,在学习英语时，我们知道句子由主语、谓语组成，主语由冠词、形容词及名词组成等等，这就是说明句子组成的规则。而在形式语言里，这种规则可采用“:=”、“:=”这种形式来表示。分析一个句子是否正确，就是根据这些规则进行的。实际上，文法就是描述语言语法结构的形式规则。,从“产生语言”的角度出发，给出方法和语言的形式定义。 产生语言：指制定出有限个规则，借助这些规则可以产生此语言的全部句子。,文法形式定义1,在表示文法时，要说明语言的语法成分(语法范畴），句子中的符号以及语法结构。 例如，能够描述句子“the monkey ate a banana”的文法如下：,在这个文法里，其中用“”符号括起来的部分，表示评议的一个语法实体。 符号“:=”是一个整体，其含义是“定义为”，也就是左边的语法实体可进一步定义为右边的符号串。在推导过程中，就是一种“替换”关系。 而像the、ate、banana这样的符号只在规则中:=的右边出现，不需要进一步定义，这些符号不能用其它符号代替。我们最终需定义的语法成分是。每条规则的形式都是:=。,1) := 2) := the 3) := 4) := 5) := monkey 6):= banana 7) := ate 8) := has 9) := the 10) := a,“:=”表示“定义为”,文法形式定义2, = = = the = the = the monkey = the monkey ate = the monkey ate a = the monkey ate a banana,如何用上述规则去产生或推导出相应语言的句子呢？, =+ the monkey ate a banana,“=”表示一步推导,“=+”表示多步推导,文法形式定义3,文法的形式定义：文法可表示为一个四元组 GS=（ VN ， VT ，P，S） VN是一个非空有穷集合，该集合中的每个元素称为非终结符号。如上例中VN=、 VT是一个非空有穷集合，该集合中的每个元素称为终结符号。如上例中VT=monkey、banana、ate、has、the、a 并且VNVT=，而VNVT称为该文法的字汇表。 P是一个非空的有穷集合，它的每个元素叫做产生式或规则。产生式的形式为： 或:= 是产生式的左部且不能为空，是产生式的右部，并且、V。 S是VN集合的一个特殊的非终结符号，称为文法的开始符号。它至少必须在某个产生式的左部出现一次。就是上例文法的识别符号。,文法形式定义4,文法分4种类型（见2.5小节），程序设计语言文法主要为2型文法，这种文法也叫前后文无关文法，本书后面说的文法都是指这种文法。 在前后文无关文法中，产生式的左部是一个非终结符号，而右部是由终结符号和非终结符号组成的有穷符号串。这样只要给出产生式集合，所有产生式的左部符号就构成了非终结符号集合VN，而只出现在产生式右部的那些符号构成终结符号集合VT，因此，在表示文法时只需给出规则集合并指定识别符号即可。为了进一步简化，在给出规则集时，可约定将左部符号为开始符号的规则作为规则集合的第一条规则，这样表示文法时只需给出规则的集合即可。显然，上例就是一个简化的文法表示。,文法形式定义5,例2.2，有如下简化表示文法，只给出规则集，写出该文法的终结符号集合、非终结符号集合和开始符号。,1. 2. 3. 4.0 5.1 6.2 7.3 8.4 9.5 10.6 11.7 12.8 13.9,解：根据简化约定，可确定： 非终结符号集合： VN=, 终结符号集合： VT=0,1,2,3,4,5,6,7,8,9 开始符号S：,文法的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.元符号“”和“”：表示可重复连接，tnm表示符号串t可重复连接n到m次，而t表示符号串t可重复连接0到无穷次。 例如， 13 与 | 相同 EE+T|T 与 ET+T 相同 而字母打头、后面可跟数字或字母的不超过8个字符的标识符文法则为： |07,文法的EBNF表示,3.元符号“”和“ ”：表示括起的内容可有可无。如t表示符号串t可有可无。 例如：IF THEN IF THEN ELSE 可写成： IF THEN ELSE 4.元符号“（”和“）”：表示括号内的成分优先。常用于在规则中提取公因子。 例如，Uxy|xw|xz 可写成：Ux（y|w|z） 从上述有关元符号的定义和例子可看出，这些元符号为表示文法提供了很大方便。,直接推导,设GS是一文法, 是该文法的一个产生式，对于符号串xy ，其中x和y是该文法的任意符号串(可为空),推导就是用产生式的右部替换左部，从而得到新的符号串xy。表示为： xy=xy 其中“=”表示一步推导。我们称xy直接推导出xy,或xy直接产生xy。若从反方向看，则称xy直接归约到xy。,x,yV*,直接推导,例如有文法 1） 2） | 3） 0|1|2|3|4|5|6|7|8|9 对符号串利用规则1可直接推导出： = 对符号串利用规则2可直接推导出： = 对符号串利用规则3可直接推导出2： = 2 将上述三个推导连接起来，可得如下推导过程： = = = 2,推导,如果文法GS存在一直接推导序列0=1=n，其中n0, 那么我们说 0推导出n或n归约到0,并记作0 =+n,推导长度为n。 如果有0= + n 或0 = n, 即n 0,则记作0= * n 。 可见，n0的推导和n=0分别称为“+推导”和“*推导”。 例如，从开始，分别利用规则1、2、2、3、3，可产生如下推导过程： = =2=23 这个推导过程可记作： =+23 ， 其推导长度n=5， 而从到的推导，无须使用任何规则，可记作： =* ，其推导长度n=0。,句型和句子,推导产生的结果可能是句型，也可能是句子。设文法G的识别符号为S，则句型、句子的定义如下： 1. 如果S =*, 且 V*, 则称是文法GS的一个句型。 2. 如果S=+,且 Vt*,则称是文法GS的一个句子。,从文法的开始符号利用规则进行推导，一旦推导出句子，推导过程就不能再继续进行，因为句子中没有非终结符号。假设符号串是某一推导的结果，那么，是句子的必要条件是从S到的推导长度大于等于，即 S =+x,而不可能是S =*x。这是因为识别符号S是非终结符号，而是终结符号串，显然，S不可能与相等，所以S不可能经过步推导就等于。,为何这里是“+推导”？,句型是从识别符号开始经过0步或多步推导出的可由终结符号和非终结符号组成的符号串 而句子是从文法的识别符号推导出的完全由终结符号组成的符号串。 句子是特殊的句型，是完全由终结符号组成的句型。,语言,一个文法GS所产生的所有句子的集合L(GS), 称为文法GS所定义的语言, 即: L(GS)=x| S =+ x,且x Vt* , 一个文法所定义的语言是该文法的终结符号集合Vt上的所有符号串组成的集合的一个子集,该子集中的每个符号串都可从识别符号开始经过至少一步推导出来，即: L(GS) Vt* 例如，对例2.1的文法G，其语言有16个句子： 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.4，已知文法GS为： 1)SaSb 2)Sab 或写成 S aSb| ab 求该文法确定的语言。 解：从识别符号开始推导，反复用规则1,最后用规则2可得: S=aSb=a2Sb2=an-1 Sbn-1 = anbn （n 2) 直接用规则2可得: S=ab 所以该文法确定的语言为：L(GS)=anbn|n1 反之，试构造产生下列语言的文法anbn|n0 S aSb| ,语言,例2.5，已知语言为: L(G)=abna|n 1，构造产生该语言的文法。 解：根据语言的形式，可构造其文法G为: SaBa BBb|b 还可以构造文法G1为: SaBa BbB|b 可见，G与G1是两个不同的文法，但它们都可以描述语abna|n1。,如果两个不同的文法可描述相同的语言,那么我们称这两个文法为等价文法。前后文无关文法的等价问题是不可判定的。等价文法的存在，对编译技术的实现有很大帮助，使我们能在不改变文法所确定的语言前提下，为了某种目的而改写文法。,引理2.1 设G=(Vn, Vt, P, S)为一文法，并设A x By是P中的一个产生式。而 B1, B2, B k 是P中的全部B-产生式，又设G1=(Vn, Vt, P1, S)是 这样的文法，其中，P1是从P中删去A x By并添加产生式Ax1y, Ax2y, , A x k y所组成的集合，则L(G1)=L(G)。,递归规则与递归文法,递归规则是指在规则的右部含有与规则左部相同符号的规则。 设文法GS，x，y是V上的符号串，若U xUy是文法的规则，且xy!= ，则称U xUy为直接递归规则，称U为直接递归的非终结符。 特别，若x= ，即这个相同的符号出现在右部的最左端，则为左递归规则。 如 U Uy 若y= ，即这个相同的符号出现在右部的最右端，则为右递归规则。如 U xU 若文法GS存在推导U=+xUy，则称U为递归的非终结符。,给定了文法，就确定了语言。句子的个数是有穷还是无穷取决于文法是否是递归的。,若文法GS中至少包含一个递归的非终结符号,则称此文法是递归 文法。递归文法使我们能用有穷的文法刻画无穷的语言。,2.3句型的分析,所谓句型的分析，是指构造一种算法，用以判定给定的符号串是否为某一文法的句型（或句子）。 通常，句型分析的方法可大致分为两类，即自顶向下的分析和自底向上的分析。前者是从文法的开始符号出发，以给定的符号串为目标，试图推导出此符号串；后者恰好和前者相反，它从给定的符号串出发，反复用文法中规则的左部去替换当前符号串中的相应子串，以期最后“归约”到文法的开始符号。这与分析过程中构造句型相应语法树的方向有关。,2.3.1规范推导,规范推导（最右推导），每步推导只替换最右边的非终结符号。定义为： 对于直接推导xUy=xuy来说，如果y只包含终结符号或为空符号串,那么就把这种推导称为规范推导或最右推导（如果只包含终结符号或为空符号串,则为最左推导），且记作: xUy=rxuy , 其中y Vt* 。 例2.6算术表达式文法GE： E E+T|T T T*F|F F (E) | i 给出句子i+i*i的最左推导和最右推导。 解：最左推导： E =lE+T=lT+T=lF+T=l i+T=li+T*F=li+F*F=li+i*F=li+i*i 最右推导： E =rE+T=rE+T*F=rE+T*i=r E+F*i=rE+i*i=rT+i*i=rF+i*i=ri+i*i,2.3.1 规范推导,每一个句子都有一个规范推导,但并非每一个句型都有规范推导，只有那些能用规范推导产生的句型才是规范句型。 例如，对于例2.3中的文法，有句型“2”,其推导过程如下: = =2 其中第3,步推导变换的不是最右边的非终结符号，不满足规范推导的要求，所以句型“2”不是规范句型。 而对于句型“3”，其推导过程如下: = =3 =3 其中的每一步推导都变换的是最右边的非终结符号，所以，句型“3”是规范句型。,2.3.1 规范推导,给定终结符号串w，通过语法分析判定w是否为某一语言L(G)中的句子： 自顶向下：试图为w建立一个从G的开始符号S到w的最左推导。显然，若某步推导中被替换的非终结符号U是由若干个后选式定义的，即有U 1 |2| |n ，那么就会出现如何选用后选式的问题。一种办法是逐个用这些后选式试探。若用某个i 替换U能使分析继续，则沿此路径继续；若发现有错，则退回出错点再用下一个i+1 继续试探。故称为带回溯的自顶向下的分析方法。回溯效率低，应设法避免。,2.3.1 规范推导,自低向上：试图从w出发，以相反方向为w建立一个规范推导。 从左到右扫视wi中各个符号，找到一个和G中某一产生式的右部相同的最左子串，用此产生式的左部替换此最左子串进行直接归约。例如符号串i+i*i的归约过程,最右推导：E =rE+T=rE+T*F=rE+T*i=r E+F*i=rE+i*i=rT+i*i=rF+i*i=ri+i*i 可见，最右（左）推导的逆过程是最左（右）归约，反之亦然。,如何确定可归约的最左子串？,2.3.2 语法树和二义性,推导过程可用图来表示，这就是语法树，也叫分析树。语法树是一棵有序有向树，每个节点都有标记。根节点代表文法的识别符号；每个内部节点（非叶节点）表示一个非终结符号，其子节点由这个非终结符号在这次推导中所用产生式的右部各个符号代表的节点组成；每个末端节点（叶节点）代表终结符号或非终结符号，它们从左向右排列起来，构成句型。如果叶节点都是终结符号，则从左向右构成句子。推导过程不同，生成语法树的过程也不同，但最终生成的语法树是相同的。,例2.8 根据如下推导过程构造语法树。 = = = 3 = 3 = 23 = 23 = 123,数字串,图2.1 语法树,返回1,返回2,2.3.2 语法树和二义性,算术表达式的运算规则是乘除高于加减，if语句规定else就近配对，为什么呢？这是为了解决文法的二义性问题。前面我们介绍语法树时说过，推导过程不同，生成语法树的过程也不同，但最终生成的语法树是相同的，这是在文法没有二义的条件下才成立。如果一个文法所定义的句子中有某个句子或句型，它存在两棵不同的语法树，那么这个句子或句型是二义性的，该文法是二义性文法。,例2.9 有文法GE：E E+E | E*E |（E）| i，分析该文法是否为二义性文法。 解：为了判断该文法是否为二义性文法，我们找一个句子i+i*i，如果能够构造出两个不同的语法树，则说明该文法是二义性文法。下面两个图是为句子i+i*i构造的两棵语法树，如图2.2(a)、(b)所示。由于这两棵语法树不同，所以可以肯定文法GE 是二义性文法。,2.3.2 语法树和二义性,图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.3.2 语法树和二义性,例2.10，IF语句文法如下： IFTHEN |IFTHENELSE | 说明该文法是二义性文法。 解：假设有一个IF语句嵌套的句型为： IFTHEN IFTHENELSE 根据文法可构造两棵语法树如图2.3(a)和图2.3(b)所示：,2.3.2 语法树和二义性,图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.3.2 语法树和二义性,文法的二义性是不可判定的，即不存在一种算法，它能够在有限步内判定一个文法是否是二义性的。第4章讨论的LL，LR等几类重要文法都是无二义性的。同时，还存在这样一些算法，可判定任一前后文无关文法是否为LL，LR文法。不过，文法的LL性，LR性只是文法无二义性的充分条件。另一方面，还存在一些用来检查文法二义性的其他充分条件。若一个文法G含有既是左递归又是右递归的非终结符号A，即有 A = A u A u V* 或A = A 或A = A 及 A = A 则G必定是二义性文法。 有时，我们还可以把一个二义性文法变换成一个等价的无二义性文法。,例2.11，改写文法GE： E E+E | E*E |（E）| i，使其无二义性。 解：新添非终结符号T和F，将文法写成： E T |E+T，T F |T*F，F (E) | i,2.3.3 短语和句柄,短语、简单短语和句柄在分析中有着重要的作用，后面介绍自底向上的语法分析时就可看到如何找句柄是非常关键的。短语是句型的子串，是在句型的推导过程中能由某个非终结符号推导出的子串，而简单短语则是能由某个非终结符号直接推导出的子串。它们的形式定义如下： 1. 短语：设GS是一文法, w=xuy是一句型,如果有 S=*xUy 且U=+u , 其中UVn , uV+，那么,我们称u是句型w相对于非终结符号U的短语。 2.简单短语：若有 S=*xUy 且U=u，那么,我们称u是句型w相对于非终结符号U的简单短语。 3.句柄：任一句型的最左简单短语（即规范分析中，最先被规约的子串）称为该句型句柄。,S=*xUy=+xuy,2.3.3 短语和句柄,例2.7 对于文法G, 确定句型1的短语、简单短语和句柄。 解：首先构造句型1的推导过程如下： = = =1 1)由于 =*,而 =+1, 对照定义，子串1是由非终结符号推出的，所以是相对的短语。 2) 由于=*,而=+1,所以子串1是相对的短语。 3) 由于 =*,而=1，且1是由非终结符号直接推出的，所以子串1是相对的短语,而且是简单短语。 在句型1中,只有一个简单短语1,所以它就是该句型的句柄。,2.3.3 短语和句柄,语法树的子树是由该树的某个节点（子树的根）连同它所有的后裔构成。子树与短语一一对应。要找一个句型的短语，可先画出该句型的语法树。判明语法树中的每棵子树，那么每棵子树的末端节点自左向右组成的符号串，就是相对于子树根符号的短语。原则上语法树中有多少棵子树，就有多少个短语 。123的语法树,例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.3.3 短语和句柄,前面分析过，采用自底向上的语法分析时，每按一个产生式进行一次归约，就用该产生式的左部去替换当前句型中的子串。从语法树的角度来看，就是把该句型的语法树的一棵直接子树的末端节点剪去。换言之，语法分析每次所归约的符号串必然是当前句型的某一直接短语。但是，由于一个句型中的直接短语可能不止一个，故为了使语法分析按一种确定的方式来进行，通常我们只考虑最左归约即规范归约。 123的规范推导,1.如何确定一个规范句型的句柄？ 2.应将句柄归约为哪个非终结符号？,2.4 文法的化简和改造,实用限制就是从实用的观点出发，对文法做一些必要的限制。本节讨论如下三个问题： 1) 无用符号和无用产生式的删除。 2) -产生式的删除。 3) 单产生式的删除。 （消除文法的左递归在后面讨论）,2.4.1 无用符号和无用产生式的删除,设G是一文法，我们说G中一符号X是有用的，是指X至少出现在一个句子的推导过程中，即X必须同时满足以下两个条件： X必须在某个句型中出现， 即存在， V*，有S=* X 2) 必须能够从X推导出终结符号串， 即存在wVt* ，使X =*w 否则，就说X是无用的。 含有无用符号的产生式称为无用产生式。,2.4.1 无用符号和无用产生式的删除,算法2.1用来将文法G=(Vn, Vt, P, S)改造为等价的文法G1=(Vn1, Vt, P1, S)，使得对于每个XVn1,都有w1 Vt*，满足X =*w1。（即改造为满足条件2的文法）,算法2.1 分别置Vn1，P1为空； 对于P中的每一产生式A ，若Vt*，则将A置于Vn1中； 对于P中的每一产生式A X1X2Xm，若每一个Xi都属于Vt或Vn1， 则将A置于Vn1中； 重复步骤3，直到Vn1不再增大为止； 对于P中的每一产生式B Y1Y2Yn，若B及每一个Yi都属于Vt或Vn1， 则将此产生式置于 P1中。,2.4.1 无用符号和无用产生式的删除,对于给定的文法G，若执行算法2.2，便能得到一等价的文法G=(Vn, Vt, P, S)，使得对于每个XVnVt ,都存在， （ VnVt ）*,有S=* X 。（即改造为满足条件1的文法）,算法2.2 分别置Vn，Vt，P为空； 将文法G的开始符号S置于Vn中； 对于G中任何形如A 1 2 m的产生式，若A属于 Vn ，则将符号串 1 ， 2， ， m中的全部非终结符置于Vn 中， 而将其中的全部终结符置于Vt 中； 重复步骤3，直到Vn 和Vt 都不再增大为止； 将P中左右部仅含VnVt 中的符号的所有产生式置于 P 中。,2.4.1 无用符号和无用产生式的删除,例如，对于文法G=(S,U,V,W, a ,b ,c, P, S) 其中，P为 S a S SW SU U a V b V V ac W a W 对G执行算法.步骤如下： 由于U a及V ac，故 Vn1U,V; 对于产生式SU ，由于UVn1，故 Vn1S,U,V; Vn1不再增大； G=(S,U,V, a ,b ,c, P, S) 其中，P1为 S a S SU U a V b V V ac 再对G1执行算法.步骤如下： 置Vn=S; 由于SU及U a，故Vn=S,U， Vt=a; Vn及 Vt不再增大; G =(S,U, a, P, S) 其中， P为 S a S SU U a,注意：两个算法的 执行顺序不能颠倒,2. -产生式的消除,所谓-产生式，是指右部为一空符号串的产生式。 如果一个语言L(G)中不含有，则可以消除全部-产生式；而当L(G)时，G中的-产生式不能全部消除。因此，为了判断一个语言L(G)中是否含有，同时也为了构造消除-产生式算法的需要，我们首先给出算法2.3，该算法能够找出所有能导出空串(即满足A=* )的非终结符号A。,算法2.3 设G是一文法： 作集合 W1 =AA P 作集合序列 Wk+1=Wk B P，且 Wk 对于此集合序列，必存在一个i，使Wi=Wi+1=Wi+2= 若令W=Wi，则对每一个A W，有A=* 。 特别，当SW时，则L(G)；否则L(G)。,2. -产生式的消除,下面分别就 是否属于L(G)来讨论消除G中-产生式的问题。,1. 不属于L(G) 设G=(Vn, Vt, P, S)是一文法，则可按下述算法构造一文法 G=(Vn, Vt, P, S)，使L(G)=L(G)，且G中不含任何-产生式。 算法2.4 按算法2.3求出集合W。 设A X1X2Xm是P中任一产生式，按如下规则将形如 A Y1Y2Ym的产生式放入P中，对于一切1im: 若XiW，则取Yi=Xi; 若Xi W，则分别取Yi为Xi和，即如果X1X2Xm中有j个符号属 于W，1jm，则将有2j个形如A Y1Y2Ym的产生式放入P中，但 若所有的Xi均属于W，则不能把所有的Yi都取为。,2. -产生式的消除,例如，设有文法G=(S,A,B,C, a, b, c, P, S) 其中，P为 S a A A BC B b B C c C B C 对G执行算法2.3有W=A,B,C;再对G执行算法2.4有P: S a A S a A BC A B A C B b B B b C c C C c,2. -产生式的消除,2. 属于L(G) 算法2.5 如果在原文法中，开始符号S不出现在任何产生式的右边，则 可直接执行算法2.4得到P，令P 1= P S ，Vn1=Vn， S1=S，则G1=(Vn1,Vt,p1,S1)即为所求之文法。但若文法的开始 符号S出现在某些产生式的右边，则 引入新的符号S1作为前面算法2.4中G 的开始符号，并令 Vn1=Vn S1 ； 作产生式集P=P S1 S P 对文法G=(Vn1,Vt,P,S1)执行算法2.4，同理，再添加产 生式S1 得到P1 。,2. -产生式的消除,例如，设有文法G=(S,A,B, a, b, c, P, S) 其中，P为 S c S S AB A a A b B B b A B 引入新的符号S1；作产生式集P=PS1 c S,S1 AB 执行算法2.4并加入产生式S1 得到P1 S1 c S S1 c S1AB S1 A S1 B S1 S c S S c SAB SA SB A a A b A a b B B b B b,W=？,W=A,B,S,S1,2.4. 单产生式的消除,右部仅含一个非终结符号的产生式，即形如AB(A,BVn)的产生式称为单产生式。 例如，设有文法G=(S,A,B, a, b, P, S) 其中，P为 S AB S A S B A a A b A a b B B b B b W(S)=S,A,B W(A)=A W(B)=B P=S AB，S a A b，S a b，S B b ，S b A a A b，A a b B B b，B b,算法2.6 设Vn=A1,A2,An，对于每个Ai（1in）作集合序列 W1(Ai)=Ai Wk+1(Ai)=Wk(Ai) DCDP，C Wk(Ai)，D Vn (k1) 则必存在一个j，使Wj(Ai)=Wj+1(Ai)= 令Wi=Wj(Ai) 即Wi= B Ai =* B, B Vn 构造产生式集 P= i=1nAiBP，B Wi， Vn,2.5文法和语言的Chomsky分类,著名的语言学家乔姆斯基在1956年对形式语言进行了