《编译原理》第3章 (1)

《《编译原理》第3章 (1)》由会员分享，可在线阅读，更多相关《《编译原理》第3章 (1)（90页珍藏版）》请在金锄头文库上搜索。

1、第三章 文法和语言,2,【学习指南】, 什么是文法,什么是它定义的语言？ 在乔姆斯基（Chomsky）的文法类型中，我们为什么 关注上下文无关文法？ 什么是语法分析？语法分析方法的分类。,【难重点】,关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定义为一个数学系统。“形式“是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。,3,知识体系,推导/归约,凑规则,4,教学内容,字母表与符号串 文法与语言的关系 文法的概念 文法与语言的形式定义 文法构造与文法简化 由语言构造文法的例子 文法的简化 语法树与文法的二义性,5,语言,语言

2、是由句子组成的集合，是由一组记号所构成的集合。 汉语-所有符合汉语语法的句子的全体 英语-所有符合英语语法的句子的全体 程序设计语言-所有该语言的程序的全体 研究语言 ： 每个句子构成的规律 每个句子的含义 每个句子和使用者的关系,6,研究程序设计语言： 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面： 语法 Syntax 语义 Semantics 语用 Pragmatics 语法 - 表示构成语言句子的各个记号之间的组合规律。 语义 - 表示按照各种表示方法所表示的各个记号的特定 含义。（各个记号和记号所表示的对象之间的关系） 语用 -表示在各个记号所出现的行

3、为中，它们的来源、 使用和影响。,7,如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。 形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,形式语言,8,字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，例如: 1.机器语言：由符号“0”和“1”组成的字母表, =0，1 2.ASCII字符集； 3.汉语的字母表中包括汉字、数字及标点符号 4.C字母表为： =AZ, az, 09, +, -, *, /, , :

4、, , ; ，.， , (, ), , , , ,一、字母表,3.1 符号和符号串,9,1.符号 一个抽象实体,我们不再形式地定义它(就象几何中的”点”一样).例如字母是符号,数字也是符号 2.符号串 由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作“字”或“句子”。 (1)不包含任何符号的符号串，称为空符号串简称空串，记为 。 (2) 若=a,b 则a,b,ab,ba,abb,baa.是上的符号串。 在符号串中，符号的顺序是很重要的，符号串ab就不同于ba,abca和aabc也不同。,二、 符号串,10,设z是符号串 长度:是该符号串中的符号的数目。例如|aab|=3

5、,|=0。 前缀(头):删去z尾部的若干个(包括0个)符号所得的。 表示: z=x 后缀(尾):删去z头部的若干个(包括0个)符号所得的。 表示: z=x 真前缀(固有头)x，真后缀(固有尾)x :xz 子串: 从z中删去一个前缀和一个后缀 逆转（用z表示）：将z中的符号按相反次序写出而得到的符号串。,3术语,11,例：符号串z=banana 长度：banana=6 前缀：,b,ba,ban,bana,banan,banana 真前缀: ,b,ba,ban,bana,banan 后缀：banana,anana,nana,ana,na,a, 真后缀: anana,nana,ana,na,a, 子

6、串: banana,anana,banan,anan, 逆转（用z表示）：ananab,12,1.连接：设x和y是符号串，它们的连接 xy是把y的符号写在x的符号之后得到的符号串。 例如，x=ba,y=nana,xy=banana 显然：x=x=x 2.方幂：符号串x自身连接n次得到的。 x0= ; x1=x; x2=xx; ;xn=xn-1x= xxn-1; 例如, x=ba, x1= ba, x2=baba, x3=bababa, xn=(ba)n,三.符号串的运算,13,定义:集合中的一切元素都是某字母表上的符号串。 设A和B是两个符号串集合，则 1. 乘积(连接)：AB xy|xA a

7、nd yB A=ab,bcB=ac,cbAB=abac,abcb,bcac,bccb 2. 合并：ABx|xA or xB AB=ab,bc,ac,cb 3. 空集: A=A=A 4. 方幂：符号串集合的自身乘积。 A0=， A1A， A2AA, ., AnAn-1AAAn-1 A=a,b A0=， A1A=a,b， A2AA=aa,ab,ba,bb A3A2A=AA2=aaa,aab,aba,abb, ,四. 符号串集合(语言）的运算,14,5. 集合A的Kleene闭包(星闭包)，记作A*，字母表A的各次方幂之并。其含义是由A上符号组成的所有串的集合（包括空串) A*Ai(i=0) =A0

8、A1A2A3 A=a,b A*,a,b,aa,ab,ba,bb, aaa,aab,aba,abb, 6集合A的正闭包，记作A+，其含义是由字母表A上的符号组成的所有串(不包括空串)的集合。 A+Ai(i =1) =A1A2A3A4 A=a,b A+a,b,aa,ab,ba,bb, aaa,aab,aba,abb, A* A0 A+ A+ AA*A*A,15,语言是由句子组成的集合，是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合 (字母表上的每个语言是*的一个子集)。 例如：字母表=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, 集合ab,aabb,a

9、aabbb,anbn, 或表示为w|w*且w=anbn,n1 字母表上的一个语言。 集合a,aa,aaa, 或表示为w|w*且w=an,n1 字母表上的一个语言。 是一个语言。 即 是一个语言。,16,给出语言上的有关运算,设L是（上的）一个语言, M是（上的）一个语言, 语言L和M的并，交，差，补是一个语言。 语言L和M的并为 LM: LM=w|wL 或 wM 如： L1 =a,b,y,z M1 =1,28,9 L1M1=a,b, y,z，1,28,9 语言L和M的连接为 LM:LM=st |sL且tM 如： L1M1 =a1,b1,y1,z1,a2,b2a9z9 有L = L=L。 L的n

10、次连接Ln= LL.L 如： L12 =aa,ab,az,ba,bb, bz, ,za,zbzz,17,语言L的闭包记为 L*， L*= L0 L1 L2 . L0= ， Ln= L Ln-1= Ln-1 L,n1 语言L的正闭包记为 L+， L+= L1 L2 L3 . L+= LL*= L*L L*= L+ 如： L1 =a,b,y,z M1 =1,28,9 （L1M1）=a,b, y,z，1,28,9 （L1M1）*=a,b, y,z，1,28,9 ，aa,1a,xyz,6789st L1（L1M1）*=所有字母打头的字母和数字符号串,18,例如：L=AZ,az D=09 1LD是由所有

11、一个字母后跟一个数字组成的符号串所构成的集合。 2LD=AZ,az ,09 3.L4是由所有的四个字母的符号串构成的集合。 4L（LD)* 是由所有的字母打头的字母和数字组成的符号串所构成的集合。 5D+是由所有长度大于等于1的数字串所构成的集合。,如何来描述一种语言？ (1)枚举法 例:1,11,111,1111 (2)自然语言 (3)省略表示法 例:1,11,111, (4)描述法 例:1i|i0,19,如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示； 如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经： 生成方式 （文法）：语言中的每个句子可以用严格定义的规

12、则来构造。 识别方式（自动机）：是使用自动机的行为描述语言：它的行为相当于一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）,20,文法即是生成方式描述语言的： 语言中的每个句子可以用严格定义的规则来构造。 下面给出文法的定义.进而在文法的定义的基础 上,给出推导的概念,句型、句子和语言的定义。,21,3.2 文法和语言的形式定义,文法的直观概念和语言概述 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它

13、的有穷表示的问题。 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用BNF来表示这种句子的构成规则：,22,语法规则：“句子由主语后跟随谓语组成”表示为：句子 主语 谓语,句子 主语 谓语 主语 代词 主语 名词 代词我 代词你 代词他 名词王明 名词 大学生 名词工人 名词 英语 谓语 动词 直接宾语 动词 是 动词 学习 直接宾语 代词 名词,一、 引子,23,有了一组规则以后，按照如下方式用它们导出句子：开始去找左端的带有的规则并把它由右端的符号串代替，这

14、个动作表示成： 句子 主语谓语， 然后在得到的串中,选取或,再用相应规则的右端代替之。比如,选取了,并采用规则, 那么得到: ,重复做下去。,句子主语 谓语 代词 谓语 我 谓语 我 动词 直接宾语 我是直接宾语 我是名词 我是大学生,句子根据规则推导出来,24,分析：我是大学生,谓语,主语,代词,动词,直接宾语,句子,大学生,我,是,名词,25,句子 + 我是大学生 英语是工人 大学生是英语 符合语法且符合语义的句子仅是： 我是大学生。 “我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种

15、元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。,句子既要符合语法又要符合语义,26,每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。 语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看， 其一是该句子的创立者所想要表示的意义， 另一是接收者所检验到的意义。 这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。,27,如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。 “形式”是指这样的事实：语言的所有规则只以