最新【考研计算机专业课】天津大学 编译原理讲义 第三章文法和语言(共50张PPT课件).pptx

《最新【考研计算机专业课】天津大学 编译原理讲义 第三章文法和语言(共50张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新【考研计算机专业课】天津大学 编译原理讲义 第三章文法和语言(共50张PPT课件).pptx（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 文法文法(wnf)和语言和语言3.1 文法和语言文法和语言3.2 文法的等价文法的等价(dngji)变换变换第一页，共五十页。3.1 文法文法(wnf)和语言和语言文法文法(wnf): 定义的一些形式规则。定义的一些形式规则。语言语言: 由定义由定义(dngy)的规则所能识别的全部句子的集的规则所能识别的全部句子的集合。合。1)1) 文法和语言的定义文法和语言的定义2) 2) 文法的文法的Chomsky分类分类 3) 3) 文法产生式的其它表示法文法产生式的其它表示法 字母字母| |字母字母| |数字数字 第二页，共五十页。3.1.1 文法文法(wnf)和语言的定义和语言的定义1

2、. 文法文法是描述语言的语法结构的形式是描述语言的语法结构的形式(xngsh)规则规则(即即语法规则语法规则)。文法文法(wnf)(wnf)是一个四元组是一个四元组: : GS=(VN，VT，P，S) VN为为非终极符集合非终极符集合； VT为为终极符集合终极符集合； VNVT =；一般令一般令V= VNVT ，V中的符号称为文法符号；中的符号称为文法符号； P为为产生式集合产生式集合； P中的每个产生式写为中的每个产生式写为: : ；VV* *V VN NV V* *，VV* * S为为开始符号开始符号。第三页，共五十页。例例，G =（N，0，1，N0N，N1N，N0，N1，N） VN =N

3、 VT =0，1 V=N，0，1 S=NP =N1N0N1NN0N第四页，共五十页。2. 2. 符号串的推导符号串的推导(tudo)(tudo)与归约与归约 已给文法已给文法G=(VN,VT,P,S)，V=VV=VN NV VT T，令，令x x、y y、 VV* *，且，且PP，此时，我们，此时，我们(w men)(w men)称符号串称符号串x xy y能够能够直接直接推导推导出符号串出符号串xxy y，记作，记作x xy y xxy y。 例例，文法，文法G存在存在(cnzi)(cnzi)如下推导如下推导: : N 1N 11。 若符号串若符号串1 1，2 2，n nV* 且且1 12

4、2 n n，则称，则称1 1可可推导推导出出n n来，记作来，记作1 1n n。 +若允许若允许1 1=n n，则，则1 1和和n n的推导关系记作的推导关系记作1 1n n。 *第五页，共五十页。若符号串若符号串xy是符号串是符号串xy的的直接直接(zhji)推导推导；则符号串则符号串xy是符号串是符号串xy的的直接直接(zhji)归约归约。归约归约是推导是推导(tudo)(tudo)逆过程逆过程 若存在若存在1 1n n，则认为，则认为n n能够归约成能够归约成1 1。*设存在产生式设存在产生式，即，即x xy yxxy y例例，文法，文法G存在如下推导存在如下推导: : N 1N 11。

5、 11为为1N的直接推导的直接推导1N为为11的直接规约的直接规约第六页，共五十页。3. 3. 文法的句型文法的句型(j xn)(j xn)、句子和语言的定义、句子和语言的定义 设设G=(VN,VT,P,S)是一文法是一文法(wnf)(wnf) 若若S ，其中，其中(qzhng)(qzhng)S是开始符号，是开始符号，V*，则，则称称为为文法文法G的句型的句型。 *若若S ，且，且VT*，则称，则称为为G的句子的句子。 *文法文法G所产生所产生的语言的语言，记作，记作L(G)=|VT*，且，且S *第七页，共五十页。例例，令，令G2.3= VN，VT，P，数，数 其中，其中，VT =0，1，2

6、，3，4，5，6，7，8，9 VN =数，数字数，数字 P: : | 0| |1| |2| |3| |4| |5| |6| |7| |8| |9 文法文法G产生的产生的语言语言L(G)为十进制正整数。为十进制正整数。 例例，G =（N，0，1，N0N，N1N，N0，N1，N） 存在如下推导存在如下推导: : N 1N 111N为文法为文法G的的句型句型；11为文法为文法G的的句子句子。文法文法G表示的表示的语言语言是是二进制数二进制数第八页，共五十页。4. 4. 产生产生(chnshng)(chnshng)式和文法的递归性式和文法的递归性设给定设给定(i dn)(i dn)文法文法G=(VN,

7、VT,P,S)， 若若=且且,则称产生则称产生(chnshng)(chnshng)式式A是是左递归左递归产产生式；生式； 若若且且=,则称产生式则称产生式A是是右递归右递归产生式。产生式。 P中至少有一个产生式是递归产生式，则称此文法中至少有一个产生式是递归产生式，则称此文法G是是递归文递归文法法。 若存在产生式若存在产生式A且且A A成立，则称产生式成立，则称产生式A是是递归递归的；的； *一般的文法都是递归的，文法一般的文法都是递归的，文法G只有递归定义，只有递归定义，L(G)中句子才是无穷的。中句子才是无穷的。 第九页，共五十页。5. 句型的规范句型的规范(gufn)推导和规范推导和规范

8、(gufn)规约规约句型的句型的最右最右推导称为推导称为规范推导规范推导，逆过程，逆过程(guchng)(guchng)称为称为规范规范归约归约，即，即最左最左规约。规约。 若在推导若在推导(tudo)关系关系1 1n n中，每次最先替换最右中，每次最先替换最右(左左)的非终结符，则称为的非终结符，则称为最右最右(左左)推导推导。若在规约过程中，每次最先规约最左若在规约过程中，每次最先规约最左(右右)的非终结符，的非终结符，则称为则称为最左最左(右右)规约规约。例例，文法，文法G的产生式的产生式为为: : SaAcBe，AAb| |b，S aAcBe aAcde aAbcde abbcde最右

9、推导最右推导: :称为规范推导，逆过程称为规范归约。称为规范推导，逆过程称为规范归约。Bd第十页，共五十页。6. 文法句型文法句型(j xn)的短的短语语设文法设文法(wnf)(wnf)G=(VN,VT,P,S) 若有若有SxAyxy，则，则称为句型称为句型xy的相对于的相对于A的的短语短语。 *+若有若有SxAyxy，则，则称为句型称为句型xy的相对于的相对于A的的直接短语直接短语。 *句型的最左直接短语句型的最左直接短语(duny)(duny)称为此句型的称为此句型的句柄句柄。 短语定义分两部分短语定义分两部分: : 一是一是SxAy成立，二是成立，二是A成立。成立。 *+第十一页，共五十

10、页。i1 ，i2，i3 ，i1*i2 ，i1*i2+ i3都是句型都是句型(j xn)i1*i2+i3的短语。的短语。i1 ，i2，i3 均为直接均为直接(zhji)短语。短语。例例，文法，文法G的产生式的产生式为为: : ET| |E+TTF| |T*FF(E)| |iE E+T E+F E+i3 T+i3 T*F+i3T*i2+i3 F*i2+i3 i1*i2+i3 i1是句柄。是句柄。i2+i3是否句型是否句型i1*i2+i3的短语？的短语？不是，尽管有不是，尽管有E i2+i3，但不存在从，但不存在从E到到i1*E的推导。的推导。+第十二页，共五十页。3.1.2 文法文法(wnf)(w

11、nf)的的Chomsky分类分类 设文法设文法(wnf)(wnf)G=(VN,VT,P,S) ，其产生式形式为，其产生式形式为: : 0型文法型文法（短语（短语(duny)(duny)结构文法）结构文法）: : V*VNV* ，V* 如果对如果对 0 型文法分别加上以下的第型文法分别加上以下的第 i 条限制，则我们就得到条限制，则我们就得到 i 型文法型文法。1.G的任何产生式的任何产生式均满足均满足|，SS除外；除外；2.G的任何产生式的任何产生式 AA，AAVN ，V* ；3.G的任何产生式的任何产生式 AB AB 或或 A A，其中，其中 B BVN VT* ；第十三页，共五十页。例例，

12、文法，文法(wnf)(wnf)G=(=(VN,VT,P,S) )， P定义为定义为: : L(G)=anbncn|n1SA| | AabD| |aABDDcDBCB CBCDCDBD bBbb1 1型文法型文法也称也称上下文有关文法上下文有关文法，产生式形式为，产生式形式为 x xAyxyxy y ，A A必须在上下文必须在上下文x yx y中才可以替换中才可以替换为为。第十四页，共五十页。2 2型文法型文法也称也称上下文无关文法上下文无关文法，用于描述，用于描述(mio sh)(mio sh)多多数现今数现今程序设计语言的语法结构程序设计语言的语法结构。例例，文法，文法(wnf)(wnf)G

13、 =（S，a,b，P，S） L(G)=anbn|n1SaSb| |abP定义定义(dngy)(dngy)为为: :第十五页，共五十页。3 3型文法型文法也称也称正则文法正则文法，由其产生，由其产生(chnshng)(chnshng)的语言的语言叫做正规语言，即正规集。叫做正规语言，即正规集。例例，文法，文法(wnf)(wnf)G =（S，0,1，P，S） L(G)=(0| |1)* S0S| |1S| |0| |1P定义定义(dngy)(dngy)为为: :第十六页，共五十页。每一种类型的文法每一种类型的文法G G都定义都定义(dngy)(dngy)了一类语言了一类语言L(G)L(G)，每种类

14、型的语言都存在一种识别器。每种类型的语言都存在一种识别器。0 0型型 图灵机图灵机1 1型型 线性界限线性界限(jixin)(jixin)自动机自动机2 2型型 下推自动机下推自动机3 3型型 有限有限(yuxin)(yuxin)自动机自动机第十七页，共五十页。3.1.3 文法产生文法产生(chnshng)(chnshng)式的其他表示式的其他表示法法规则规则2.1 产生产生(chnshng)(chnshng)式的花括号表示法。式的花括号表示法。 用用表示字符串表示字符串的的0次出现或多次重复出现，次出现或多次重复出现，即即表示表示或或，或，或 。 例例，有产生式，有产生式 SS| |，其中，

15、其中(qzhng)(qzhng): : SVN，VT ，则可用花括号表示为则可用花括号表示为: : S 若花括号有上、下角标，即若花括号有上、下角标，即0n ，表示，表示或或0次出现，次出现，或或n次出现。次出现。 第十八页，共五十页。规则规则(guz)(guz)2.2 产生式的方括号表示法。产生式的方括号表示法。 若字符串若字符串可可0次出现次出现(chxin)(chxin)或或1次出现，则可用方括号次出现，则可用方括号表示，即表示，即= 01 。 例例，有两个产生式，有两个产生式TT*FF，可用方括号表示式，可用方括号表示式 T T*F。 例例，两种条件语句可写成，两种条件语句可写成: :

16、 if B then S else S 第十九页，共五十页。规则规则(guz)(guz)2.3 提取候选式左、右部的公用因子。提取候选式左、右部的公用因子。 若有产生若有产生(chnshng)(chnshng)式式: AxW1yxW2yxWny 则可表示则可表示(biosh)成成: Ax(W1W2 Wn )y 例例，条件语句的产生式，条件语句的产生式:Sif B then sif B then S else S提取左公因子，可写成提取左公因子，可写成: Sif B then S (| |else S) 第二十页，共五十页。3.1.4 正则正则(zhn z)文法文法 1. 正则正则(zhn z)

17、文法与状态转换图文法与状态转换图右线性文法右线性文法(wnf)GS (UxV|yxV|y) V VVN，x,yx,yVT* 左线性文法左线性文法GS (UVx|yVx|y) V VVN，x,yx,yVT* 许多程序设计语言的单词可以用正则文法来表示，而对于许多程序设计语言的单词可以用正则文法来表示，而对于正则文法所描述的语言又可以用状态转换图来非形式的表正则文法所描述的语言又可以用状态转换图来非形式的表示。示。第二十一页，共五十页。对于对于右线性文法右线性文法GS (UxV|yxV|y)，状态转换，状态转换(zhunhun)图的表示方图的表示方法如下：法如下： (1) GS中的非终结符表示中的

18、非终结符表示(biosh)状态，状态，GS的开始符号的开始符号S对应对应状态转换图的开始状态状态转换图的开始状态S； (2) 增加一个新状态增加一个新状态Z，作为状态转换，作为状态转换(zhunhun)图的终止状态；图的终止状态； (3) 对于对于GS中形如中形如UxVxV的每条产生式，画一条从状态的每条产生式，画一条从状态U到到状态状态V的方向弧，弧上的标记为的方向弧，弧上的标记为x； (4) 对于对于GS中形如中形如Uy的每条产生式，画一条从状态的每条产生式，画一条从状态U到终态到终态Z的方向弧，弧上的标记为的方向弧，弧上的标记为y 第二十二页，共五十页。例例，给出与正则文法给出与正则文法

19、G(S)等价等价(dngji)的状态转换图。的状态转换图。GS： SaA SbBS a AaB AbA BaS BbA B ASBZababab正则文法与状态转换图等价，是指正则文法所确定正则文法与状态转换图等价，是指正则文法所确定(qudng)的语言的语言L(G)，与状态转换图所接受的语言，与状态转换图所接受的语言L(TG)相同：相同： L(G)=L(TG)a第二十三页，共五十页。左线性文法左线性文法GZ (UVx|y)Vx|y)，状态转换图的表示方法，状态转换图的表示方法(fngf)如下如下: (1) 用状态表示用状态表示(biosh)GZ中的非终结符，中的非终结符，GZ的开始符号的开始符

20、号Z对应状态转换图的终止状态对应状态转换图的终止状态Z (2) 增加一个增加一个(y )新状态新状态S，作为状态转换图的初始状态；，作为状态转换图的初始状态； (3) 对于对于GZ中形如中形如UVxVx的每条产生式，画一条从状态的每条产生式，画一条从状态V到状到状态态U的方向弧，弧上的标记为的方向弧，弧上的标记为x； (4) 对于对于GZ中形如中形如Uy的每条产生式，画一条从初态的每条产生式，画一条从初态S到状态到状态U的方向弧，弧上的标记为的方向弧，弧上的标记为y。 第二十四页，共五十页。例例，给出与正则文法给出与正则文法GZ等价等价(dngji)的状态转换图的状态转换图 GZ: ZU0 Z

21、V1 UZ1 U1 VZ0 V0UVZS100011第二十五页，共五十页。2. 正则文法正则文法(wnf)与正规式与正规式一个一个(y )(y )正则语言可以由正则文法定义，也可以由正规式定义。正则语言可以由正则文法定义，也可以由正规式定义。 对任意一个正规文法，存在对任意一个正规文法，存在(cnzi)(cnzi)一个定义同一语言的正规一个定义同一语言的正规式；反之，对每个正规式，存在式；反之，对每个正规式，存在(cnzi)(cnzi)一个生成同一语言的一个生成同一语言的正规文法正规文法。正规文法和正规式之间是可以相互转换的。正规文法和正规式之间是可以相互转换的。 第二十六页，共五十页。A.

22、首先首先(shuxin)(shuxin)介绍将介绍将上的一个正规式上的一个正规式R转换成正规文法转换成正规文法G=(VN，VT，S，P)，并使，并使L(G)=L(R)的方法的方法: : (1)(1) 文法的终结符号文法的终结符号(fho)(fho)集集VT与字母表与字母表相同，即相同，即VT=； (2)(2) 对于正规式对于正规式R，定义一非终结符号，定义一非终结符号S生成产生生成产生(chnshng)(chnshng)式式SR，并将，并将S定为文法定为文法G的开始符号的开始符号( (识别符号识别符号) )； (3)(3) 对已有的产生式，按以下原则进行变换，直到每个产生对已有的产生式，按以下

23、原则进行变换，直到每个产生式最多含有一个终结符号为止式最多含有一个终结符号为止: : 第二十七页，共五十页。设设x,y是正规是正规(zhnggu)式，则式，则 对于对于(duy)形如形如Axy的产生式，重写成：的产生式，重写成：AxB，By两产生式，其中，两产生式，其中，BVN ；对于对于(duy)形如形如Ax| |y的产生式，重写成：的产生式，重写成：Ax，Ay两产生式；两产生式； 按按(2)和和(3)所确定的产生式组成文法的产生式集合所确定的产生式组成文法的产生式集合P，而，而(2)和和(3)中的非终结符号组成文法的非终结符号集中的非终结符号组成文法的非终结符号集VN 对于形如对于形如Ax

24、 y的产生式，重写成：的产生式，重写成：AxBxB，Ayy，BxBxB，Byy四个产生式；四个产生式；*第二十八页，共五十页。例例，将正规式将正规式R=a(a|b) *转换成相应转换成相应(xingyng)的正规文法的正规文法G，并使，并使L(G)=L(R) (1)根据正规根据正规(zhnggu)式式R可以确定可以确定=a，b，所以，所以VT=a，b； (2)Sa(a| |b) * ， S VN ；(3)Sa(a| |b) *符合符合(fh)Axy的形式，改写的形式，改写: SaA A(a| |b) * (4)A(a| |b) * 符合符合Ax*y的形式，改写的形式，改写: A(a| |b)B

25、 A B(a| |b)B B整理得变换结果整理得变换结果GS: SaA AaBAbB A BaBBbB B 第二十九页，共五十页。B.正规文法转换成正规式正规文法转换成正规式: 将正规文法将正规文法G=(VN，VT，S，P)转转换成正规式换成正规式R，并使，并使L(R)=L(G)的方法的方法(fngf)如下如下:使用转换规则合并文法的产生使用转换规则合并文法的产生(chnshng)式，最后只剩下一个开始符式，最后只剩下一个开始符号定义的产生号定义的产生(chnshng)式，并且产生式，并且产生(chnshng)式的右部不含非终结式的右部不含非终结符号。转换规则如下符号。转换规则如下: (1)若

26、有产生若有产生(chnshng)式式AxB By 则转换成正规式则转换成正规式: A=xy (2)若有产生式若有产生式AxA| |y 则转换成正规式则转换成正规式: A=x*y (3)若有产生式若有产生式Ax Ay 则转换成正规式则转换成正规式: A=x| |y 第三十页，共五十页。例例，设有文法，设有文法(wnf)GS SaAaA Saa AaA aA AdA dA Aa a Add试求正规式试求正规式R，使，使L(R)=L(GS)(1)产生产生(chnshng)式式和得和得正规正规式式: S=aA| |a (3)将将A代入代入S得得: S=a(a| |d) * (a| |d) | |a =

27、a(a| |d) * (a| |d) | |) =a(a| |d)+ | |) =a(a| |d) * (2)由产生由产生(chnshng)式、得正规式式、得正规式:=(a| |d)A| |(a| |d)= (a| |d) * (a| |d)A=aA| |dA| |a| |d第三十一页，共五十页。3.2 文法的等价文法的等价(dngji)(dngji)变换变换 若文法若文法G1、G2满足等式满足等式(dngsh)(dngsh)L( (G1 ) ) =L( (G2 ) ) ，则称，则称文法文法G1、G2是是等价等价的。的。 设文法设文法(wnf)(wnf)G1S= (VN,VT,P,S)，显然显

28、然L（G1）=L（G2），），G2称为称为G1的的拓广文法拓广文法。其中，其中，P=A| APPSS我们构造文法我们构造文法G2S=(VNSS，VT，P，S)初始化初始化:第三十二页，共五十页。等价等价(dngji)(dngji)变换的几种方法变换的几种方法 1. 消除无用符号消除无用符号(fho)(fho)和无用产生式和无用产生式 2. 消除消除(xioch)(xioch)单个产生式单个产生式 3. 消除或规范空符号产生式消除或规范空符号产生式 第三十三页，共五十页。1. 消除无用符号消除无用符号(fho)(fho)和无用产生式和无用产生式 设文法设文法GS=(VN,VT,P,S)且且L(

29、(G)，任给一文法符，任给一文法符号号XV，若，若X 满足满足: : (1) SX和和(2) X，其，其中中VT*则说文法符号则说文法符号X是有用的，否则，称是有用的，否则，称X为为无无用符号用符号。 *任给一产生式任给一产生式AP，若产生式左部或右部含有无用，若产生式左部或右部含有无用(w yn)(w yn)符号，则称此产生式符号，则称此产生式A为为无用产生式无用产生式。 已知文法已知文法G=(VN,VT,P,S)，下面，下面(xi mian)(xi mian)的的算法算法1，按定义，按定义中中(2)的要求构造文法的要求构造文法G1=(VN1,VT,P1,S)，算法算法2按定义中按定义中(1

30、)的要求的要求构造文法构造文法G2=(VN2,VT2,P2,S)。 第三十四页，共五十页。算法算法1: 根据定义要求根据定义要求 (2) X，VT*1. VN1=；P =。2. 对每个对每个Ax1x2xnP且且xiVN1VT (i=1,n)，则置，则置VN1= VN1A； 3. 重复重复(2)，直至，直至VN1不再扩大不再扩大(kud)(kud)为止。为止。 4. 对每个对每个Ax1x2xnP且且xiVN1VT (i=1,n)，则，则Ax1x2xn置入置入P1中。中。 构造构造(guzo)(guzo)文法文法G1=(VN1,VT,P1,S) 第三十五页，共五十页。例例，文法，文法(wnf)GS

31、=( (S，U，V，M，N，a,b，P，S) )由由SV可得可得: VN1=S，V，NP1 = SV，Va，Nb 其中其中(qzhng)(qzhng)P为为: : SUV，UM，Va，Nb文法文法G1S=( ( S，V，N，a,b， SV, ,Va, ,Nb，S ) ) 可得可得:由由Nb可得可得: VN1=N初始初始(ch sh): VN1=由由Va可得可得: VN1=V，N第三十六页，共五十页。1. VN2=S；VT2=；P2= 2. 对于对于(duy)(duy)G1的每个产生式的每个产生式Ax1x2xn，则置，则置VN2= VN2xiAVN2xiVN1，i=1,n VT2 = VT2xi

32、AVN2xiVT，i=1,n 3. 重复重复(chngf)(chngf)(2)，直至不再扩大为止。，直至不再扩大为止。 4. 对于每一个对于每一个AP1 ，若，若A的左、右部之的左、右部之任一文法任一文法(wnf)(wnf)符号符号X，都有，都有XVN2VT2 ，则，则P2= P2A。 算法算法2: 根据定义要求根据定义要求 (1) SX*构造文法构造文法G2=(VN2,VT,P2,S) 第三十七页，共五十页。可得文法可得文法(wnf)G2 : VN2=S，V, ,VT2=a, ,P2 = SV，Va。 上例上例，文法，文法(wnf)(wnf)G1S=( ( S，V，N，a,b， SV, ,V

33、a, ,Nb，S ) ) 由由SV可得可得: VN2=S，V；VT2=初始初始(ch sh): VN2=S；VT2=由由Va可得可得: VN2=S，V；VT2=aP2 = SV，Va 第三十八页，共五十页。例例，设文法，设文法(wnf)(wnf)GS=（S,U,V,W，a,b,c，P，S) ，VbVac WaW 其中其中(qzhng)(qzhng) P: : SaSWU Ua P2 = SaSU，Ua P1 = SaSU，Ua，VbVac 由由Vac可得可得: VN1=V初始初始(ch sh): VN1=由由Ua可得可得: VN1=V，U施行施行算法算法1由由SU可得可得: VN1=S，V，U

34、VT=a,b,c施行施行算法算法2由由SaSU可得可得: VN2=S，U；VT2=a初始初始: VN2=S；VT2=由由Ua可得可得: VN2=S，U；VT2=a第三十九页，共五十页。2. 消除单一消除单一(dny)(dny)产生式产生式 单一单一(dny)(dny)产生式产生式系指系指AB P(A ，B VN )。 例例，文法文法(wnf)(wnf)G =（S,A,B，a,b，P，S），），其中其中 P: : SABAB AaAbabBBbb P中去掉单一产生式中去掉单一产生式SA应加入应加入SaAbab； 去掉单一产生式去掉单一产生式SB应加入应加入SBbb。 第四十页，共五十页。3. 构

35、造构造(guzo)(guzo)VN1=A|AP1。 2. 构造构造G1的产生式集，的产生式集，P1 = Ai| |BP BW(Ai) VN ni=11. 将文法将文法G的非终极符给出一种排序，使的非终极符给出一种排序，使 VN = A1，An ，对于每个，对于每个Ai作集合作集合 W( (Ai) )= BAiB，BVN ，（，（i=1,2,n）；）； *第四十一页，共五十页。首先首先(shuxin)构造构造W( (Ai) )集合集合: : W( (S) )=S，A，B再构造再构造(guzo)(guzo)产生式产生式P1 : :AaAbab例例，文法文法(wnf)(wnf)G = ( ( S,A

36、,B，a,b，P，S ) )，其中其中 P: : SABAB AaAbabBBbb W( (A) )=AW( (B) )=BSABaAbabBbbBBbb第四十二页，共五十页。例例，文法，文法(wnf)(wnf)G=( (S,A,B,C，a，P，S) )，其中其中(qzhng)(qzhng) P: : SAB，AB，BC，Ca 解解: : W( (S) )=S； W( (A) )=A,B,C； W( (B) )=B,C； W( (C) )=C 由由W( (S) )得得: SAB 由由W( (A) )得得: Aa 由由W( (B) )得得: Ba 由由W( (C) )得得: Ca 消除无用产生式

37、消除无用产生式 Ca，得文法，得文法G1的产生式的产生式: : SAB Aa Ba 第四十三页，共五十页。3. 消除消除(xioch)(xioch)或规范空符号产生式或规范空符号产生式 空符号空符号(fho)(fho)产生式产生式是指是指A，其中，其中AVN 。 例例，文法，文法(wnf)(wnf)G1: SaUbV U Vc 变成文法变成文法G2: SabV Vc 显然，显然，L（G1），消除空符号产生式），消除空符号产生式U 任给一文法任给一文法G=(VN,VT,P,S)，若，若L(G)，则消除任何空，则消除任何空符号产生式，称为符号产生式，称为消除空符号产生式消除空符号产生式；若若L(G

38、)，则除消除所有空符号产式以外，还必须增加，则除消除所有空符号产式以外，还必须增加S，其中，其中S 是根符号，称为是根符号，称为规范空符产生式规范空符产生式。第四十四页，共五十页。算法算法1，确定，确定(qudng)(qudng)是否属于是否属于L(G) 1. 令令W1 =AAP； 2. Wn =Wn-1xxP Wn-1+，n2； 3. （2）中集合序列）中集合序列Wn存在存在K，使得，使得(sh de)(sh de)WK =WK+1，此时，令此时，令W=WK，显然有，显然有W1 W2 W VN ； 4. 若若SW，则，则L(G)，否则，否则L(G)。 第四十五页，共五十页。例例，设文法，设文

39、法(wnf)(wnf) GS=（S,A,B,C，a,b,c，P，S），），其中其中(qzhng)(qzhng)，P: SaA ABC P: SaA ABC BbB CcC 由由B和和C可得可得: : W1=B，C；因为，因为，S W，所以，所以，S 不成立；即不成立；即L(G)。 *W=W3=W2= A，B，C；由由ABCABC可得可得: : W2= A，B，C；第四十六页，共五十页。算法算法2，消除空符号消除空符号(fho)产生式产生式 1. P1 =； 2. 对每个产生式对每个产生式Ax1x2xnP和所有和所有i，1in，作作 P1=P1Ay1y2yn| |若若xi (VN-W)VT，则取

40、则取 yi=xi；若；若xiW，则，则yi取取xi和和*- A| |Ax1x2xnPx1x2xn第四十七页，共五十页。(2)中说明，若产生中说明，若产生(chnshng)(chnshng)式式Ax1x2xn右端有右端有K个符号属于个符号属于W，且，且Kn，则产生式，则产生式Ax1x2xn 派生出派生出2K个产生工加入个产生工加入P1，包括产生式包括产生式Ax1x2xn，但，但AA不加入不加入P P1 1。 消去空符号产生式得消去空符号产生式得: : G1 1S=(S=(VN,VT,P1,S) )， 其中其中P1为为: : SaAa ABCBC BbBb CcCc 上例上例，设文法，设文法 GS

41、=（S,A,B,C，a,b,c，P，S），），其中，其中，P: SaA ABC BbB CcC W=A，B，C第四十八页，共五十页。算法算法(sun f)(sun f)3，规范空符号产生式，规范空符号产生式 若若L（G），则先按算法），则先按算法2消去空符号产生消去空符号产生(chnshng)(chnshng)式，若式，若出现产生出现产生(chnshng)(chnshng)式式SS，则删除，则删除SS，最后加入空符号产，最后加入空符号产生式生式S（S 是根符号）。是根符号）。 例例，设文法，设文法(wnf)G的产生式的产生式P为为:由算法由算法1，W=S，A ，L（G） ；由算法由算法2，P规

42、范成规范成P1 : : SASAS Aa ；由算法由算法3，P1规范成规范成P2: : SASA | Aa 。SAS Aa第四十九页，共五十页。内容(nirng)总结第三章 文法和语言。3型文法也称正则文法，由其产生的语言叫做正规(zhnggu)语言，即正规(zhnggu)集。每一种类型的文法G都定义了一类语言L(G)，每种类型的语言都存在一种识别器。许多程序设计语言的单词可以用正则文法来表示，而对于正则文法所描述的语言又可以用状态转换图来非形式的表示。(1) GS中的非终结符表示状态，GS的开始符号S对应状态转换图的开始状态S。一个正则语言可以由正则文法定义，也可以由正规(zhnggu)式定义第五十页，共五十页。