编译方法马知行曹启君机械工业出版社编译原理演示文稿2.ppt
《编译方法马知行曹启君机械工业出版社编译原理演示文稿2.ppt》由会员分享,可在线阅读,更多相关《编译方法马知行曹启君机械工业出版社编译原理演示文稿2.ppt(58页珍藏版)》请在三一文库上搜索。
1、第二章 文法和语言 2.1 文法的基本概念 一个程序设计语言是一个记号系统,如自然语言一样,它的完整的定义应包括语法和语义两方面。所谓一个语言的语法其实是指一组规则,用它可以形成和产生一个合适的程序。目前在程序设计语言的识别中广泛使用的是上下文无关的文法。在这理主要介绍文法和语言的概念。 语言根据所含句子数量有限(穷)与否又可分为: 有限(穷)语言和无限(穷)语言。,例:设有文法: G: the big ate|caught mouse|cat,则: = =the= the big =the big cat =the big cat =the big cat ate=the big cat a
2、te=the big cat ate the =the big cat ate the mouse,2.1.1 符号和符号串 定义 2.1 字母表是有穷非空集合。用或 V表示。 例:无符号二进制数的字母表为: =0,1 C语言的字母表为字母、数字和若干专用符号组成的符号集 定义 2.2 符号串是由字母表中的符号组成的有穷序列,又称字符串、串。 例:a,b,c,ba,bbac,caacb,等都是字母表a,b,c上的符号串。,定义 2.3 不包含任何字符串的空符号串用表示 定义 2.4 符号串x的长度,即符号串x中的字符的个数用|x|表示(读作x的长度) 例:|abc|=3 |a|=1 |=0 定
3、义 2.5 设非空符号串u=xvy,其中v,则称v为u的子串,若|u| |v|则称v为u的真子串,定义 2.6 如果z=xy是一个符号串,则x是z和头,而y是z的尾。如果x是非空的,那么y是固有尾;同样如果y非空,那么x是固有头。 例:设z=abc,那么z的头是,a,ab,abc。除abc外,其它都是固有头。z的尾是,c,bc,abc。z的固有尾是,c,bc,定义 2.7 设x、y 是同一字母表上的两个符号串,把符号串y写在符号串X的后面所得到的符号串,称为x、y的连接。记为xy 例:x=ab,y=wabu 则 z=xy=abywabu 显然:|x|+|y|=|z| x=x=x,定义 2.8
4、设x是符号串,把x自身连接n次得到符号串z,即z=xxxx(n个x),称为符号串x的方幂,记为z=xn 例:x0= x1=x x2=xx x3=xxx 定义 2.9 符号串集合,若集合A中的一切元素都是其字母表上的符号串,则称A为该字母表上的符号串集合。 注意:、和(表示空集)的区别,定义 2.10 两个符号串集合A和B的乘积, AB定义为: AB=xy|xA且yB 例:设A=a,bc,B=b,c,da则集合 AB=ab,ac,ada,bcb,bcc,bcda。 注意:由于x=x=x 因此A=A=A ,但A=A= 则: A0= A1=A A2=AA An=An-1A=AAn-1(n0),定义
5、2.11 A的闭包 A*=A0A1A2 A的正闭包 A+= A1A2A3 显然A+=AA*=A*A A*=A0A+,由于一个字母表上的正闭包包含了该字母表中的符号所能组成的一切符号串,而语言是该字母表上的某些符号串的集合,因此,某个字母表上的语言是这个字母表上的正闭包的子集,而且通常是真子集。 例:若=0,1,则*=,0,1,00,01,10,11,000,001,010, 例:令L=A,B,C,Z,a,b, ,z,D=0,1, 9 1.LD 2.LD 3.L 4. L(LD)* 5. D+ 6.D+L*则分别代表什么集合? 1.字母或数字的集合 2.由一个字母开头后面跟一个数字的集合 3.由
6、字母组成的集合 4.由字母开头后面是字母数字(可省略)的集合 5.数字串集合 6.数字串和字母串集合(包括),:当对符号串z=xy的头感兴趣而对其余部分不感兴趣时,可以采用省略写法:z=x;如果只是为了强调x在符号串z中的某处出现,则可表示为:z=x;如果只是为了强调x在符号串z约定中的末尾出现,则可表示为:z=x;,2.1.2 文法和语言的形式定义 语言是字母表上的某些符号串集合,在这集合中的每个符号串都是按一定规则生成的。其规则最常用的是重写规则(又称产生式),它是形如或:=或(,)的有序对,(读作定义为或 由组成),其中称为规则的左部,称为规则的右部。,定义 2.12 文法G定义为四元组
7、(Vn,Vt,P,S)。 其中: Vn为非终结符号(或语法实体,或变量)集; Vt为终结符号集; P为产生式(也称规则)的集合; S称作识别符号或开始符号。它是一个非终结符,至少要在一条规则中作为左部出现。 Vn,Vt和P是非空有穷集, 显然:Vn和Vt不含公共的元素,即VnVt = 定义 2.13 用V表示VnVt。V称为文法G的字汇表。,例:文法G=(Vn,Vt,P,S) 其中 : Vn=S, Vt=0,l, P=S 0 ,S1 , S0 S ,S1 S , S=S。 该文法刻划的是无符号二进制整数。 上述文法可(通过约定)简单表示为: GS: S 0 S1 S0 S S1 S 进而可(通
8、过引入“|” )简单表示为:(巴科斯范式 BNF) GS: S 0 |1 |0 S | 1 S,例:刻划整数的文法: G =(Vn, Vt,P,S) 其中: Vn=, Vt=+,-,0,1,2,3,4,5,6,7 ,8,9 P= + | | 0 |1 |2 | 3 |4 |5 |6 |7 |8 |9 S=,例:能被5整除的整数文法: G=(Vn, Vt,P,S) 其中: Vn=,, Vt=+,-,0,1,2,3,4,5,6,7,8,9 P= + | | 0 |1 |2 | 3 |4 |5 |6 |7 |8 |9 | 0 |5 S=,约定: 1:用尖括号括起的是非终结符,不用尖括号括起来的是终结
9、符号;或者用大写字母表示非终结符号,小写字母表示终结符号 2:可用GZ指出识别符号;如果文法G没有明确指出识别符号,将第一条产生式的左部的非终结符号称为识别符号 3:如果A1,A2,A3, A 4 , Ak是所有以A为左部的产生式(称它们为A的产生式),可以写成A1|2|3|4|k,称1,2,3,4,k 为A的选择(或候选式).,例:| +|- | 0|1|2|3|4|5|6|7|8|9 定义 2.14 设G是一文法,如果对于符号串2,,1, 1,2v*能写出1=1A2,2=12且A 是G中的一条规则,则说符号串1 直接推导到2 ,或说,2是1的直接推导(一步推导),或说,2归约到1,记作1=
10、2,例:设有文法G: | +|- | 0|1|2|3|4|5|6|7|8|9 试推导出2012 = =2=20=201=2012,定义 2.15 若文法G存在直接推导的序列 V=0=1=2=3=4=n=W(n0) 则称V推导出W, 或称W归约到V,记作V=+=W, 其中n为推导的步数,也称推导长度,称V +推导出W。 例:=+=2012 定义 2.16 如果对于符号串V和W有V=+=W或V=W 即(n0)则记作V=*=W,称V *推导出W. 例: 对文法G有: =*=2006 例: 对文法G有: =*=,定义2.17 设GS是一文法, 若V*且有S=*=,则称为文法GS的一个句型; 若Vt*且
11、有S=+= ,则称为GS的一个句子。 可见句子是句型的特例 例: 设有文法G: | 0|1|2|3|4|5|6|7|8|9 显然0000、2012、1234、都是G文法的句型 ,其中0000、2012、1234是G的句子.而 3、 不是句型(因为它们不能从开始符号推导出),定义 2.18 文法G所产生的语言定义为: L(G)=|S=+=且Vt*。 定义 2.19 若L(G1)= L(G2),则称G1,G2是等价的 例:设 G1: | 0|1|2|3|4|5|6|7|8|9 设G2): 0| 1| 2| 3| 4| 5| 6| 7| 8| 9 |0|1|2|3|4|5|6|7|8|9 则L( G
12、1)= L( G2),由此可以看出,语言是该文法描述的全部句子的集合。 换言之,一个语言是在某特定字母表上按一定的规则构成的符号串集合。,文法提供了三个要点。 1在语言的设计和编译器的编写方面,文法都提供了极大的优点. 2文法给出了精确的,也于理解的语言语法说明 设计得漂亮的文法,把结构加于程序设计语言,这些结构对把源程序翻译成真正的目标代码和错误诊断都是有用的。 3语言也是逐步完善的,需要补充新的结构和完成附加任务。如果存在以语法为基础的语言的实现,这些新结构的加入就更方便了。,语言的特征: 1一种语言需借助于另一种语言(元语言)来描述 2语法是以有穷的方式来描述潜在无穷句子集合的手段 3语
13、法上的正确不能保证语义上的正确,2.1. 推导与递归 定义 2.20 如果每次推导最左非终结符称最左推导,记为=L= 定义 2.21 如果每次推导最右非终结符称最右推导,最右推导又称为规范推导,记为=R=,由最右推导得出的句型称为右句型又称规范句型,递归规则与递归文法 由于语言通常是无穷的而文法是有限的,用有限的文法定义无穷的语言就必须使用递归定义。 递归规则 若文法中存在规则 AA 这种左部和右部具有相同的非终结符号的规则称为直接递归规则或称递归规则。 若AA,即为左递归规则; 若AA,即为右递归规则; 若AA(、),即为自嵌套规则。 这种递归称为直接递归或规则递归,递归文法 有时文法中不含
14、有直接的递归规则,但通过若干推导仍能得到递归,这种递归称为间接递归或文法递归. 含有递归的文法被称为递归文法。 如: AB BA 则A=B= A,2.1.4 文法的分类 形式语言自1956年乔姆斯基(Chomsky)进行描述以来,得到了很大的发展。乔姆斯基从理论上讨论了语言和文法,按照文法规则的不同定义形式进行分类,并且为每一语言构造象自动机一样的识别器。形式语言的理论形成和发展对计算机科学有着深刻的影响,特别是对程序设计语言的设计技术、编译实现都有重大影响。 乔姆斯基把文法分成四种类型,即0型、1型、2型和3型文法。 1. 设文法G=(Vn,Vt,P,S)如果P中的每条规则为如下形式:,uv
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 方法 马知行曹启君 机械 工业出版社 原理 演示 文稿
链接地址:https://www.31doc.com/p-3459107.html