东北大学秦皇岛分校编译原理课件第二章第三章.ppt
《东北大学秦皇岛分校编译原理课件第二章第三章.ppt》由会员分享,可在线阅读,更多相关《东北大学秦皇岛分校编译原理课件第二章第三章.ppt(91页珍藏版)》请在三一办公上搜索。
1、1,第三章文法和语言,本章目的 为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。(严谨、简洁、易读)形式工具-形式语言抽象地定义为一个数学系统。“形式”是指这样的事实:语言的所有规则只以什麽符号串能出现的方式来陈述,2,本章知识点(内容),引言和预备知识文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明,3,3.1 文法的直观概念和语言概述,当我们表述一种语言时,无非是说明这种语言的句子,如果语言只含有有穷多个句子,则只需列出句子的有穷集就行了,但对于含有无穷句子的语言来讲,存在着如何给出它的有穷表示的问题:给出一些规则
2、,用这些规则来说明(或者定义)句子的组成结构。,4,“我是大学生”。是汉语的一个句子,句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词,5,有了一组规则以后,按照如下方式用它们导出句子:开始去找=左端的带有句子的规则并把它由=右端的符号串代替,这个动作表示成:句子 主语谓语,然后在得到的串主语谓语中,选取主语或谓语,再用相应规则的=右端代替之。比如,选取了主语,并采用规则主语=代词,那么得到:主语谓语 代词谓语,重复做下去,句子:“我是大学生”的全部动作过程是:句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名
3、词 我是大学生,6,“我是大学生”的构成符合上述规则,而“我大学生是”不符合上述规则,我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据,换句话说,这些规则看成是一种元语言,用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。注:用于产生其他语言的语言称为元语言。,7,3.2 编译原理所涉及到的一些数学概念和运算,集合 笛卡儿乘积 关系 符号串,8,3.2.1 集合,概念 表示法:(1)枚举法:1,2,3(2)谓词法:x|x-32 特性:(1)唯一性(2)确定性 集合间的关系:相等、不相等、子集 集合的运算:并集、交集、差集、幂集,9,3.2.2 笛卡儿乘积,序
4、偶:由两个按一定次序排列的客体组成的序列,记为(x,y)n重序组:由n个按一定次序排列的客体组成的序列,记为(x1,x2,xn)笛卡儿乘积:A、B为任意两个集合,若序偶的第一个成员是集合A的一个元素,第二个成员是集合B的一个元素,则所有这样的序偶组成的集合称为集合A和B的笛卡儿乘积。,10,3.2.3 关系,定义 关系矩阵和关系图 关系的基本性质1、自反2、非自反3、对称4、非对称5、传递 关系的乘积 关系的传递闭包 自反传递闭包,11,3.3 有关定义和记号,符号:可以相互区别的记号(元素)。字母表:符号(元素)的非空有穷集合。符号串:由字母表中的符号组成的任何有穷序列称为该字母表上的符号串
5、。1.空符号串(没有符号的符号串)是上的符号串 2.若x是上的符号串,a是的元素,则xa是上的符号串 3.y是上的符号串,当且仅当它可以由1和2导出。例如:=a,b,a,b,aa,ab,aabba都是上的符号串,12,介绍有关符号串的一些运算,符号串的头,尾,固有头和固有尾:如果z=xy是一符号串,那么x是z的头,y是z的尾,如果x是非空的,那么y是固有尾;同样如果y非空,那么x是固有头。举个例子:设z=abc,那么z的头是,a,ab,abc,除abc外,其它都是固有头;z的尾是,c,bc,abc,z的固有尾是,c,bc。当对符号串z=xy的头感兴趣而对其余部分不感兴趣时,采用省略写法:z=x
6、;如果只是为了强调x在符号串z中的某处出现,则可表示为:z=x;符号t是符号串z的第一个符号,则表示为z=t。,13,符号串的连接:设x和y是符号串,它们的连接xy是把y的符号写在x的符号之后得到的符号串.由于 的含义,显然有 x=x=x。例如 x=ST,y=abu,则它们的连接xy=STabu,看出x=2,y=3,xy=5符号串的方幂:符号串自身连接n次得到的符号串 an 定义为 aaaa n个a a1=a,a2=aa且a0=例;若x=AB 则:x0=x1=AB x2=ABAB x3=ABABAB xn=xxn-1=xn-1 x(n0),14,符号串集合:若集合A中所有元素都是某字母表上的符
7、号串,则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为 AB=xy|xA且yB 若 集合A=ab,cde B=0,1 则 AB=ab1,ab0,cde0,cde1使用*表示上的一切符号串(包括)组成的集合。*称为的闭包。上的除外的所有符号串组成的集合记为+。+称为的正闭包。,15,例:=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,16,有关定义和记号,语言是由句子组成的集合,是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合(字母表上的每个语言是*的一个子集)。例如:字母表=a,b,*=,
8、a,b,aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或表示为w|w*且w=anbn,n1为字母表上的一个语言。集合a,aa,aaa,或表示为w|w*且w=an,n1 为字母表上的一个语言。是一个语言。即 是一个语言。,17,3.4文法和语言的形式定义,语言是由句子组成的集合,是由一组符号所构成的集合。汉语-所有符合汉语语法的句子的全体英语-所有符合英语语法的句子的全体程序设计语言-所有该语言的程序的全体 每个句子构成的规律研究语言 每个句子的含义 每个句子和使用者的关系,语言概述,18,程序设计语言的概念和描述方法,程序设计语言是形式语言,其定义和描述包
9、括语法、语义和语用三个方面。程序设计语言的语法实际上是一组规则。程序设计语言的语句可分为两大类:1、非执行语句2、可执行语句 描述程序程序设计语言的语法规则的有效工具是文法中的上下文无关文法。,19,语言研究的三个方面 语法 Syntax 语义 Semantics 语用 Pragmatics语法-表示构成语言句子的各个记号之间的组合规律,即句子的组成结构。语义-表示各个记号的特定含义。(各个记号和记号所表示的对象之间的关系)语用-表示在各个记号所出现的行为中,它们的来源、使用和影响。,编译原理只讨论语言的语法和语义,20,每种语言具有两个可识别的特性,即语言的形式和该形式相关联的意义。语言的实
10、例若在语法上是正确的,其相关联的意义可以从两个观点来看,其一是该句子的创立者所想要表示的意义,另一是接收者所检验到的意义。这两个意义并非总是一样的,前者称为语言的语义,后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。,21,如果不考虑语义和语用,即只从语法这一侧面来看语言,这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实:语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,22,文法和语言的形式定义,如何来描述一种语言?如果语言是有穷的(只含有有穷多个
11、句子),可以将句子逐一列出来表示如果语言是无穷的,找出语言的有穷表示。语言的有穷表示有两个途经:生成方式(文法):语言中的每个句子可以用严格定义的规则来构造。识别方式(自动机):用一个过程,当输入的一任意串属于语言时,该过程经有限次计算后就会停止并回答“是”,若不属于,要麽能停止并回答“不是”,(要麽永远继续下去。),23,文法即是生成方式描述语言的:语言中的每个句子可以用严格定义的规则来构造.下面给出文法的定义.进而在文法的定义的基础上,给出推导的概念,句型、句子和语言的定义。,24,定义,文法G定义为四元组(VN,VT,P,S)其中VN为非终结符号(或语法实体,或变量)集;VT为终结符号集
12、;P为产生式(也称规则)的集合;VN,VT和P是非空有穷集。S称作识别符号或开始符号,它是一个非终结符,至少要在一条产生式中作为左部出现。VN和VT不含公共的元素,即VN VT=用V表示VN VT,称为文法G的字母表或字汇表规则,也称重写规则、产生式或生成式,是形如或=的(,)有序对,其中是字母表V的正闭包V+中的一个符号,是V*中的一个符号。称为规则的左部,称作规则的右部。,25,文法的定义,例 文法G=(VN,VT,P,S)VN=S,VT=0,1 P=S0S1,S01 S为开始符号,例 文法G=(VN,VT,P,S)VN=标识符,字母,数字VT=a,b,c,x,y,z,0,1,9P=a,z
13、 0,9 S=,27,文法的写法 1 G:SaAb Aab AaAb A 2 GS:Aab AaAb A SaSb 3 GS:Aab|aAb|SaSb,元符号:=|习惯表示 大写字母:终结符 小写字母:非终结符S ABA Ax|yB z,29,推导的定义,直接推导“”是文法G的产生式,若有v,w满足:v=,w=,其中V*,V*则称v直接推导到w,记作 v w 也称w直接归约到v例:G:S0S1,S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1,30,.VAR;BEGIN READ()END.VAR A;BEGIN READ()END.,31,
14、推导的定义,若存在v w0 w1.wn=w,(n0)则记为v=+w,v推导出w,或w归约到v 若有v=+w,或v=w,则记为v=*w,32,例:G:S0S1,S010S1 00S1100S11 000S111000S111 00001111 S 0S1 00S11 000S111 00001111 S=+00001111 S=*S 00S11=*00S11,33,句型、句子的定义,句型有文法G,若S=*x,则称x是文法G的句型。句子有文法G,若S=*x,且xVT*,则称x是文法G的句子。例:G:S0S1,S01S 0S1 00S11 000S111 00001111G的句型S,0S1,00S1
15、1,000S111,00001111G的句子00001111,01,34,例:GE:EE+T|T TT*F|F F(E)|aEE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a句子:用符号a,+,*,(和)构成的算术表达式,35,文法,语言的定义,由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)=x|S=*x,其中S为文法的开始符号,且x VT*例:G:S0S1,S01L(G)=0n1n|n1,例 文法GS:(1)SaSBE(2)SaBE(3)EBBE(4)aBab(5)bBbb(6)bEbe(7)eEee L(G)=anbnen|n1,37,S
16、 a S BE(SaSBE)a aBEBE(SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE(bBbb)aabbeE(bEbe)aabbee(eEee)G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成,38,使用产生式(1)n-1次,得到推导序列:S=*an-1S(BE)n-1,然后使用产生式(2)一次,得到:S=*an-1S(BE)n-1 an(BE)n。然后从an(BE)n继续推导,总是对EB使用产生式(3)的右部进行替换,而最终在得到的串中,所有的B都先于所有的E。例如,若n=3,aaaBEBEBE aaaBBEEBE aaaBBEBEE aaaBBBE
17、EE。即有:S=*anBnEn接着,使用产生式(4)一次,得到S=*anbBn-1En,然后使用产生式(5)n-1次得到:S=*anbnEn,最后使用产生式(6)一次,使用产生式(7)n-1次,得到:S=*anbnen 也能证明,对于n1,串anbnen是唯一形式的终结符号串,39,文法的等价,若L(G1)=L(G2),则称文法G1和G2是等价的。如文法G1A:A0R 与G2S:S0S1 等价 A01 S01 RA1,40,文法的类型,通过对产生式施加不同的限制,Chomsky将文法分为四种类型:0型文法:对任一产生式,都有(VNVT)+,(VNVT)*1型文法:对任一产生式,都有|,仅仅 S
18、除外2型文法:对任一产生式,都有VN,(VNVT)*3型文法:任一产生式的形式都为AaB或Aa,其中AVN,BVN,aVT,41,文法的类型,例:1型(上下文有关)文法 文法GS:SCDAbbA CaCABaaB CbCBBbbBADaD CBDbD DAabD,42,文法的类型,例:2型(上下文无关)文法 文法GS:SABABS|0BSA|1,43,3型文法,GS:S0A|1B|0A0A|1B|0SB1B|1|0,GI:I lTI lT lTT dTT lT d,44,文法的类型,0型文法,四种文法之间的逐级“包含”关系,3型文法,45,文法和语言,0型文法产生的语言称为0型语言1型文法或上
19、下文有关文法(CSG)产生的语言称为1型语言或上下文有关语言(CSL)2型文法或上下文无关文法(CFG)产生的语言称为2型语言或上下文无关语言(CF L)3型文法或正则(正规)文法(RG)产生的语言称为3型语言正则(正规)语言(RL),46,根据形式语言理论,文法和识别系统间有这样的关系,0型文法(短语结构文法)的能力相当于图灵机,可以表征任何递归可枚举集,而且任何0型语言都是递归可枚举的 1型文法(上下文有关文法):产生式的形式为1A212,即只有A出现在1和2的上下文中时,才允许取代A。其识别系统是线性界限自动机。,47,带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 东北大学 秦皇岛 分校 编译 原理 课件 第二 第三

链接地址:https://www.31ppt.com/p-5907643.html