资源描述：
《第三讲文法和语言ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三讲 文法和语言本章学习目标形式语言由Chomsky于1956年提出，主要讨论语言和文法的数学机制以及语言和文法的分类。形式语言的形成和发展，对编译原理和技术产生了重要的影响。本章主要内容是:文法和语言的形式定义文法的分类句型的分析和语法树文法的直观概念问题：当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，如何给出它的有穷表示？解决方法：以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构。比如汉语句子可以是由主语后
2、随谓语而成，构成谓语的是动词和直接宾语，我们采用BNF来表示这种句子的构成规则：语法规则：“句子由主语后跟随谓语组成”表示为：句子主语谓语<句子>::=<主语><谓语><主语>::=<代词>
3、<名词><代词>::=我
4、你
5、他<名词>::=王明
6、大学生
7、工人
8、英语<谓语>::=<动词><直接宾语><动词>::=是
9、学习<直接宾语>::=<代词>
10、<名词>我是大学生的推导过程：<句子>=><主语><谓语>=><代词><谓语>=>我<谓语>=>我<动词><直接宾语>=>我是<直接宾语>=>我是<名词>=>我是大学生文法描述语言的语法结构的形式规则，严
11、格地定义句子的结构，用适当条数的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。符号和符号串字母表是元素的非空有穷集合，字母表中的元素称为符号，因此字母表也称为符号表。高级语言如C语言的字母表是由字母、数字、特殊符号和一些专用符号构成。字母表可以用表示例：={a,b}，={0,1}，={0,1，2，3，4，5，6，7，8，9}，∑={a,b,c,…z,if,then,else,main,1,2,3,4,…,9,0,=,==,>,<,;（，）}符号串（1）符号语言中最基本的不可再分的单位（2）符号串符号串是由字母表中的符号所组成的有穷
12、序列。符号串由小写x,y,z表示例：某个字母表∑={a,b,c}，则建立在∑上的符号串有：a,b,c,ab,aaca空串是不含任何符号的串，记作ε（3）符号串的长度符号串x中所包含的符号的个数称为符号串x的长度，记为
13、x
14、。例：字母表{0，1}，则
15、010110
16、=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*∣
17、=4与∣(c+d)∣=5（5）符号串的头和尾如果z=xy是一个符号串，则x是z的头,而y是z的尾。如果y非空，则x是z的固有头，又称为真前缀；若x非空，则y是z的固有尾，又称为真后缀。例:假设字母表={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的连接，
18、记为xy。例：设在字母表{a,b,c}上有符号串x=ab与y=cba，则z=xy=abcba。这里∣x∣=2,∣y∣=3,∣z∣=5。对于字母表上的任何符号串x，都有εx=xε=x注：xy!=yx符号串的方幂设x是某个字母表上的符号串，把x自身连接n次，即z=xx…x（n个x），称为符号串x的n次方幂，记为z=xn。例:x=abx3=ababab符号串集合符号串集合集合A中一切元素都是某字母表∑上的符号串，则称A是该字母表∑上的符号串的集合。字母表上的符号串的集合通常用大写字母来A、B、C、…表示。例：设某个字母表{a,b,c,d},符号串集合A，BA={a
19、,bc},B={abc,cd,ab}乘积两个符号串集合A和B的乘积AB定义为AB={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，…）因此字母表A的闭包A*为字母表上一切有穷长度的符号串所
20、组成的集合。注：闭包可以看作由A上符号组成的所有串的
