《【考研计算机专业课】天津大学编译原理讲义第三章文法和语言》由会员分享，可在线阅读，更多相关《【考研计算机专业课】天津大学编译原理讲义第三章文法和语言（49页珍藏版）》请在金锄头文库上搜索。
1、第三章 文法和语言,3.1 文法和语言 3.2 文法的等价变换,3.1 文法和语言,文法: 定义的一些形式规则。,语言: 由定义的规则所能识别的全部句子的集合。,1) 文法和语言的定义 2) 文法的Chomsky分类 3) 文法产生式的其它表示法,字母|字母|数字,3.1.1 文法和语言的定义,1. 文法是描述语言的语法结构的形式规则(即语法规则)。,文法是一个四元组: GS=(VN，VT，P，S),VN为非终极符集合；,VT为终极符集合； VNVT =；,一般令V= VNVT ，V中的符号称为文法符号；,P为产生式集合；,P中的每个产生式写为: ；V*VNV*，V*,S为开始符号。,例，G
2、=（N，0，1，N0N，N1N，N0，N1，N）,VN =N,VT =0，1,V=N，0，1,S=N,2. 符号串的推导与归约,已给文法G=(VN,VT,P,S)，V=VNVT，令x、y、 V*，且P，此时，我们称符号串xy能够直接推导出符号串xy，记作xy xy。,例，文法G存在如下推导: N 1N 11。,若符号串xy是符号串xy的直接推导；,则符号串xy是符号串xy的直接归约。,归约是推导逆过程,设存在产生式，即xyxy,3. 文法的句型、句子和语言的定义,设G=(VN,VT,P,S)是一文法,若S ，其中S是开始符号，V*，则称为文法G的句型。,*,若S ，且VT*，则称为G的句子。,
3、*,文法G所产生的语言，记作L(G)=|VT*，且S ,*,4. 产生式和文法的递归性,设给定文法G=(VN,VT,P,S)，,若=且,则称产生式A是左递归产生式；,若且=,则称产生式A是右递归产生式。,P中至少有一个产生式是递归产生式，则称此文法G是递归文法。,一般的文法都是递归的，文法G只有递归定义，L(G)中句子才是无穷的。,5. 句型的规范推导和规范规约,句型的最右推导称为规范推导，逆过程称为规范归约，即最左规约。,若在推导关系1n中，每次最先替换最右(左)的非终结符，则称为最右(左)推导。,若在规约过程中，每次最先规约最左(右)的非终结符，则称为最左(右)规约。,6. 文法句型的短语
4、,设文法G=(VN,VT,P,S),句型的最左直接短语称为此句型的句柄。,i1 ，i2，i3 ，i1*i2 ，i1*i2+ i3都是句型i1*i2+i3的短语。,i1 ，i2，i3 均为直接短语。,i1是句柄。,i2+i3是否句型i1*i2+i3的短语？,3.1.2 文法的Chomsky分类,设文法G=(VN,VT,P,S) ，其产生式形式为:,0型文法（短语结构文法）:, V*VNV* ，V*,如果对 0 型文法分别加上以下的第 i 条限制，则我们就得到 i 型文法。,1.G的任何产生式均满足|，S除外；,2.G的任何产生式 A，AVN ，V* ；,3.G的任何产生式 AB 或 A，其中 B
5、VN VT* ；,例，文法G=(VN,VT,P,S)， P定义为:,L(G)=anbncn|n1,SA| AabD|aABD,Dc,DBCB CBCD,CDBD bBbb,2型文法也称上下文无关文法，用于描述多数现今程序设计语言的语法结构。,例，文法G =（S，a,b，P，S）,L(G)=anbn|n1,SaSb|ab,P定义为:,3型文法也称正则文法，由其产生的语言叫做正规语言，即正规集。,例，文法G =（S，0,1，P，S）,L(G)=(0|1)*,S0S|1S|0|1,P定义为:,每一种类型的文法G都定义了一类语言L(G)，每种类型的语言都存在一种识别器。,0型 图灵机,1型 线性界限自
6、动机,2型 下推自动机,3型 有限自动机,3.1.3 文法产生式的其他表示法,规则2.1 产生式的花括号表示法。,例，有产生式 SS|，其中: SVN，VT ，则可用花括号表示为: S,若花括号有上、下角标，即0n ，表示或0次出现，或n次出现。,规则2.2 产生式的方括号表示法。,若字符串可0次出现或1次出现，则可用方括号表示，即= 01 。,规则2.3 提取候选式左、右部的公用因子。,若有产生式: AxW1yxW2yxWny,则可表示成: Ax(W1W2 Wn )y,3.1.4 正则文法,1. 正则文法与状态转换图,右线性文法GS (UxV|y) VVN，x,yVT*,左线性文法GS (U
7、Vx|y) VVN，x,yVT*,许多程序设计语言的单词可以用正则文法来表示，而对于正则文法所描述的语言又可以用状态转换图来非形式的表示。,对于右线性文法GS (UxV|y)，状态转换图的表示方法如下：,(1) GS中的非终结符表示状态，GS的开始符号S对应状态转换图的开始状态S；,(2) 增加一个新状态Z，作为状态转换图的终止状态；,(3) 对于GS中形如UxV的每条产生式，画一条从状态U到状态V的方向弧，弧上的标记为x；,(4) 对于GS中形如Uy的每条产生式，画一条从状态U到终态Z的方向弧，弧上的标记为y,例，给出与正则文法G(S)等价的状态转换图。,GS： SaA SbB S a Aa
8、B AbA BaS BbA B,正则文法与状态转换图等价，是指正则文法所确定的语言L(G)，与状态转换图所接受的语言L(TG)相同： L(G)=L(TG),左线性文法GZ (UVx|y)，状态转换图的表示方法如下:,(1) 用状态表示GZ中的非终结符，GZ的开始符号Z对应状态转换图的终止状态Z,(2) 增加一个新状态S，作为状态转换图的初始状态；,(3) 对于GZ中形如UVx的每条产生式，画一条从状态V到状态U的方向弧，弧上的标记为x；,(4) 对于GZ中形如Uy的每条产生式，画一条从初态S到状态U的方向弧，弧上的标记为y。,例，给出与正则文法GZ等价的状态转换图,GZ: ZU0ZV1 UZ1
9、 U1 VZ0 V0,2. 正则文法与正规式,一个正则语言可以由正则文法定义，也可以由正规式定义。,对任意一个正规文法，存在一个定义同一语言的正规式；反之，对每个正规式，存在一个生成同一语言的正规文法。,正规文法和正规式之间是可以相互转换的。,A. 首先介绍将上的一个正规式R转换成正规文法G=(VN，VT，S，P)，并使L(G)=L(R)的方法:,(1) 文法的终结符号集VT与字母表相同，即VT=；,(2) 对于正规式R，定义一非终结符号S生成产生式SR，并将S定为文法G的开始符号(识别符号)；,(3) 对已有的产生式，按以下原则进行变换，直到每个产生式最多含有一个终结符号为止:,设x,y是正
10、规式，则,对于形如Axy的产生式，重写成：AxB，By两产生式，其中，BVN ；,对于形如Ax|y的产生式，重写成：Ax，Ay两产生式；,按(2)和(3)所确定的产生式组成文法的产生式集合P，而(2)和(3)中的非终结符号组成文法的非终结符号集VN,例，将正规式R=a(a|b) *转换成相应的正规文法G，并使L(G)=L(R),(1)根据正规式R可以确定=a，b，所以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,整理
11、得变换结果GS:,B.正规文法转换成正规式: 将正规文法G=(VN，VT，S，P)转换成正规式R，并使L(R)=L(G)的方法如下:,使用转换规则合并文法的产生式，最后只剩下一个开始符号定义的产生式，并且产生式的右部不含非终结符号。转换规则如下:,(1)若有产生式AxB By 则转换成正规式: A=xy,(2)若有产生式AxA|y 则转换成正规式: A=x*y,(3)若有产生式Ax Ay 则转换成正规式: A=x|y,例，设有文法GS SaA Sa AaA AdA Aa Ad 试求正规式R，使L(R)=L(GS),(1)产生式和得正规式: S=aA|a,(3)将A代入S得: S=a(a|d)
12、* (a|d) |a,=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|d,3.2 文法的等价变换,若文法G1、G2满足等式L(G1 ) =L(G2 ) ，则称文法G1、G2是等价的。,设文法G1S= (VN,VT,P,S)，,显然L（G1）=L（G2），G2称为G1的拓广文法。,其中，P=A| APSS,我们构造文法G2S=(VNS，VT，P，S),初始化:,等价变换的几种方法,1. 消除无用符号和无用产生式,2. 消除单个产生式,3. 消除或规范空符号
13、产生式,1. 消除无用符号和无用产生式,任给一产生式AP，若产生式左部或右部含有无用符号，则称此产生式A为无用产生式。,已知文法G=(VN,VT,P,S)，下面的算法1，按定义中(2)的要求构造文法G1=(VN1,VT,P1,S)，算法2按定义中(1)的要求构造文法G2=(VN2,VT2,P2,S)。,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,S),例，
14、文法GS=(S，U，V，M，N，a,b，P，S),由SV可得: VN1=S，V，N,P1 = SV，Va，Nb ,其中P为: SUV，UM，Va，Nb,由Nb可得: VN1=N,初始: VN1=,由Va可得: VN1=V，N,1. VN2=S；VT2=；P2=,2. 对于G1的每个产生式Ax1x2xn，则置VN2= VN2xiAVN2xiVN1，i=1,n VT2 = VT2xiAVN2xiVT，i=1,n,3. 重复(2)，直至不再扩大为止。,4. 对于每一个AP1 ，若A的左、右部之任一文法符号X，都有XVN2VT2 ，则P2= P2A。,可得文法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=a,P2 = SV，Va ,
