《形式语言基础》PPT课件.ppt
《《形式语言基础》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《形式语言基础》PPT课件.ppt(19页珍藏版)》请在三一办公上搜索。
1、编译程序的设计原理与实现,如何让计算机认识、理解 和 执行 高级程序设计语言?,第 2 章 形式语言基础,计算机处理语言,首先应考虑语言的形式化、规范化,使其具有可计算性和可操作性;这就是形式语言理论研究的问题。形式语言诞生于1956年,由chomsky创立。通常,语言研究至少涉及三个方面:语法、语义和语用;这里仅侧重于语法的研究。,形式语言的基本观点是:语言是符号串之集合!,形式语言理论研究的基本问题是:,研究符号串集合的表示方法、结构特性,以及运算规律。,【前 言】,【内容提要】,第 2 章 形式语言基础,2.1 形式语言是符号串集合 2.2 形式语言是由文法定义的 2.3 主要语法成分的
2、定义 2.4 两类特性文法 2.5 文法变换方法 2.6 关于形式语言的分类问题,字母表-元素(符号)的非空有限集合;符号串-符号的有限序列;符号串集合-有限个或者无限个符号串组成的集合;规 则-以某种形式表达的在一定范围内共同遵守的章程和制度;这里,指符号串的组成规则。,2.1 形式语言是符号串集合,【形式语言】是字母表上的符号,按一定的规则组成的所有符号串集合;其中的每个符号串称为句子。,【名词解释】:,三要素!,【例2.1】L1=00,01,10,11;字母表1=0,1,句子有:00,01,10,11,【注】b0=(epsilon空符号串),b1=b,b2=bb,b3=bbb,L1 为有
3、限语言;L2 为无限语言。,形式语言概念示例:,【例2.2】L2=abmc,bn|m0,n0 字母表2=a,b,c,句型1:abmc,有句子:abc,abbc,abbbc,句型2:bn;有句子:,b,bb,bbb,两个语言!,1.连接:.=如 a.b=ab,2.1.1 符号串(集合)的运算,3.方幂:n=n-1=n-1,4.闭包:,n个,.符号串的运算,设,为两个符号串,则:,的正闭包:+=1|2|n|,的星闭包:*=0|1|2|n|,0=(空符号串)什麽符号也没有的符号串!,1=;2=;,2.或:|=(或者),这是一种泛指!,2.1.1 符号串(集合)的运算(续1),【例】:,ab|cd=a
4、b(或者 cd),abc.de=abcde,(a|b)1=(a|b)=a|b,(a|b)*=(a|b)0|(a|b)1|(a|b)2|,(a|b)2=(a|b)(a|b)=aa|ab|ba|bb,即:(a|b)*=(a|b)n,n0,同理:(a|b)+=(a|b)n,n0,符号串运算示例,泛指:由a,b组成的任意符号串!(包括空串),1.乘积:AB=xy|xA 且 yB,2.1.1 符号串(集合)的运算(续2),4.闭包:A 的正闭包:A+=A1A2AnA 的星闭包:A*=A0A1A2An,设 A 和 B 为两个符号串集合,则:,3.方幂:An=AAA=AAn-1=An-1A,n个,A0=;,
5、A1=A;A2=AA;A3=AAA;,.符号串集合的运算,符号串集合运算示例:,【例2.3】设 A=a,b,B=c,d 则 A+B=a,b,c,d 则 AB=xy|xA,yB=ac,ad,bc,bd,【例2.4】设 A=a 则 A*=A0A1A2An=+a+aa+aaa+=,a,aa,aaa,=an|n0,【例2.5】设 A=a,b,A*=?A*=A0A1A2An A0=;A1=A=a,b;A2=A.A=a,b.a,b=aa,ab,ba,bb;A3=A.A2=a,b.aa,ab,ba,bb=aaa,aab,aba,abb,baa,bab,bba,bbb;A*=x|x=(a|b)n,n0,符号串
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言基础 形式语言 基础 PPT 课件
链接地址:https://www.31ppt.com/p-5507624.html