编译原理PPT第二章形式语言基础课件.ppt

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

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

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

3、示例：【例2.2】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.1.1符

15、号串(集合)的运算(续1)【例】：⑵ab

16、cd=ab（或者cd）⑴abc.de=abcde⑶(a

17、b)1=(a

18、b)=a

19、b(a

20、b)*=(a

21、b)0

22、(a

23、b)1

24、(a

25、b)2

26、…(a

27、b)2=(a

28、b)(a

29、b)=aa

30、ab

31、ba

32、bb…即：(a

33、b)*=(a

34、b)n，n≥0同理：(a

35、b)+=(a

36、b)n，n＞0※符号串运算示例泛指：由a，b组成的任意符号串！（包括空串）1.乘积：AB={xy

37、xA且yB}2.1.1符号串(集合)的运算(续2)4.闭包：A的正闭包：A+=A1∪A2∪…∪An∪…A的星闭包：A*=A0∪A1∪A2∪…∪An∪…设A和B为两个符号串集合，

38、则：2.和：A∪B=A+B={x

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

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

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

42、，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

43、x=(a

44、b)n，n≥0}符号串集合运算示例(续)：推论：若A为任一字母表,则A*就是该字母表上的所有符号串(包括空串)的集合。⑴S,A—定义的对象(S句子,最大的定义对象，又称为开始符号;A为句型aAc的短语），⑵a,b,c--为字母表∑中的符号;ε-空符号串。⑶->,

45、--为描述符号(->定义为;

46、或者是）2.1.2符号串集合的文法描述【例2.5】L={abnc

47、

48、n≥0}，字母表：∑={a,b,c}；展开：L={ac,abc,abbc,abbbc,…}右图给出的表示S->aAcA->bA

49、长久以来，探讨符号串集合(即形式语言)的各种描述方法，一直是语言计算机处理的重要任务之一。方法 --文法规则；其中：从开始符号出发，对符号串中的定义对象，采用推导的方法（用其规则右部替换左部）产生新的符号串，如此进行，直到新符号串中不再出现定义的对象为止，则最终的符号串就是一个句子。S->aAcA->bA

50、规则应用说明示例：【句子产生过程】(=>推导算符):怎样