资源描述：
《编译原理第二章课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章形式语言与自动机理论基础主要内容：语言文法有限自动机正则表达式1自然语言（NaturalLanguage）是人类在社会生活中发展起来的，用于日常相互交流的符号系统。形式语言（FormalLanguage）是为了特定应用而设计的人工语言，形式语言是用精确的数学或机器可处理的公式定义的语言，公式由人们公认的数学和逻辑符号组成。2.1语言和文法2语法和语义一个程序设计语言是一个记号系统，它的完整定义包括语法和语义两个方面。语法（Grammar）是一组规则，用它可以产生一个与其所包含的符号含义无关的合法程序,语法是语言
2、的形式。语义(Semantic)是语言的内容，以语法为媒介来说明语义是语言的实质。本章目的形式语言的基础知识。2.1语言和文法2.132.1基本概念1.字母表（alphabet)字母表是元素的非空有穷集合,字母表中的一个元素称为该字母表的一个字母（letter）,也可叫做符号（symbol）或者字符(character)。注意：字母表具有非空性和有穷性。字母表有时也称为符号表,通常用∑表示。2.1语言和文法42.符号串由字母表中的符号组成的任何有穷序列称为字母表上的符号串。符号串还可以称为“字符串”、“字”或“句子”
3、，一般用，，….，x，y，z，…表示。或表示空串。对任一字母表∑，都有(或)是∑上的符号串。空串集{}不同于空集。∑={a，b，c，d}符号串又可定义如下：1.空符号串ε是上的符号串；2.若x是上的符号串,a是的元素,则xa是上的符号串；3.y是上的符号串,当且仅当它可以由1和2导出。2.1语言和文法853.符号串长度符号串中字符的个数。用
4、
5、表示符号串的长度。
6、
7、=0;只有当两个符号串长度相等且相应位置的符号均相同时，这两个符号串才是相等的。2.1语言和文法64.符号串连接设和均
8、是字母表∑上的符号串，和的连接是把的所有符号顺次地接在的所有符号之后所得到的符号串。记为:。例如:设=abc,=de,则和的连接:=abcde
9、
10、=
11、
12、+
13、
14、。由于是不包含任何符号的字符串，特别有：==连接运算不满足交换律。2.1语言和文法75.符号串的方幂设x是字母表∑上的符号串，把x自身连接n次得到的符号串z,即z=xx…xx(n个x),称作符号串x的n次幂，记作z=xn。根据定义有：x0=x1=xx2=xxx3=x2x=xx2=xxx……xn=xn-1x=xxn-1
15、=xx…xx(n个x)例2.1设x=001，则有:x0=εx1=001x2=001001x3=00100100186.符号串前缀和后缀设x是某一字母表上的符号串，x=yz,则y是x的前缀，z是x的后缀，特别是当z≠时，y是x的真前缀；y≠ε时，z是x的真后缀。例:设x=abc,则:前缀真前缀后缀真后缀x=abcabcx=abcabcx=abcabcx=abcabc2.1语言和文法97.子字符串一个非空字符串x,同时删去它的一个前缀和一个后缀后所得到的字符串称为x的子字符串，简称子串。如果删去
16、的前缀和后缀不同时为ε,则称该子串为真子串。例如:设x=abc,其子串为:abc,ab,a,,bc,c,b。真子串为:ab,a,,bc,b,c。注意:ac并不是x的子串。2.1语言和文法10当对符号串z=xy的头感兴趣而对其余部分不感兴趣时，采用省略写法：z=x…如果只是为了强调x在符号串z中的某处出现，则可表示为：z=…x…2.1语言和文法118.符号串集的乘积设A、B是两个符号串集合，AB表示A与B的乘积，具体定义为：AB={xy
17、(x∈A)∧(y∈B)},运算结果仍然表示符号串的集合。例2.3设A={a,b
18、c}，B={de,f},则：AB={ade,af,bcde,bcf}特别有：1、A=A=，其中表示空集。2、{}A=A{}=A2.1基本概念129.符号串集合的方幂设A为符号串的集合，则称Ａi为符号串集Ａ的方幂。具体定义如下：Ａ０＝{}Ａ1＝AＡ2＝AA……Ａn＝Ａn-1A＝AAA……A(n个）例：Ａ＝{a,b}则：Ａ0＝{}Ａ1＝{a,b}Ａ2＝AA＝{aa,ab,ba,bb}Ａ3＝A2A＝{aaa,aab,aba,abb,baa,bab,bba,bbb}……Ａn＝Ａn-1A＝AAA……A2.1基本
19、概念1310.符号串集合的正闭包设A为符号串的集合，则称Ａ＋为符号串集Ａ的正闭包．具体定义如下：Ａ＋＝Ａ1∪A2∪A3∪……∪AN2.1基本概念1411.符号串集合的星闭包设A为符号串的集合，则称Ａ＊为符号串集Ａ的星闭包．具体定义如下：Ａ＊＝A0∪Ａ1∪A2∪A3∪……∪AN注意:Ａ＋＝AＡ＊2.1基本概念15例:设A={ab,cd}，则:A+
