编译原理文法和语言精选文档.ppt
《编译原理文法和语言精选文档.ppt》由会员分享,可在线阅读,更多相关《编译原理文法和语言精选文档.ppt(59页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、编译原理文法和语言1本讲稿第一页,共五十九页第第2章章文法和语言文法和语言【学习目标学习目标】本章是为语言的语法描述寻求工具本章是为语言的语法描述寻求工具 掌握对程序设计语言给出精确、无二义掌握对程序设计语言给出精确、无二义(严谨、易读)的语法描述的手段之一(严谨、易读)的语法描述的手段之一文法。文法。对形式语言的理论有一个初步基础对形式语言的理论有一个初步基础 根据文法的特点指导语法分析过程根据文法的特点指导语法分析过程2本讲稿第二页,共五十九页2.1 文法的直观表示文法的直观表示文法:文法:阐明语法的一个工具,也可以说是以有穷的集合刻阐明语法的一个工具,也可以说是以有穷的集合刻画无穷的集合
2、的一个工具。画无穷的集合的一个工具。语言:语言:程序设计语言。程序设计语言。一、语言概述一、语言概述4语言是由符合语法的句子组成的集合。语言是由符合语法的句子组成的集合。汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体 每个句子构成的规律每个句子构成的规律语法语法4研究语言研究语言 每个句子的含义每个句子的含义 语义语义 每个句子和使用者的关系每个句子和使用者的关系语用语用3本讲稿第三页,共五十九页形式语言:只考虑语法而不考虑语义的符号语言。
3、形式语言:只考虑语法而不考虑语义的符号语言。4每种语言具有两个可识别的特性每种语言具有两个可识别的特性语言的形式语言的形式与该形式相关联的意义与该形式相关联的意义4“形式形式”指语言的所有规则,描述出现什么符号指语言的所有规则,描述出现什么符号串串4语言可以看成在一个基本符号集上定义的,按一语言可以看成在一个基本符号集上定义的,按一定规则构成的基本符号串组成的所有集合。定规则构成的基本符号串组成的所有集合。4形式语言理论是对符号串集合的表示法、结构及形式语言理论是对符号串集合的表示法、结构及其特性的研究,是程序设计语言语法分析研究的其特性的研究,是程序设计语言语法分析研究的基础。基础。4本讲稿
4、第四页,共五十九页4表达语言时,一般无法穷尽语言的所有句子,表达语言时,一般无法穷尽语言的所有句子,常用规则加以描述常用规则加以描述4 例:汉语句子的构成规则:例:汉语句子的构成规则:句子句子=主语主语谓语谓语主语主语=代词代词|名词名词代词代词=我我|你你|他他名词名词=王明王明|大学生大学生|工人工人|英语英语谓语谓语=动词动词直接宾语直接宾语动词动词=是是|学习学习直接宾语直接宾语=代词代词|名词名词二、文法的直观概念二、文法的直观概念5本讲稿第五页,共五十九页推导:推导:“我是大学生我是大学生”是汉语的一个句子是汉语的一个句子句子句子 主语主语 谓语谓语 代词代词谓语谓语 我我谓语谓语
5、 我我动词动词直接宾语直接宾语 我是我是直接宾语直接宾语 我是我是名词名词 我是大学生我是大学生 6本讲稿第六页,共五十九页2.2 符号与符号串符号与符号串一、相关概念一、相关概念程序设计语言是由程序构成的集合,程序是由基程序设计语言是由程序构成的集合,程序是由基本符号按照一定的规则构成的集合。本符号按照一定的规则构成的集合。1.符号、字母表和符号串符号、字母表和符号串4基本符号:基本符号:可以相互区别的基本元素,如字母,可以相互区别的基本元素,如字母,数字,标点符号。数字,标点符号。4字母表:字母表:基本符号的非空有穷集合,常用基本符号的非空有穷集合,常用表示。表示。例:例:=0,1,=a,
6、b,c,x,y,z7本讲稿第七页,共五十九页4符号串:由字母表中的符号串:由字母表中的符号构成的任何有穷序列符号构成的任何有穷序列称为符号串。称为符号串。符号串中的符号是有顺序的。符号串中的符号是有顺序的。例如例如 =0,1上的符号串上的符号串0,1,00,01,11,10 注意:注意:表示空符号串表示空符号串,它表示不包含任何符号串,它表示不包含任何符号串,不是不是空格符。空格符。符号串集合:符号串集合:字母表上若干个符号串组成的集合字母表上若干个符号串组成的集合.例:字母表例:字母表=0,1 的符号串集合的符号串集合A=1,00,01;约定:小写字母约定:小写字母 a,b,r表示符号表示符
7、号.小写字母小写字母 s,t,z表示符号串表示符号串;8本讲稿第八页,共五十九页4符号串符号串s的头(前缀)和尾(后缀)的头(前缀)和尾(后缀):如果如果s=xy是一符号串,那么是一符号串,那么x是是s的头,的头,y是是s的的尾。若尾。若x是非空,则是非空,则y是固有尾;若是固有尾;若y非空,则非空,则x是固有头。是固有头。前缀前缀:移走符号串:移走符号串s尾部的零个或多个符号得尾部的零个或多个符号得到的串。到的串。如:设如:设s=abc,那么那么s的前缀是的前缀是,a,ab,abc 后缀:后缀:移走符号串移走符号串s头部的零个或多个符号头部的零个或多个符号得到的串。得到的串。如:如:s=ab
8、c的后缀是的后缀是,c,bc,abc,s的固有尾是的固有尾是,c,bc。4 9本讲稿第九页,共五十九页4符号串符号串s的子串:的子串:从从s中删去中删去任何任何前缀或后缀得到的串前缀或后缀得到的串.如如:bc是符号串是符号串abc的一个子串的一个子串.4对符号串对符号串s,s和和两者都两者都是符号串是符号串s的前缀、的前缀、后缀和子串。后缀和子串。4符号串符号串s的真前缀,真后缀,真子串:的真前缀,真后缀,真子串:任何非空符号串任何非空符号串 x,是,是s的前缀,后缀或子的前缀,后缀或子串,并且串,并且 s x10本讲稿第十页,共五十九页2.符号串的运算符号串的运算(1)符号串相等:符号串相等
9、:符号串符号串x,y,如果两者诸符号依次相等,则两,如果两者诸符号依次相等,则两符号串相等。符号串相等。(2)符号串的长度:符号串的长度:符号串中包含符号的个数。符号串中包含符号的个数。|abc|=3;|=0;(3)符号串的连结:符号串的连结:x=abc,y=def 则则xy=abcdef;yx=defabc;xy yx x=x =x;11本讲稿第十一页,共五十九页(4)符号串集合的乘积:符号串集合的乘积:设设A、B为两个符号串集合,其乘积为为两个符号串集合,其乘积为AB=xy|x A,y B;例:例:A=aa,bb,B=cc,dd,则,则AB=aacc,aadd,bbcc,bbdd A=A
10、=A;(5)空集:空集:不含任何元素的集合称为空集。记为不含任何元素的集合称为空集。记为;对任何集合对任何集合A:A =A=;注意:注意:12本讲稿第十二页,共五十九页(6)符号串的方幂:符号串的方幂:x是字母表上的符号串,则是字母表上的符号串,则x的幂运算为:的幂运算为:x0=;x1=x;x2=xx;xn=xn-1x=x xn-1 (n0)xn表示表示n个个x相连结。相连结。eg:x=ok;则;则 x0=;x1=ok;x2=okok;(7)符号串集合的方幂:符号串集合的方幂:A为符号串集合,则为符号串集合,则A的幂运算为:的幂运算为:A0=;A1=A;A2=AA;.An=An-1A=AAn-
11、1;(n0)A=aa,bb,则,则A0=;A1=aa,bb;A2=AA=aaaa,aabb,bbaa,bbbb;.13本讲稿第十三页,共五十九页(8)符号串集合的闭包和正闭包符号串集合的闭包和正闭包集合集合A的闭包表示为的闭包表示为A*(亦称为自反闭包或星(亦称为自反闭包或星闭包)定义为:闭包)定义为:A*=A0 A1 A2 A3 =Ak,k0正闭包表示为正闭包表示为A+具体定义为具体定义为A+=A1 A2 A3 =Ak,k1由定义可以看到由定义可以看到A*=A0 A+例:例:=a,b *=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,1
12、4本讲稿第十四页,共五十九页3、语言、语言(1)由由一一组组符符号号所所构构成成的的集集合合。即即:字字母母表表 上上的的每个语言是每个语言是*的一个子集。的一个子集。例如:例如:字母表字母表=a,b=a,b,*=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,集合集合ab,aabb,aaabbb,ab,aabb,aaabbb,a,an nb bn n,或表示为或表示为w|ww|w*且且w=aw=an nb bn n,n1,n1为为字母表字母表 上上的一个语的一个语言。言。集合集合a,aa,aaa,a,aa,aaa,或表示为或表示为w|ww
13、|w*,且且w=aw=an n,n1 n1 为为字母表字母表 上上的一个语言。的一个语言。(2)是一个语言。是一个语言。(3)即即 是一个语言。是一个语言。15本讲稿第十五页,共五十九页2.3 文法和语言的形式定义文法和语言的形式定义如何来描述一种语言?如何来描述一种语言?如果语言是有穷的(只含有有穷多个句子),可以将如果语言是有穷的(只含有有穷多个句子),可以将句子逐一列出来表示句子逐一列出来表示如果语言是无穷的,找出语言的如果语言是无穷的,找出语言的有穷表示有穷表示。语言的有。语言的有穷表示有两个途径:穷表示有两个途径:生成方式生成方式(文法):(文法):语言中的每个句子可以用严格语言中的
14、每个句子可以用严格定义的规则来构造。定义的规则来构造。识别方式(自动机):识别方式(自动机):用一个过程,当输入的一个任意串用一个过程,当输入的一个任意串属于语言时,该过程经有限次计算后就会停止并回答属于语言时,该过程经有限次计算后就会停止并回答“是是”,若不属于,要么能停止并回答,若不属于,要么能停止并回答“不是不是”,(要么永远,(要么永远继续下去。)继续下去。)16本讲稿第十六页,共五十九页一、规则(重写规则、产生式或生成式)一、规则(重写规则、产生式或生成式)4规则是形如规则是形如或或=的的(,)有序对,有序对,其其中中 V+,V*中的一个符号中的一个符号称为规则的左部称为规则的左部称
15、作规则的右部。称作规则的右部。4例:例:4文法可利用规则来描述。文法可利用规则来描述。17本讲稿第十七页,共五十九页二、文法的定义二、文法的定义1、文法、文法G定义为四元组定义为四元组(VN,VT,P,S)其中其中VN:非终结符号;非终结符号;VT:终结符号集;:终结符号集;P:规则集:规则集合;合;VN,VT和和P是非空有穷集。是非空有穷集。S:开始符或识别符,是一个非终结符,至少要在:开始符或识别符,是一个非终结符,至少要在一条规则的一条规则的左部左部出现。出现。VN VT=,V=VN VT,V称为文法称为文法G的字母表的字母表例例1:文法:文法G=(VN,VT,P,S),其中其中 VN=
16、S,VT=0,1,P=S0S1,S01。18本讲稿第十八页,共五十九页文法文法G习惯上只将规则写出。习惯上只将规则写出。如例如例1还可以写成:还可以写成:G:S0S1 S01或或GS:S0S1S01 或或GS:S0S1|S0119本讲稿第十九页,共五十九页总结一个文法的几种写法总结一个文法的几种写法 G=(S,A,a,b,P,S)其中其中P:SaAb Aab AaAb A G:SaAb Aab AaAb A GS:S aAb Aab AaAb A GS:SaAb Aab|aAb|20本讲稿第二十页,共五十九页三、推导的定义三、推导的定义用文法定义语言的中心思想是:从文法的开始符号出发,反复使用
17、用文法定义语言的中心思想是:从文法的开始符号出发,反复使用合适规则,对非终结符施行替换和展开。合适规则,对非终结符施行替换和展开。1 1、直接直接推导:推导:是文法是文法G G的产生式,若有的产生式,若有v v,w w满足:满足:v=v=,w=,w=,其中其中VV*,V,V*。则称。则称v v直接推导到直接推导到w w,或或w w直接归直接归约到约到v v记作记作 v vw w,2 2、推导:、推导:如果存在直接推导的序列:如果存在直接推导的序列:v=Wv=W0 0 W W1 1 W W2 2 W Wn n=w,=w,(n(n0)0);称;称v v推导出推导出w(w(推导长度为推导长度为n)n
18、),或称,或称w w归约到归约到v v。记作记作v wv w。若有若有v wv w,或,或v=wv=w,则记作,则记作v v w w,(n(n=0)=0)*21本讲稿第二十一页,共五十九页例3:G:S0S1,S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S 00001111 S S 00S11 00S11+*22本讲稿第二十二页,共五十九页43、规范推导、规范推导最左最左(最右最右)推导:在推导的任何一步推导:在推导的任何一步,其,其中中、是句型,都是对是句型,都是对中的最左(右)非中的最左(
19、右)非终结符进行替换终结符进行替换 最右推导被称为规范推导。最右推导被称为规范推导。例例4:GE E:EE+T|TEE+T|T TT*F|F TT*F|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a(最左推导最左推导)E EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a(最右推导最右推导)23本讲稿第二十三页,共五十九页四、句型、句子和语言的定义四、句型、句子和语言的定义1.句型句型:文法文法GS,若,若S x,则称,则称x是是G的句型。的句型。2.句子句子:文法文法GS,若,若S
20、x,且,且xVT*,则称,则称x是是G的句子。句子是句型的特殊,只包含终结符。的句子。句子是句型的特殊,只包含终结符。例例5 5:G G:S0S1,S01 S 0S1 00S11 000S111 00001111 G的句型的句型S,0S1,00S11,000S111,00001111 G的句子的句子000011113.语言语言:文法文法G的一切句子的集合的一切句子的集合,记为记为L(G),*24本讲稿第二十四页,共五十九页例例 6 文法文法GS:(1)SaSBE(2)SaBE(3)EBBE(4)aBab(5)bBbb(6)bEbe(7)eEee SanBnEn anbnen 则则 L(G)=a
21、nbnen|n1 因为因为San-1S(BE)n-1 an(BE)n,继续,继续推导时,将用规则推导时,将用规则(3)(7)替换替换*25本讲稿第二十五页,共五十九页S a S BE (SaSBE)a aBEBE (SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE(bBbb)aabbeE(bEbe)aabbee(eEee)G生成的每个串都在生成的每个串都在L(G)中中L(G)中的每个串确实能被中的每个串确实能被G生成生成26本讲稿第二十六页,共五十九页五、语言和文法五、语言和文法4给定一个文法,能从结构上唯一确定其语言给定一个文法,能从结构上唯一确定其语言4给定一个语言,
22、不能唯一确定其文法,即一个给定一个语言,不能唯一确定其文法,即一个语言可有多个文法与之对应语言可有多个文法与之对应4已知语言描述,写出文法已知语言描述,写出文法,应满足:,应满足:所描述的语言的任何句子都能由该文法产生所描述的语言的任何句子都能由该文法产生该文法推导不出不是已知语言的任何句子该文法推导不出不是已知语言的任何句子4已知文法,写出语言描述已知文法,写出语言描述,应满足:,应满足:该文法能推导出的任何句子都包含在所描述的该文法能推导出的任何句子都包含在所描述的语言中语言中描述的语言中不包含该文法推导不出的句子描述的语言中不包含该文法推导不出的句子27本讲稿第二十七页,共五十九页六、文
23、法的等价六、文法的等价若若L(G1)=L(G2),称文法),称文法G1和和G2是等价的是等价的如文法如文法G G1AA:A0R A0R 与与G G2SS:S0S1 S0S1 等价等价 A01 S01A01 S01 RA1 RA1作业:作业:P47:1P47:1,4 4,5 528本讲稿第二十八页,共五十九页2.4 文文 法法 的的 类类 型型一、文法分类一、文法分类 通过对产生式施加不同的限制,将文法分为四类通过对产生式施加不同的限制,将文法分为四类 设有文法设有文法G=(VN,VT,P,S);40型文法:(短语结构文法)型文法:(短语结构文法)图灵机图灵机对任一产生式对任一产生式,都有,都有
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 文法 语言 精选 文档
限制150内