编译原理前后文无关文法和语言.ppt

第二章 文法和语言,在20世纪50年代，N.Chomsky首先对语言的描述问题进行了探讨。他提出了一种用来描述语言的数学系统，并以此定义了四类性质不同的语言，称为语言（文法）的Chomsky分类。 人们把用一组数学符号和规则来描述语言的方式称为形式描述，把所用的数学符号和规则称为形式语言。 目前，形式语言与自动机理论已成为计算机科学中的一个重要分支。 本章将初步介绍形式语言中的某些基本概念和知识，重点是与编译技术密切相关的一些术语和概念，诸如文法、语言、句子、句型、短语、句柄以及句型分析等。,本 章 内 容,2.1 语言的概述 2.2 文法和语言的定义,2.1 语言的概述,什么是语言 自然语言(Natural Language) 是人与人的通讯工具 语义(Semantics):环境、背景知识、语气、二义性难以形式化 计算机语言(Computer Language) 计算机系统间、人机间通讯工具 严格的语法(Grammar)、语义(Semantics) 易于形式化：严格 语言是用来交换信息的工具功能性描述,2.1 语言概述,语言的描述方法现状 自然语言：自然、方便-非形式化 数学语言（符号）：严格、准确-形式化 形式化描述 高度的抽象，严格的理论基础和方便的计算机表示。,2.1 语言概述,语言形式化的内容提取 单词(Token)：满足一定规则字符(Character)串 句子(Sentence)：满足一定规则单词序列 语言(Language)：满足一定条件的句子集合 语言是字和组合字的规则结构性描述 例：一译开天第课今始编节上 今天开始上第一节编译课,程序设计语言形式化的内容提取 程序设计语言(Programming Language)：组成 程序的所有语句的集合 程序(Program)：满足语法规则的语句序列 语句(Sentence) ：满足语法规则的单词序列 单词(Token) ：满足词法规则的字符串 例 变量=表达式 if 条件 then 语句 while条件 do 语句 call 过程名(参数表),2.1 语言概述,语言描述形式文法 语法语句 语句的组成规则 描述方法：BNF（巴科斯范式： Backus Normal Form ）范式、语法(描述)图 词法单词 单词的组成规则 描述方法：BNF范式、正规式,2.1 语言概述,遗憾的是，对于自然语言来说，目前尚无能够完全刻划一语言全部句子的结构的方法。 然而，对大多数程序设计语言来说，此问题已被解决。1960年，P.Naur & J.Backus（巴科斯-瑙尔）首先用BNF（Backus-Naur-Formal（范式）对ALGOL语言进行了描述。应指出，BNF成功地解决了程序设计语言的语法描述问题，但描述其语义，还必须借助自然语言。,复习：巴科斯范式 （BNF - Backus Normal Form）,通常，可用如下方式表示或定义一种语言： （1）若语言的句子有限时，可用枚举法。 例如，只含两个句子的语言： “I am a teacher”, “You are students”; （2）制定有限条规则，用于产生所要描述的语言的全部句子（可无限多），这些规则构成了该语言的文法。 （3）建立一种装置（算法或过程），它以某字母表上的符号串为输入，判别该符号串是否为所描述语言的句子。此装置称为自动机。,巴科斯范式 （BNF ）,例子： The big elephant ate the peanut.(大象吃花生） The little boy ran quickly.(小男孩跑得快） The man has a dog.(这人有一条狗） 以上都是符合英语语法规则的句子，即它们是在英语语法规则中成立的句子。 如何描述一个给定的句子在给定规则下是否成立呢？,句子=主语谓语 主语=冠词形容词名词 冠词=the 形容词= big 谓语=动词宾语 动词=ate 宾语=冠词名词 名词=elephant | peanut 我们把这种描述语法规则方法称巴科斯范式，也称巴科斯-瑙尔范式(Backus Normal Form)，简称BNF。,那么上面叙述的语法规则可写为：,步骤 推导 所用规则 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. 过程如下：,用巴科斯范式描述语言能给研究问题带来很大方便。 如下面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 可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际意义.它用一组规则来代替枚举法，用有穷来描述无限。,2.2 文法和语言的定义,本节主要内容 基本概念和术语（字母表，符号串等）； 规则； 文法的定义； 推导； 句型与句子； 文法和语言的等价转换等,2.2.1 基本概念和术语,1。字母表（符号表、符号集） 由若干元素（符号、字母）组成的有限非空集合。 2。符号串 用字母表中符号所组成的任何有限序列。 符号串的长度 = 符号串中所含符号的个数 例：aba的长度为3。记为：|aba|=3 空串 不含任何符号的符号串，记为 。显然，| |= 0。 本课约定 用A、B、C、 等表示字母表或符号串集；用a,b,c,S,T,U 等表示符号；用s,t,u,x,y,z,等表示符号串。 3。符号串的前（后）缀及子串 设,，x是符号串，若x= ，则称是x的子串； 特别地，当= （= ）时，称 是x的前（后）缀。,2.2.1 基本概念和术语,4。符号串的连接和方幂 连接 设x,y是符号串，将y直接地拼接到x之后所得的新符号串称为x与y的连接，记为xy 注意，一般说来，xy 不等于 yx；但 x = x = x 方幂 符号串x与其自身的 n-1次连接称为 x 的 n 次方幂，记为,2.2.1 基本概念和术语,5。符号串集合的和与积 设A，B为两个符号串之集，定义 和 A+B（或A B） = w | w A，或 w B 积 AB（或 AB）= xy |x A, y B 显然， A+ = +A = A ； A = A = ；A = A = A 6。符号串集的方幂与闭包,例 0,1+=0，1，00，01，11，000，001，010，011，100， a，b，c，d+ =a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc,例 0,1*=，0，1，00，01，11，000，001，010，011，100， a，b，c，d*=，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc，,2.2.1 基本概念和术语,当我们把字母（符号）表视为由长度为1的符号串构成的符号串集时，就可定义字母表上的连接、积、方幂等运算。 例 A=a,b,c,2.2.2 文法和语言的形式定义,我们从“产生语言”的角度出发,讨论文法和语言的形式定义。 产生语言 指制定出有限条规则，借助它们就能产生出些语言的句子。 我们以几个英语句子构成的语言为例进行讨论。并设每个句子都是“主-谓-宾”结构。 语法规则见右。其中，每个用括起来的部分是所要定义语言中的一个语法实体（称为语法单位、语法结构、语法范畴、语法变量等）。“:=”是用于定义语法结构的符号，其含义（并读作）“定义为”。 语法规则也称为产生式(Production),: := the := := :=monkey :=banana :=eat :=has := the := a,现在，我们讨论如何用上述规则推导出相应语言的全部句子。 推导：从语言最大的一个语法范畴（本例中是）开始，反复用语法规则中“:=” 右侧的符号串取代其左侧符号，直到所得的符号串中不再含有可被替换语法范畴。每次替换称为一步（直接）推导，并用符号“”表示。 例如，我们首先用规则进行第一步推导(derivation)，就可得到 ，记为： 所得的符号串含有两个语法范畴，可对其中任一个（例如对）进行新的推导（替换）： 重复上述过程，可得到一个推导序列（见下页）。,用语法规则进行推导所得的推导序列,推导步骤 所用规则 所得的符号串 1 2 3 the 4 the 5 the monkey 6 the monkey eat 7 the monkey eat a 8 the monkey eat a banana,2.2.2 文法和语言的形式定义,从前面的推导看，从出发，经8步推导得到了一个英语句子。故前面的推导称为长度为8的推导。 若不关心推导的中间过程，可将从一符号串到另一符号串的推导用记号,规则的简化表示,在前面的语法规则定义中，有些语法范畴（如、）有若干条不同的规则来定义它，为简明起见，我们可以将它们写在同一个左部语法范畴下，将其定义值用符号“|”（读作或）隔开。如、 、 的定义规则可简记为 := monkey | banana := eat | has := the | a,语法规则及其产生的语言,前面的语法规则可以产生16个不同的句子，由这16个句子组成的集合，就是该规则所定义（或所产生）的语言。 应指出，所产生的句子中，有些句子的含义是荒谬的（如 the banana eat a monkey和the banana eat the banana等）。然而，若不考虑语义，则我们就必须承认它们是语法上合法的句子。,2.2.2 文法和语言的形式定义,为得到文法的严格定义，我们对前面的规则进行如下的概括：,1、文法G 的形式定义,1文法G为一个四元组: = (T，N，) T：终结符(Terminal)集 N：非终结符(Variable)集，TN= 语法范畴某个语言结构 ：开始符号(Start Symbol)，SN 至少在产生式左侧出现一次,规定：（1）VN ，VT，P是有穷非空集合； （2）VNVT （不含公共元素）,：产生式(Product)集合 ，被称为产生式（定义式），读作：定义为。其中： (TN)+，且中至少有N中元素的一个出现。 (TN)*。 称为产生式的左部(Left Part)，称为产生式的右部(Right Part)。,例：算术表达式的文法,P: EE + E EE - E EE * E EE/ E E( E ) Eid G =（id，+，-，*，/，(，)，E，P，E） 约定：只写产生式。可简写为： E E + E | E - E | E * E | E / E | ( E ) | id,产生式的简写,对一组有相同左部的产生式 1，2，n 可以简单地记为： 1|2|n 读作：定义为或者1，或者2，或者n。并且称它们为产生式。1，2，n称为候选式(Candidate)。,例、 文法G =（VN ，VT ，P，S）， 其中： VN=S，VT =0，1， P=S 0S1，S 01。 开始符号是S S 0S1 00S11 0n-1S1n-1 0n1n 所以描述的语言为： L=0n1n|n1,例： 文法G =（VN ，VT，P，S） 其中 ：VN =标识符，字母，数字 VT= a,b ,c,x,y,z,0,1,9 S= P = | | a|b|z 0|1|9 ,1、文法的定义 文法的第二种表示法： 上例1改为： G: S 0S1 S 01 文法的第三种表示法： 上例1改为： GS: S 0S1 S 01,一般约定，第一条产生式的左部是开始符号；用尖括号括起来的是非终结符号，不用尖括号括起来的是终结符号，或者用大写字母表示非终结符号，小写字母表示终结符号。,2、直接推导的定义,如：有文法G: EE+E|E*E|(E)|i E (E) (E+E) (i+E) (i+i) （称这样一串替换序列是从E推出(i+i)的一个推导) （1）定义： 称 A直接推出 ，即： A 仅当 A 是一个产生式， 且、 (VNVT)*,例：GS: S 0S1, S 01 S 0S1 00S11 000S111 00001111 可有： A = 00S11 , =000S111 (相当A=S, = 0S1),A =S， 0S1 直接推导：S 0S1 A=0S1， =00S11 直接推导： 0S100S11,例： A0S1，=0011 直接推导：0S1 0011,使用规则：S 01 0，1， AS， 01,规则： S 0S1 ， AS， 0S1,规则： S 0S1 0 ， 1 AS， 0S1,（多步）推导,012 n 记为 0n n (恰用n步) 0+ n （至少一步） 0* n （若干步:零步或多步）,id+id*id的不同推导EE+E|E*E|(E)|id,E E+E id+E id+E*E id+id*E id+id*id,E E+E E+E*E E+E*id E+id*id id+id*id,E E*E E+E*E E+id*E id+id*E id+id*id,不做限制 句型 (sentential Form) （归约） E * id+id*id,施于最右变量 右句型/规范句型 (canonical ) (最左/规范归约) E + id+id*id,施于最左变量 左句型(left-) （最右归约） E5 id+id*id,例：算术表达式 GE: E E+T | T T T*F | F F (E) | a 可推导出： E E+T T+TF+T a+T a+T*F a+F*Fa+a*F a+a*a 表示文法GE能推导出用符号a, +, *, (和)构成的所有算术表达式,3、句型与句子,4、文法G产生的语言,定义：L(G)= xSx， S为文法开始符号， xVT* L(G)是文法GS描述的语言，也是该文法能推导出所有句子的集合。 文法 EE+E|E*E|(E)|id可以派生出多少个句子？ 文法G的作用语言的有穷描述 以有限的规则描述无限的语言现象 有限: 产生式集合、终结符集合、非终结符集合 无限： 可以导出无穷多个句子 （注：L也可是有穷）,例： GS: S 0S1, S 01 L(G)0n1n n1,因为S0S100S11 0n1n 重复利用规则S0S1,例：文法G: S bA A aA|a 考虑该文法定义的语言。,S bA S bA baA baa S bA baA baaA baaa S bA baA baa 所以： L(G)=ban| n1,例 考虑文法G: E (E)a 这个文法有1个非终结符E、3个终结符(,),a 这个文法生成语言: L(G)=a ,(a),(a),(a),.， 即：串由零个或多个左括号、后接一个a ，以及后面是与左括号相同数量的右括号组成。作为这些串的一个推导示例，我们给出(a)的一个推导： E (E) (E) (a),练习