编译原理-第二章形式语言基础.ppt

《编译原理-第二章形式语言基础.ppt》由会员分享，可在线阅读，更多相关《编译原理-第二章形式语言基础.ppt（244页珍藏版）》请在三一办公上搜索。

1、1,编 译 原 理Compiler Principles,徐小龙南京邮电大学.计算机学院,第二章 形式语言基础知识,教材：编译技术原理及其实现方法王汝传 编著,2,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 三、语法树2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,2.4 语法分析初步 一、自顶向下语法分析 二、自底向上语法分析2.5 文法

2、和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法2.6 文法其他表示法 一、扩充巴科斯范式 二、语法图,3,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 三、语法树2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,2.4 语法分析初步 一、自顶向下语法分析 二、自底向上语法分析2.5 文法和语言分类 一、文法分类 二、文法和自动机 三

3、、压缩过文法2.6 文法其他表示法 一、扩充巴科斯范式 二、语法图,4,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法,5,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法,6,2.1 引言 一、形式语言提出 形式语言是研究符号的语言，它仅考虑符号间的关系，不考虑含义即用数学方法（主要是代数方法）对语言进行形式化描述。语言非形式描述：人们交流思想的工具。从语言学本身来说也是一门古老的科学，但是在很早以前人们就用数学方法开始对语言学进行研究。1847年，俄国数学家布拉库夫斯基就用概率论进行语法词源及语言历史比较研究。1904年，波兰语言学家指

4、出，语言学家不仅要掌握初等数学而且还要掌握高等数学。1931年，俄国数学家就用概率论研究俄语元音字母和辅音字母序列。1946年电子计算机问世以来更加促使数学和语言学结合研究。,7,2.1 引言 一、形式语言提出,1956年N.Chomsky(乔姆斯基）在研究自然语言过程中提出一种文法数学模型，为形式语言理论打下了基础，成为计算机科学理论一个重要分支，即形式语言与自动机。为什么要提出形式语言呢？1.控制论出现，促使对语言的深入研究 2.用计算机进行科技文献检索，自动作文摘要及其它信息处理时 要求将自然语言转换成一定形式的信息。3.在计算机上从一种自然语言翻译成另一种自然语言也需要对 语言进行形式

5、描述，以便机器对其分析和综合。4.计算机编译理论、人工智能、数据库等需要对语言进行形式 描述。,8,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法,9,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法,10,2.1 引言 二、语言描述方法无论是自然语言或者是程序设计语言，都是由许多句子组成，当然这些句子是由本语言字母表上符号并按照一定规则组成的符号串。对一个语言的描述，就是如何刻画一个语言中哪些句子是属于该语言的句子，哪些句子是不属于该语言的句子。,11,2.1 引言 二、语言描述方法我们可以用三种方法来描述语言，枚举法、文法生成法和自动机

6、识别法：1.枚举法：如果一个语言仅含有有限个句子，就可以采用枚举法来描述此语言，即把语言中全部句子一一列举出来即可。然而，绝大多数重要语言都有无穷多个语句，因此枚举法显然失效。2.文法生成法：就是用有限个规则来产生出语言中无限个句子，这种规则集合称文法。3.自动机识别法：用自动机对语言中的句子进行识别，自动机是描述离散变量的一个系统（数学模型），因在形式语言中称为识别器，也可看成是一个识别程序。不同语言对应不同自动机，对应某个语言的自动机能接受该语言句子，否则不接受。,下面我们着重讨论用文法生成法来描述语言。,12,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法2.

7、2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 三、语法树2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,2.4 语法分析初步 一、自顶向下语法分析 二、自底向上语法分析2.5 文法和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法2.6 文法其他表示法 一、扩充巴科斯范式 二、语法图,13,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法2.2 用文法生成法对语言进行描述 一、巴科斯范

8、式 二、语法和语义 三、语法树2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,2.4 语法分析初步 一、自顶向下语法分析 二、自底向上语法分析2.5 文法和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法2.6 文法其他表示法 一、扩充巴科斯范式 二、语法图,14,第二章 形式语言基础知识,2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树,15,第二章 形式语言基础知识,2.2

9、用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树,16,2.2 用文法生成法对语言进行描述 一、巴科斯范式 BNF-Backus Normal Form例子：The big elephant ate the peanut.(大象吃花生）The little boy ran quickly.(小男孩跑得快）The man has a dog.(这人有一条狗）以上都是符合英语语法规则的句子，即它们是在英语语法规则中成立 的句子。如何描述一个给定的句子在给定规则下是否成立呢？我们以“=”符号(或“”符号)表示”定义为”，以“|”符号表示“或”，以“”符号表示

10、语法实体(语法单位)，这些符号是元语言符号，,17,句子=主语谓语主语=冠词形容词名词冠词=the 形容词=big谓语=动词宾语 动词=ate 宾语=冠词名词 名词=elephant|peanut 我们把这种描述语法规则方法称巴科斯范式，也称 巴科斯-瑙尔范式(Backus Normal Form)，简称BNF。,那么上面叙述的语法规则可写为：,18,步骤 推导 所用规则1 谓语 2 形容词 名词 谓语 3 the 形容词 名词 谓语 4 the big 名词 谓语 5 the big elephant 谓语 6 the big elephant 动词 7 the big elephant a

11、te 8 the big elephant ate 冠词 9 the big elephant ate the 10 the big elephant ate the peanut 可见句子the big elephant ate the peanut成立。当然我们还可以推导出其它的句子，如the big peanut ate the elephant，在这里，我们只考虑句子的语法，而不考虑句子的语义。,根据以上规则，可以推导出句子The big elephant ate the peanut.过程如下：,19,巴科斯范式是描述语法规则一种表示方法,它是由巴科斯为了在ALGOL60报告中来 描

12、述ALGOL语言首先提出的。采用这种形式体系方式定义语法规则,可以用简洁的公式把各种语法规则严格而清晰描述出来。例如,在高级语言中大家所熟知的标识符这种语法成分,它用巴科斯范式描述为:标识符=字母|标识符字母|标识符数字而字母=A|B|C|D|Z数字=0|1|2|9这样便刻画出了标识符是以字母开始的一串字母和数字任意组合这种特点。,20,用巴科斯范式描述语言能给研究问题带来很大方便。如下面9个句子都是正确的：We ran He ran I ran We ate He ate I ateWe sat He sat I sat如果我们用巴科斯范式来描述上面9个句子只要几条规则就行了。句子=主语谓语

13、主语=We|He|I 谓语=ran|ate|sat可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际意义.它用一组规则来代替枚举法，用有穷来描述无限。,21,第二章 形式语言基础知识,2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树,22,第二章 形式语言基础知识,2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树,23,2.2 用文法生成法对语言进行描述 二、语法和语义 1.语法 用类似巴科斯范式来描述某种语言，称为该语言的语法（也称文法）。实际上语法是在字母表上构造句子的一组规则。

14、对于自然语言就是造句的规则；对于程序设计语言就是书写程序规则。,24,2.2 用文法生成法对语言进行描述 二、语法和语义 2.语义 语义是按照语法规则所构成结构的含义。对于自然语言，语义是所要表达的意思；对于程序设计语言，语义是一个程序所要完成工作，或者某个语法成分的含义。显然，一个句子语法上正确不等于语义上也是正确的。例如，“The big peanut ate the elephant”在语法上是正确，在语义上是荒谬的。在PASCAL语言中，标识符以字母开头是语法，而标识符使用必须加以说明则是语义。对于语法目前研究比较成熟，可以进行形式描述，但对语义的描述还没能 形式化，还得借助于自然语言

15、。,25,编译程序如何将源程序变成目标程序？第一：就是语法分析，看源程序是否符合该语言的语法关系第二：就是语义分析，根据该语言语义生成目标代码这是两个核心问题。,2.2 用文法生成法对语言进行描述 二、语法和语义,26,第二章 形式语言基础知识,2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树,27,第二章 形式语言基础知识,2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树,28,2.2 用文法生成法对语言进行描述 三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以

16、图解（树）形式来描述句子语法结构关系，称语法树。,29,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子the man has a book的推导过程及对应的语法树,30,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子the man has a book的推导过程及对应的语法树,31,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子the ma

17、n has a book的推导过程及对应的语法树,32,the,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子the man has a book的推导过程及对应的语法树,33,man,the,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子the man has a book的推导过程及对应的语法树,34,man,the,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子

18、语法结构关系，称语法树。句子the man has a book的推导过程及对应的语法树,35,man,has,the,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子the man has a book的推导过程及对应的语法树,36,man,has,the,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子the man has a book的推导过程及对应的语法树,37,man,has,a,the,三、语法树 除了上面可以根据

19、语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子the man has a book的推导过程及对应的语法树,38,man,has,a,book,the,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子the man has a book的推导过程及对应的语法树,39,man,has,a,book,the,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。句子the man ha

20、s a book的推导过程及对应的语法树,其中：称为语法树根 带和不带的都称为语法树的结点 一个结点以及向下射出部分称为子树 没有向下射出部分的结点称为末端结点,40,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 三、语法树2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,2.4 语法分析初步 一、自顶向下语法分析 二、自底向上语法分析2.5

21、文法和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法2.6 文法其他表示法 一、扩充巴科斯范式 二、语法图,41,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 三、语法树2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,2.4 语法分析初步 一、自顶向下语法分析 二、自底向上语法分析2.5 文法和语言分类 一、文法分类 二、文法和自动

22、机 三、压缩过文法2.6 文法其他表示法 一、扩充巴科斯范式 二、语法图,42,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,43,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,44,2.3 形式语言基本概念和术语 一、元语

23、言 1.元语言 2.元语言变量,45,2.3 形式语言基本概念和术语 一、元语言 1.元语言 2.元语言变量,46,2.3 形式语言基本概念和术语 一、元语言 1.元语言与编译有关的形式语言基本概念和术语：用来描述其它语言的语言，称元语言。被描述语言称对象语言。例如：英语教科书中，英语是对象语言，汉语是元语言。元语言与被描述语言可以是相同的，也可以是不同的。,47,2.3 形式语言基本概念和术语 一、元语言 1.元语言 2.元语言变量,48,2.3 形式语言基本概念和术语 一、元语言 1.元语言 2.元语言变量,49,2.3 形式语言基本概念和术语 一、元语言 2.元语言变量 元语言的词汇称为

24、元语言的变量(或元语言的符号)。例如：在上一节中描述句子，我们用了等，这些符号的引入完全是为了描述英语句子the big elephant ate the peanut.而这些引入符号并为出现在句子中，对于这种用尖括号括起来的词汇就是元语言变量或语法单位。,50,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,51,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推

25、导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,52,2.3 形式语言基本概念和术语 二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算,53,2.3 形式语言基本概念和术语 二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算,54,2.3 形式语言基本概念和术语 二、符号和符号串 1.字母表 有限个元素的非空集合称字母表，也称符号集。它是组成一个语言最基本的成分。字母表中元素称符号。习惯上用V、或其它大写字母表示。例如V=a,b,c，V=,

26、等都是字母表。|V|表示字母表中符号的个数。对于不同程序设计语言有不同字母表。例如，机器语言字母表=0,1，PASCAL语言的字母表由字母、数字以及一些特殊符号，如+，-，*，/，(，)，=，等组成。注意：在一个语言中不能出现字母表以外的符号。,55,2.3 形式语言基本概念和术语 二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算,56,2.3 形式语言基本概念和术语 二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算,57,2.3 形式语言基本概念和术语 二、符号和符号串 2.符号串（1）定义 符号串是字母表中的符号所组成的任

27、何有穷序列(有时也称为符号 行或字)例如：设V=a,b,c,则符号串有 a,b,c,aa,ab,ac,ba,abc 又如：设V=0,1,则符号串有 0，1，00，01，10，11，000 由上例可以看出，符号串与符号组成顺序有关，如符号串ab不同于ba，符号串01不同于10，今后我们常用t,u,v,x,y,z等小写字母表示符号串。（2）空符号串 不包含任何符号的符号串称为空符号串，记为。（3）符号串长度 符号串中所含符号个数称为该符号串的长度，设符 号串为x，则用|x|来表示x的长度。例如：x=abc，则|x|=3,显然,|=0。,58,2.3 形式语言基本概念和术语 二、符号和符号串 1.字

28、母表 2.符号串 3.行集合 4.关于行集合V*上几种运算,59,2.3 形式语言基本概念和术语 二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算,60,2.3 形式语言基本概念和术语 二、符号和符号串 3.行集合 字母表V上各种长度符号串构成行集合，记为V*，不包括空行的 集合记为V+即 V*=x|x是V上符号串且包括空符号串 V+=x|x是V上符号串且不包括空符号串 V+=V*-如：V=a,b，则 V*=,a,b,aa,ab,ba,bb,aaa,bbb,V+=a,b,aa,ab,ba,bb,aaa,bbb,61,2.3 形式语言基本概念和术语 二、符号和符

29、号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算,62,2.3 形式语言基本概念和术语 二、符号和符号串 1.字母表 2.符号串 3.行集合 4.关于行集合V*上几种运算,63,2.3 形式语言基本概念和术语 二、符号和符号串 4.关于行集合V*上几种运算（1）联结 设有符号串x和y，则它们的联结xy是将符号串y直接拼接在符号串x之后，即 x=x1x2x3xm,y=y1y2y3yn 则 x y=x1x2x3xmy1y2y3yn 显然x=x，x=x,64,（2）行集合乘积设A和B为两个符号串集合，并包含于V*，则A和B的乘积定义为 AB=xy|xA 且 yB 由此定义，乘积

30、AB是满足xA且yB的所有符号串xy所组成的集合。如：V=0，1 V*=,0,1,00,01,10,11,000,001，010，011，100,101 如果 A=0，101 B=10，11，110则 AB=010，011，0110，10110，10111，101110,65,（3）符号串的方幂 若XV*，是符号串 则X0=，X1=X，X2=XX，X3=XXX，Xn=XXX(n个）如X=abc 则X0=,X1=abc,X2=abcabc X3=abcabcabc（4）符号串集合的方幂设符号串集合A V*则A0=,A1=A,A2=AA,A3=AAA,An=AAAA(n个）如：设A=a,b，则A0

31、=,A1=a,b，A2=a,ba,b=aa,ab,ba,bbA3=aaa,aab,aba,abb,baa,bab,bba,bbb,66,(5)闭包和正闭包 设A为符号串集合，则A的正闭包定义为 A+=A1A2An 符号串集合A的闭包定义为 A*=A0A+=A+如 A=a,b 则 A+=a,baa,ab,ba,bb=a,b,aa,ab,ba,bb,aaa,bbb,A*=,a,b,aa,ab,ba,bb,aaa,bbb,我们可以证明：A+=AA*=A*A AA*=A（A0A1A2 An）=A1A2 An=A+,67,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四

32、、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,68,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,69,2.3 形式语言基本概念和术语 三、产生式（规则）1.定义 2.字汇表,70,2.3 形式语言基本概念和术语 三、产生式（规则）1.定义 2.字汇表,71,2.3 形式语言基本概念和术语 三、产生式（规

33、则）1.定义 产生式(规则)就是一个符号与另一个符号串的有序偶(U,x),通常记为 Ux或U=x 其中：U是符号,x是有限非空符号串。U称为规则的左部,x称为规则的右部 如果 Ux1，Ux2，Ux3，Uxn 可以写成Ux1|x2|xn,并称xi是U的一个候选式。,72,2.3 形式语言基本概念和术语 三、产生式（规则）1.定义 2.字汇表,73,2.3 形式语言基本概念和术语 三、产生式（规则）1.定义 2.字汇表,74,2.3 形式语言基本概念和术语 三、产生式（规则）2.字汇表,（1）定义 用于规则左部和右部中所有符号形成集合为字汇表，记为V。,75,（2）分类 1）非终结符号 出现在规则

34、左部,且能派生出符号或符号串的那些符号称为非终结符,也称语法实体或语法单位,它们的全体构成一个非终结符的集合,记为VN 2）终结符 规则中不属于VN的那些符号,称为终结符,它们的全体组成终结符的集合,记为VT。终结符一般出现在规则的右部。显然,V=VN VT,VN VT=,76,如：在PASCAL中，对标识符的定义规则为：标识符=|字母=a|b|z数字=0|1|9 由此得：VN=字母,数字,标识符 VT=a,b,z,0,1,9,（2）分类,77,例如：有产生式:S=0S1 S=01 则 VN=S VT=0,1 V=S,0,1,（2）分类,78,2.3 形式语言基本概念和术语 一、元语言 二、符

35、号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,79,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,80,2.3 形式语言基本概念和术语 四、文法 为研究方便，下面给出文法的形式定义定义：文法是规则的有穷集合,形式定义为四元组形式为 G=(VN,VT,P,Z)其中：VN是非终

36、结符集合,VT是终结符集合,P代表产生式集,ZVN是文法G开始符号,也称识别符号,它至少要在一 条产生式左部出现。文法G通常记为GZ。,81,对于前面例子中用8条文法规则来描述英语句子,其文法可表示为 G=(VN,VT,P,Z)其中:VN=，,VT=the,big,elephant,peanut,ate P是前述8条规则Z=句子,2.3 形式语言基本概念和术语 四、文法,82,又例如：标识符文法可定义如下:GZ=(VN,VT,P,Z)VN=字母,数字,标识符 VT=a,b,z,0,1,9 P由下列规则组成:标识符=|字母=a|b|z 数字=0|1|9 Z=标识符,2.3 形式语言基本概念和术语

37、 四、文法,83,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,84,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,85,2.3 形式语言基本概念和术语 五、推导和归约 定义1 设G为一个文法，U=u是G中一个规则，x和y是

38、V*上符号串，使 v=xUy 与 w=xuy则称符号串v直接推导出符号串w，或称w直接归约到v，并把w叫做v直接派生式，记作 v w 注意三点：1）v，w是两个不同符号串 2）有一规则U=u 3）直接推导v w 若x=y=，则v=xUy=U，w=xuy=u 可见v w即U u 说明一个规则就是一个直接推导例如句子直接推导到，而直接归约到。,86,例如:G=(VN,VT,P,S)VN=S,VT=0,1 P:S=0S1 S=01 S=Z 令 v=xSy,w=x01y,因 S=01(U=u)即 v w xSy x01y 若 x=y=则 S 01(一个规则就是一个直接推导)同样 S=0S1 v=00S

39、11，w=000S111 U u 即 v w 00S11 000S111,2.3 形式语言基本概念和术语 五、推导和归约,87,又如：标识符文法定义如下:GZ=(VN,VT,P,Z)VN=字母,数字,标识符 VT=a,b,z,0,1,9 P由下列规则组成:标识符=|字母=a|b|z 数字=0|1|9 Z=标识符则有：标识符 a,从v出发应用规则U=u,把v=xUy中U替换为右部u,即v直接推导到w,这时长度可能增加,至少不会缩小:|w|v|。从w出发应用规则U=u,把w=xuy中u替换为左部U,即w直接归约为v,这时长度可能缩小,至少不会变:|v|w|。,88,定义2 设u0,u1,u2,un

40、均为V*上符号串,若w是v经过一系列直接推导得到的,即 v=u0 u1 u2 un-1 un=w(n0)则称v推导到w,或称w归约到v,记作 v+w称这个直接推导序列为长度为n的推导。如果v+w或者v=w(表示0步推导),则记作 v*w称v广义推导到w或称w广义归约到v。显然,直接推导 的长度为1,推导+的长度1,而广义推导*的长度0 例如在前面的例子中,因 S=0S1 S=01 0S1 00S11 000S111 00001111所以 0S1+00001111(n=3),89,例 设有文法G整数:(1)=(2)=(3)=(4)=0(5)=1(6)=2(7)=3(8)=4(9)=5(10)=6

41、(11)=7(12)=8(13)=9 V w X U y x u y 整数 数字串 规则1 规则2 数字 数字 规则3 数字 数字 2 数字 规则6 2 数字 2 3 规则7由此建立下列推导:2 23因此,+23,其推导长度为5。显而易见,在推导时,任意地选取规则(4)到(13),就可以推导得到任意整数。,90,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,91,2.3 形式语言基本概念和术语 一、元语言 二

42、、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,92,2.3 形式语言基本概念和术语 六、句型和句子在上述推导过程中产生了一系列的符号串，它们或全由终结符组成（如：23），或全由非终结符组成（如：，），或由终结符和非终结符混合组成（如：2）。为了区别这些组成不同的符号串，我们引入句型和句子两个概念。定义：设GZ是一文法,若符号串x是由识别符Z推导而得,即 Z*x xV*则称符号串x为该文法G的一个句型。如果一个句型x仅由终结符组成,即 Z*x xVT*则称

43、句型x为该文法一个句子。例如在例2.16中,整数,数字数字,2数字,23等都是文法G的句型,其中仅23是句子。,可见：句子一定是句型，而句型未必是句子。一个正确的源程序是句子。,93,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,94,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推

44、导和最右推导 十一、文法二义性,第二章 形式语言基础知识,95,2.3 形式语言基本概念和术语 七、语言设GZ为一文法,由该文法所产生的一切句子的集合称为由该文法所定义的语言,记为L(G)(或记为L(G),即 L(G)=x|Z*x且xVT*有时我们称这样定义的语言为形式语言，以区别于自然语言。上述公式包含两层意思：语言是句子集合，是VT*一个子集合，即VT中行集合子集。句子必须有该语言文法识别符推出。例如：GZ=(VN,VT,P,S)VN=S VT=0,1 P:S=01,S=0S1 S:识别符很容易推出：L（G）=0n1n|n1,96,又如：写一个文法，使其语言为偶整数集合。首先分析以下偶整数

45、（1）偶整数最后一个数字应该是偶数字0，2，4，6，8（2）偶整数前面符号可以是+，-或不带符号由此得其文法应由下列规则组成：=|=0|2|4|6|8=1|3|5|7|9|=|=+|-所以文法可表示为：G=(VN,VT,P,)其中：VN=，VT=0，1，2，3，4，5，6，7，8，9，+，-,97,对于通常的程序设计语言其文法为:G程序=(VN,VT,P,程序)其中 VN=程序,说明,语句,VT=0,1,9,a,z,-,(,),P=,说明=,语句=,L(G)=w|程序*w且wVT*由此可知,每一个w就是一个源程序，所谓PASCAL语言也就是所有PASCAL程序的集合。,98,2.3 形式语言基

46、本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,99,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,100,2.3 形式语言基本概念和术语 八、递归文法构成一个语言的句子集合可以是有穷的，也可以是无穷的，例如文法G句子所描述的语言L(G句子)是

47、有穷的，仅包含8个句子。但文法G整数所描述的语言L(G整数)是无穷的，它包含无穷多个句子，不难发现，两个文法其根本差别在于文法G整数有形如数字串=数字串数字的规则。在这个规则中左部和右部皆出现非终结符数字串。这种借助于自己来定义自己的规则，即在规则左部和右部具有相同的非终结符规则称为递归规则。,101,2.3 形式语言基本概念和术语 八、递归文法 1.定义 2.说明,102,2.3 形式语言基本概念和术语 八、递归文法 1.定义 2.说明,103,2.3 形式语言基本概念和术语 八、递归文法 1.定义 对于一个文法,若有一个规则U=U,则称直接递归,若有规则U=U,则称直接左递归,若有规则U=

48、U,则称直接右递归。若有推导式U+U,则称间接递归,若有推导式U+U,则称间接左递归,若有推导式U+U,则称间接右递归。非终结符U称递归非终结符。如果一个文法中至少含有一个递归非终结符,则将此文法称为递归文法。,例如：规则 S=0S1 是直接递归 规则 A=Aa 是直接左递归 规则 B=aBB 是直接右递归,104,例如：设有文法G的规则P为 S=Qc|c Q=Rb|b R=Sa|a在这6条规则中,无直接递归规则,但有如下推导:Q Rb Sab Qcab所以 Q+Qcab因此是间接左递归。显然，直接递归是间接递归一种特殊情况。,105,2.3 形式语言基本概念和术语 八、递归文法 1.定义 2

49、.说明,106,2.3 形式语言基本概念和术语 八、递归文法 1.定义 2.说明,107,2.3 形式语言基本概念和术语 八、递归文法 2.说明 如果一个语言是无穷的，则描述该语言的文法必定是 递归的。一般说，程序设计语言是无穷的，因此描述 它们的文法必定是递归的。应当指出，从语法定义上 角度来看，递归定义使文法的形式比较简练，给无限 的语言有限的表示提供了一种可用的方法。然而在后 面我们将会看到，文法的左递归性将会给某些语法分 析方法的实现带来很大的麻烦。,108,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语

50、言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,109,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则）四、文法 五、推导和归约 六、句型和句子 七、语言 八、递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,110,2.3 形式语言基本概念和术语 九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树,111,2.3 形式语言基本概念和术语 九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树,112,2.3 形式语言基本概念和术