形式语言基础1

《形式语言基础1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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为无限语言。形式语言概念示例

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.3】

15、：(2)abc.=.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∪

38、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.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=

42、{};A1=A={a,b};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)使用文法：语言为无

45、穷集合时，无法枚举设有字母表B={0,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、注：此文法实际称为上下文无关文法