文法和形式语言

《文法和形式语言》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、（二）文法和形式语言程序设计语言与形式语言基本概念文法文法和语言分类正则表达式和正则集9/2/20211一、程序设计语言与形式语言1。程序设计语言：生成系统：文法识别系统：自动机2。语法、语义、语用语法：涉及语言的构成规律，即程序的结构或形式语义：语言所代表的含义。语用：语言的实际应用9/2/202123。形式化方法与形式化语言形式化方法：使用一整套有严格规定的符号体系来描述问题的理论和方法。形式化语言：一种不考虑含义的符号语言。形式化语言理论主要研究组成这种符号串的集合、它们的表示方法、结构及特性。形式化

2、语言只涉及符号的结构方式上的规定，不涉及符号的含义。一、程序设计语言与形式语言（续）9/2/20213二、基本概念1。字母表和符号串字母表:一个非空的有穷集合.V={0,1}符号:字母表中的元素称为符号或字符符号串:符号的有穷序列称为符号串.eg.字母表={a,b,c,d}则有符号串:a,b,c,d,aa,ddd,acc…注意:表示空符号串,它表示不包含任何符号串.不是空格符.符号串中的符号是有顺序的.符号串集合:字母表上若干个符号串组成的集合.A={ab,acc,da,a};约定:小写字母a,b,…,

3、r表示符号.小写字母:s,t,…,z表示字符串;大写字母:A,B,..,Z表示字符串集合;9/2/202142.符号串的运算符号串相等：符号串x，y，如果两者诸符号依次相等，则两符号相等。符号串的长度：符号串中包含符号的个数。

4、abc

5、=3；

6、

7、=0；符号串的连结：x，y是字母表上的两个字符串，把y的所有符号相继写在x的符号之后所得到的符号串称为x与y的连结，用xy表示。X=abc，y=def则xy=abcdef；yx=defabc；xyyxx=x=x；符号串的逆:设x是字母表上的符号串，其逆为符号串

8、x的倒置，记为x。x=abcd；x=dcba；二、基本概念（续一）~~9/2/20215符号串的前缀、后缀和子串：设x，y，z是字母表上的符号串，则称x为符号串xy的前缀，y是符号串xy的后缀，z是符号串xzy的子串。前缀后、缀是特殊的子串。符号串集合的乘积：设A、B为两个符号串集合，其乘积为AB={xy

9、xA，yB}；eg：A={aa，bb}，B={cc，dd}则AB={aacc，aadd，bbcc，bbdd}{}A=A{}=A；空集：不含任何元素的集合称为空集。记为；对任何集合A：A=A

10、=;注意：二、基本概念（续二）9/2/20216符号串的幂：x是字母表上的符号串，则x的幂运算为：x0=;x1=x;x2=xx;…xn=xn-1x=xxn-1(n>0)xn表示n个x相连结。eg：x=ok；则x0=;x1=ok;x2=okok;…xn=okok…ok(n个ok连结）符号串集合的幂：A为符号串集合，则符号串集合A的幂运算为：A0={};A1=A;A2=AA;...An=An-1A=AAn-1;(n>0)A={aa，bb}，则A0={}；A1={aa，bb}；A2=AA={aaa

11、a，aabb，bbaa，bbbb};...二、基本概念（续三）9/2/20217符号串集合的闭包和正闭包集合A的闭包表示为A*（亦称为自反闭包或星闭包）具体定义为：A*=A0A1A2A3…=Ak正闭包表示为A+，具体定义为A+=A1A2A3…=Ak由定义可以看到A*=A0A+二、基本概念（续四）k1k09/2/202183、语言定义:给出字母表,则上任一字符串集合,称为上的一个语言,记为L,该语言的每一个字符串便是语言L的一个语句或句子.eg:设={a,b,c}则L={a,a

12、a,ab,aaa,aab,aba,abb,…}为上的一个语言,如果a表示字母,b表示数字,c看作其它符号,则L通常是程序语言中的标识符集.其中每个标识符便是标识符集的一个句子.由有限个字符串组成的集合为有穷语言,反之为无穷语言.显然L*二、基本概念（续五）9/2/20219三、文法1。引例〈句子〉〈冠词〉〈动词〉〈名词〉〈宾语〉〈冠词〉〈名词〉carmandrovethethe句子themandrovethecar的结构〈主语〉〈谓语〉9/2/202110引例(续)上图中用尖括号<>括起来的称为语法成

13、分或语法类(绿色表示)。其余的称为单词符号或单词（用红色表示）图中包括下列描述句子结构的规则：1〈句子〉——〉〈主语〉〈谓语〉2〈主语〉——〉〈冠词〉〈名词〉3〈谓语〉——〉〈动词〉〈宾语〉4〈宾语〉——〉〈冠词〉〈名词〉5〈冠词〉——〉the6〈名词〉——〉man7〈名词〉——〉car8〈动词〉——〉drove9/2/2021112。文法定义：文法G是一个四元组，G=（VT，VN，S，P），其中VT为终结符号集