《《形式语言与文法》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《形式语言与文法》PPT课件.ppt(93页珍藏版)》请在金锄头文库上搜索。
1、第二章 形式语言与文法主要内容:v1 语言的形式描述.v2 语言与文法的形式定义.v3 文法的分类.v4 语法树及句型分析. 主要问题:v已知给定的文法求该文法表示的语言v已知语言求描述该语言的文法v求给定语句的短语、简单短语和句柄1.符号串 符号串是形式语言中最基本的名词.一, 字母表与符号串v 1,字母表v定义:元素的非空有穷集合v例:=a,b,c(a,b,c字母表)v=0,1(二进制数字字母表)v=汉字,数字,标点符号,(汉字组成的字母表)v注:元素可是字母、数字或其他符号.v字母表中至少有一个元素.2. 符号(字符)定义:字母表中的元素.注:符号是字母表中不可再分解的最小单位. 3.
2、符号串定义:字母表中的符号组成的有穷序列. 例:=a,b,c符号:a,b,c符号串:a,b,c,ab,ac,aa,ba,ca,abc, 例;设字母表A=0,1A中的符号:0,1A中的符串: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的连接设xa
3、bc,y10a则xyabc10a;yx10aabc符号串的方幂设有符号串x,则x的n次连接称为x的n次方幂,记为:x例:x(注:x)xxxxxxxxxxxxxxxxxxxxxn次连接例: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个)例
4、:设A=a,bA=A=a,bA=aa,ab,ba,bb(A共有2=4个长度为2的元素)A=AA=aa,ab,ba,bba,b=aaa,aba,baa,bba,aab,abb,bab,bbb(A共有2=8个长度为3的元素)012322nn1n1012322335.符号串集合的正闭包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
5、(A=A)123n012n0+例 设A=a,b则A=,a,b,aa,ab,ba,bb,aaa,bbb,=a,b显然:对于所有的A,有A2.文法和语言的形式定义一.文法与语言的关系 语言:由定义在该语言字母表上,且按一定组成规则所构成的句子的集合.即:字母表字符串(句子)(语言)语言的描述.当语言为有穷个句子的集合时,可用枚举的方法表示语言.当语言为无穷个句子的集合时,则用有无穷的语法规则(文法)描述无穷的句子的结构.语法规则例:汉语:人们无法列出全部的句子.但人们可以给出一些规则,用这些规则来说明(或定义)句子的组成结构.如:汉语句子结构:=+=+=用扩充BNF来表示这种句子的结构:=(=表示
6、“定义为”,“产生”,“生成”)=(表示“或者”)=我你他(表示非终结符)=王明大学生工人英语=(不加表示终结符)=是学习 =利用以上规则(文法)推导句子:我是大学生. 我 我 我是 我是 我是大学生利用上列文法:可以产生的句子:我学习英语,他学习,语,他是工人,.(很多句子)利用上列文法不可产生“我大学生是”.它不符合以上规则.文法的作用:不仅严格定义句子的结构,也是为了用有限的规则把语言的全部句子描述出来。它是用有穷的集合刻画无穷集合的工具.文法:语言的语法规则的有穷表示.(文法又称元语言)注:1.有穷的文法通过推导的方法,可以推导出给定字母表上的所有句子.2.描述文法的所有字符构成了语言
7、的字母表.3.通过文法在推导合法句子过程中会有多个句型产生.4.合法的句型和句子是用字符串表示的.二. 文法的形式定义1. 规则(产生式,生成式,重写规则)是一个符号与一个符号串的有序对(A,)常写成:A=或A其中:A是规则的左部.它是某个字母表的正闭包中的一个符号.即A.是规则的右部.它是中一个符号串.(包括)2. 文法的形式定义 定义:文法G是一个四元组,它是规则的非空有穷集合.G=(V,V,P,S)其中:V是文法规则式中的非终结符号集.V是文法规则式中的终结符号集.NTNTVV=P是文法的规则式集。S是文法的开始符号(识别符号)。SVv非终结符号:出现在产生是左边,能派生出符号和符号串的
8、符号,常用大写字母表示,即,每一个非终结符号表示一定的符号串。它至少要在产生式左边出现一次。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|9v其中:VN=,S=VT=a,b,c,z,0,1,2,9字母表:V=VNVT=,a,b,c,z,0,1,2,93.推导v有了文法,怎样由文法推导出与
9、该文法相应的语言?为此引入了“推导”等概念。1)直接推导2)设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)说明:每利用文法中的一条规则U:=u一次,均可得到一次直接推导:Uu2)推导(推导)若使用若干次规则式可以从x推出y,则称y为x的推导,记为:xy(或称x产生y,或称y规约到x),或记为:xy例:上例:0S100S
10、11000S111000011110S1+00001111(推导长度为3)3)广义推导(推导)若xy或者xy(表示0步推导),则写为xy(反之亦然,即:xy,当且仅当xy或者xy)例,上例中:0S1+00001111也可记为:0S1*00001111注:直接推导、推导、广义推导的区别:推导长度n不同:直接推导:n1推导:n1广义推导:n0(0步推导:如Ss)包涵包涵4.句型和句子v设有文法GS,若有Sx,则称符号串x为文法GS的句型。v换句话说:凡是由识别符号推导出来的任意符号串称为句型。v句子:仅有终结符号组成的句型称为句子。v区别:符号串x(VNVT)*;x称为句型,符号串xVT*;x称为
11、句子。v例:GS:S:=01|0S1S01S0S100S11000111可见:01,0S1,00S11,000111均为文法GS的句型。其中:01,000111为句子(说明句型包含了句子,句子是特殊的句型)但是:符号串000S11,0000111都不是文法GS的句型。v例:已知文法GE:vE:=E+E|E*E|(E)|i(其中:VN=E VT=+,*,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
12、)所以,符号串(i*i+i)是文法GE的一个句子。三、语言的形式定义:三、语言的形式定义:v定义:由文法GS产生的所有句子的集合。即:L(GS)=x|S=+x,且xV*v注:一旦文法给定,语言就确定。语言L(G)是V*的子集。(语言是字母表中终结符号串闭包的子集)即:属于L(G)的句子属于V*反之,属于V*的符号串x不一定属于L(G)。TTTTv例:已知文法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,000
13、0,0011,1111,,可见L(G)仅是VT的真子集。例:已知文法:GS:S=0S|1S|,求L(G)=?解:L(GS)=,0,1,01,11,00,10,=x|x0,1*例:已知:S=aB|bAA=a|aS|bAAB=b|bS|aBB求:L?解: S=aB=abS=aB=abS=abaB=ababS=aB=aaBB=aabB=aabb又S=bA=baS=bA=baS=babA=babaS=bA=bbAA=bbaA=bbaaL(GS)=x|xa,b,且x中a,b个数相同反过来,给定语言L(G)后,若要写出能正确描述此语言的文法,是有一定难度的。+例:试对语言L(G)=(n)n|n=0,1,2
14、,构造相应的文法G。解:(1)首先分析L是由怎样的符号串x组成的。当n=0时,x=当n=1时,x=()当n=2时,x=()当n=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看成
15、另一个整体用非终结符B来表示。设S为G的识别符号,则有S=AB,而由A推出anbn,B推出cm。保证anbn成立,即a,b个数相等,且大于等于1。所以可以用产生式:A=aAb|ab又因为m可以为0,所以S:=AB改写为S:=AB|A;又由于A=aAb|ab,则对B容易看出B=cB|c S=AB|AS=ABA=aAb|ab 或者:A=aAb|abB=cB|cB=cB|c|例:设字母表a,b,试设计一个文法,描述语言La,b|n1解:分析语言由怎样的符号串组成。当n=1时,L=aa,bb当n=2时,L=aaaa,bbbb当n=3时,L=aaaaaa,bbbbbbL=aa,bb,aaaa,bbbb,
16、aaaaaa,bbbbbb,即:语言由偶数个a和偶数个b的符号串组成。所以,描述语言的文法:GA:A=aa|aaB|bb|bbDB=aa|aaBD=bb|bbD2n2n可以写出另一个文法:G1A:A=B|DB=aa|aBaD=bb|bDb可见,对于给定语言,描述该语言的文法不是唯一的。注:描述一个语言的文法不是唯一的若不同的文法产生相同的语言,则称这些文法是等价的。例:设有文法G1=VN,VT,P,A其中:VN=AVT=a,bP=A:=ab显然:L(G1)=ab文法G2=VN,VT,P,A其中:VN=A,BVT=a,bP=A:=Bb,B:=a显然:L(G2,)=ab即:L(G1)=L(G2),
17、且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)文法应该能准确地描述语言,不能扩大或缩小。例:设计一个表示所有标识符的文法。解:分
18、析:标识符:字母|字母开头的字母数字串,用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的描述范围3 与语法分析有关的概念与语法分析有关的概念一、短语、简单短语与句柄一、短语、简单
19、短语与句柄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.是句型w的短语吗?根据短语定义,可由句型的推导中找到全部短语及简单短语。最左推导:由此可见,下式成立:S=*S,且S=+baSbbaSb是短语(句型本
20、身是短语)(注意:主要求异于句型本身的短语).又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中子串,所以他不是该句型的短语.sb,a,ba是句型baSb异于自身的短语(句型本身是短语),其中Sb,a是简单短语。最右推导:同样可求出同上的该句型的短语,同学们可自求.可用同样的方法
21、分析句型bBABb和baabaab的全部短语和简单短语(略)同学们也可自求。v句柄:句型的最左简单短语特征:句柄至少是简单短语(某规则的右部),且为最左简单短语(具有最左性)。例如:上例中a是最左简单短语句柄。 注注:短语、简单短语与句柄的关系短语、简单短语与句柄的关系: 它们都是针对某个句型而言的,离开了句型来谈短语、简单短语与句柄,是毫无意义的. 句柄一定是简单短语和短语,反之不成立. 简单短语和句柄一定是某个产生式的右部符号串,短语不是(他作为我们寻找和判断句型的简单短语的依据);但文法中产生式的右部符号串不见得都是简单短语或句柄.二、最右(左)推导,规范推导和规范规约,规范句型二、最右
22、(左)推导,规范推导和规范规约,规范句型(1)最右(左)推导:在推导过程中,任何一步=都是对中最右(左)非终结符进行替换。称为最右(左)推导。v特别:最右推导称为规范推导。得到的句型称为规范句型。例:设有文法G的规则集P为:S:=ABA:=Aa|bBB:=a|Sb给出babaab的最右(左)推导解:最右推导:S=AB=ASb=AABb=AAab=AbBab=Abaab=bBbaab=babaab规范推导。最左推导:S=AB=bBB=baB=baSb=baABb=babBBb=babaBb=babaab忽左忽右推导:v归约:将句型中某一个子串用一个非终结符替换的过程。归约:将句型中某一个子串用一
23、个非终结符替换的过程。若有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三、文法的递归三、文法的递归1递归规则递归规则v若文法中有形如规则:A:=A,称为规则左递归。v若文法中有形如规则:A:=A,称为规则右递归。v若文法中有形如规则:A:=A,称为规则递归。(规则递归称为直接递归)文法的递归性文法的递归性v如果有推导A=+A,称文法左递归v如果有推导A=+A,称文法右递归v如果有推导A=+A,称文法
24、递归(文法递归称为间接递归)例:GN1: N1:=NN:=ND(规则左递归:直接递归)例:GU:U:=VxV:=Uy|aU=Vx=Uyx(左递归文法:间接递归)GU的规则中无规则左递归,但在推导过程中存在左递归,所以GU是左递归文法。作用:用递归规则可以定义无穷集合的语言。例:GA:A:=BB:=D|DD|DDD,D:=0|1|2|结论:若语言为无穷集合,描述语言的文法一定是递归的。可用 A:=AD替代四、语法树与文法的二义性四、语法树与文法的二义性1.句型的语法树句型的语法树(1) 作用:作用:直观地求出一个句型的短语,简单短语和句柄。直观地表示一个句型(或句子)的推导或归约过程,即它是语法
25、分析的工具。可以判断一个文法的二义性问题。(2) 句型推导的语法树表示句型推导的语法树表示用树型结构直观地表示一个句型的推导过程,称为该句型的一棵语法树(又称推导树)语法树的构成:v树的根为文法的识别符号;v树的中间结点是文法的非终结符;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-
26、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最左推导:从左向右画子树。子树:由某一结点连同所有分支组成的部分。简单子树:包括叶子在内的单层子树。(3) 语法语法树中的短语,简单短语和句柄的概念中的短语,简单短语和句柄的概念短语:子树的末端结点形成的符号串是相对子树根的短语。简单短语:简单子树末端结点形成的符号串是相对于简单子树根的简单短语。句柄:最左简单子树的末端结点形成的符号串是句柄。例:设有文法GE:E:=E+T|E-T|TT:=T*F|T/F|FF:=(E)|i求(T+i)*iF的短语,简单短语和句柄。(T+i
27、)*iF为句型的相对根E的短语。(T+i)*i为句型的相对于以T为根的子树的短语。(T+i)为句型的相对于以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)句
28、柄:T,S=(T,(T)句柄:(T)=(T,(T,S)句柄:T,S=(T,(T,a)句柄:第三个a=(T,(S,a) 句柄:S=(T,(a,a) 句柄:第二个a=(S,(a,a) 句柄:S=(a,(a,a) 句柄:第一个a2.文法的二义性文法的二义性v所谓文法的二义性是指文法存在的某个句子对应两棵不同的语法树(或说存在两个不同的最左(右)推导)。例:文法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+iE=E*E=i*E=i*E+E=i*i+E=i*i+iGE具有二义性v文法的二义性会导致对二义性文法的句
29、子结构产生多种不同的理解,造成语法分析和语义理解的不确定性。希望描述语言的文法是无二义性的。3.文法二义性的消除文法二义性的消除(1)不改变文法中原有的语法规则,仅加进一些语法的非形式规定。v例如,对于上例文法GE,不改变已有的4条规则,仅加入运算符的优先顺序和结合规则;即*优先于+;+,*服从左结合。这样,句子i*i+i只有唯一的一棵语法树(如上例的第一个图)。(2)改写文法。把排除二义性的规则合并到原文法中,构造一个等价的无二义性的文法。v例如,对于上例文法GE,将运算符的优先顺序及结合规则(*优先于+;+,*服从左结合)加到原文法中:E:=E+T|TT:=T*F|FF:=(E)|i则句子
30、i*i+i只有唯一的语法树可见:对于有二义性文法描述的语言,有时可以找到等价的无二义性文法来描述它。例:某语言的条件语句的文法G为:S:=ifbS|ifbSelseS|A(A为其它语句)证明G具有二义性,并消除之。分析:该文法的句子ifbifbAelseA对应的两棵不同的语法树所以G是具有二义性的文法。消除二义性:(1).不改变已有规则,仅加入一项非形式语法规定:else与前面最接近的if配对。这时句子ifbifbAelseA只唯一对应语法树(a).(2).改造文法G为G:S:=S1|S2S1:=ifbS1elseS1|AS2:=ifbS|ifbS1elseS2注:v文法的二义性和语言的二义性
31、是两个不同的概念。通常只说文法的二义性,而且不说语言的二义性,因为描述语言的文法不唯一,可能存在一个文法G有二义性,一个文法G无二义性:使L(G)=L(G)v如果语言是二义性的,则它不存在无二义性的文法,这样的语言称为先天二义性语言。v如:L=abc|i=j或jk,i,j,k1便是这种语言。v已证明,不存在一个算法,它能在有限步骤内确切地判定任意给定一个上下文无关文法是否为二义性文法,或它是否会产生一个先天二义性的上下文无关语言。ij k4 文法与语言的分类文法与语言的分类v分类的依据:将文法中的规则施加不同的限制。v文法被划分为4类:03型文法一、一、0型文法(短语文法)型文法(短语文法)若
32、文法G的规则式具有形式::=(其中(VNVT)+,(VNVT)*)即,都是符号串对它们没有作任何限制。(也可以|)v由0型文法产生的语言称为0型语言v0型文法的能力相当于图灵机。例:有产生式P:S:=0AB1B:=0B:=SA|01A1:=SB1A0:=S0Bv|为0型文法v该文法推不出任何句子:L=二、二、1型文法(上下文有关文法)型文法(上下文有关文法)若文法G中规则呈现下列的形式:A:=u其中:AVN,u(VNVT)+,(VNVT)*则称G为1型文法,所产生的语言为1型语言。由于利用规则将A替换为u时,必须考虑A在上下文中出现的情况,即与上下文有关,故又称为下文有关文法。v特点:每个规则
33、式:|左边|右边|;规则右部符号个数至少与左部符号个数一样多。例:设有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型文法(上下文无关文法)型文法(上下文无关文法)若文法G中规则呈现如下形式:A:=其中,AVN,(VNVT)*则称G为2型文法,由它产生的语言称2型语言。由于利用规则将A替换成时与其上下文无关,即与A在上下文出现的情况无关,所以又称这种文法为上下文无关文法。例:文法G的产生式P:E:=E+E|E*E|(E)|
34、i属于2型文法。v特点:2型文法产生式的左部是单个的非终结符,右部为终结符和非终结符组成的符号串。v注:上下文无关文法可以描述当今的程序语言四、四、3型文法(正规文法)型文法(正规文法)如果对2型文法的产生式作进一步的限制,限制产生式的右部是单一终结符或单一终结符和单一非终结符组成。若文法G中的规则式,呈现如下形式:右线性文法 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左线性文法注:文法类型是由产生式的形式来划分:
35、NT即:G0G1G2G3表格:文法类型与产生式文法文法类型型产生式限制生式限制0:=(|0, |):无限制文法1:= (1|):上下文有关文法2A:=((VNVT)+) : 上下文无关文法3A:=a A:=aA:=aB 或 A:=Ba :正则(规)文法或左(右)线性文法文法的分类对于程序设计语言的编译程序有重要的意义。v程序语言的词法规则属于正则文法编译程序词法扫描器采用正则文法识别技术。v程序语言的语法和语义部分的规则属于上下文有关文法。但考虑高功效而采用上下文无关文法定义语法编译程序语法分析器采用上下文文法识别技术。v程序语言的词法由正则文法描述。v程序语言中与局部语法有关的规则属于上下文
36、无关文法。v程序语言中全局的语法与语义有关的部分属于上下文有关文法。(如标识符类型匹配问题(说明部分与语句部分)。过程调用中实参与形参要求一致的问题等等)5文法的实用限制在实际使用中,对文法要作一些假定或限制。例如限制文法不含有有害规则或多余的规则。一、文法中不能含有有害规则一、文法中不能含有有害规则U:=Uv这样的规则显然没有必要,而且会引起二义性。v例如,文法GS:S:=0S1|01是无二义性的,若将规则写成:S:=0S1|01|S则文法G不再是无二义性的。就句子0011而言,可画出多棵语法树。二、文法中不能含有多余的规则二、文法中不能含有多余的规则v文法的规则中不含有无用的非终结符和不可
37、到达的符号。1.无用的非终结符号(不可终止符号)无用的非终结符号(不可终止符号)如果从文法中某个非终结符推不出终结符号串,则称该非终结符号为无用的非终结符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在推导中不起作用,应该删去。删除多余
38、的规则后的文法为:Z:=BeA:=Ae|eB:=Afv文法中不含多余规则的充要条件:U(UVN)必须出现在某个推导的句型中,即:Z=xy。(U为文法的非终结符)能从U推出终结符号串,即:U=+t(tVT)满足上述条件的文法称为压缩过的或化简了的。v对文法的限制还有:文法中不含有左递归规则U:=U。(消除左递归在后面会讲到)对于上下文无关文法,限制U:=,即不含有空规则。(可以变换消除)等等6小结小结本章主要解决的问题:v已知文法,确定该文法描述的语言v已知语言,设计描述该语言的文法v求句型的短语,简单短语及句柄v文法二义性的判断一、已知文法,确定该文法描述的语言一、已知文法,确定该文法描述的语
39、言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)=anbnc|n1,m0m例:
40、已知文法GS为:S:=dABA:=aA|aB:=Bb|GS产生的语言是什么?GS能否改写为等价的正规文法?解:首先分析GS产生的语言:语言的句子都是d开头,后跟a或b,且a,b个数不等。L(GS)=danbm|n1,m0根据语言的特点:a,b的个数n与m没有相互制约的关系,所以将an与bm分别构造,得到正规文法:GS:S:=dAA:=aA|aB|aB:=bB|b二、已知语言,设计描述该语言的文法二、已知语言,设计描述该语言的文法1.文法的形式定义:四元组GS=(VN,VT,P,S),主要求产生式P。2.分析已知语言句子的结构特征,设计相应的产生式,但求出的文法不唯一。3.设计出的文法必须能准确
41、地定义已知的语言,不能超出或缩小所定义的语言范围。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的文法。解:解:将句子的描述变形:a2mabbm和a2mbbbm发现句子中前后的a和b的个数有倍数关系于是:GZ:Z:=aaZb|ab|bb例:
42、例:写一文法,使其语言是偶整数的集合(不允许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|9D:=0|B类似问题:v写出带符号奇整数集合的文法v写出不能被5整除的无符号偶整数集合的文法v写出能被5整除的带符号偶整数集合的文法v三、三、求句型的短语,简单
43、短语及句柄以及判断文法二义性的问求句型的短语,简单短语及句柄以及判断文法二义性的问题题 用语法树作为分析的工具。用语法树作为分析的工具。1. 求句型的短语,简单短语及句柄求句型的短语,简单短语及句柄v句型的定义:对文法GS,若S=x,x(VNVT)*,则称x为句型。v短语,简单短语和句柄总是针对某个句型而言的。v短语总是句型的某个子串,它对应该句型语法树中,子树末端结点形成的符号串。v简单短语总是某个产生式右部,它对应该句型语法树中,简单子树末端结点形成的符号串。v语法树中最左边的简单短语就是句柄。例:有文法GE:E:=E+T|E-T|TT:=T*F|T/F|FF:=(E)|i求句型(F+i)
44、-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。文法中某产生式的右部句柄:F2. 文法二义性的判断及消除文法二义性的判断及消除判断:找出正确的句子,使之对应两棵不同的语法树。例:已知文法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
45、具有二义性。(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,下面的符号串为该文法句子的是()。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)?