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

1、编译原理前后文无关文法和语言第1页，共51页，2022年，5月20日，20点31分，星期二本 章 内 容2.1 语言的概述2.2 文法和语言的定义第2页，共51页，2022年，5月20日，20点31分，星期二2.1 语言的概述什么是语言自然语言(Natural Language)是人与人的通讯工具语义(Semantics):环境、背景知识、语气、二义性难以形式化计算机语言(Computer Language)计算机系统间、人机间通讯工具严格的语法(Grammar)、语义(Semantics) 易于形式化：严格语言是用来交换信息的工具功能性描述第3页，共51页，2022年，5月20日，20点31

2、分，星期二2.1 语言概述语言的描述方法现状自然语言：自然、方便-非形式化数学语言（符号）：严格、准确-形式化形式化描述高度的抽象，严格的理论基础和方便的计算机表示。第4页，共51页，2022年，5月20日，20点31分，星期二2.1 语言概述语言形式化的内容提取单词(Token)：满足一定规则字符(Character)串句子(Sentence)：满足一定规则单词序列语言(Language)：满足一定条件的句子集合语言是字和组合字的规则结构性描述例：一译开天第课今始编节上 今天开始上第一节编译课第5页，共51页，2022年，5月20日，20点31分，星期二程序设计语言形式化的内容提取程序设计语

3、言(Programming Language)：组成 程序的所有语句的集合程序(Program)：满足语法规则的语句序列语句(Sentence) ：满足语法规则的单词序列单词(Token) ：满足词法规则的字符串例变量=表达式if 条件 then 语句while条件 do 语句call 过程名(参数表)2.1 语言概述第6页，共51页，2022年，5月20日，20点31分，星期二语言描述形式文法语法语句语句的组成规则描述方法：BNF（巴科斯范式： Backus Normal Form ）范式、语法(描述)图词法单词单词的组成规则描述方法：BNF范式、正规式2.1 语言概述第7页，共51页，20

4、22年，5月20日，20点31分，星期二遗憾的是，对于自然语言来说，目前尚无能够完全刻划一语言全部句子的结构的方法。然而，对大多数程序设计语言来说，此问题已被解决。1960年，P.Naur & J.Backus（巴科斯-瑙尔）首先用BNF（Backus-Naur-Formal（范式）对ALGOL语言进行了描述。应指出，BNF成功地解决了程序设计语言的语法描述问题，但描述其语义，还必须借助自然语言。复习：巴科斯范式 （BNF - Backus Normal Form）第8页，共51页，2022年，5月20日，20点31分，星期二通常，可用如下方式表示或定义一种语言：（1）若语言的句子有限时，可用

5、枚举法。 例如，只含两个句子的语言： “I am a teacher”, “You are students”;（2）制定有限条规则，用于产生所要描述的语言的全部句子（可无限多），这些规则构成了该语言的文法。（3）建立一种装置（算法或过程），它以某字母表上的符号串为输入，判别该符号串是否为所描述语言的句子。此装置称为自动机。第9页，共51页，2022年，5月20日，20点31分，星期二巴科斯范式 （BNF ）例子：The big elephant ate the peanut.(大象吃花生）The little boy ran quickly.(小男孩跑得快）The man has a dog

6、.(这人有一条狗） 以上都是符合英语语法规则的句子，即它们是在英语语法规则中成立的句子。 如何描述一个给定的句子在给定规则下是否成立呢？第10页，共51页，2022年，5月20日，20点31分，星期二句子=主语谓语主语=冠词形容词名词冠词=the 形容词= big谓语=动词宾语 动词=ate 宾语=冠词名词 名词=elephant | peanut 我们把这种描述语法规则方法称巴科斯范式，也称巴科斯-瑙尔范式(Backus Normal Form)，简称BNF。那么上面叙述的语法规则可写为：第11页，共51页，2022年，5月20日，20点31分，星期二步骤 推导 所用规则1 谓语 2 形容词

7、 名词 谓语 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，在这里，我们只考虑句子的语法，而不考

8、虑句子的语义。 根据以上规则，可以推导出句子 The big elephant ate the peanut. 过程如下：第12页，共51页，2022年，5月20日，20点31分，星期二用巴科斯范式描述语言能给研究问题带来很大方便。如下面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 可见，如果一个语言有无穷多个句子，那么用上述规则来描述更有实际意义.它用一组

9、规则来代替枚举法，用有穷来描述无限。第13页，共51页，2022年，5月20日，20点31分，星期二2.2 文法和语言的定义本节主要内容 基本概念和术语（字母表，符号串等）； 规则； 文法的定义； 推导； 句型与句子； 文法和语言的等价转换等第14页，共51页，2022年，5月20日，20点31分，星期二2.2.1 基本概念和术语1。字母表（符号表、符号集） 由若干元素（符号、字母）组成的有限非空集合。2。符号串 用字母表中符号所组成的任何有限序列。 符号串的长度 = 符号串中所含符号的个数 例：aba的长度为3。记为：|aba|=3 空串 不含任何符号的符号串，记为 。显然，| |= 0。本

10、课约定 用A、B、C、 等表示字母表或符号串集；用a,b,c,S,T,U 等表示符号；用s,t,u,x,y,z,等表示符号串。3。符号串的前（后）缀及子串 设,，x是符号串，若x= ，则称是x的子串；特别地，当= （= ）时，称 是x的前（后）缀。第15页，共51页，2022年，5月20日，20点31分，星期二 基本概念和术语4。符号串的连接和方幂 连接 设x,y是符号串，将y直接地拼接到x之后所得的新符号串称为x与y的连接，记为xy 注意，一般说来，xy 不等于 yx；但 x = x = x 方幂 符号串x与其自身的 n-1次连接称为 x 的 n 次方幂，记为第16页，共51页，2022年，

11、5月20日，20点31分，星期二 基本概念和术语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 = A6。符号串集的方幂与闭包第17页，共51页，2022年，5月20日，20点31分，星期二例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，

12、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， 第18页，共51页，2022年，5月20日，20点31分，星期二 基本概念和术语当我们把字母（符号）表视为由长度为1的符号串构成的符号串集时，就可定义字母表上的连接、积、方幂等运算。例A=a,b,c第19页，共51页，2022年，5月20日，20点31分，星期二2.2.2 文法和语言的形式定义 我们从“产生语言”的角度出发,讨论文法和语言的形式定义。产生语言指制定出有限条规则，借助它们就能产生出

13、些语言的句子。我们以几个英语句子构成的语言为例进行讨论。并设每个句子都是“主-谓-宾”结构。语法规则见右。其中，每个用括起来的部分是所要定义语言中的一个语法实体（称为语法单位、语法结构、语法范畴、语法变量等）。“:=”是用于定义语法结构的符号，其含义（并读作）“定义为”。 语法规则也称为产生式(Production): := the :=:=:=monkey:=banana:=eat:=has:= the:= a第20页，共51页，2022年，5月20日，20点31分，星期二 现在，我们讨论如何用上述规则推导出相应语言的全部句子。推导：从语言最大的一个语法范畴（本例中是）开始，反复用语法规则中

14、“:=” 右侧的符号串取代其左侧符号，直到所得的符号串中不再含有可被替换语法范畴。每次替换称为一步（直接）推导，并用符号“”表示。 例如，我们首先用规则进行第一步推导(derivation)，就可得到 ，记为： 所得的符号串含有两个语法范畴，可对其中任一个（例如对）进行新的推导（替换）： 重复上述过程，可得到一个推导序列（见下页）。第21页，共51页，2022年，5月20日，20点31分，星期二用语法规则进行推导所得的推导序列推导步骤 所用规则所得的符号串 1 2 3 the 4 the 5 the monkey 6 the monkey eat 7 the monkey eat a 8 th

15、e monkey eat a banana第22页，共51页，2022年，5月20日，20点31分，星期二2.2.2 文法和语言的形式定义从前面的推导看，从出发，经8步推导得到了一个英语句子。故前面的推导称为长度为8的推导。若不关心推导的中间过程，可将从一符号串到另一符号串的推导用记号第23页，共51页，2022年，5月20日，20点31分，星期二规则的简化表示在前面的语法规则定义中，有些语法范畴（如、）有若干条不同的规则来定义它，为简明起见，我们可以将它们写在同一个左部语法范畴下，将其定义值用符号“|”（读作或）隔开。如、 、 的定义规则可简记为:= monkey | banana:= ea

16、t | has:= the | a第24页，共51页，2022年，5月20日，20点31分，星期二语法规则及其产生的语言前面的语法规则可以产生16个不同的句子，由这16个句子组成的集合，就是该规则所定义（或所产生）的语言。应指出，所产生的句子中，有些句子的含义是荒谬的（如 the banana eat a monkey和the banana eat the banana等）。然而，若不考虑语义，则我们就必须承认它们是语法上合法的句子。第25页，共51页，2022年，5月20日，20点31分，星期二2.2.2 文法和语言的形式定义为得到文法的严格定义，我们对前面的规则进行如下的概括：第26页，共

17、51页，2022年，5月20日，20点31分，星期二1、文法G 的形式定义1文法G为一个四元组: = (T，N，) T：终结符(Terminal)集 N：非终结符(Variable)集，TN= 语法范畴某个语言结构 ：开始符号(Start Symbol)，SN至少在产生式左侧出现一次规定：（1）VN ，VT，P是有穷非空集合； （2）VNVT （不含公共元素）第27页，共51页，2022年，5月20日，20点31分，星期二：产生式(Product)集合 ，被称为产生式（定义式），读作：定义为。其中： (TN)+，且中至少有N中元素的一个出现。 (TN)*。 称为产生式的左部(Left Part

18、)，称为产生式的右部(Right Part)。 第28页，共51页，2022年，5月20日，20点31分，星期二例：算术表达式的文法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第29页，共51页，2022年，5月20日，20点31分，星期二产生式的简写对一组有相同左部的产生式 1，2，n 可以简单地记为： 1|2|n 读作：定义为或者1，或者2，或者n。并且称它们为产生式。1，2，n称为候

19、选式(Candidate)。 第30页，共51页，2022年，5月20日，20点31分，星期二例、 文法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第31页，共51页，2022年，5月20日，20点31分，星期二例： 文法G =（VN ，VT，P，S）其中 ：VN =标识符，字母，数字 VT= a,b ,c,x,y,z,0,1,9 S= P = | | a|b|z 0|1|9 第32页，共51页，2022年，5月20日，20点31分，

20、星期二1、文法的定义 文法的第二种表示法： 上例1改为： G: S 0S1 S 01 文法的第三种表示法： 上例1改为： GS: S 0S1 S 01一般约定，第一条产生式的左部是开始符号；用尖括号括起来的是非终结符号，不用尖括号括起来的是终结符号，或者用大写字母表示非终结符号，小写字母表示终结符号。 第33页，共51页，2022年，5月20日，20点31分，星期二2、直接推导的定义 如：有文法G: EE+E|E*E|(E)|i E (E) (E+E) (i+E) (i+i) （称这样一串替换序列是从E推出(i+i)的一个推导)（1）定义： 称 A直接推出 ，即： A 仅当 A 是一个产生式，

21、 且、 (VNVT)*第34页，共51页，2022年，5月20日，20点31分，星期二例：GS: S 0S1, S 01 S 0S1 00S11 000S111 00001111 可有： A = 00S11 , =000S111 (相当A=S, = 0S1)第35页，共51页，2022年，5月20日，20点31分，星期二A =S， 0S1直接推导：S 0S1A=0S1， =00S11直接推导： 0S100S11例：A0S1，=0011直接推导：0S1 0011使用规则：S 010，1，AS， 01 规则： S 0S1 ， AS， 0S1 规则： S 0S1 0 ， 1AS， 0S1 第36页，

22、共51页，2022年，5月20日，20点31分，星期二 若有 1 n ，或 1=n ,则记作1 n 例： 在例1中存在序列：10S1 00S11 000S111 00001111 n 记作： 0S1 00001111 0S1 00001111 +*一样的 若存在直接推导的序列： 1 2 3 n (n1)则 称1推导 n (或n规约到1 ) ，记 1 n +第37页，共51页，2022年，5月20日，20点31分，星期二（多步）推导012 n记为 0n n (恰用n步) 0+ n （至少一步） 0* n （若干步:零步或多步）第38页，共51页，2022年，5月20日，20点31分，星期二id+

23、id*id的不同推导EE+E|E*E|(E)|idE E+E id+E id+E*E id+id*E id+id*idE E+E E+E*E E+E*id E+id*id id+id*idE 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第39页，共51页，2022年，5月20日，20点31分，星期二例：算术表达式 GE: E E

24、+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, +, *, (和)构成的所有算术表达式第40页，共51页，2022年，5月20日，20点31分，星期二3、句型与句子句型：设GS是文法，若S x，且xV* , 则称x是文法GS的句型 句子：设GS是文法，若S x，且xVT* , 则称x是文法GS的句子（句子是句型的特殊）结论句子一定是句型，句型不一定是句子。 例：GS: S 0S1, S 01 S 0S1 00S11 000S111 00001111 S, 0S1 ,

25、 00S11 , 000S111 , 00001111都是句型，只有00001111是G的句子*第41页，共51页，2022年，5月20日，20点31分，星期二4、文法G产生的语言定义：L(G)= xSx， S为文法开始符号， xVT* L(G)是文法GS描述的语言，也是该文法能推导出所有句子的集合。 文法 EE+E|E*E|(E)|id可以派生出多少个句子？ 文法G的作用语言的有穷描述以有限的规则描述无限的语言现象有限: 产生式集合、终结符集合、非终结符集合无限： 可以导出无穷多个句子 （注：L也可是有穷）第42页，共51页，2022年，5月20日，20点31分，星期二例： GS: S 0S

26、1, S 01 L(G)0n1n n1因为S0S100S11 0n1n重复利用规则S0S1第43页，共51页，2022年，5月20日，20点31分，星期二例：文法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第44页，共51页，2022年，5月20日，20点31分，星期二例 考虑文法G: E (E)a 这个文法有1个非终结符E、3个终结符(,),a这个文法生成语言: L(G)=a ,(a),(a),(a),.， 即：串由零个或多个左括号、后接一个a ，以及后面是与左括号相同数量的右括号组成。作为这些串的一个推导示例，我们给出(a)的一个推导： E (E) (E) (a)第45页，共51页，2022年，5月20日，20点31分，星期二练习：文法GS：（1）SaSBE