《形式语言概述》PPT课件

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

1、第二章　形式语言概述本章学习目标形式语言由Chomsky于1956年提出，主要讨论语言和文法的数学机制以及语言和文法的分类。形式语言的形成和发展，对编译原理和技术产生了重要的影响。本章主要内容是:文法和语言的形式定义文法的分类句型的分析和语法树字母表字母表是元素的非空有穷集合，字母表中的元素称为符号，因此字母表也称为符号表。高级语言如C语言的字母表是由字母、数字、特殊符号和一些专用符号构成。字母表可以用表示例：={a,b}，={0,1}，={0,1，2，3，4，5，6，7，8，9}，∑={a,b,c,…z,i

2、f,then,else,main,1,2,3,4,…,9,0,=,==,>,<,;（，）}2.1.2符号串（1）符号语言中最基本的不可再分的单位（2）符号串符号串是由字母表中的符号所组成的有穷序列。符号串由小写x,y,z表示例：某个字母表∑={a,b,c,…z,if,then,else,main,1,2,3,4,…,9,0,=,==,>,<,;}，则建立在∑上的符号串有：if(2+3==5)thena=6elseb=8;空串是不含任何符号的串，记作ε（3）符号串的长度符号串x中所包含的符号的个数称为符号串x的长度，记

3、为

4、x

5、。例：字母表{0，1}，则

6、010110

7、=6。空串的长度为0。（4）子字符串设有非空符号串u=xvy，其中x、v、y是符号串，且v≠ε，则称v为符号串u的子符号串。例：设字母表Σ={a，b，c，d，+，-，*，/，(，)}上有符号串x=a+b*(c+d)，则a、a+b*与（c+d）等都是x的子符号串，且其长度分别为∣a∣=1、∣a+b*∣=4与∣(c+d)∣=5（5）符号串的头和尾如果z=xy是一个符号串，则x是z的头,而y是z的尾。如果y非空，则x是z的固有头，又称为真前缀；若x非空，则y是z的固有尾，又

8、称为真后缀。例假设字母表={a,b,c}上的符号串z=abc，则ε、a、ab、abc都是z的头，且除abc外都是z的固有头；ε、c、bc、abc都是z的尾，且除abc外都是z的固有尾。若只对符号串的头部感兴趣，记做z=x…。若只对尾部感兴趣，则记为z=…x。符号串的运算连接（乘积）运算设x与y是同一个字母表上的两个符号串，把y的各个符号相继写在x的符号后所得到的符号串称为x与y的连接，记为xy。例：设在字母表{a,b,c}上有符号串x=ab与y=cba，则z=xy=abcba。这里∣x∣=2,∣y∣=3,∣z∣=5

9、。对于字母表上的任何符号串x，都有εx=xε=x注：xy!=yx符号串的方幂设x是某个字母表上的符号串，把x自身连接n次，即z=xx…x（n个x），称为符号串x的n次方幂，记为z=xn。例:x=abx3=ababab2.1.3符号串集合符号串集合集合A中一切元素都是某字母表∑上的符号串，则称A是该字母表∑上的符号串的集合。字母表上的符号串的集合通常用大写字母来A、B、C、…表示。例：设某个字母表{a,b,c,d},符号串集合A，BA={a,bc},B={abc,cd,ab}乘积两个符号串集合A和B的乘积AB定义为AB

10、={xy∣x∈A，且y∈B}例:设A={a,b}，B={c,d,e}则AB={ac,ad,ae,bc,bd,be}对于任何空集合Φ，都有ΦA=AΦ=A方幂类似于符号串的方幂，可以定义符号串集合的方幂，特别地定义字母表A的方幂为：A0={ε}，A1=A，An=An-1A(n>0)符号串集合的运算字母表的闭包与正闭包的运算闭包设有字母表A，A的闭包定义如下：A*=A0∪A1∪A2∪…∪An∪…,其中，An（n=0，1，2，3，…）中所有的符号串的长度为n，因此字母表A的闭包A*为字母表上一切长度为n的符号串所组成的集合。

11、注：闭包可以看作由A上符号组成的所有串的集合（包括空串）正闭包如果不允许包含空串ε，则得到字母表A的正闭包。A的正闭包A+=A1∪A2∪…∪An∪…注：正闭包可以看作由A上符号组成的所有串的集合（不包括空串）语言字母表上按照某种规则形成的某个符号串的集合，所以，语言是该字母表上正闭包的子集例：设字母表Σ={a,b,c},依次写出长度为1、2、3…的符号串，可得到Σ的正闭包Σ+：Σ+={a,b,c,aa,ab,ac,bb,bc,aaa,aab,aac,abb,abc,baa,…}在Σ+上添入空串ε即得Σ*。2.2文法的

12、定义及其分类什么是文法?描述语言的语法结构的形式规则，严格地定义句子的结构，用适当条数的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。<句子>::=<主语><谓语><主语>::=<代词>

13、<名词><代词>::=我

14、你

15、他<谓语>::=<动词><直接宾语><动词>::=是

16、学习<直接宾语>::=<代词>

17、<名词>我是大学生的推