《形式语言基础》PPT课件.ppt

《形式语言基础》PPT课件.ppt

ID:51599148

大小:1.49 MB

页数:51页

时间:2020-03-25

《形式语言基础》PPT课件.ppt_第1页
《形式语言基础》PPT课件.ppt_第2页
《形式语言基础》PPT课件.ppt_第3页
《形式语言基础》PPT课件.ppt_第4页
《形式语言基础》PPT课件.ppt_第5页
资源描述:

《《形式语言基础》PPT课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、编译程序的设计原理与实现如何让计算机认识、理解和执行高级程序设计语言?第2章形式语言基础计算机处理语言,首先应考虑语言的形式化、规范化,使其具有可计算性和可操作性;这就是形式语言理论研究的问题。形式语言诞生于1956年,由Chomsky创立。通常,语言研究至少涉及三个方面:语法、语义和语用;※形式语言的基本观点是:语言是符号串之集合!※形式语言理论研究的基本问题是:研究符号串集合的表示方法、结构特性以及运算规律。因此:【内容提要】2.1形式语言是符号串集合2.2形式语言是由文法定义的2.3各种语法成分的定义2.4两类特性文法2.5文法变换方法2.6形式语言的分类第2章形式语

2、言基础字母表--元素(符号)的非空有限集合;符号串--符号的有限序列;符号串集合--有限个或者无限个符号串组成的集合;规则--以某种形式表达的在一定范围内共同遵守的章程和制度;这里,指符号串的组成规则。2.1形式语言是符号串集合【形式语言】是字母表上的符号按一定的规则组成的所有符号串集合;其中的每个符号串称为一个句子。【名词解释】:三要素!【例2.1】L1={00,01,10,11};字母表∑1={0,1},句子有:00,01,10,11【注】(1)b0=(空符号串),b1=b,b2=bb,b3=bbb,…(2)L1为有限语言;L2为无限语言。形式语言概念示例:【例2.2

3、】L2={abmc,bn

4、m>0,n≥0}字母表∑2={a,b,c},句型1:abmc有句子:abc,abbc,abbbc,…句型2:bn有句子:,b,bb,bbb,…两个语言!1.连接:.=如:a.b=ab2.1.1符号串(集合)的运算3.方幂:n=…=n-1=n-14.闭包:n个Ⅰ.符号串的运算设,为两个符号串,则:的正闭包:+=1

5、2

6、…

7、n

8、…的星闭包:*=0

9、1

10、2

11、…

12、n

13、…※0=(空符号串)什么符号也没有的符号串!1=;2=;…2.或:

14、=或者这是一种泛指!【例2.3】:(2)abc.

15、=.abc=abc(1)abc.de=abcde(4)(a

16、b)1=(a

17、b)=a

18、b(a

19、b)*=(a

20、b)0

21、(a

22、b)1

23、(a

24、b)2

25、…(a

26、b)2=(a

27、b)(a

28、b)=aa

29、ab

30、ba

31、bb…即:(a

32、b)*=(a

33、b)n,n≥0同理:(a

34、b)+=(a

35、b)n,n>0※符号串运算示例泛指:由a,b组成的任意符号串!(包括空串)(3)ab

36、cd=ab或者cd1.乘积:AB={xy

37、xA且yB}4.闭包:A的正闭包:A+=A1∪A2∪…∪An∪…A的星闭包:A*=A0∪A1∪A2∪…∪An∪…设A和B为两个符号串集合,则:2.和:A∪B=A+B={x

38、xA

39、或xB}3.方幂:An=AA…A=AAn-1=An-1An个※A0={};A1=A;A2=AA;A3=AAA;…Ⅱ.符号串集合的运算2.1.1符号串(集合)的运算符号串集合运算示例【例2.4】设A={a,b},B={c,d}则A+B={a,b,c,d}则AB={xy

40、xA,yB}={ac,ad,bc,bd}【例2.5】设A={a}则A*=A0∪A1∪A2∪…∪An∪…={}+{a}+{aa}+{aaa}+…={,a,aa,aaa,…}={an

41、n≥0}【例2.6】设A={a,b},A*=?∵A*=A0∪A1∪A2∪…∪An∪…A0={};A1=A={a,b};

42、A2=AA={a,b}{a,b}={aa,ab,ba,bb};A3=AA2={a,b}{aa,ab,ba,bb}={aaa,aab,aba,abb,baa,bab,bba,bbb};…∴A*={x

43、x=(a

44、b)n,n≥0}符号串集合运算示例(续):推论:若A为任一字母表,则A*就是该字母表上的所有符号串(包括空串)的集合。2.2形式语言是由文法定义的形式语言是符号串的集合,对形式语言的描述有两种方式:(1)枚举方式:语言为有穷集合时设有字母表A={a,b,c},有L1={a,aa,ab,ac},L2={c,cc}(2)使用文法:语言为无穷集合时,无法枚举设有字母表B={0

45、,1},B+={0,1,00,10,11,01,000,…}用A表示B+,可以表示为A->0A->1A->A0A->A1文法:用有穷的集合刻画无穷的集合的工具。【定义】文法(grammar)是规则的有限集,通常可以表示为四元组:G(Z)=(VN,VT,Z,P)VN:非终结符集(定义的对象集,如:语法成分等);VT:终结符集(字母表);Z:开始符号(研究范畴中最大的定义对象);P:规则集(又称产生式集);2.2形式语言是由文法定义的每个元素2.2.1什么是文法?Z->或者A->

46、注:此文法实际称为上下文无关文法

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。