形式语言与文法讲稿.ppt-得力文库

资源描述

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

1、形式语言与文法第一页，讲稿共九十三页哦1.符号串符号串是形式语言中最基本的名词.一,字母表与符号串v 1,字母表v定义:元素的非空有穷集合v例:=a,b,c(a,b,c字母表)v=0,1(二进制数字字母表)v=汉字,数字,标点符号,(汉字组成的字母表)v注:元素可是字母、数字或其他符号.v字母表中至少有一个元素.第二页，讲稿共九十三页哦2.符号(字符)定义：字母表中的元素.注:符号是字母表中不可再分解的最小单位.3.符号串定义：字母表中的符号组成的有穷序列.例:=a,b,c符号:a,b,c符号串:a,b,c,ab,ac,aa,ba,ca,abc,例;设字母表A=0,1A中的符号:0,1A中的

2、符串:0,1,01,10,00,11,001,010,01000,第三页，讲稿共九十三页哦显然:字母表上的符号串可形成一个集合(可数无穷)注:1.符号串的组成与符号串组成的顺序有关.如0110,abba2.空符号串为不包含任何符号的符号串,记为:3.符号串的长度:符号串所含符号的个数.设符号串为x,则x的长度为x。例:a=1abc=3特别：|0即空符号串的长度为零二符号串的运算连接运算定义：设x和y为符号串，则xy被称为x与y的连接设xabc，y10a则xyabc10a；yx10aabc第四页，讲稿共九十三页哦符号串的方幂设有符号串x，则x的n次连接称为x的n次方幂，记为:x例：x（注:x）x

3、xxxxxxxxxxxxxxxxxxxxn次连接例:xabc则x，xabc，xabcabc即x，x，xn0012322nn1n1011022第五页，讲稿共九十三页哦符号串集合的乘积设ABxyx，y即:AB是x,且y的所有符号串xy构成的集合例:设Aa，b，Bc，d则ABac，ad，bc，bd注：A=A=AA=A=A(其中为空集)=注:不属于，即空符号串并不属于空集第六页，讲稿共九十三页哦4.符号串集合的方幂设A为符号串集合,则定义A=A=AA=AAA=AA=AA=AAAA=AA=AA=AAA(n个)例:设A=a,bA=A=a,bA=aa,ab,ba,bb(A共有2=4个长度为2的元素)A=

4、AA=aa,ab,ba,bba,b=aaa,aba,baa,bba,aab,abb,bab,bbb(A共有2=8个长度为3的元素)012322nn1n101232233第七页，讲稿共九十三页哦5.符号串集合的正闭包A和闭包A .符号串集合的正闭包A设A为符号串集合,则A定义为:A=AUAUAUUAU例设A=a,b则A=a,bUaa,ab,ba,bbU=a,b,aa,ab,ba,bb,aaa,bbb,=a,b即:A包括了由A上的元素a,b构成的所有符号串.符号串集合A的闭包A.A=AUAUAUUAU(A=AUA)即A=UA=AU(A=A)123n012n0+第八页，讲稿共九十三页哦例设A=a,

5、b则A=,a,b,aa,ab,ba,bb,aaa,bbb,=a,b显然:对于所有的A,有A第九页，讲稿共九十三页哦2.文法和语言的形式定义一.文法与语言的关系语言:由定义在该语言字母表上,且按一定组成规则所构成的句子的集合.即:字母表字符串(句子)(语言)语言的描述.当语言为有穷个句子的集合时,可用枚举的方法表示语言.当语言为无穷个句子的集合时,则用有无穷的语法规则(文法)描述无穷的句子的结构.语法规则第十页，讲稿共九十三页哦例:汉语:人们无法列出全部的句子.但人们可以给出一些规则,用这些规则来说明(或定义)句子的组成结构.如:汉语句子结构:=+=+=用扩充BNF来表示这种句子的结构:=(=

6、表示“定义为”，“产生”，“生成”)=(表示“或者”)=我你他(表示非终结符)=王明大学生工人英语=(不加表示终结符)第十一页，讲稿共九十三页哦=是学习 =利用以上规则(文法)推导句子:我是大学生.我我我是我是我是大学生利用上列文法:可以产生的句子:我学习英语,他学习,语,他是工人,.(很多句子)第十二页，讲稿共九十三页哦利用上列文法不可产生“我大学生是”.它不符合以上规则.文法的作用:不仅严格定义句子的结构,也是为了用有限的规则把语言的全部句子描述出来。它是用有穷的集合刻画无穷集合的工具.文法:语言的语法规则的有穷表示.(文法又称元语言)注:1.有穷的文法通过推导的方法,可以推导出给

7、定字母表上的所有句子.2.描述文法的所有字符构成了语言的字母表.3.通过文法在推导合法句子过程中会有多个句型产生.4.合法的句型和句子是用字符串表示的.第十三页，讲稿共九十三页哦二.文法的形式定义1.规则(产生式,生成式,重写规则)是一个符号与一个符号串的有序对(A,)常写成:A=或A其中:A是规则的左部.它是某个字母表的正闭包中的一个符号.即A.是规则的右部.它是中一个符号串.(包括)2.文法的形式定义定义:文法G是一个四元组,它是规则的非空有穷集合.G=(V,V,P,S)其中:V是文法规则式中的非终结符号集.V是文法规则式中的终结符号集.NTNT第十四页，讲稿共九十三页哦VV=P是文法的

8、规则式集。S是文法的开始符号（识别符号）。SVv非终结符号：出现在产生是左边，能派生出符号和符号串的符号,常用大写字母表示，即，每一个非终结符号表示一定的符号串。它至少要在产生式左边出现一次。v终结符号：不能派生出符号串的符号，它是组成语言不可再分的基本符号，一般用小写字母表示。NTN第十五页，讲稿共九十三页哦例：文法G=(V,V,P,S)v其中VN=SVT=0,1P=S0S1,S01一般约定:1.只写出文法的产生式2.第一条产生式的左部是开始符号，且习惯用G（开始符号）表示。上例文法可写成：GS:S:=0S1S:=01NT第十六页，讲稿共九十三页哦例：G:=|:=a|b|c|z:=0|1|2

9、|9v其中：VN=，S=VT=a,b,c,z,0,1,2,9字母表：V=VNVT=,a,b,c,z,0,1,2,9第十七页，讲稿共九十三页哦3.推导v有了文法，怎样由文法推导出与该文法相应的语言？为此引入了“推导”等概念。1)直接推导设x,y是V*中任意符号串，若用一次规则式可以从x推出y，则称y是x的直接推导，记为：xy。（或称符号串x直接产生了符号串y，或称y直接归约到x）第十八页，讲稿共九十三页哦例：设GS:S:=0S1|01则有如下一些直接推导：vS01（利用S:=01）vS0S1（利用S:=0S1）v0S10011（利用S:=01）v0S100S11（利用S:=0S1）说明：每利用文

10、法中的一条规则U:=u一次，均可得到一次直接推导：Uu第十九页，讲稿共九十三页哦2)推导（推导）若使用若干次规则式可以从x推出y，则称y为x的推导，记为：xy（或称x产生y，或称y规约到x），或记为：xy例：上例：0S100S11000S111000011110S1+00001111（推导长度为3）第二十页，讲稿共九十三页哦3)广义推导（推导）若xy或者xy（表示0步推导），则写为xy（反之亦然，即：xy，当且仅当xy或者xy）例，上例中：0S1+00001111也可记为：0S1*00001111注：直接推导、推导、广义推导的区别：推导长度n不同：直接推导：n1推导：n1广义推导：n0(0步推

11、导：如Ss)包涵包涵第二十一页，讲稿共九十三页哦4.句型和句子v设有文法GS,若有Sx,则称符号串x为文法GS的句型。v换句话说：凡是由识别符号推导出来的任意符号串称为句型。v句子：仅有终结符号组成的句型称为句子。v区别：符号串x(VNVT)*;x称为句型，符号串xVT*;x称为句子。第二十二页，讲稿共九十三页哦v例：GS:S:=01|0S1S01S0S100S11000111可见：01,0S1,00S11,000111均为文法GS的句型。其中：01，000111为句子（说明句型包含了句子，句子是特殊的句型）但是：符号串000S11,0000111都不是文法GS的句型。第二十三页，讲稿共九十三

12、页哦v例：已知文法GE：vE:=E+E|E*E|(E)|i(其中:VN=EVT=+,*,i,(,)v试证明:符号串(i*i+i)是文法GE的一个句子。v证明：只要证明(i*i+i)是文法GE的一个存在的推导）(需从开始符号出发)E=(E)=(E+E)=(E*E+E)=(i*E+E)=(i*i+E)=(i*i+i)即：E=(i*i+i)所以,符号串(i*i+i)是文法GE的一个句子。第二十四页，讲稿共九十三页哦三、语言的形式定义：三、语言的形式定义：v定义：由文法GS产生的所有句子的集合。即：L(GS)=x|S=+x,且xV*v注：一旦文法给定，语言就确定。语言L(G)是V*的子集。（语言是字母

13、表中终结符号串闭包的子集）即：属于L(G)的句子属于V*反之,属于V*的符号串x不一定属于L(G)。TTTT第二十五页，讲稿共九十三页哦v例：已知文法GS：S:=0S1|01v求:L(G)=?v解：分析：S=0S1=00S11=000S111=0n-1S1n-1=0n1n即：S=0n1nG描述的语言：L(GS)=0n1n|n1但：VT0,1,00,01,10,11,000,111,0000,0011,1111,，可见L(G)仅是VT的真子集。第二十六页，讲稿共九十三页哦例：已知文法：GS:S=0S|1S|,求L(G)=?解：L(GS)=,0,1,01,11,00,10,=x|x0,1*第二十七

15、3时，x=()L(G)=,(),(),(),第二十九页，讲稿共九十三页哦(2)归纳集合L(G)的组成特点：vL(G)中每个符号串呈对称形式，即(和)成对出现。vL(G)为无穷集合，因此描述出的规则中必然含有递归定义。vL(G)中的终结符号只有两个:(和)。(3)写出规则：S=(S)|即，定义此语言L(G)的文法：G:VT=(,),VN=S,S为开始符号，产生式：P：S=(S)|第三十页，讲稿共九十三页哦例：给出语言L(G)anbncm|n1,m0的对应文法解：分析：将anbn看成一个整体用一个非终结符号A来表示，cm看成另一个整体用非终结符B来表示。设S为G的识别符号，则有S=AB，而由A推出

18、2)，且G1=G2若语言在语法上等价，并不一定意味着语义上等价。若语言在语法上等价，并不一定意味着语义上等价。第三十四页，讲稿共九十三页哦例：G3S和G4S它们的VN和VT相同：VN=S,A,VT=a,b,c而,G3S的P为：S:=A|S-AA:=a|b|cG4S的P为：S:=A|A-SA:=a|b|c显然：G3S和G4S等价（语法），因为它们都产生相同的句子：a,b,c,a-b-c,a-b-b-c,但：句子的含义（语义）不一定相同：例如：由G3S推导出的句子：a-b-c其含义为(a-b)-c由G4S推导出的句子：a-b-c其含义为a-(b-c)第三十五页，讲稿共九十三页哦文法应该能准确地描述

19、语言，不能扩大或缩小。例：设计一个表示所有标识符的文法。解：分析：标识符：字母|字母开头的字母数字串,用B表示标识符；L-字母；D-数字：则GB的产生式P:B:=L|BL|BDL:=a|b|c|x|y|zD:=0|1|2|9 可以表示a1b2c3第三十六页，讲稿共九十三页哦若将产生式设计成P1：B:=L|BDL:=a|b|c|x|y|zD:=0|1|2|9表示：字母开头，后面全是数字：abc1，不能表示a1b2c3显然：P1缩小了标识符的表示，比P描述的范围缩小了若将产生式设计成P2：B:=L|BL|BD|DL:=a|b|c|x|y|zD:=0|1|2|9显然:P2也不能准确地描述，扩大了P的

20、描述范围第三十七页，讲稿共九十三页哦3 与语法分析有关的概念与语法分析有关的概念一、短语、简单短语与句柄一、短语、简单短语与句柄v短语：设有文法GS，W=是G的一个句型。若有识别符号S=A,且A=+,则称是相对非终结符A的句型w的短语。特别，如果上式A=+为：A=则称为句型w的简单短语（直接短语）第三十八页，讲稿共九十三页哦例：设有文法G=(S,A,B,a,b,P,S)其中P为：1.S:=AB2.A:=Aa3.A:=bB4.B:=a5.B:=Sb试求句型baSb,bBABb和baabaab全部短语，简单短语。解：先讨论句型w=baSb,其中子串b,a,S,ba,aS,Sb,baS,aSb.是句

21、型w的短语吗？根据短语定义，可由句型的推导中找到全部短语及简单短语。最左推导：第三十九页，讲稿共九十三页哦由此可见，下式成立：S=*S,且S=+baSbbaSb是短语(句型本身是短语)(注意:主要求异于句型本身的短语).又S=*AB,且B=Sb句型baSb中子串Sb也该句型（相对于B）的短语,且是简单短语。又S=*bBSb,且B=a句型baSb中子串a也该句型（相对于B）的短语,且是简单短语。又S=*ASb,且A=+ba句型baSb中子串ba也该句型（相对于A）的短语.注:短语是句型中的子串,在推导中不是句型中的子串不能作短语。如:S=*ASb,A=bB;则由于bB不是句型baSb中子串,所以

22、他不是该句型的短语.第四十页，讲稿共九十三页哦sb，a，ba是句型baSb异于自身的短语(句型本身是短语),其中Sb,a是简单短语。最右推导：同样可求出同上的该句型的短语,同学们可自求.可用同样的方法分析句型bBABb和baabaab的全部短语和简单短语（略）同学们也可自求。v句柄：句型的最左简单短语特征：句柄至少是简单短语（某规则的右部），且为最左简单短语（具有最左性）。例如：上例中a是最左简单短语句柄。第四十一页，讲稿共九十三页哦注注:短语、简单短语与句柄的关系短语、简单短语与句柄的关系:它们都是针对某个句型而言的,离开了句型来谈短语、简单短语与句柄,是毫无意义的.句柄一定是简单短语和短

23、语,反之不成立.简单短语和句柄一定是某个产生式的右部符号串,短语不是(他作为我们寻找和判断句型的简单短语的依据);但文法中产生式的右部符号串不见得都是简单短语或句柄.二、最右（左）推导，规范推导和规范规约，规范句型二、最右（左）推导，规范推导和规范规约，规范句型(1)最右（左）推导：在推导过程中，任何一步=都是对中最右（左）非终结符进行替换。称为最右（左）推导。v特别：最右推导称为规范推导。得到的句型称为规范句型。第四十二页，讲稿共九十三页哦例：设有文法G的规则集P为：S:=ABA:=Aa|bBB:=a|Sb给出babaab的最右（左）推导解：最右推导：S=AB=ASb=AABb=AAab=A

24、bBab=Abaab=bBbaab=babaab规范推导。最左推导：S=AB=bBB=baB=baSb=baABb=babBBb=babaBb=babaab忽左忽右推导：第四十三页，讲稿共九十三页哦v归约：将句型中某一个子串用一个非终结符替换的过程。归约：将句型中某一个子串用一个非终结符替换的过程。若有A:=,则xAy=xy，有：xy=xAy规约(2)规范归约（又称最左规约）：规范推导（最右推导）的逆过程。例：GN1:N1:=NN:=ND|DD:=0|1|2最右推导：N1=N=ND=N2=D2=12最左规约：12=D2=N2=ND=N=N1第四十四页，讲稿共九十三页哦三、文法的递归三、文法的递

25、归1递归规则递归规则v若文法中有形如规则:A:=A，称为规则左递归。v若文法中有形如规则:A:=A，称为规则右递归。v若文法中有形如规则:A:=A，称为规则递归。（规则递归称为直接递归）文法的递归性文法的递归性v如果有推导A=+A，称文法左递归v如果有推导A=+A，称文法右递归v如果有推导A=+A，称文法递归（文法递归称为间接递归）第四十五页，讲稿共九十三页哦例：GN1:N1:=NN:=ND（规则左递归：直接递归）例：GU:U:=VxV:=Uy|aU=Vx=Uyx(左递归文法:间接递归)GU的规则中无规则左递归，但在推导过程中存在左递归，所以GU是左递归文法。作用：用递归规则可以定义无穷集合的

26、语言。例：GA:A:=BB:=D|DD|DDD，D:=0|1|2|结论：若语言为无穷集合，描述语言的文法一定是递归的。可用 A:=AD替代第四十六页，讲稿共九十三页哦四、语法树与文法的二义性四、语法树与文法的二义性1.句型的语法树句型的语法树(1)作用：作用：直观地求出一个句型的短语，简单短语和句柄。直观地表示一个句型（或句子）的推导或归约过程，即它是语法分析的工具。可以判断一个文法的二义性问题。第四十七页，讲稿共九十三页哦(2)句型推导的语法树表示句型推导的语法树表示用树型结构直观地表示一个句型的推导过程，称为该句型的一棵语法树（又称推导树）语法树的构成：v树的根为文法的识别符号；v树的中间

27、结点是文法的非终结符；v叶子结点为文法的终结符号或非终结符号。v若一个标记为U的结点，它有标记依次为x1x2x3xn的直接后继结点，即U:=x1x2x3xn必定是文法G的一条规则。一个句型的推导过程用语法树表示：第四十八页，讲稿共九十三页哦例：设有文法GE：E:=E+T|E-T|TT:=T*F|T/F|FF:=(E)|i根据推导，画出句型（T+I)i-F的语法树：最右推导：E=E-T=E-F=T-F=T*F-F=T*i-F=F*i-F=(E)*i-F=(E+T)*i-F=(E+F)*i-F=(E+i)*i-F=(T+i)*i-F第四十九页，讲稿共九十三页哦第五十页，讲稿共九十三页哦最左推导：从

28、左向右画子树。子树：由某一结点连同所有分支组成的部分。简单子树：包括叶子在内的单层子树。(3)语法语法树中的短语，简单短语和句柄的概念中的短语，简单短语和句柄的概念短语：子树的末端结点形成的符号串是相对子树根的短语。简单短语：简单子树末端结点形成的符号串是相对于简单子树根的简单短语。句柄：最左简单子树的末端结点形成的符号串是句柄。第五十一页，讲稿共九十三页哦例：设有文法GE：E:=E+T|E-T|TT:=T*F|T/F|FF:=(E)|i求(T+i)*iF的短语，简单短语和句柄。(T+i)*iF为句型的相对根E的短语。(T+i)*i为句型的相对于以T为根的子树的短语。(T+i)为句型的相对于以

29、F为根的子树的短语。T+i为句型的相对于以E为根的子树的短语。T为句型的相对于以E为根的子树的短语，且为简单短语。第一个i为句型的相对于以F为根的子树的短语，且为简单短语。第二个i为句型的相对于以F为根的子树的短语，且为简单短语。F为句型的相对于以T为根的子树的短语，且为简单短语。在四个简单短语T，i，i，F中，T为句型的句柄第五十二页，讲稿共九十三页哦例：设有文法GS：S:=(T)|a|T:=T,S|S求句子（a,(a,a)）最右推导的逆过程（最左规约）每一步的句柄。最右推导：S=(T)句柄:（T）=(T,S)句柄:T,S=(T,(T)句柄:(T)=(T,(T,S)句柄:T,S=(T,(T,

30、a)句柄:第三个a=(T,(S,a)句柄:S=(T,(a,a)句柄:第二个a=(S,(a,a)句柄:S=(a,(a,a)句柄:第一个a第五十三页，讲稿共九十三页哦第五十四页，讲稿共九十三页哦2.文法的二义性文法的二义性3.所谓文法的二义性是指文法存在的某个句子对应两棵不同的语法树（或说存在两个不同的最左（右）推导）。例：文法GE：E:=E+E|E*E|(E)|i句子i*i+i有两个不同的语法树（最左推导）E=E+E=E*E+E=i*E+E=i*i+E=i*i+i第五十五页，讲稿共九十三页哦E=E*E=i*E=i*E+E=i*i+E=i*i+iGE具有二义性v文法的二义性会导致对二义性文法的句子

31、结构产生多种不同的理解，造成语法分析和语义理解的不确定性。希望描述语言的文法是无二义性的。第五十六页，讲稿共九十三页哦3.文法二义性的消除文法二义性的消除(1)不改变文法中原有的语法规则，仅加进一些语法的非形式规定。v例如，对于上例文法GE,不改变已有的4条规则，仅加入运算符的优先顺序和结合规则；即*优先于+；+,*服从左结合。这样，句子i*i+i只有唯一的一棵语法树（如上例的第一个图）。(2)改写文法。把排除二义性的规则合并到原文法中，构造一个等价的无二义性的文法。第五十七页，讲稿共九十三页哦v例如，对于上例文法GE,将运算符的优先顺序及结合规则（*优先于+；+,*服从左结合）加到原文法中：

32、E:=E+T|TT:=T*F|FF:=(E)|i则句子i*i+i只有唯一的语法树可见：对于有二义性文法描述的语言，有时可以找到等价的无二义性文法来描述它。第五十八页，讲稿共九十三页哦例：某语言的条件语句的文法G为：S:=ifbS|ifbSelseS|A(A为其它语句)证明G具有二义性，并消除之。分析：该文法的句子ifbifbAelseA对应的两棵不同的语法树第五十九页，讲稿共九十三页哦所以G是具有二义性的文法。消除二义性：(1).不改变已有规则，仅加入一项非形式语法规定：else与前面最接近的if配对。这时句子ifbifbAelseA只唯一对应语法树(a).(2).改造文法G为G:S:=S1|

33、S2S1:=ifbS1elseS1|AS2:=ifbS|ifbS1elseS2第六十页，讲稿共九十三页哦注：v文法的二义性和语言的二义性是两个不同的概念。通常只说文法的二义性，而且不说语言的二义性，因为描述语言的文法不唯一，可能存在一个文法G有二义性，一个文法G无二义性：使L(G)=L(G)v如果语言是二义性的，则它不存在无二义性的文法，这样的语言称为先天二义性语言。v如：L=abc|i=j或jk,i,j,k1便是这种语言。v已证明，不存在一个算法，它能在有限步骤内确切地判定任意给定一个上下文无关文法是否为二义性文法，或它是否会产生一个先天二义性的上下文无关语言。ijk第六十一页，讲稿共九十三

34、页哦4 文法与语言的分类文法与语言的分类v分类的依据：将文法中的规则施加不同的限制。v文法被划分为4类：03型文法一、一、0型文法（短语文法）型文法（短语文法）若文法G的规则式具有形式：:=(其中(VNVT)+,(VNVT)*)即，都是符号串对它们没有作任何限制。（也可以|）v由0型文法产生的语言称为0型语言v0型文法的能力相当于图灵机。第六十二页，讲稿共九十三页哦例：有产生式P：S:=0AB1B:=0B:=SA|01A1:=SB1A0:=S0Bv|为0型文法v该文法推不出任何句子：L=第六十三页，讲稿共九十三页哦二、二、1型文法（上下文有关文法）型文法（上下文有关文法）若文法G中规则呈现下列

35、的形式：A:=u其中：AVN，u(VNVT)+,(VNVT)*则称G为1型文法，所产生的语言为1型语言。由于利用规则将A替换为u时，必须考虑A在上下文中出现的情况，即与上下文有关，故又称为下文有关文法。v特点：每个规则式：|左边|右边|；规则右部符号个数至少与左部符号个数一样多。第六十四页，讲稿共九十三页哦例：设有G=(VN，VT，P，S)VN=S,B,CVT=a,b,cP:S:=aSBCS:=aBCCB:=BCaB:=abbB:=bbbC:=bccC:=cc这是一个1型文法，它描述了如下语言L(G)=anbncn|n1第六十五页，讲稿共九十三页哦三、三、2型文法（上下文无关文法）型文法（上下

36、文无关文法）若文法G中规则呈现如下形式：A:=其中，AVN，（VNVT）*则称G为2型文法，由它产生的语言称2型语言。由于利用规则将A替换成时与其上下文无关，即与A在上下文出现的情况无关，所以又称这种文法为上下文无关文法。例：文法G的产生式P：E:=E+E|E*E|(E)|i属于2型文法。v特点：2型文法产生式的左部是单个的非终结符，右部为终结符和非终结符组成的符号串。v注：上下文无关文法可以描述当今的程序语言第六十六页，讲稿共九十三页哦四、四、3型文法（正规文法）型文法（正规文法）如果对2型文法的产生式作进一步的限制，限制产生式的右部是单一终结符或单一终结符和单一非终结符组成。若文法G中的规

37、则式，呈现如下形式：右线性文法A:=aBA:=a或左线性文法A:=BaA:=a其中：A，BVN，aVT称G为3型文法。或称正规（正则）文法，由它产生的语言为3型语言或正规语言。+第六十七页，讲稿共九十三页哦例：设有G=(V,V,P,S)P:S:=A0|B1A:=0|1B:=0|1左线性文法注：文法类型是由产生式的形式来划分：NT第六十八页，讲稿共九十三页哦即：G0G1G2G3表格：文法类型与产生式文法文法类类型型产产生式限制生式限制0:=(|0,|)：无限制文法1:=(1|):上下文有关文法2A:=(（VNVT)+):上下文无关文法3A:=a A:=aA:=aB 或 A:=Ba :正则（规）文

38、法或左（右）线性文法第六十九页，讲稿共九十三页哦文法的分类对于程序设计语言的编译程序有重要的意义。v程序语言的词法规则属于正则文法编译程序词法扫描器采用正则文法识别技术。v程序语言的语法和语义部分的规则属于上下文有关文法。但考虑高功效而采用上下文无关文法定义语法编译程序语法分析器采用上下文文法识别技术。v程序语言的词法由正则文法描述。第七十页，讲稿共九十三页哦v程序语言中与局部语法有关的规则属于上下文无关文法。v程序语言中全局的语法与语义有关的部分属于上下文有关文法。（如标识符类型匹配问题（说明部分与语句部分）。过程调用中实参与形参要求一致的问题等等）第七十一页，讲稿共九十三页哦5文法的实用限

39、制在实际使用中，对文法要作一些假定或限制。例如限制文法不含有有害规则或多余的规则。一、文法中不能含有有害规则一、文法中不能含有有害规则U:=Uv这样的规则显然没有必要，而且会引起二义性。v例如，文法GS:S:=0S1|01是无二义性的，若将规则写成：S:=0S1|01|S则文法G不再是无二义性的。就句子0011而言，可画出多棵语法树。第七十二页，讲稿共九十三页哦二、文法中不能含有多余的规则二、文法中不能含有多余的规则v文法的规则中不含有无用的非终结符和不可到达的符号。1.无用的非终结符号（不可终止符号）无用的非终结符号（不可终止符号）如果从文法中某个非终结符推不出终结符号串，则称该非终结符号为

40、无用的非终结符2.不可到达的符号不可到达的符号如果文法规则中的一个非终结符（不是识别符号），不出现在文法的任何一条产生式的右部，则称该非终结符为不可到达的符号.第七十三页，讲稿共九十三页哦例：已知文法G=(VN，VT，P，Z)其中，VN=Z,A,B,C,D,VT=e,fP:Z:=BeA:=Ae|eB:=Ce|AfC:=CfD:=fC为无用的非终结符，因为C在推导中没有终结符号替换。C:=cf和B:=Ce多余应该删去。第七十四页，讲稿共九十三页哦D为不可到达的符号，即D:=f在推导中不起作用，应该删去。删除多余的规则后的文法为：Z:=BeA:=Ae|eB:=Af第七十五页，讲稿共九十三页哦v文法

41、中不含多余规则的充要条件：U(UVN)必须出现在某个推导的句型中，即：Z=xy。（U为文法的非终结符）能从U推出终结符号串，即：U=+t(tVT)满足上述条件的文法称为压缩过的或化简了的。v对文法的限制还有：文法中不含有左递归规则U:=U。（消除左递归在后面会讲到）对于上下文无关文法，限制U:=，即不含有空规则。（可以变换消除）等等第七十六页，讲稿共九十三页哦6小结小结本章主要解决的问题：v已知文法，确定该文法描述的语言v已知语言，设计描述该语言的文法v求句型的短语，简单短语及句柄v文法二义性的判断第七十七页，讲稿共九十三页哦一、已知文法，确定该文法描述的语言一、已知文法，确定该文法描述的语言

42、1.语言的定义：文法G产生句子的全体。即L(GS)=x|S=+x,且xVT*2.语言的描述：用自然语言：L=x|xa,b+,且x中a，b个数相同用式子：L=a2nbb|n0用正规式：L=bna|n0，可用：L=b*a来描述。3.求法：根据给定文法，从文法的识别符号开始，推导出所有的句子，然后归纳写出语言描述的三种形式之一。第七十八页，讲稿共九十三页哦例：有如下文法GS：S:=ABA:=aAb|abB:=BC|求：L(GS)=?解：S=AB=abB=abS=AB=abB=abBc=abcS=AB=aAbB=aabbB=aabbS=AB=aAbB=aabbB=aabbBC=aabbcL(GS)=a

44、句子的结构特征，设计相应的产生式，但求出的文法不唯一。3.设计出的文法必须能准确地定义已知的语言，不能超出或缩小所定义的语言范围。4.若语言是句子的无穷集合，则设计的文法一定是递归的。第八十一页，讲稿共九十三页哦例：例：已知L=x|xa,b,c*,且x中符号的排列是对称的。（例如：aabcbaa或aabbaa等）试写出产生该语言的文法。解：解：句子x中符号有多个，所以有递归产生式存在。又因为句子x中符号是对称的，保证对称的推导出每个符号就可以了。GZ:Z:=aZa|bZb|cZc|a|b|c|例：例：给出描述：L=a2m+1bm+1|m0a2mbm+2|m0的文法。解：解：将句子的描述变形：a

45、2mabbm和a2mbbbm发现句子中前后的a和b的个数有倍数关系于是：GZ:Z:=aaZb|ab|bb第八十二页，讲稿共九十三页哦例：例：写一文法，使其语言是偶整数的集合（不允许0开头，且不考虑带符号数）解：解：根据题意，将偶整数结构划分如图所示的三个部分：v最高位允许19，用非终结符B表示v中间位允许任意多位数字09，每位用非终结符D表示v最低位只允许出现0，2，4，6，8偶数，用A表示。第八十三页，讲稿共九十三页哦由于中间部分可以出现任意位，所以引入一个非终结符M，它包括最高位和中间位。所求文法GN:N:=A|MAM:=B|MDA:=0|2|4|6|8B:=1|2|3|4|5|6|7|8

46、|9D:=0|B类似问题：v写出带符号奇整数集合的文法v写出不能被5整除的无符号偶整数集合的文法v写出能被5整除的带符号偶整数集合的文法v第八十四页，讲稿共九十三页哦三、三、求句型的短语，简单短语及句柄以及判断文法二义性的问题求句型的短语，简单短语及句柄以及判断文法二义性的问题用语法树作为分析的工具。用语法树作为分析的工具。1.求句型的短语，简单短语及句柄求句型的短语，简单短语及句柄v句型的定义：对文法GS，若S=x，x(VNVT)*，则称x为句型。v短语，简单短语和句柄总是针对某个句型而言的。v短语总是句型的某个子串，它对应该句型语法树中，子树末端结点形成的符号串。v简单短语总是某个产生式

47、右部，它对应该句型语法树中，简单子树末端结点形成的符号串。v语法树中最左边的简单短语就是句柄。第八十五页，讲稿共九十三页哦例：有文法GE:E:=E+T|E-T|TT:=T*F|T/F|FF:=(E)|i求句型(F+i)-T*(E-T)的短语，简单短语和句柄。解：画句型(F+i)-T*(E-T)的语法树：EE-TTF(+ETF)ETFiTF*()EET短语：F,i,F+i,(F+i),E-T,(E-T),T*(E-T),(F+i)T*(E-T).。简单短语：F,i,E-T。文法中某产生式的右部句柄：F第八十六页，讲稿共九十三页哦2.文法二义性的判断及消除文法二义性的判断及消除判断：找出正确的句子

48、，使之对应两棵不同的语法树。例：已知文法GN：N:=SE|ES:=SD|DE:=0|2|4|6|8|10D:=0|1|2|3|4|5|6|7|8|9证明此文法具有二义性。求此文法描述的语言找出等价的无二义性文法第八十七页，讲稿共九十三页哦解：（1）证明：如：句子10所以G具有二义性。第八十八页，讲稿共九十三页哦（2）L是所有偶整数的集合（3）等价无二义性文法去掉E:=10假定除0外，偶整数均不以0开头：GN：N:=SE|ES:=SD|DE:=0|2|4|6|8D:=0|1|2|3|4|5|6|7|8|9第八十九页，讲稿共九十三页哦第第2章章练习题练习题一，单选题1.给定文法：AbA|cc,下

49、面的符号串为该文法句子的是（）。ccbcbccbccbccbbbccA.B.C.D.2.文法GZ和语言L（GZ）存在如下关系（）。A.一一对应：一个文法对应唯一的语言；并且反过来，一个语言对应唯一的文法。B.一个语言对应唯一的文法，反之则不然。C.一个文法对应唯一的语言，反之则不然。D.若G为非二义性文法，则C是正确的；若G为二义性文法，则一个文法不对应唯一的语言。第九十页，讲稿共九十三页哦3.有文法GE：EEE，EE，Ea|b|c则文法的句子abc的所有可能的语法树有（）棵。A.1B.2C.4D.34.有文法GS，如果Sx，(xV)，则x是（）。A.句型B.句子C.A和BD.非A和B二.构造一个上下文无关文法G，使得：L(G)=ab|m0*T2mm第九十一页，讲稿共九十三页哦三.已知文法GE：EET+|TTTF*|FFFP|PP(E)|i有句型TF*PP+，问此句型的短语，简单短语和句柄是什么？（画语法树说明）第九十二页，讲稿共九十三页哦四.请用语法树证明文法Gs是二义性的，Gs：SSS|(S)|()。五.已知文法GZ：ZABAaAb|abBBc|则，L(GZ)？第九十三页，讲稿共九十三页哦

展开阅读全文