《编译概述》PPT课件.ppt
《《编译概述》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《编译概述》PPT课件.ppt(61页珍藏版)》请在三一办公上搜索。
1、2023/7/31,1,Chapter2Grammar and Language,串和语言(Strings and Languages)文法和语言的定义(Definitions of Grammar and Language)文法和语言的分类(Classification of Grammar and Language)分析树与句型(Parse Tree and Sentential form),2023/7/31,2,2.1 串和语言,字母表(alphabet):字母表是符号(symbols)的非空有穷集合,用表示符号:可以相互区别的记号(元素),不同的语言有不同的字母表汉语汉字英语26个英
2、文字母,2023/7/31,3,2.1 串和语言,符号串(String):符号串是由字母表中的符号所组成的有穷序列,在语言理论中,符号串又称为:句子(sentence)、字(word),例如:=a,b a,b,aa,ab,aabba都是上的符号串是任何上的符号串,2023/7/31,4,2.1 串和语言,符号串的长度符号串中包含符号的个数符号串 s 的长度记为|s|,例,对于字母表a,b,c,aab 是其上的一个符号串,|aab|=3注意:空符号串,|=0,2023/7/31,5,2.1 串和语言,符号串的前缀(prefix)、后缀(suffix)、子串(substring),后缀:删去符号串
3、 s 头部的零个或多于零个符号得到的符号串例如:nana是符号串banana的一个后缀,前缀:移走符号串 s 尾部的零个或多于零个符号得到的符号串例如:b是符号串banana的一个前缀,2023/7/31,6,2.1 串和语言,符号串的真(proper)前缀、真后缀和真子串非空,子串:从 s 中删去一个前缀和一个后缀得到的符号串例如:ana是符号串banana的一个子串*对于每个符号串s,s和两者都是符号串 s的前缀,后缀和子串,2023/7/31,7,2.1 串和语言,语言(Language):某个字母表上的符号串的集合,例:汉语所有符合汉语语法的句子构成的集合 PASCAL语言所有合法的P
4、ASCAL程序构成的集合,注意:空集、和的不同,2023/7/31,8,2.1 串和语言,符号串的运算:连接(concatenation):符号串x、y的连接,是把 y 的符号写在 x 的符号之后得到的符号串 xy,如 x=ab,y=cd 则 xy=abcd 注:=,方幂(exponentiation):符号串自身连接n次得到的符号串,n 定义为 n个1=,2=,注:0=,2023/7/31,9,2.1 串和语言,语言的运算(operations on languages):,语言是符号串的集合,集合的运算有并、交、差等,并运算 等同于集合的并运算,2023/7/31,10,2.1 串和语言,
5、连接(乘积)两个符号串集合 A 和 B 的乘积定义为:AB=xy|x A 且 y B,例如:集合A=ab,cde B=0,1 则 AB=ab1,ab0,cde0,cde1,L=L=L LLL=Ln L0=,2023/7/31,11,2.1 串和语言,*闭包(Kleene closure)L*=L0L1L2L3,+闭包(Positive closure)L+=L1L2L3L*=L+,2023/7/31,12,2.1 串和语言,注:后面通常是考虑字母表的*闭包和+闭包例:=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,2023/7/
6、31,13,2.1 串和语言,综合性的例子:P93 example 3.2 L=A,B,C,Z,a,b,c,z D=0,1,9,把 L 和 D 两个字母表看作长度为1的符号串集合,即语言,1.L D 2.LD 3.L4 4.L*5.L(L D)*6.D+,2023/7/31,14,2.2 文法和语言的定义,如何来描述一种语言?,如果语言是有穷的(只含有有穷多个句子),可以将句子逐一列出来表示,如果语言是无穷的,找出语言的有穷表示。,2023/7/31,15,2.2 文法和语言的定义,语言的有穷表示有两个途经:生成方式(文法):语言中的每个句子可以用严格定义的规则来构造。,识别方式(自动机):用
7、一个过程,当输入的一任意串属于语言时,该过程经有限次计算后就会停止并回答“是”,若不属于,要么能停止并回答“不是”,(要么永远继续下去。),文法即是以生成方式描述语言的:语言中的每个句子可以用严格定义的规则来构造.,2023/7/31,16,2.2 文法和语言的定义,文法 G 定义为四元组(VT,VN,S,P):,VT:终结符(terminals)集,其中的元素一般用小写字母或数字表示(a,b,c0,1.),代表语言中不可再分的基本符号,如汉语中的汉字、PASCAL语言中的基本字,VN:非终结符(nonterminals)集,其中的元素一般用大写字母表示(A,B,C),或者用尖括号括起,代表语
8、法单位,如汉语中的语句、段落,PASCAL语言中的语句、表达式、子程序等,2023/7/31,17,2.2 文法和语言的定义,S 是一个特殊的非终结符号,称为开始符号(start symbol)S 至少要在一条产生式中作为左部出现,P是一个产生式(production)的集合产生式(重写规则、生成式),是形如或=的(,)有序对,且V+,V*其中 V=(VTVN)称为产生式的左部,不能为空称为产生式的右部,可以为空(如:A),2023/7/31,18,2.2 文法和语言的定义,例1:文法 G=(VT,VN,S,P)VN=S VT=0,1 P=S0S1,S01,可以只写出产生式,通过产生式可以得到
9、文法的其它部分,左部相同的产生式可以写在一起,如:S 0S1|01,2023/7/31,19,2.2 文法和语言的定义,例2:文法 G=(VT,VN,S,P)VN=,VT=a,b,c,x,y,z,0,1,9P=a,z 0,9 S=,2023/7/31,20,2.2 文法和语言的定义,推导(derivation)与归约(reduction):,直接推导与直接归约如果 A 是 G 的一条产生式,则称用代替A为一步直接推导,记为A=;称用A代替为一步直接归约,记为=A,推导是用产生式的右部代替左部,归约是用产生式的左部代替右部,归约是推导的逆过程,2023/7/31,21,2.2 文法和语言的定义,
10、推导的长度直接推导的次数,长度大于等于1的推导,长度大于等于0的推导,推导的例子:S=0S1=00S11=000111,长度为3 记为:S 000111 S S,2023/7/31,22,2.2 文法和语言的定义,最左推导与最右推导=是一步推导,(VTVN)*最左推导(=lm)对 中的最左非终结符进行展开最右推导(=rm)对 中的最右非终结符进行展开,2023/7/31,23,2.2 文法和语言的定义,例子:表达式文法 E E+T E T T T*F T F F(E)F a,最左推导:E=lmT=lmT*F=lmF*F=lma*F=lma*a,*最右推导又称为规范推导,最右推导:E=rmT=r
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译概述 编译 概述 PPT 课件
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-5590330.html