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

1,编 译 原 理Compiler Principles,徐小龙 南京邮电大学.计算机学院,第二章 形式语言基础知识,教材：编译技术原理及其实现方法王汝传 编著,2,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法 2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 三、语法树 2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,2.4 语法分析初步 一、自顶向下语法分析 二、自底向上语法分析 2.5 文法和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法 2.6 文法其他表示法 一、扩充巴科斯范式 二、语法图,3,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法 2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 三、语法树 2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,2.4 语法分析初步 一、自顶向下语法分析 二、自底向上语法分析 2.5 文法和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法 2.6 文法其他表示法 一、扩充巴科斯范式 二、语法图,4,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法,5,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法,6,2.1 引言 一、形式语言提出 形式语言是研究符号的语言，它仅考虑符号间的关系，不考虑含义 即用数学方法（主要是代数方法）对语言进行形式化描述。 语言非形式描述：人们交流思想的工具。 从语言学本身来说也是一门古老的科学，但是在很早以前人们就用数学方法开始对语言学进行研究。 1847年，俄国数学家布拉库夫斯基就用概率论进行语法词源及语言 历史比较研究。 1904年，波兰语言学家指出，语言学家不仅要掌握初等数学而且还要 掌握高等数学。 1931年，俄国数学家就用概率论研究俄语元音字母和辅音字母序列。 1946年电子计算机问世以来更加促使数学和语言学结合研究。,7,2.1 引言 一、形式语言提出,1956年N.Chomsky(乔姆斯基）在研究自然语言过程中提出一种 文法数学模型，为形式语言理论打下了基础，成为计算机科学理论 一个重要分支，即形式语言与自动机。 为什么要提出形式语言呢？ 1. 控制论出现，促使对语言的深入研究 2. 用计算机进行科技文献检索，自动作文摘要及其它信息处理时 要求将自然语言转换成一定形式的信息。 3. 在计算机上从一种自然语言翻译成另一种自然语言也需要对 语言进行形式描述，以便机器对其分析和综合。 4. 计算机编译理论、人工智能、数据库等需要对语言进行形式 描述。,8,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法,9,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法,10,2.1 引言 二、语言描述方法 无论是自然语言或者是程序设计语言，都是由许多句子组成，当然这些句子是由本语言字母表上符号并按照一定规则组成的符号串。 对一个语言的描述，就是如何刻画一个语言中哪些句子是属于该语言的句子，哪些句子是不属于该语言的句子。,11,2.1 引言 二、语言描述方法 我们可以用三种方法来描述语言，枚举法、文法生成法和自动机识别法： 1. 枚举法 ：如果一个语言仅含有有限个句子，就可以采用枚举法来描述此语言，即把语言中全部句子一一列举出来即可。然而，绝大多数重要语言都有无穷多个语句，因此枚举法显然失效。 2. 文法生成法：就是用有限个规则来产生出语言中无限个句子，这种规则集合称文法。 3. 自动机识别法：用自动机对语言中的句子进行识别，自动机是描述离散变量的一个系统（数学模型），因在形式语言中称为识别器，也可看成是一个识别程序。不同语言对应不同自动机，对应某个语言的自动机能接受该语言句子，否则不接受。,下面我们着重讨论用文法生成法来描述语言。,12,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法 2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 三、语法树 2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,2.4 语法分析初步 一、自顶向下语法分析 二、自底向上语法分析 2.5 文法和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法 2.6 文法其他表示法 一、扩充巴科斯范式 二、语法图,13,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法 2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 三、语法树 2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,2.4 语法分析初步 一、自顶向下语法分析 二、自底向上语法分析 2.5 文法和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法 2.6 文法其他表示法 一、扩充巴科斯范式 二、语法图,14,第二章 形式语言基础知识,2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树,15,第二章 形式语言基础知识,2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 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.(这人有一条狗） 以上都是符合英语语法规则的句子，即它们是在英语语法规则中成立 的句子。 如何描述一个给定的句子在给定规则下是否成立呢？ 我们以“=”符号(或“”符号)表示”定义为”，以“|”符号表示“或”， 以“ ”符号表示语法实体(语法单位)，这些符号是元语言符号，,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 ate 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 报告中来 描述ALGOL语言首先提出的。采用这种形式体系方式定义语法 规则,可以用简洁的公式把各种语法规则严格而清晰描述出来。 例如, 在高级语言中大家所熟知的标识符这种语法成分,它用巴科斯范式 描述为: 标识符=字母|标识符字母|标识符数字 而 字母=A|B|C|D|Z 数字=0|1|2|9 这样便刻画出了标识符是以字母开始的一串字母和数字任意组合 这种特点。,20,用巴科斯范式描述语言能给研究问题带来很大方便。 如下面9个句子都是正确的： We ran He ran I ran We ate He ate I ate We sat He sat I sat 如果我们用巴科斯范式来描述上面9个句子只要几条规则就行了。 句子=主语谓语 主语=We | He | I 谓语=ran | ate | sat 可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际意义.它用一组规则来代替枚举法，用有穷来描述无限。,21,第二章 形式语言基础知识,2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树,22,第二章 形式语言基础知识,2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树,23,2.2 用文法生成法对语言进行描述 二、语法和语义 1.语法 用类似巴科斯范式来描述某种语言，称为该语言的语法（也称文法）。实际上语法是在字母表上构造句子的一组规则。 对于自然语言就是造句的规则； 对于程序设计语言就是书写程序规则。,24,2.2 用文法生成法对语言进行描述 二、语法和语义 2.语义 语义是按照语法规则所构成结构的含义 。 对于自然语言，语义是所要表达的意思；对于程序设计语言，语义是一个程序所要完成工作，或者某个语法成分的含义。显然，一个句子语法 上正确不等于语义上也是正确的。例如，“The big peanut ate the elephant”在语法上是正确，在语义上是荒谬的。 在PASCAL语言中，标识符以字母开头是语法，而标识符使用必须加以 说明则是语义。 对于语法目前研究比较成熟，可以进行形式描述，但对语义的描述还 没能 形式化，还得借助于自然语言。,25,编译程序如何将源程序变成目标程序？ 第一：就是语法分析，看源程序是否符合该语言的语法关系 第二：就是语义分析，根据该语言语义生成目标代码 这是两个核心问题。,2.2 用文法生成法对语言进行描述 二、语法和语义,26,第二章 形式语言基础知识,2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树,27,第二章 形式语言基础知识,2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 1.语法 2.语义 三、语法树,28,2.2 用文法生成法对语言进行描述 三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。,29,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。 句子the man has a book的推导过程及对应的语法树,30,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。 句子the man has a book的推导过程及对应的语法树,31,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。 句子the man has a book的推导过程及对应的语法树,32,the,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。 句子the man has a book的推导过程及对应的语法树,33,man,the,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。 句子the man has a book的推导过程及对应的语法树,34,man,the,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。 句子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,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。 句子the man has a book的推导过程及对应的语法树,38,man,has,a,book,the,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。 句子the man has a book的推导过程及对应的语法树,39,man,has,a,book,the,三、语法树 除了上面可以根据语言语法规则来推导出句子，还可以用图解形式来表示。以图解（树）形式来描述句子语法结构关系，称语法树。 句子the man has a book的推导过程及对应的语法树,其中：称为语法树根 带和不带的都称为语法树的结点 一个结点以及向下射出部分称为子树 没有向下射出部分的结点称为末端结点,40,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法 2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 三、语法树 2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,2.4 语法分析初步 一、自顶向下语法分析 二、自底向上语法分析 2.5 文法和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法 2.6 文法其他表示法 一、扩充巴科斯范式 二、语法图,41,第二章 形式语言基础知识,2.1 引言 一、形式语言提出 二、语言描述方法 2.2 用文法生成法对语言进行描述 一、巴科斯范式 二、语法和语义 三、语法树 2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,2.4 语法分析初步 一、自顶向下语法分析 二、自底向上语法分析 2.5 文法和语言分类 一、文法分类 二、文法和自动机 三、压缩过文法 2.6 文法其他表示法 一、扩充巴科斯范式 二、语法图,42,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,43,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,44,2.3 形式语言基本概念和术语 一、元语言 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. 元语言变量 元语言的词汇称为元语言的变量(或元语言的符号)。 例如：在上一节中描述句子，我们用了等，这些符号的引入完全是为了描述英语句子the big elephant ate the peanut.而这些引入符号并为出现在句子中，对于这种用尖括号括起来的词汇就是元语言变量或语法单位。,50,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,51,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,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=, 等都是字母表。| 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）定义 符号串是字母表中的符号所组成的任何有穷序列(有时也称为符号 行或字) 例如： 设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. 字母表 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 形式语言基本概念和术语 二、符号和符号串 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 由此定义，乘积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=,A1=a,b ，A2=a,ba,b=aa,ab,ba,bb A3=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 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,68,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,69,2.3 形式语言基本概念和术语 三、产生式（规则） 1.定义 2.字汇表,70,2.3 形式语言基本概念和术语 三、产生式（规则） 1.定义 2.字汇表,71,2.3 形式语言基本概念和术语 三、产生式（规则） 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）非终结符号 出现在规则左部,且能派生出符号或符号串的那些符号称为非终结符,也称语法实体或语法单位,它们的全体构成一个非终结符的集合,记为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 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,79,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,80,2.3 形式语言基本概念和术语 四、文法 为研究方便，下面给出文法的形式定义 定义： 文法是规则的有穷集合,形式定义为四元组形式为 G=(VN,VT,P,Z) 其中： VN是非终结符集合,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 形式语言基本概念和术语 四、文法,83,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,84,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,85,2.3 形式语言基本概念和术语 五、推导和归约 定义1 设G为一个文法，U=u是G中一个规则，x和y是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=00S11， 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均为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(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 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,92,2.3 形式语言基本概念和术语 六、句型和句子 在上述推导过程中产生了一系列的符号串，它们或全由终结符组成 （如：23），或全由非终结符组成（如：， ），或由终结符和非终结符混合组成（如： 2）。 为了区别这些组成不同的符号串，我们引入句型和句子两个概念。 定义：设GZ是一文法,若符号串x是由识别符Z推导而得,即 Z *x xV* 则称符号串x为该文法G的一个句型。如果一个句型x仅由终结符组成,即 Z *x xVT* 则称句型x为该文法一个句子。 例如在例2.16中,整数,数字数字,2数字,23等都是 文法G的句型,其中仅23是句子。,可见：句子一定是句型，而句型未必是句子。一个正确的源程序是句子。,93,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,94,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,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,又如：写一个文法，使其语言为偶整数集合。 首先分析以下偶整数 （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 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,99,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,100,2.3 形式语言基本概念和术语 八、递归文法 构成一个语言的句子集合可以是有穷的，也可以是无穷的，例如文法G句子所描述的语言L(G句子)是有穷的，仅包含8个句子。但文法G整数所描述的语言L(G整数)是无穷的，它包含无穷多个句子，不难发现，两个文法其根本差别在于文法 G整数有形如数字串=数字串数字的规则。 在这个规则中左部和右部皆出现非终结符数字串。这种借助于自己来定义自己的规则，即在规则左部和右部具有相同的非终结符规则称为递归规则。,101,2.3 形式语言基本概念和术语 八、 递归文法 1.定义 2.说明,102,2.3 形式语言基本概念和术语 八、 递归文法 1.定义 2.说明,103,2.3 形式语言基本概念和术语 八、递归文法 1. 定义 对于一个文法,若有一个规则U=U,则称直接递归,若有规则U=U,则称直接左递归,若有规则U=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.说明,106,2.3 形式语言基本概念和术语 八、 递归文法 1.定义 2.说明,107,2.3 形式语言基本概念和术语 八、递归文法 2.说明 如果一个语言是无穷的，则描述该语言的文法必定是 递归的。一般说，程序设计语言是无穷的，因此描述 它们的文法必定是递归的。应当指出，从语法定义上 角度来看，递归定义使文法的形式比较简练，给无限 的语言有限的表示提供了一种可用的方法。然而在后 面我们将会看到，文法的左递归性将会给某些语法分 析方法的实现带来很大的麻烦。,108,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,109,2.3 形式语言基本概念和术语 一、元语言 二、符号和符号串 三、产生式（规则） 四、文法 五、推导和归约 六、句型和句子 七、语言 八、 递归文法 九、短语和简单短语 十、最左推导和最右推导 十一、文法二义性,第二章 形式语言基础知识,110,2.3 形式语言基本概念和术语 九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树,111,2.3 形式语言基本概念和术语 九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树,112,2.3 形式语言基本概念和术语 九、短语和简单短语 1. 短语和简单短语 定义：设GZ是一文法，w=xuy是其中一句型，若有 Z *xUy,UVN 且 U +u,uV+ 则称u是一个相对于非终结符U、句型w的短语。 若 Z *xUy 且U u 则称u是一个相对于非终结符U、句型w的简单短语。,113,例2.16 设有文法G整数: (1)= (2)= (3)= (4)=0 (5)=1 (6)=2(7)=3 (8)=4 (9)=5 (10)=6(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,由定义可知： * ， w=2 所以 +2，即2是相对于非终结符句型2 的短语，而* ， w=2 2 所以2是相对于非终结符句型2的简单短语,114,例2.22 设有文法GS=(S,A,B,a,b,P,S),其中P为 S=AB A=Aa|bB B=a|Sb 找出句型baSb的全部短语，简单短语，根据句型推导过程有 S AB bBB baB baSb 由上可见，下式成立： S *baB 且 B Sb 所以子串Sb是相对于非终结符B，句型baSb的简单短语。 同样有 S AB ASb bBSb baSb 即 S *bBSb 且 B a 子串a是相对于B，句型baSb的简单短语。 还有 S *Asb 且 A +ba 即子串ba是相对于非终结符A，句型baSb的短语。 对于句型baSb，再没有其它能产生新的短语推导了，所以句型baSb 有短语ba简单短语a和Sb,115,2.3 形式语言基本概念和术语 九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树,116,2.3 形式语言基本概念和术语 九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树,117,2.3 形式语言基本概念和术语 九、短语和简单短语 2、柄短语 定义 一个句型最左边的简单短语称为该句型 的句柄(或柄短语)，而且句柄最左边的符号 称句柄的头，句柄最右边的符号称句柄的尾。 如上例句型baSb简单短语为a和Sb ，由于a是 最左简单短语，所以a又是句柄。,118,例如：设文法GS S=A A=B|A+B B=C|B*C C=|（A） 现在我们看w=C+B*C句型 SAA+BB+BC+BC+B*C S*C+B BB*C B*C是相对于B句型C+B*C的简单短语 同样 SAA+BB+BB+B*CC+B*C S*B+B*C BC C是相对于B句型C+B*C的简单短语。由于C在左边，所以C是句柄， 柄头和柄尾都是C,119,2.3 形式语言基本概念和术语 九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树,120,2.3 形式语言基本概念和术语 九、短语和简单短语 1.短语和简单短语 2.柄短语 3.再谈语法树,121,2.3 形式语言基本概念和术语 九、短语和简单短语 3. 再谈语法树 前面我们曾利用语法树直观地描述句子语法结构关系，现在我们仍然 借助于语法树进行句型和句子的推导，同时，利用它寻找短语和简单 短语也是十分直观和方便的。 （1）语法树形式定义 设有文法G=（VN，VT，P，Z），满足下列条件的树即为一个语法树 a. 树中每一个结点都有标记，且该标记是VNVT中某一符号 b. 树根标记是识别符号 c. 若有一个结点至少有一个后继结点，则该结点标记必为非终结符 d. 若一个标记为U的结点，它有标记依次为X1，X2，X3，Xn的 直接后继结点，则U=X1X2Xn必定是G的一条规则。,122,S,A,B,b,B,S,b,a,我们以例2.22文法GS为例，句型baSb的推导 设有文法GS=(S,A,B,a,b,P,S),其中P为 S=AB A=Aa|bB B=a|Sb S AB bBB baB baSb 画出语法树如下图所示,123,（2）语法树构造过程 句型baSb的语法树构造过程如下： (1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。,S,124,（2）语法树构造过程 句型baSb的语法树构造过程如下： (1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。,S,A,B,125,（2）语法树构造过程 句型baSb的语法树构造过程如下： (1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。 (2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),A被替换为bB(规则A=bB)。 ,S,A,B,126,（2）语法树构造过程 句型baSb的语法树构造过程如下： (1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。 (2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),A被替换为bB(规则A=bB)。,S,A,B,b,B,127,（2）语法树构造过程 句型baSb的语法树构造过程如下： (1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。 (2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),A被替换为bB(规则A=bB)。 (3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB),其中B被替换成a(规则B=a)。,S,A,B,b,B,128,（2）语法树构造过程 句型baSb的语法树构造过程如下： (1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。 (2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),A被替换为bB(规则A=bB)。 (3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB),其中B被替换成a(规则B=a)。,S,A,B,b,B,a,129,（2）语法树构造过程 句型baSb的语法树构造过程如下： (1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。 (2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),A被替换为bB(规则A=bB)。 (3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB),其中B被替换成a(规则B=a)。 (4)最后由句型baB中标记B的结点向下画分支,表示最后一个推导(baBbaSb),其中B被替换成Sb(规则B=Sb)。,S,A,B,b,B,a,130,（2）语法树构造过程 句型baSb的语法树构造过程如下： (1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。 (2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),A被替换为bB(规则A=bB)。 (3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB),其中B被替换成a(规则B=a)。 (4)最后由句型baB中标记B的结点向下画分支,表示最后一个推导(baBbaSb),其中B被替换成Sb(规则B=Sb)。,S,A,B,b,B,S,b,a,131,（2）语法树构造过程 句型baSb的语法树构造过程如下： (1)从识别符号S开始,向下画一分支,表示第一个直接推导(SAB),S被替换为AB(规则S=AB)。 (2)从分支结点A出发,向下画一分支,表示第二个直接推导(ABbBB),A被替换为bB(规则A=bB)。 (3)再由分支A的分支结点B向下画分支,表示第三个直接推导(bBBbaB),其中B被替换成a(规则B=a)。 (4)最后由句型baB中标记B的结点向下画分支,表示最后一个推导(baBbaSb),其中B被替换成Sb(规则B=Sb)。,S,A,B,b,B,S,b,a,这时末端结点自左至右排列起来就是句型baSb。这棵语法树形象地表示了句型baSb上述推导过程。,132,结论： 对于每一个语法树（或者子树）至少对应一个推导（可能是直接推导。可能是n步推导） 对于每个推导必存在有一个