【精品】【考研计算机专业课】天津大学 编译原理讲义 第三章文法和语言（可编辑.ppt

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

1、【考研计算机专业课】天津大学 编译原理讲义 第三章文法和语言3.1 文法和语言文法和语言文法文法:定义的一些形式规则。定义的一些形式规则。语言语言:由定义的规则所能识别的全部句子的集合。由定义的规则所能识别的全部句子的集合。1)1)文法和语言的定义文法和语言的定义2)2)文法的文法的Chomsky分类分类 3)3)文法产生式的其它表示法文法产生式的其它表示法 字母字母|字母字母|数字数字 3.1.1 文法和语言的定义文法和语言的定义1.文法文法是描述语言的语法结构的形式规则是描述语言的语法结构的形式规则(即即语法规则语法规则)。文法文法是一个四元组是一个四元组:GS=(VN，VT，P，S)VN

2、为为非终极符集合非终极符集合；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 VT=0，1 V=N，0，1 S=NP=N1N0N1NN0N2.2.符号串的推导与归约符号串的推导与归约 已给文法已给文法G=(VN,VT,P,S)，V=VV=VN NV VT T，令，令x x、y y、VV*，且，且PP，此时，我们称符号串，此时，我们称符号串

3、x xy y能够直接能够直接推导推导出符号串出符号串xxy y，记作，记作x xy y xxy y。例例，文法，文法G存在如下推导存在如下推导:N 1N 11。若符号串若符号串1 1，2 2，n nV*且且1 12 2 n n，则称，则称1 1可可推导推导出出n n来，记作来，记作1 1n n。+若允许若允许1 1=n n，则，则1 1和和n n的推导关系记作的推导关系记作1 1n n。*例例，令，令G2.3=VN，VT，P，数，数 其中，其中，VT=0，1，2，3，4，5，6，7，8，9 VN=数，数字数，数字 P:|0|1|2|3|4|5|6|7|8|9 文法文法G产生的产生的语言语言L(

4、G)为十进制正整数。为十进制正整数。例例，G=（N，0，1，N0N，N1N，N0，N1，N）存在如下推导存在如下推导:N 1N 111N为文法为文法G的的句型句型；11为文法为文法G的的句子句子。文法文法G表示的表示的语言语言是是二进制数二进制数4.4.产生式和文法的递归性产生式和文法的递归性设给定文法设给定文法G=(VN,VT,P,S)，若若=且且,则称产生式则称产生式A是是左递归左递归产生式；产生式；若若且且=,则称产生式则称产生式A是是右递归右递归产生式。产生式。P中至少有一个产生式是递归产生式，则称此文法中至少有一个产生式是递归产生式，则称此文法G是是递归文法递归文法。若存在产生式若存

5、在产生式A且且A A成立，则称产生式成立，则称产生式A是是递归递归的；的；*一般的文法都是递归的，文法一般的文法都是递归的，文法G只有递归定义，只有递归定义，L(G)中句子才是无穷的。中句子才是无穷的。5.句型的规范推导和规范规约句型的规范推导和规范规约句型的句型的最右最右推导称为推导称为规范推导规范推导，逆过程称为，逆过程称为规范归规范归约约，即，即最左最左规约。规约。若在推导关系若在推导关系1 1n n中，每次最先替换最右中，每次最先替换最右(左左)的非的非终结符，则称为终结符，则称为最右最右(左左)推导推导。若在规约过程中，每次最先规约最左若在规约过程中，每次最先规约最左(右右)的非终结

6、的非终结符，则称为符，则称为最左最左(右右)规约规约。例例，文法，文法G的产生式的产生式为为:SaAcBe，AAb|b，S aAcBe aAcde aAbcde abbcde最右推导最右推导:称为规范推导，逆过程称为规范归约。称为规范推导，逆过程称为规范归约。Bd6.文法句型的短语文法句型的短语设文法设文法G=(VN,VT,P,S)若有若有SxAyxy，则，则称为句型称为句型xy的相对于的相对于A的的短短语语。*+若有若有SxAyxy，则，则称为句型称为句型xy的相对于的相对于A的的直接短语直接短语。*句型的最左直接短语称为此句型的句型的最左直接短语称为此句型的句柄句柄。短语定义分两部分短语定

7、义分两部分:一是一是SxAy成立，二是成立，二是A成立。成立。*+i1，i2，i3，i1*i2，i1*i2+i3都是句型都是句型i1*i2+i3的短语。的短语。i1，i2，i3 均为直接短语。均为直接短语。例例，文法，文法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 文法的文法的Chomsky分类分

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

9、CB CBCDCDBD bBbb1 1型文法型文法也称也称上下文有关文法上下文有关文法，产生式形式为，产生式形式为 x xAyxyxy y，A A必须在上下文必须在上下文x yx y中才可以替换中才可以替换为为。2 2型文法型文法也称也称上下文无关文法上下文无关文法，用于描述多数，用于描述多数现今现今程序设计语言的语法结构程序设计语言的语法结构。例例，文法，文法G=（S，a,b，P，S）L(G)=anbn|n1SaSb|abP定义为定义为:3 3型文法型文法也称也称正则文法正则文法，由其产生的语言叫做，由其产生的语言叫做正规语言，即正规集。正规语言，即正规集。例例，文法，文法G=（S，0,1，

10、P，S）L(G)=(0|1)*S0S|1S|0|1P定义为定义为:每一种类型的文法每一种类型的文法G G都定义了一类语言都定义了一类语言L(G)L(G)，每种类型的语言都存在一种识别器。每种类型的语言都存在一种识别器。0 0型型 图灵机图灵机1 1型型 线性界限自动机线性界限自动机2 2型型 下推自动机下推自动机3 3型型 有限自动机有限自动机3.1.3 文法产生式的其他表示法文法产生式的其他表示法规则规则2.1 产生式的花括号表示法。产生式的花括号表示法。用用表示字符串表示字符串的的0次出现或多次重复出现，次出现或多次重复出现，即即表示表示或或，或，或 。例例，有产生式，有产生式 SS|，其

11、中，其中:SVN，VT，则可用花括号表示为则可用花括号表示为:S 若花括号有上、下角标，即若花括号有上、下角标，即0n，表示，表示或或0次次出现，或出现，或n次出现。次出现。规则规则2.2 产生式的方括号表示法。产生式的方括号表示法。若字符串若字符串可可0次出现或次出现或1次出现，则可用方括号次出现，则可用方括号表示，即表示，即=01。例例，有两个产生式，有两个产生式TT*FF，可用方括号表示式，可用方括号表示式 T T*F。例例，两种条件语句可写成，两种条件语句可写成:if B then S else S 规则规则2.3 提取候选式左、右部的公用因子。提取候选式左、右部的公用因子。若有产生式

12、若有产生式:AxW1yxW2yxWny 则可表示成则可表示成:Ax(W1W2 Wn)y 例例，条件语句的产生式，条件语句的产生式:Sif B then sif B then S else S提取左公因子，可写成提取左公因子，可写成:Sif B then S(|else S)3.1.4 正则正则文法文法 1.正则文法与状态转换图正则文法与状态转换图右线性文法右线性文法GS(UxV|yxV|y)V VVN，x,yx,yVT*左线性文法左线性文法GS(UVx|yVx|y)V VVN，x,yx,yVT*许多程序设计语言的单词可以用正则文法来表示，许多程序设计语言的单词可以用正则文法来表示，而对于正则文

13、法所描述的语言又可以用状态转换图而对于正则文法所描述的语言又可以用状态转换图来非形式的表示。来非形式的表示。对于对于右线性文法右线性文法GS(UxV|yxV|y)，状态转换图的表示方法，状态转换图的表示方法如下：如下：(1)GS中的非终结符表示状态，中的非终结符表示状态，GS的开始符号的开始符号S对应对应状态转换图的开始状态状态转换图的开始状态S；(2)增加一个新状态增加一个新状态Z，作为状态转换图的终止状态；，作为状态转换图的终止状态；(3)对于对于GS中形如中形如UxVxV的每条产生式，画一条从状态的每条产生式，画一条从状态U到状态到状态V的方向弧，弧上的标记为的方向弧，弧上的标记为x；(

14、4)对于对于GS中形如中形如Uy的每条产生式，画一条从状态的每条产生式，画一条从状态U到终态到终态Z的方向弧，弧上的标记为的方向弧，弧上的标记为y 例例，给出与正则文法给出与正则文法G(S)等价的状态转换图。等价的状态转换图。GS：SaA SbBS a AaB AbA BaS BbA B ASBZababab正则文法与状态转换图等价，是指正则文法所确定的语正则文法与状态转换图等价，是指正则文法所确定的语言言L(G)，与状态转换图所接受的语言，与状态转换图所接受的语言L(TG)相同：相同：L(G)=L(TG)a左线性文法左线性文法GZ(UVx|y)Vx|y)，状态转换图的表示方法如下，状态转换图

15、的表示方法如下:(1)用状态表示用状态表示GZ中的非终结符，中的非终结符，GZ的开始符号的开始符号Z对对应状态转换图的终止状态应状态转换图的终止状态Z(2)增加一个新状态增加一个新状态S，作为状态转换图的初始状态；，作为状态转换图的初始状态；(3)对于对于GZ中形如中形如UVxVx的每条产生式，画一条从状态的每条产生式，画一条从状态V到状态到状态U的方向弧，弧上的标记为的方向弧，弧上的标记为x；(4)对于对于GZ中形如中形如Uy的每条产生式，画一条从初态的每条产生式，画一条从初态S到状态到状态U的方向弧，弧上的标记为的方向弧，弧上的标记为y。例例，给出与正则文法给出与正则文法GZ等价的状态转换

16、图等价的状态转换图 GZ:ZU0 ZV1 UZ1 U1 VZ0 V0UVZS1000112.正则文法与正规式正则文法与正规式一个正则语言可以由正则文法定义，也可以由正规式一个正则语言可以由正则文法定义，也可以由正规式定义。定义。对任意一个正规文法，存在一个定义同一语言的正规对任意一个正规文法，存在一个定义同一语言的正规式；反之，对每个正规式，存在一个生成同一语言的式；反之，对每个正规式，存在一个生成同一语言的正规文法正规文法。正规文法和正规式之间是可以相互转换的。正规文法和正规式之间是可以相互转换的。A.首先介绍将首先介绍将上的一个正规式上的一个正规式R转换成正规文法转换成正规文法G=(VN，

17、VT，S，P)，并使，并使L(G)=L(R)的方法的方法:(1)(1)文法的终结符号集文法的终结符号集VT与字母表与字母表相同，即相同，即VT=；(2)(2)对于正规式对于正规式R，定义一非终结符号，定义一非终结符号S生成产生式生成产生式SR，并将，并将S定为文法定为文法G的开始符号的开始符号(识别符号识别符号)；(3)(3)对已有的产生式，按以下原则进行变换，直到每对已有的产生式，按以下原则进行变换，直到每个产生式最多含有一个终结符号为止个产生式最多含有一个终结符号为止:设设x,y是正规式，则是正规式，则 对于形如对于形如Axy的产生式，重写成：的产生式，重写成：AxB，By两两产生式，其中

18、，产生式，其中，BVN；对于形如对于形如Ax|y的产生式，重写成：的产生式，重写成：Ax，Ay两两产生式；产生式；按按(2)和和(3)所确定的产生式组成文法的产生式集合所确定的产生式组成文法的产生式集合P，而而(2)和和(3)中的非终结符号组成文法的非终结符号集中的非终结符号组成文法的非终结符号集VN 对于形如对于形如Ax y的产生式，重写成：的产生式，重写成：AxBxB，Ayy，BxBxB，Byy四个产生式；四个产生式；*例例，将正规式将正规式R=a(a|b)*转换成相应的正规文法转换成相应的正规文法G，并使，并使L(G)=L(R)(1)根据正规式根据正规式R可以确定可以确定=a，b，所以，

19、所以VT=a，b；(2)Sa(a|b)*，S VN；(3)Sa(a|b)*符合符合Axy的形式，改写的形式，改写:SaA A(a|b)*(4)A(a|b)*符合符合Ax*y的形式，改写的形式，改写:A(a|b)B A B(a|b)B B整理得变换结果整理得变换结果GS:SaA AaBAbB A BaBBbB B B.正规文法转换成正规式正规文法转换成正规式:将正规文法将正规文法G=(VN，VT，S，P)转换成正规式转换成正规式R，并使，并使L(R)=L(G)的方法如下的方法如下:使用转换规则合并文法的产生式，最后只剩下一个开始使用转换规则合并文法的产生式，最后只剩下一个开始符号定义的产生式，并

20、且产生式的右部不含非终结符号。符号定义的产生式，并且产生式的右部不含非终结符号。转换规则如下转换规则如下:(1)若有产生式若有产生式AxB By 则转换则转换成正成正规规式式:A=xy(2)若有产生式若有产生式AxA|y 则转换则转换成正成正规规式式:A=x*y(3)若有产生式若有产生式Ax Ay 则转换则转换成正成正规规式式:A=x|y 例例，设有文法，设有文法GS SaAaA Saa AaA aA AdA dA Aa a Add试求正规式试求正规式R，使，使L(R)=L(GS)(1)产生式产生式和和得得正规正规式式:S=aA|a(3)将将A代入代入S得得:S=a(a|d)*(a|d)|a=

21、a(a|d)*(a|d)|)=a(a|d)+|)=a(a|d)*(2)由产生式由产生式、得正规式得正规式:=(a|d)A|(a|d)=(a|d)*(a|d)A=aA|dA|a|d3.2 文法的等价变换文法的等价变换 若文法若文法G1、G2满足等式满足等式L(G1)=L(G2)，则称文，则称文法法G1、G2是是等价等价的。的。设文法设文法G1S=(VN,VT,P,S)，显然显然L（G1）=L（G2），），G2称为称为G1的的拓广文法拓广文法。其中，其中，P=A|APPSS我们构造文法我们构造文法G2S=(VNSS，VT，P，S)初始化初始化:等价变换的几种方法等价变换的几种方法 1.消除无用符号

22、和无用产生式消除无用符号和无用产生式 2.消除单个产生式消除单个产生式 3.消除或规范空符号产生式消除或规范空符号产生式 1.消除无用符号和无用产生式消除无用符号和无用产生式 设文法设文法GS=(VN,VT,P,S)且且L(G)，任给一文法符号，任给一文法符号XV，若，若X 满足满足:(1)SX和和(2)X，其中，其中VT*则说文法符号则说文法符号X是有用的，否则，称是有用的，否则，称X为为无用符无用符号号。*任给一产生式任给一产生式AP，若产生式左部或右部含有无用，若产生式左部或右部含有无用符号，则称此产生式符号，则称此产生式A为为无用产生式无用产生式。已知文法已知文法G=(VN,VT,P,

23、S)，下面的，下面的算法算法1，按定义，按定义中中(2)的要求构造文法的要求构造文法G1=(VN1,VT,P1,S)，算法算法2按定义中按定义中(1)的要求构造文法的要求构造文法G2=(VN2,VT2,P2,S)。算法算法1:根据定义要求根据定义要求 (2)X，VT*1.VN1=；P=。2.对每个对每个Ax1x2xnP且且xiVN1VT (i=1,n)，则置，则置VN1=VN1A；3.重复重复(2)，直至，直至VN1不再扩大为止。不再扩大为止。4.对每个对每个Ax1x2xnP且且xiVN1VT (i=1,n)，则，则Ax1x2xn置入置入P1中。中。构造文法构造文法G1=(VN1,VT,P1,

24、S)例例，文法，文法GS=(S，U，V，M，N，a,b，P，S)由由SV可得可得:VN1=S，V，NP1=SV，Va，Nb 其中其中P为为:SUV，UM，Va，Nb文法文法G1S=(S，V，N，a,b，SV,Va,Nb，S )可得可得:由由Nb可得可得:VN1=N初始初始:VN1=由由Va可得可得:VN1=V，N1.VN2=S；VT2=；P2=2.对于对于G1的每个产生式的每个产生式Ax1x2xn，则置，则置VN2=VN2xiAVN2xiVN1，i=1,n VT2=VT2xiAVN2xiVT，i=1,n 3.重复重复(2)，直至不再扩大为止。，直至不再扩大为止。4.对于每一个对于每一个AP1，

25、若，若A的左、右部的左、右部之任一文法符号之任一文法符号X，都有，都有XVN2VT2，则，则P2=P2A。算法算法2:根据定义要求根据定义要求 (1)SX*构造文法构造文法G2=(VN2,VT,P2,S)可得文法可得文法G2:VN2=S，V,VT2=a,P2=SV，Va。上例上例，文法，文法G1S=(S，V，N，a,b，SV,Va,Nb，S )由由SV可得可得:VN2=S，V；VT2=初始初始:VN2=S；VT2=由由Va可得可得:VN2=S，V；VT2=aP2=SV，Va 例例，设文法，设文法GS=（S,U,V,W，a,b,c，P，S)，VbVac WaW 其中其中 P:SaSWU Ua P

26、2=SaSU，Ua P1=SaSU，Ua，VbVac 由由Vac可得可得:VN1=V初始初始:VN1=由由Ua可得可得:VN1=V，U施行施行算法算法1由由SU可得可得:VN1=S，V，UVT=a,b,c施行施行算法算法2由由SaSU可得可得:VN2=S，U；VT2=a初始初始:VN2=S；VT2=由由Ua可得可得:VN2=S，U；VT2=a2.消除单一产生式消除单一产生式 单一产生式单一产生式系指系指AB P(A，B VN)。例例，文法文法G=（S,A,B，a,b，P，S），），其中其中 P:SABAB AaAbabBBbb P中去掉单一产生式中去掉单一产生式SA应加入应加入SaAbab；去

27、掉单一产生式去掉单一产生式SB应加入应加入SBbb。3.构造构造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）；）；*首先首先构造构造W(Ai)集合集合:W(S)=S，A，B再构造产生式再构造产生式P1:AaAbab例例，文法文法G=(S,A,B，a,b，P，S)，其中其中 P:SABAB AaAbabBBbb W(A)=AW(B)=BSABaAbabBbbBB

28、bb例例，文法，文法G=(S,A,B,C，a，P，S)，其中其中 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 消除无用产生式消除无用产生式 Ca，得文法，得文法G1的产生式的产生式:SAB Aa Ba 3.消除或规范空符号产生式消除或规范空符号产生式 空符号产生式空符号产生式是指是指A，其中，其中AVN。例例，文法，文法G1:SaUbV U Vc 变成文法变成文法G2:SabV Vc 显然，显然，L（G1），消除空符号产生式），消除空符号

29、产生式U 任给一文法任给一文法G=(VN,VT,P,S)，若，若L(G)，则消除任何空，则消除任何空符号产生式，称为符号产生式，称为消除空符号产生式消除空符号产生式；若若L(G)，则除消除所有空符号产式以外，还必须，则除消除所有空符号产式以外，还必须增加增加S，其中，其中S 是根符号，称为是根符号，称为规范空符产生式规范空符产生式。算法算法1，确定，确定是否属于是否属于L(G)1.令令W1=AAP；2.Wn=Wn-1xxP Wn-1+，n2；3.（2）中集合序列）中集合序列Wn存在存在K，使得，使得WK=WK+1，此时，令此时，令W=WK，显然有，显然有W1 W2 W VN；4.若若SW，则，

30、则L(G)，否则，否则L(G)。例例，设文法，设文法 GS=（S,A,B,C，a,b,c，P，S），），其中，其中，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，消除空符号产生式消除空符号产生式 1.P1=；2.对每个产生式对每个产生式Ax1x2xnP和所有和所有i，1in，作作 P1=P1Ay1y2yn|若若xi(VN-W)VT，则取则取 yi=xi；若；若xiW，则，则yi取取xi和和*-A|A

31、x1x2xnPx1x2xn(2)中说明，若产生式中说明，若产生式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=（S,A,B,C，a,b,c，P，S），），其中，其中，P:SaA ABC BbB CcC W=A，B，C算法算法3，规范空符号产生式，规范空符号产生式 若若L（G），则先按算法），则先按算法2消去空符号产生式，若出消去空符号产生式，若出现产生式现产生式SS，则删除，则删除SS，最后加入空符号产生式，最后加入空符号产生式S（S 是根符号）。是根符号）。例例，设文法，设文法G的产生式的产生式P为为:由算法由算法1，W=S，A，L（G）；由算法由算法2，P规范成规范成P1 :SASAS Aa；由算法由算法3，P1规范成规范成P2:SASA|Aa。SAS Aa