文法和形式语言.pptx-得力文库

资源描述

《文法和形式语言.pptx》由会员分享，可在线阅读，更多相关《文法和形式语言.pptx（93页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1概述程序设计语言包含三方面如：x=a+b*c语法：语言的构成规律,C语言中赋值语句的写法语义：语言所代表的含义，对=号右边的表达式进行计算，再赋值给左边的变量语用：语言的实际应用，用于计算和保存值形式化方法：定义基本符号串和规则，根据规则“造句”形式语言：只看语法，不考虑含义用规定的符号串和规则来书写的语言第1页/共93页22.1 符号和符号串组成形式语言的基本要素字母表是符号的非空有穷集合习惯用大写字母表示如有字母表、V：=a,b,cV=0,1符号(字符)字母表中的元素如：a，b，c即为符号不同文种的语言有适用于该语言的字母表第2页/共93页3符号串：字母表中符号组成的有穷序列。如：=a

2、,b,c，则可以有符号串a,b,c,aa,ab,ac,aaa有序性：若符号串中符号出现的顺序不同，符号串也不同，如ab和ba是不同的符号串空串：不含有任何符号的串称作空串，记作。符号串集合：字母表上若干个符号串组成的集合如：有符号串集合A=ab,bcB=a,ab,abc符号串与符号串集合第3页/共93页4句子字母表上符合某种规则构成的符号串。语言字母表上句子的集合。注：用a,b,c,r表示符号；用s,t,u,z表示符号串；用A,B,C,Z表示符号串集合。如在字母表=a,b,c上，有符号串集合A=a,ab,aa,abc，s=ab是A中的符号串，a,b,c都是字母表中的符号句子和语言第4页/共93

3、页5例如：=a，b，c，有x,y符号串二、符号串的运算符号串相等字母表上的两个符号串x，y，若x，y的各个符号依次相等，则该两符号串相等，记x=yx=y若x=abbc，y=abbc若x=ab，y=baxy第5页/共93页6符号串长度符号串中包含符号的个数，用x表示abcd=4=0符号串连接设字母表上的两个符号串x，y，把y的所有符号相继写在x的符号之后所得到的符号串称为x与y的连接，用xy表示若x=ab，y=ba则xy=abba且xy=x+yx=x=xxyyx第6页/共93页7符号串的逆符号串x的倒置例：x=abc，符号串x的逆为cba符号串的前缀、后缀、子串后缀：符号串任意尾部，包括空串前缀

4、：符号串任意首部，包括空串如：符号串abc前缀：,a,ab,abc后缀：c,bc,abc,子串：a,b,c,ab,abc,bc,第7页/共93页8符号串的幂符号串x自身连接n次得到的如：x=ab，则有x0=x1=abx2=ababxn=ababab(n个ab相连，而不是相乘)注：用an表示n个a相连接的符号串，而不是n个a相乘第8页/共93页9符号串集合的乘积定义：若串集A=1,2,，串集B=1,2,，则乘积AB=|AandB在A中任取一个符号串与B中任一符号串连接例如：A=ab,bc;B=ac,cb则AB=abac，abcb，bcac，bccb注：由于x=x=x所以A=A=A串集的自身乘积称

5、作串集的方幂空集：不包含任何元素有A=A=，但第9页/共93页10符号串集合的幂例如：串集A的各次方幂定义为：A0=A1=AA2=AAAn=AAn-1（=An-1A）(n0)为符号串集合A的自身乘积若A=ab,bc，则有A0=A1=ab,bcA2=abab,abbc,bcab,bcbc第10页/共93页11集合的闭包与正闭包正闭包：A+=A1A2An，不包含空串闭包：A*=A0A1A2An可证明：A*=A0A+A+=AA*=A*A若A=a,b，则有A*=,a,b,aa,ab,ba,bb,aaa,A+=a,b,aa,ab,ba,bb,aaa,推论：若A是字母表，则A*包含空串和由A中符号构成的所

6、有可能的符号串第11页/共93页122.2 文法和语言语言的有穷表示生成方式（文法）识别方式（自动机）类似自然语言由句子构成，句子要符合一定的规则，称为“文法”语言是无穷的，规则确是有限的如何用有限的文法规则推导出无限的句子，即“语言的有穷表示”第12页/共93页13一、文法的概念文法构造句子的规则，用于产生或推导句子规则，二元组形如：U:=u或Uu，即“符号:=符号串”的形式含义：U定义为u，或者U由u组成规则又叫产生式：U产生出u第13页/共93页14例如：自然语言中有下面的句子Youngmenlikepopmusic.其语法规则如下：句子由主语和谓语构成Young|pop：形容词可以是y

7、oung或者popmen|musiclike语法成分或语法类单词符号或单词引例第14页/共93页15形式化定义文法写成GZ的形式Z为开始符号或识别符号，至少要出现一次在某一条规则的左部规则中出现的所有符号构成字汇表，记为V该文法中的字汇表V=0,1,9,如文法G中有下列规则：:=:=:=:=0:=1:=9开始符号为：第15页/共93页16规则的组成元素推论：V=VnVtVnVt=句子是由终结符组成的符号:=符号串“非终结符”用大写字母书写其集合记为Vn终结符：字汇表V中除了Vn以外的其他符号其集合记为Vt由字汇表V中的元素组成G中Vn=,Vt=0,1,9第16页/共93页17BNF表示法用“

8、|”表示“或”，用以合并左部相同的规则规则的左部只有单个非终结符如G:=:=:=:=0:=1:=9:=|:=0|1|2|9第17页/共93页18Chomsky对文法的定义文法是四元组G=Vn,Vt,P,SVn：非空有穷的非终结符号集合,即规则左部符号的集合Vt：非空有穷终结符号集合；且VnVt；字汇表V=VnVtS属于Vn，称为开始符号或识别符号。P是一个产生式(规则)的非空有穷集合，每个产生式的形式是(或:=)，其中V+，V*。开始符号S至少必须在某个产生式的左部出现一次如有文法G=Vn,Vt,P,S其中：Vn=N,DVt=0,1,2,9P=N:=D|ND,D:=0|1|2|9此文法将产生所

9、有的无符号整数第18页/共93页19二、推导的定义推导与归约，互为逆过程推导：使用产生式的右部取代左部的过程用于：从开始符号生成符号串的一步步推导过程归约：将左部取代右部的过程用于：由符号串反过来归约到开始符号的过程推导的分类直接推导推导广义推导最左推导最右推导(规范推导)第19页/共93页20vw即xuyxUy直接推导与直接归约定义：对于文法G，字汇表V，x，yV*，有规则U:=u，若v=xUy，w=xuy则称v直接推导出w，记为或w直接归约到v，记为直接推导就是在推导过程中每次只用一个规则来进行替换即xUyxuywv第20页/共93页21直接推导举例EE+TT+TF+T_E:=T例：设有文

10、法GE要从开始符号E推导出符号串F+T，则经过下面步骤：E:=E+T|TT:=T*F|FF:=(E)|i第21页/共93页22定义：对文法G，其中存在一直接推导序列即v经过n次直接推导得到w，n1有多少个，则推导长度为多长v=u0u1u2.un=w(n0)称v推导出wvw或称w归约到vwv推导长度若v=w则vwwv称为广义推导，n0推导与归约第22页/共93页23EE+T_T+T_F+T_i+T_i+T*F_i+F*F_i+i*F_i+i*i从开始符号E进行推导ETT*F_F*F_i*Fi*(E)i*(E+T)_i*(T+T)_i*(F+T)_i*(i+T)i*(i+F)i*(i+i)n=8n

12、设GZ是字汇表V上的一个文法则称x是G的一个句型，x是由Z推导出来的符号串Zx，xV*文法GZ产生的所有句子的集合称为文法GZ所定义的语言L(GZ)如果Zx，xVt*，即仅含有终结符的句型是一个句子+文法和语言第26页/共93页27例：考虑一个文法G(0,1,S,S,P)，其中P=S:=0S1|01最后语言为L(GS)=0n1nn1第27页/共93页28例1：文法GZZ:=aZbabZaZbaaZbban-1Zbn-1an-1abbn-1=anbn可以确定语言L(GZ)=anbnn1文法Vs语言给定一个文法，能从结构上唯一地确定其语言第28页/共93页29例2：L(GS)=aibjakcjbi

13、i0，j1，k1给出文法GSS:=aSbPP:=bPcbQcQ:=Qaa生成的语言。S推出的符号串的形式是aiPbi（i0），而P推出的符号串的形式是bjQcj（j1），Q推出的符号串的形式是ak（k1）。第29页/共93页30给定一种语言，能确定其文法，但这种文法不唯一例：L(GZ)=abnan1abaabbaabbba.文法G1ZZ:=aBaB:=bBb文法G2ZZ:=aBB:=babB文法G3ZZ:=BaB:=abBb等价文法：产生相同语言的文法L(G1Z)=L(G2Z)第30页/共93页31例1:写一个文法,使其语言是奇数集,且每个奇数不以0开头D13579D2468DD0DAADDN

14、ADDGN第31页/共93页32例2:写一个文法,使其语言L(G)=anbman|n,m0考查形式抽象能力。应当仔细研究语言的结构特点，通常是这些语言具有形式上的对称性和字符数目上的相关性等特点。S:=aSaBB:=bBGS第32页/共93页33直接递归规则：某规则的左、右部具有相同的非终结符号例：U:=xUy为直接递归规则，简称递归规则若x=，U:=Uy左递归规则若y=，U:=xU右递归规则若x、y，U:=xUy自嵌入规则递归规则与递归文法第33页/共93页34直接递归文法至少含有一条递归规则的文法文法中使用递归规则后，可以用有限的规则定义无限语言但不利是对于具有左递归性的文法，不能采用自顶

15、向下的分析算法文法GZZ:=aBaB:=bBb间接递归文法如U:=VxV:=Uy|z，因UVxUyx，是间接递归文法UxUy称U为间接递归UUy称U为间接左递归UxU称U为间接右递归第34页/共93页35定义：设有文法GZ，w=xuy是其一个句型若有ZxUy且Uu则u是句型w=xuy相对于U的短语若有ZxUy 且Uu则u是句型w=xuy相对于U的简单短语或直接短语短语、简单短语、句柄短语与简单短语即U可以推导出u即U可以直接推导出u第35页/共93页36理解定义UuxUyxuyZxUyxuy短语须满足两个条件：A、可以归约B、原句型归约后仍为一个句型简单短语须满足两个条件：A、可以直接归约B、

16、原句型归约后仍为一个句型句柄句型的最左简单短语为该句型的句柄Uu短语u是句型w中的子串：可以由u归约到U，而w也可以归约到一个句型第36页/共93页37用定义求T+i的所有短语、简单短语和句柄写出由E到T+i的所有推导过程，由此求得句型T+i的所有可能的子串u有三种情况：u=T+i，u=i，u=T每个u分别试探出归约到的UEET+iT+i为句型T+i相对于E的短语ET+TT+ii为句型T+i相对于T的短语ET+FT+ii为句型T+i相对于F的短语，且为简单短语T为句型T+i相对于E的短语，且为简单短语，句柄T+iEE+i例：设有文法GE E:=E+T|TT:=T*F|FF:=(E)|iF:=i

17、E:=TwuUTi+第37页/共93页382.3 语法树和二义性一、语法树和推导1、语法树定义：、树根是文法的开始符号、每个结点都是文法的终结符或非终结符、非终结符结点一定有子结点、若结点A有n个分枝结点为B1B2Bn，则有A:=B1B2Bn为G的一个规则第38页/共93页39设有文法GS:SaBAaBbdSaABabd则下面两棵树都是G的语法树：S:=aABA:=Ba|aB:=bd第39页/共93页402、语法树的生成反映了一次推导过程例:文法GNN:=NDDD:=0129句子25的推导过程和语法树NN DD25NN D5D2最左推导NNDDD2D25最右推导NNDN5D525推导过程不同，

18、语法树的生长过程也不同，但最终生成的语法树完全相同第40页/共93页413、子树与短语子树语法树的某一结点连同它向下射出的部分组成了语法树的子树。简单子树只含有单层分枝的子树称为简单子树。NNDD52ND2D2D5NND第41页/共93页42子树与短语的关系子树末端结点组成的符号串是相对于子树根的短语简单子树末端结点组成的符号串是相对于简单子树根的简单短语最左简单子树末端结点组成的符号串是句柄利用生成树方便求得短语、简单短语和句柄先从开始符推导出句型w，由此写出生成树第42页/共93页43+EETTFi短语：T+i为语法树的根E的短语T为E的短语，且为简单短语i为T的短语i为F的短语，且为

19、简单短语句柄：T最左的简单子树的末端结点求T+i的所有短语、简单短语和句柄例：设有文法GE E:=E+T|TT:=T*F|FF:=(E)|i步骤：从根开始，每棵子树的根作为U，该子树的末端结点连接成的符号串即为u，u是相对于U的短语或简单短语第43页/共93页44EE-TT*FFi短语：E-F*iF*iFi简单短语：Fi句柄：F求E-F*i的所有短语、简单短语和句柄例：设有文法GE E:=E+T|TT:=T*F|FF:=(E)|i第44页/共93页45设有文法GA求#C+C*a#的所有短语、简单短语和句柄A#B#B+CCC*a短语：#C+C*a#C+C*aCC*a简单短语：CC*a句柄：CA:

20、=#B#B:=B+C|CC:=C*a|a第45页/共93页46已知语法树得到推导对已知的语法树，自底向上可以得到句型的归约过程，进一步可以得到推导过程步骤：从左到右、由下而上修剪子树末端结点即从最左边的子树开始依次修剪末端结点NNDD52如左图中句子25的归约过程为25D5N5NDN(最左归约、规范归约)反过来即推导过程NNDN5D525rrrr第46页/共93页47例：ifBthenifBthenSelseS理解一ifBthenifBthenSelseS理解二ifBthenifBthenSelseS二、文法的二义性第47页/共93页48设有文法GE句子i+i*i的按不同推导得到的两棵语法树E

21、E+EiE*EiiEE*EiE+Eii不同E:=E+EE*E(E)i二、文法的二义性最右推导(先乘)EE+EE+E*Ei+i*i+最左推导(先加)EE*EE+E*Ei+i*i+第48页/共93页49SifB then SifBthen S else SSifBthenSelse SifBthen S二义性文法的定义定义：一个文法的某个句子存在两棵不同的语法树，则称该文法是二义性文法。文法GS：S:=ifBthenSifBthenSelseSA句型ifBthenifBthenSelseS的语法树第49页/共93页50注意文法的二义性和语言的二义性是两个不同的概念对于一个程序语言来说，通常希望它的

22、文法是无二义的可能有两个不同的文法G和G，其中一个是二义的而另一个是无二义的，但是却有L(G)=L(G)，即这两个文法所产生的语言是相同的。二义性问题是不可判定的，即不存在一个算法，它能在有限步骤内，确切的判定一个文法是否为二义的。第50页/共93页51二义性的解决办法修改编译算法此时i+i*i只有最右推导，先乘后加GE规定：*/的优先级大于+-，优先级高的先归约优先级相同的，先左后右进行归约GS规定：else与最近的未匹配的then相匹配句型ifBthenifBthenSelseS的语法树也只有一棵通常不说语言本身的二义性，句子或句型的不确定性是由文法的二义性带来的。我们不可以改变句子的集合

23、，但能改变其二义性文法。第51页/共93页52尽量避免规则左部的符号在规则右部同时出现两次或两次以上。修改文法修改后为文法GEE:=E+E E*E(E)i如文法GEE:=E+T|E-T|TT:=T*F|T/F|FF:=(E)|i某规则的左部在右部出现一次也可能导致二义性第52页/共93页532.4 文法的实用限制一、文法的实用限制1、有害规则形如U:=U的规则为有害规则如GNN:=NN:=NDDD:=019则句子25的多种语法树第53页/共93页542、多余规则则称U为活的非终结符号，一定会出现在句型中ZxUyUVn，x,yVt*活的非终结符号：可推出符号：在某句型中出现的符号称为可推出符号，

24、其中包含非终结符和终结符活的非终结符号亦为可推出符号第54页/共93页55例：文法GSS:=aABaA:=aAbbB:=dC:=aBfSSaABaaAbBaaAbd可推出符号集：SaA Bbd活的非终结符号集：S A B第55页/共93页56多余规则某规则的左部符号U，若不满足下列条件，则该规则为多余规则。U为可推出符号（活的非终结符号）必须能从U推出句子（终结符号串）所谓多余规则是指：在推导文法的所有句子时，始终用不到的规则在推导过程中，一旦用了此规则，则无法推出句子来第56页/共93页57例：文法GZZ:=BeA:=AeeB:=CeAfC:=CfD:=fD为不可推出符号D:=f为多余规则不

25、能从C推出句子C:=Cf为多余规则不能从B:=Ce推出句子 B:=Ce为多余规则ZBeAfeefeZBeCeeCfe可推出符号集：ZBACef第57页/共93页58多余规则的危害在程序设计语言的文法中如果包含有多余规则,其中必定有错误存在：文法GZZ:=AbA:=fB:=f在归约时，碰到f，若使用B:=f，则无法分析下去，就会出错第58页/共93页593 文法的实用限制两点：不能有多余规则不能有有害规则如果文法G中所有规则均满足实用限制条件，则称文法G是压缩或化简过的。第59页/共93页60例：文法GZZ:=BeA:=AeeB:=CeAfC:=CfD:=f经过压缩化简后的文法GZZ:=BeA:

26、=AeeB:=Af被删除的多余规则有D:=fC:=CfB:=Ce第60页/共93页611文法的开始符号不出现在规则的右部二、文法的变换2每个非终结符号均能导出终结符号串3每个非终结符号都出现在任意句型中4没有特殊规则，形如A:=B，A,BVn文法的六种假定：5没有空规则，形如A:=6没有直接左递归规则，形如A:=Ay等价变换第61页/共93页621文法的开始符号不出现在规则的右部引进符号S，在文法中拓充一条规则SS,以S为开始符，变GS为GS例G1NNNDDD019NN变为G2N称G2为G1的拓广文法六种文法变换技术第62页/共93页63即找到推不出句子的非终结符，并删除多余规则算法：(1)构

27、造非终结符号集I首先令=AAtG1,tVt+，找到右部只有终结符的规则，将其左部非终结符归入II递归扩充=W|WxG1,x(Vt)+，找到右部由终结符和原中非终结符组成符号串的规则，其左部归入(2)从文法G1中删除那些左部或右部含有不属于中的符号的规则2每个非终结符号均能导出终结符号串第63页/共93页64例文法G1SS:=aABSbDADdA:=bABdsAdDDB:=bABdSBD:=dSdI首先令=D|D:=d=DII递归扩充=DA|A:=dDD=A,D=A,DS|S:=bDADd=S,A,D等价文法G2SS:=bDADdA:=dsAdDDD:=dsd仅有D:=d的右部全是终结符A:=d

28、DD的右部由d和D组成，A入S:=bDADd的右部由b、d和A、D组成，S入第64页/共93页653 消除用不到的非终结符使每个非终结符都能出现在某一句型中算法：构造非终结符集合(所有活的非终结符)从开始符起，将开始符归入=S递归扩充，找到由中非终结符直接推导出的规则,将其右部的非终结符归入，直到中所有非终结符推出的规则都扫描完毕删除左部不在中的非终结符的规则删除的也是多余规则，结合方法2先删除推不出句子的非终结符的规则，再用3最终=U|SxUy,UVn,x,yV*第65页/共93页66先利用2,找出不能推导出句子的非终结符号，并删除相应的规则再利用3,找出不在任意句型中出现的非终结符号,并删

29、除相应的规则：从S开始，=S，考查G2中所有规则，没有变化，所以左部为D的规则是多余规则。故得等价文法G3SS:=ad例：文法G1SS:=adbAA:=dBDB:=asAD:=bDe=S,D，由S:=ad，D:=e得到，A、B为推不出句子的非终结符得等价文法G2SS:=adD:=bDe第66页/共93页67算法：1构造非终结符号集4 没有特殊规则A:=B，A,BVn对文法中的每一个非终结符号A，求其AA=BABG1，BVn，即对每个A求由其推导出的非终结符B构成的集合+2若有AB，并且文法中有B:=x，则在文法G2中增加规则A:=x，删除AB和无用规则+第67页/共93页68例：文法G1AA:

30、=BdEB:=ADbD:=BdE:=EaeAAdEAABDbdBAdEBBbBDdDAdEDBbDDdA=B=D=A,B,DE=，对A中由A推出的每个非终结符的规则判断是否为特殊规则和无用规则等价文法G2AA:=bdEdB:=ddEbD:=dEdbE:=EaeA:=B特殊规则，删除，增加A:=b因A:=B，删除B:=D，增加A:=dB:=A特殊规则，删除，增加B:=dEB:=D特殊规则，删除，增加B:=dD:=B特殊规则，删除，增加D:=b因D:=B特殊规则，增加D:=dEA:=dE保留B:=b保留D:=d保留第68页/共93页69例G1AA:=aBbDB:=DDD:=b删除D:=，=B,D对

31、B:=DD和A:=aBbD进行扩充与G1等价的文法G2为A:=ababDaBbaBbDB:=DDDD:=b5 没有空规则算法：构造非终结符所有空规则的左部归入递归扩充：由中符号构成的符号串能归约到的非终结符归入删除空规则和只能导出空串的非终结符扩充新规则对形如A:=xByD，B,D，x,y(V-)*增加下列规则A:=xy|xyD|xBy|xByD第69页/共93页70解：=D|D:=DB|B:=DD=B,D删除空规则D:=后A:=aBbDB:=DDD:=b对A:=aBbD和B:=DD进行扩充新规则A:=ababDaBbB:=D例G1AA:=aBbDB:=DDD:=b与G1等价的文法G2为A:=

32、ababDaBbaBbDB:=DDDD:=b第70页/共93页716 消除左递归规则若文法中有规则A:=Ayx(x不以A开头)可用A:=xAA:=yA来代替这两种形式是等价的一般而言AAy1Ay2Aynx1x2xn消除其左递归Ax1Ax2AxnAAy1Ay2AynA第71页/共93页72例：文法G1EE:=E+TETTT:=T*FT/FFF:=(E)i消除左递归后的等价文法G2EE:=TEE:=+TE|TET:=FTT:=*FT/FTF:=(E)i第72页/共93页732.5 扩充的BNF表示法在BNF表示法中引进6个专用符号，(，)(1)花括号t表示t可重复多次如：N:=ND|DD:=0|1

34、类Chomsky对文法的定义从形式上说文法G是一个四元式(VN,VT,P,S)Chomsky对文法的分类根据对产生式施加的限制，可分为0型文法1型文法2型文法3型文法四种类型的文法分别对应着四种类型的语言第76页/共93页770型文法0型文法(短语文法或无限制文法)：文法G中的每个规则若为:=，V+,V*非空，可为空，,是用字汇表中任意符号构成的符号串0型文法确定的语言为0型语言L0注：识别0型语言的自动机称为图灵机(TM).0型文法是对产生式限制最少的文法。任何0型语言都是递归可枚举的。对0型文法产生式的形式作某些限制，可得到其他类型文法的定义。第77页/共93页780型文法举例设文法G(V

35、n,Vt,S,P)，VnS,A,B,C,D,E,Vta其中P为:(0)S:=ACaB(1)Ca:=aaC(2)CB:=E(3)aD:=Da(4)AD:=AC(5)aE:=Ea(6)AE:=第78页/共93页791型文法(上下文有关文法)1型文法：文法G中的每个规则若为xUy:=xuy，UVn,x，yV*，uV+，规则的左右部前缀和后缀对应相同U是非终结符，u是非空句型1型文法中没有空规则1型文法确定的语言为1型语言L1或上下文有关语言。注：自然语言是上下文有关文法识别1型语言的自动机称为线性界限自动机(LBA)1型文法意味着，对非终结符进行替换时务必考虑上下文，并且，一般不允许替换成，除非是开

36、始符号产生第79页/共93页801型文法举例设文法G(Vn,Vt,P,S)，VnS,B,C,D,Vta,b,c其中P为:(0)S:=aSBC|aBC(1)CB:=DB(2)DB:=DC(3)DC:=BC(4)aB:=ab(5)bB:=bb(4)bC:=bc(6)cC:=cc第80页/共93页812型文法(上下文无关文法)2型文法：文法G中的每个规则若为A:=其中AVn，V*规则的左部是单个非终结符2型文法确定的语言为2型语言L2或上下文无关语言。注：2型文法对产生式的要求是：产生式左部一定是非终结符，产生式右部可以是Vn、Vt或BNF表示法等价于2型文法非终结符的替换不必考虑上下文;识别2型语

37、言的自动机称为下推自动机(PDA);第81页/共93页822型文法举例设文法G(Vn,Vt,P,S)，VnS,A,B,Vta,b其中P为:(0)S:=aB(1)S:=bA(2)A:=a(3)A:=aS|bAA(4)B:=b(5)B:=bS|aBB第82页/共93页833型文法(正则文法)3型文法：文法G中的每个规则若为A:=B（A:=B）或者A:=，其中A，BVN，Vt*A,B都是非终结符，是终结符组成的符号串或规则的左部是单个非终结符3型文法确定的语言为3型语言L3或正则语言。注：3型文法也称为正规文法RG、右线性文法或左线性文法3型文法中：要么均是右线性产生式，要么都是左线性产生式左线性文

38、法：规则均形如A:=B或A:=右线性文法：规则均形如A:=B或A:=识别3型语言的自动机称为有穷自动机FA。第83页/共93页843型文法举例设文法G(Vn,Vt,P,S)，VnS,A,B，Vt0,1其中P为:(0)S:=0A|1B|0(1)A:=0A|1B|0S(2)B:=1B|1|0第84页/共93页85四种文法之间的逐级“包含”关系注意：因为1型文法中不允许空规则，故2型或3型文法中若有空规则，就不能属于1型文法用途3型文法用于描述词法部分，2型文法用于描述语法部分第85页/共93页86程序设计语言的单词可由正则文法产生如：标识符可以由正则文法描述如下:=|现用字母表=,上的正则表达式表

39、示为(|)*正则文法与正则表达式的关系？除了正则文法以外，正则表达式也是描述单词的重要工具。由正则文法或正则式描述的正则语言的集合都称为正则集2.7 正则表达式与正则集第86页/共93页87字母表上的正则表达式和它表示的正则集递归定义如下1空串与空集是上的正则表达式，其正则集分别为、空集2任意字符a是正则表达式，其正则集为a3若e1，e2是的任意正则表达式，其正则集分别为L(e1)和L(e2),则e1|e2,e1e2,(e1)*也都是正则表达式,或连接闭包其正则集分别为L(e1|e2)=L(e1)L(e2)L(e1e2)=L(e1)L(e2)L(e1)*)=L(e1)*仅由有限次使用上述三步骤

40、而定义的表达式才是正则式第87页/共93页88正则表达式a*正则集L(a*)=L(a)*=，a，aa，aaa，正则表达式(ab)*正则集L(ab)*)=L(ab)*=，ab，abab，ababab，正则表达式ab*正则集L(ab*)=L(a)L(b)*=a，ab，abb，abbb，正则表达式b(ab)*正则集L(b(ab)*)=L(b)L(ab)*=b，bab，babab，bababab，正则表达式a|ba*正则集L(a|ba*)=L(a)L(ba*)=a，b，ba，baa，baaa,正则表达式a(a|b)*正则集L(a(a|b)*)=L(a)L(a|b)*=a，aa，ab，aaa，aab,a

41、ba,abb例令=a，b第88页/共93页89正则表达式的性质若、是正规式则下述等价式成立(|)|=|(|)()=()|=|=|(|)=|(|)|=|=(*)*=*=|*第89页/共93页90三个概念间关系一个正则语言可以用正则文法定义，也可以用正则式定义对任意一个正则文法，存在一个定义同一个语言的正则式；同样，对每个正则式，存在一个生成同一语言的正则文法；有些正则语言很容易用文法定义，有些则用正则式定义更容易；两者之间是可以转换的，结构上具有等价性。由正则文法或正则式描述的正则语言的集合都称为正则集正则文法、正则集与正则式第90页/共93页91正则文法与正则式的等价性正则文法正则式利用以下规则作变换文法产生式正则式规则1A:=xBB:=yA=xy规则2A:=xA|yA=x*yA:=Ax|yA=yx*规则3A:=xA:=yA=x|y正则式转化为正则文法（略）第91页/共93页92例文法GS S:=Sc|Bc B:=Bb|Ab A:=Aa|a，求该文法对应的正则式解：S:=Sc|BcB:=Bb|AbA:=Aa|a对应正则式A=aa*(1)将(1)代入B:=Bb|Ab=Bb|aa*b=aa*bb*(2)将(2)代入S:=Sc|Bc=Sc|aa*bb*c=aa*bb*cc*即该文法对应的正则式为aa*bb*cc*第92页/共93页93感谢您的观看！第93页/共93页

展开阅读全文