编译原理-蒋立源第2章文法和语言.ppt
《编译原理-蒋立源第2章文法和语言.ppt》由会员分享,可在线阅读,更多相关《编译原理-蒋立源第2章文法和语言.ppt(56页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第二章第二章 文法和语言文法和语言 编译过程的核心就是翻译,就是把一种语言翻译成为另一种语言,与自然语言的翻译类似,只不过其工作对象是某种程序设计语言。两个重要的前提:1)描述和定义程序设计语言2)识别或分析这种语言20世纪50年代,语言学家Noam Chomsky(乔姆斯基)提出了一个用来描述语言的数学系统,把用一组数学符号和规则来描述语言的方式叫做形式描述,而把能用数学符号和规则描述的语言称为形式语言形式语言。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。程序设计语言就是形式语言。2.1 2.1 文法及语言的表示文法及语言的表示 如何来描述一种语言?1)当一个语言仅含有有限个
2、句子时,可采用枚举法来表示这种语言。对于无限的语言寻找出有限的表示,有两种途径:1.2)生成方式(文法):制定有限条规则,用来生成所要描述的语言中的全部句子。2.3)识别方式(自动机):建立一种装置(更确切的说,是构造一种算法或过程),此装置以某一字母表上的所有符号串作为输入,并识别这些符号串,当一个符号串是此字母表上某给定语言中的句子时,就接受它,反之,则拒绝接受。语言的定义:Webster定义:为相当大地区的公众所懂得并使用的“话”,以及组成这些“话”的方法的统一体。另一种定义:某一字母表上符号串(句子)的集合一种精确化的语言的要求:(1)为所定义语言中的句子提供一种结构性的描述(2)提供
3、一种手段,准确地判别什么是该语言的正确句子,而什么又不是基本概念和术语基本概念和术语 字字母母表表:元素的非空有穷集合。字母表中的每个元素称为“符号”,因此“字母表”也可称为“符号集”。典型的符号有字母、数字、各种标点符号和各种运算符。例如,集合a,b,c,+,*是一个含有5个符号的字母表,而字母表0,1只有2个符号。符号串符号串:由字母表上0个或多个符号所组成的任何有穷序列。特别地,把不包含任何符号的符号串称为空符号串。例如有字母表a,b,c,+,*,则a,b,c,+,*,aa,ab,ac,a+,a*,ba,bb,bc,b+,b*,aaa,bbb等等都是该字母表上的符号串。而所有二进制数都是
4、定义在字母表0,1上的符号串。显然,一个字母表上的全部符号串所组成的集合是无穷的。2.2 2.2 文法和语言的定义文法和语言的定义 符号串及其集合的运算符号串及其集合的运算1 11.符号串的长度符号串的长度:指符号串x中所含符号的个数,记为|x|。如:|abc|=3,|abc+*abc|=8,|=?2.符符号号串串的的前前缀缀:指从符号串x的末尾删除0或多个符号后得到的符号串,如、a、ab、abc都是abc的前缀。符号串的后缀符号串的后缀:指从符号串x的开头删除0或多个符号后得到的符号串,如、c、bc、abc都是abc的后缀。符号串的子串符号串的子串:指从符号串x的开头和末尾删除0或多个符号后
5、得到的符号串,如abc的子串?符号串的前缀、后缀都是它的子串。、a、b、c、ab、bc、abc|=0符号串及其集合的运算符号串及其集合的运算2 23.3.符号串的连接符号串的连接:若x、y是两个符号串,则xy表示连接,是将符号串y连接在符号串x的后面。若x、y是字母表上的两个符号串,则xy也是字母表上的符号串。如:x=ab,y=ba,那么 xy=abba注意:连接没有交换律,即 xy yx 对于空串有 x=x=x 符号串的方幂符号串的方幂:一个符号串x与其自身的n-1次连接称为x的n次方幂,即:X0=,x1=x,x2=xx,,xn=xxx=xxn-1=xn-1x如:x=abc,x0=,x1=a
6、bc,x2=abcabc,符号串及其集合的运算符号串及其集合的运算3 34.符符号号串串集集合合的的乘乘积积:令A、B为两个符号串集合,A和B的乘积AB定义为:AB=xy|x A,y B例如:A=a,b B=c,d,则AB=ac,ad,bc,bd对于有:A=A=A符号串集合的方幂符号串集合的方幂:设A为符号串集合,则A的方幂定义为:A0=,A1=A,A2=AAAn=AAA=AAn-1=An-1A例如:A=a,b,c A0=A1=a,b,c A2=AA=aa,ab,ac,ba,bb,bc,ca,cb,cc符号串及其集合的运算符号串及其集合的运算4 45.符符号号串串集集合合的的闭闭包包:设设A为
7、为一一个个集集合合,则则集集合合A的的正正闭闭包包用用A+表示,定义为:表示,定义为:A+=A1A2.An集合集合A的闭包用的闭包用A*表示,定义为:表示,定义为:A*=A0A+例如:A=a,b,c则A+=a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,A*=,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,可可见见,字字母母表表A的的正正闭闭包包A+就就是是由由A中中字字母母所所构构成成的的一一切切符符号号串的集合,而串的集合,而A*仅比比A+多个多个。2.2.2 2.2.2 文法和语言的形式定义文法和语言的形式定义 在学习
8、英语时,我们知道句子由主语、谓语组成,主语由冠词、形容词及名词组成等等,这就是说明句子组成的规则。而在形式语言里,这种规则可采用“:=”、“:=”这种形式来表示。分析一个句子是否正确,就是根据这些规则进行的。实际上,文法就是描述语言语法结构的形式规则。从“产生语言”的角度出发,给出方法和语言的形式定义。产生语言:指制定出有限个规则,借助这些规则可以产生此语言的全部句子。文法形式定义文法形式定义1 1 在表示文法时,要说明语言的语法成分(语法范畴),句子中的符号以及语法结构。例如,能够描述句子例如,能够描述句子“themonkeyateabanana”的文法如下:的文法如下:在这个文法里,其中用
9、“”符号括起来的部分,表示评议的一个语法实体。符号“:=”是一个整体,其含义是“定义为”,也就是左边的语法实体可进一步定义为右边的符号串。在推导过程中,就是一种“替换”关系。而像the、ate、banana这样的符号只在规则中:=的右边出现,不需要进一步定义,这些符号不能用其它符号代替。我们最终需定义的语法成分是。每条规则的形式都是:=。1):=2):=the3):=4):=5):=monkey6):=banana 7):=ate8):=has9):=the10):=a“:=”表示“定义为”文法形式定义文法形式定义2 2=the=the=themonkey=themonkeyate=themo
10、nkeyatea=themonkeyateabanana如何用上述规则去产生或推导出相应语言的句子呢?=+themonkeyateabanana“=”表示一步推导“=+”表示多步推导文法形式定义文法形式定义3 3文法的形式定义:文法的形式定义:文法可表示为一个四元组文法可表示为一个四元组GS=(VN,VT,P,S)VN是是一一个个非非空空有有穷穷集集合合,该该集集合合中中的的每每个个元元素素称称为为非非终终结结符符号号。如如上上例例中中VN=、VT是是一一个个非非空空有有穷穷集集合合,该该集集合合中中的的每每个个元元素素称称为为终终结结符符号号。如如上上例例中中VT=monkey、banana
11、、ate、has、the、a并且并且VNVT=,而,而VNVT称为该文法的字汇表。称为该文法的字汇表。P是是一一个个非非空空的的有有穷穷集集合合,它它的的每每个个元元素素叫叫做做产产生生式式或或规规则则。产产生生式式的的形形式式为:为:或或:=是产生式的左部且不能为空,是产生式的左部且不能为空,是产生式的右部,并且是产生式的右部,并且、V。S是是VN集集合合的的一一个个特特殊殊的的非非终终结结符符号号,称称为为文文法法的的开开始始符符号号。它它至至少少必必须须在在某个产生式的左部出现一次。某个产生式的左部出现一次。就是上例文法的识别符号。就是上例文法的识别符号。文法形式定义文法形式定义4 4文
12、法分文法分4种类型(见种类型(见2.5小节),程序设计语言文法主要为小节),程序设计语言文法主要为2型型文法,这种文法也叫文法,这种文法也叫前后文无关文法前后文无关文法,本书后面说的文法都,本书后面说的文法都是指这种文法。是指这种文法。在前后文无关文法中,产生式的左部在前后文无关文法中,产生式的左部是一个非终结符号,而是一个非终结符号,而右部右部是由终结符号和非终结符号组成的有穷符号串。这样只是由终结符号和非终结符号组成的有穷符号串。这样只要给出产生式集合,所有产生式的左部符号就构成了非终结要给出产生式集合,所有产生式的左部符号就构成了非终结符号集合符号集合VN,而只出现在产生式右部的那些符号
13、构成终结符,而只出现在产生式右部的那些符号构成终结符号集合号集合VT,因此,在表示文法时只需给出规则集合并指定识,因此,在表示文法时只需给出规则集合并指定识别符号即可。别符号即可。为了进一步简化,在给出规则集时,可约定将为了进一步简化,在给出规则集时,可约定将左部符号为开始符号的规则作为规则集合的第一条规则,这左部符号为开始符号的规则作为规则集合的第一条规则,这样表示文法时只需给出规则的集合即可。显然,上例就是一样表示文法时只需给出规则的集合即可。显然,上例就是一个简化的文法表示。个简化的文法表示。文法形式定义文法形式定义5 5 例2.2,有如下简化表示文法,只给出规则集,写出该文法的终结符号
14、集合、非终结符号集合和开始符号。1.2.3.4.05.16.27.38.49.510.611.712.813.9解:根据简化约定,可确定:解:根据简化约定,可确定:非终结符号集合:非终结符号集合:VN=,终结符号集合:终结符号集合:VT=0,1,2,3,4,5,6,7,8,9开始符号开始符号S:文法的文法的EBNFEBNF表示表示 所谓文法的所谓文法的EBNF表示,就是在书写文法的规则时,可采用一些特殊的符表示,就是在书写文法的规则时,可采用一些特殊的符号号“|”、“”和和“”、“(”和和“)”、“”和和“”来表示文法,来表示文法,这些符号叫做元符号。其中这些符号叫做元符号。其中“”和和“”、
15、“(”和和“)”、“”和和“”这些元符号总是成对出现。下面介绍各种元符号的含义。这些元符号总是成对出现。下面介绍各种元符号的含义。1.元符号元符号“|”:表示:表示“或或”.对于具有相同左部的那些规则对于具有相同左部的那些规则如如1、n,可以缩写为,可以缩写为:1|2|n例例2.3,对例,对例2.2文法的文法的13条规则可缩写成:条规则可缩写成:|0|1|2|3|4|5|6|7|8|9文法的文法的EBNFEBNF表示表示2.元符号元符号“”和和“”:表示可重复:表示可重复连接连接,tnm表示符号串表示符号串t可可重复重复连接连接n到到m次,而次,而t表示符号串表示符号串t可重复可重复连接连接0
16、到无穷次。到无穷次。例如,例如,13与与|相同相同EE+T|T与与ET+T相同相同而字母打头、后面可跟数字或字母的不超过而字母打头、后面可跟数字或字母的不超过8个字符的标识符文法则为:个字符的标识符文法则为:|07文法的文法的EBNFEBNF表示表示3.元元符符号号“”和和“”:表表示示括括起起的的内内容容可可有有可可无无。如如t表表示示符号串符号串t可有可无。可有可无。例如:例如:IFTHENIFTHENELSE可写成:可写成:IFTHENELSE4.元元符符号号“(”和和“)”:表表示示括括号号内内的的成成分分优优先先。常常用用于于在在规规则中提取公因子。则中提取公因子。例如,例如,Uxy
17、|xw|xz可写成:可写成:Ux(y|w|z)从从上上述述有有关关元元符符号号的的定定义义和和例例子子可可看看出出,这这些些元元符符号号为为表表示示文文法法提供了很大方便。提供了很大方便。直接推导直接推导 设设GS是一文法是一文法,是该文法的一个产生式,对于符号串是该文法的一个产生式,对于符号串xy xy,其中,其中x x和和y y是该文法的任意符号串是该文法的任意符号串(可为空可为空),推导就是用推导就是用产生式产生式的右部替换左部,从而得到新的符号串的右部替换左部,从而得到新的符号串xyxy。表。表示为:示为:xy=xyxy=xy其中其中“=”“=”表示一步推导。我们称表示一步推导。我们称
18、xyxy直接推导出直接推导出xyxy,或或xyxy直接产生直接产生xyxy。若从反方向看,则。若从反方向看,则称称xyxy直接归约到直接归约到xyxy。x,yV*直接推导直接推导例如有文法例如有文法1)2)|3)0|1|2|3|4|5|6|7|8|9对符号串对符号串利用规则利用规则1可直接推导出可直接推导出:=对符号串对符号串利用规则利用规则2可直接推导出可直接推导出:=对符号串对符号串利用规则利用规则3可直接推导出可直接推导出2:=2将上述三个推导连接起来,可得如下推导过程:将上述三个推导连接起来,可得如下推导过程:=2推导推导 如如果果文文法法GS存存在在一一直直接接推推导导序序列列0=1
19、=n,其其中中n0,那那么么我我们们说说0推导出推导出n或或n归约到归约到0,并记作并记作0=+n,推导长度为推导长度为n。如果有如果有0=+n或或0=n,即即n0,则记作则记作0=*n。可见,可见,n0的推导和的推导和n=0分别称为分别称为“+推导推导”和和“*推导推导”。例如,从开始,分别利用规则1、2、2、3、3,可产生如下推导过程:=2=23这个推导过程可记作:=+23,其推导长度n=5,而从到的推导,无须使用任何规则,可记作:=*,其推导长度n=0。句型和句子句型和句子 推导产生的结果可能是句型,也可能是句子。设文法G的识别符号为S,则句型、句子的定义如下:1.如果如果S=*,且且V
20、*,则称则称是文法是文法GSGS的一个句型。的一个句型。2.如果如果S=+,且且 VVt t*,则称则称是文法是文法GSGS的一个句子。的一个句子。从文法的开始符号利用规则进行推导,一旦推导出句子,推导过程就不能再继续进行,因为句子中没有非终结符号。假设符号串是某一推导的结果,那么,是句子的必要条件是从S到的推导长度大于等于,即 S=+x,而不可能是S=*x。这是因为识别符号S是非终结符号,而是终结符号串,显然,S不可能与相等,所以S不可能经过步推导就等于。为何这里是“+推导”?句型是从识别符号开始经过0步或多步推导出的可由终结符号和非终结符号组成的符号串而句子是从文法的识别符号推导出的完全由
21、终结符号组成的符号串句子是从文法的识别符号推导出的完全由终结符号组成的符号串。句子是特殊的句型,是完全由终结符号组成的句型。语言语言 一个文法一个文法GS所产生的所有句子的集合所产生的所有句子的集合L(GS),称为文法称为文法GS所定义的语言所定义的语言,即即:L(GS)=x|S=+x,且且xVt*,一一个个文文法法所所定定义义的的语语言言是是该该文文法法的的终终结结符符号号集集合合Vt上上的的所所有有符符号号串串组组成成的的集集合合的的一一个个子子集集,该该子子集集中中的的每每个个符符号号串串都都可可从从识识别别符符号号开开始始经经过过至至少少一一步步推推导导出出来,即来,即:L(GS)Vt
22、*例如,对例2.1的文法G,其语言有16个句子:the monkey ate the banana the banana ate the monkey the monkey ate the monkey the banana ate the banana而例2.3中的文法,其语言是所有无符号整数,句子是无穷的。文法和语言有如下关系:文法和语言有如下关系:1)给定一个文法给定一个文法,就能从结构上唯一的确定其语言就能从结构上唯一的确定其语言,即即:GL(G)2)给定一种语言给定一种语言,能确定其文法能确定其文法,但不唯一但不唯一,即即:LG1或或G2或或。语言语言例例2.4,已知文法,已知文法G
23、S为:为:1)SaSb2)Sab或写成或写成SaSb|ab求该文法确定的语言。求该文法确定的语言。解:从识别符号开始推导,反复用规则解:从识别符号开始推导,反复用规则1,最后用规则最后用规则2可得可得:S=aSb=a2Sb2=an-1Sbn-1=anbn(n 2)直接用规则直接用规则2可得可得:S=ab所以该文法确定的语言为:所以该文法确定的语言为:L(GS)=an nb bn n|n1|n1 反之,试构造产生下列语言的文法anbn|n0SaSb|语言语言例2.5,已知语言为:L(G)=abna|n1,构造产生该语言的文法。解:根据语言的形式,可构造其文法G为:SaBaBBb|b还可以构造文法
24、G1为:SaBaBbB|b可见,G与G1是两个不同的文法,但它们都可以描述语abna|n1。如果两个不同的文法可描述相同的语言如果两个不同的文法可描述相同的语言,那么我们称那么我们称这两个文法为等价文法。前后文无关文法的等价问这两个文法为等价文法。前后文无关文法的等价问题是不可判定的。等价文法的存在,对编译技术的题是不可判定的。等价文法的存在,对编译技术的实现有很大帮助,使我们能在不改变文法所确定的实现有很大帮助,使我们能在不改变文法所确定的语言前提下,为了某种目的而改写文法。语言前提下,为了某种目的而改写文法。引理引理2.1设设G=(Vn,Vt,P,S)为一文法,并设为一文法,并设AxBy是
25、是P中的一个产生式。而中的一个产生式。而B1,B2,Bk是是P中的全部中的全部B-产生式,又设产生式,又设G1=(Vn,Vt,P1,S)是是这样的文法,其中,这样的文法,其中,P1是从是从P中删去中删去AxBy并添加产生式并添加产生式Ax1y,Ax2y,Axky所组成的集合,则所组成的集合,则L(G1)=L(G)。递归规则与递归文法递归规则与递归文法递归规则是指在规则的右部含有与规则左部相同符号的规则。设文法GS,x,y是V上的符号串,若U xUy是文法的规则,且xy!=,则称U xUy为直接递归规则,称U为直接递归的非终结符。特别,若x=,即这个相同的符号出现在右部的最左端,则为左递归规则。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 蒋立源第 文法 语言
限制150内