程序语言的基本知识.ppt
《程序语言的基本知识.ppt》由会员分享,可在线阅读,更多相关《程序语言的基本知识.ppt(70页珍藏版)》请在三一办公上搜索。
1、编 译 原 理,杭州电子科技大学,2023/11/16,2,第 2 章 程序语言的基本知识,符号串的集合文法和语言分析树和二义性形式语言概观,2023/11/16,3,2.1 符号串的集合,字母表,字母表是符号的非空有穷集合,用 表示,符号:可以相互区别的记号(元素),不同的语言有不同的字母表英语26个英文字母Pascal语言 AZ,az,09,+,-,*,/,:,;,.,(,),2023/11/16,4,2.1 符号串的集合,符号串,符号串是由字母表中的符号所组成的有穷序列,例如:=a,b 则 a,b,aa,ab,aabba都是上的符号串是任何上的符号串,在语言理论中,符号串又称为:句子、字
2、,2023/11/16,5,2.1 符号串的集合,符号串的长度符号串中包含符号的个数符号串 s 的长度记为|s|,例,对于字母表a,b,c,aab 是其上的一个符号串,|aab|=3 注意:空符号串,|=0,2023/11/16,6,2.1 符号串的集合,符号串的前缀、后缀、子串,后缀:删去符号串 s 头部的零个或多于零个符号得到的符号串,前缀:移走符号串 s 尾部的零个或多于零个符号得到的符号串,2023/11/16,7,2.1 符号串的集合,符号串的真前缀、真后缀和真子串非空,子串:从 s 中删去一个前缀和一个后缀得到的符号串,*对于每个符号串s,s 和两者都是符号串 s 的前缀、后缀和子
3、串,2023/11/16,8,2.1 符号串的集合,符号串的运算:连接:符号串、的连接,是把 的符号写在 的符号之后得到的符号串,如=ab,=cd 则=abcd 注:=,方幂:符号串自身连接 n 次得到的符号串,n 定义为 n 个1=,2=,注:0=,2023/11/16,9,2.1 符号串的集合,例:汉语所有符合汉语语法的句子构成的集合 PASCAL语言所有合法的 PASCAL 程序构成的集合,注意:空集、和 的不同,语言,某个字母表上的符号串的集合,2023/11/16,10,2.1 符号串的集合,语言的运算:,语言是符号串的集合,集合的运算有并、交、差等,并运算 等同于集合的并运算,20
4、23/11/16,11,2.1 符号串的集合,连接两个符号串集合 L 和 M 的乘积定义为:LM=st|s L 且 t M,例如:集合 A=ab,cde B=0,1 则 AB=ab1,ab0,cde0,cde1,L=L=L L L L=Ln L0=,2023/11/16,12,2.1 符号串的集合,*闭包(Kleene 闭包)L*=L0L1L2L3,+闭包(正闭包)L+=L1L2L3L*=L+,2023/11/16,13,2.1 符号串的集合,注意:后面通常是考虑字母表的*闭包和+闭包,例:=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa
5、,aab,2023/11/16,14,2.1 符号串的集合,综合性的例子:P10 例2.1 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/11/16,15,2.2 文法和语言,如何来描述一种语言?,如果语言是有穷的(只含有有穷多个句子),可以将句子逐一列出来表示,如果语言是无穷的,找出语言的有穷表示。,2023/11/16,16,2.2 文法和语言,语言有穷表示的两个途经,*文法即是以生成方式描述语言的,生成方式,语言中的每个句子可以用严格定义的规
6、则来构造,2023/11/16,17,2.2 文法和语言,*自动机即是以识别方式描述语言的,识别方式,用一个过程,当输入的一任意串属于语言时,该过程经有限次计算后就会停止并回答“是”,若不属于,要么能停止并回答“不是”,(要么永远运行下去),2023/11/16,18,2.2 文法和语言,一个自然语言的例子,规则(文法),句子 主语 谓语(1)主语 冠词 形容词 名词(2)冠词the 形容词 grey 谓语 动词 直接宾语(5)动词 助动词 动词原形(6)助动词will 动词原形 eat 直接宾语 冠词 名词(9)名词wolf 名词 goat,2023/11/16,19,句子 主语 谓语 冠词
7、 形容词 名词 谓语 the 形容词 名词 谓语 the grey名词 谓语 the grey wolf 谓语 the grey wolf 动词 直接宾语.the grey wolf will eat the goat,句子可根据规则推导(生成)出来:,The grey wolf will eat the goat,分析句子,2023/11/16,20,谓语,主语,冠词,形容词,名词,动词,直接宾语,句子,The grey wolf will eat the goat,2023/11/16,21,2.2 文法和语言,文法 G,VT,VN,S,P,终结符号集,非终结符号集,开始符号,产生式集合,
8、文法的形式定义,2023/11/16,22,终结符号集 VT,代表语言中不可再分的基本符号,如汉语中的汉字、PASCAL语言中的基本字,其中的元素一般用小写字母或数字表示(a,b,c,0,1),2.2 文法和语言,2023/11/16,23,非终结符号集 VN,代表语法单位,如汉语中的语句、段落,PASCAL语言中的语句、表达式、子程序等,其中的元素一般用大写字母表示(A,B,C),或者用尖括号括起一个串来表示,2.2 文法和语言,2023/11/16,24,开始符号 S,是一个特殊的非终结符号,代表最高级的语法单位,S 至少要在一条产生式中作为左部出现,2.2 文法和语言,2023/11/1
9、6,25,产生式集合 P,2.2 文法和语言,产生式(重写规则、生成式),是形如或=的(,)有序对,且V+,V*,其中 V=(VTVN)称为产生式的左部,不能为空称为产生式的右部,可以为空(如:A),2023/11/16,26,2.2 文法和语言,例1:文法 G=(VT,VN,S,P)VN=S VT=0,1 P=S0S1,S01,可以只写出产生式,通过产生式可以得到文法的其它部分,左部相同的产生式可以写在一起,如:S 0S1|01,2023/11/16,27,2.2 文法和语言,例2:文法 G=(VT,VN,S,P)VN=,VT=a,b,c,x,y,z,0,1,9P=a,z 0,9 S=,20
10、23/11/16,28,2.2 文法和语言,推 导,直接推导,直接归约,归 约,如果 A 是 G 的一条产生式,则称用代替A为一步直接推导,记为A,2023/11/16,29,2.2 文法和语言,推导是用产生式的右部代替左部,归约是用产生式的左部代替右部,归约是推导的逆过程,直接推导,直接归约,用A代替为一步直接归约,记为=A,2023/11/16,30,2.2 文法和语言,推导的长度直接推导的次数,长度大于等于 1 的推导,长度大于等于 0 的推导,推导的例子:S 0S1 00S11 000111,长度为 3 记为:S 000111 S S,2023/11/16,31,2.2 文法和语言,最
11、左推导,最右推导,对中的最左非终结符进行展开,对中的最右非终结符进行展开,2023/11/16,32,2.2 文法和语言,例子:表达式文法 E E+T E T T T*F T F F(E)F a,最左推导:E T T*F F*F a*F a*a,*最右推导又称为规范推导,最右推导:E T T*F T*a F*a a*a,2023/11/16,33,2.2 文法和语言,最右归约,最左归约,最左推导的逆过程是最右归约,即对最右边的可归约串进行归约,最右推导的逆过程是最左归约,即对最左边的可归约串进行归约,a*a=a*F=F*F=T*F=T=E,a*a=F*a=T*a=T*F=T=E,*最左归约称为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 程序语言 基本知识
链接地址:https://www.31ppt.com/p-6596250.html