第2章-1-文法的形式定义

1、第第2章章 前后文无关文前后文无关文法和语言法和语言本章主要内容本章主要内容2.1 语言概述语言概述n什么是语言什么是语言n自然语言自然语言(Natural Language)n是人与人的通讯工具是人与人的通讯工具n语义语义(Semantics):环境、背景知识、语气、二环境、背景知识、语气、二义性义性难以形式化难以形式化n计算机语言计算机语言(Computer Language)n计算机系统间、人机间通讯工具计算机系统间、人机间通讯工具n严格的语法严格的语法(Grammar)、语义、语义(Semantics) 易于形式化：严格易于形式化：严格n语言是用来交换信息的工具语言是用来交换信息的工具

2、功能性描述功能性描述2.1语言概述语言概述n语言的描述方法语言的描述方法现状现状n自然语言：自然、方便自然语言：自然、方便-非形式化非形式化n数学语言（符号）：严格、准确数学语言（符号）：严格、准确-形式化形式化n形式化描述形式化描述n高度的抽象，严格的理论基础和方便的计高度的抽象，严格的理论基础和方便的计算机表示。算机表示。2.1 语言概述语言概述n语言语言形式化的内容提取形式化的内容提取n单词单词(Token)：满足一定规则字符：满足一定规则字符(Character)串串n句子句子(Sentence)：满足一定规则单词序列：满足一定规则单词序列n语言语言(Language)：满足一定条件的

3、句子集：满足一定条件的句子集合合n语言是字和组合字的规则语言是字和组合字的规则结构性描述结构性描述n例：一译开天第课今始编节上例：一译开天第课今始编节上n今天开始上第一节编译课今天开始上第一节编译课2.1 语言概述语言概述n程序设计语言程序设计语言形式化的内容提取形式化的内容提取n程序设计语言程序设计语言(Programming Language)：组成程序的：组成程序的所有语句的集合所有语句的集合n程序程序(Program)：满足语法规则的语句序列：满足语法规则的语句序列n语句语句(Sentence) ：满足语法规则的单词序列：满足语法规则的单词序列n单词单词(Token) ：满足词法规则的

4、字符串：满足词法规则的字符串n例例n变量变量=表达式表达式nif 条件条件 then 语句语句nwhile条件条件 do 语句语句ncall 过程名过程名(参数表参数表)2.1 语言概述语言概述n描述形式描述形式文法文法n语法语法语句语句n语句的组成规则语句的组成规则n描述方法：描述方法：BNF范式、语法范式、语法(描述描述)图图n词法词法单词单词n单词的组成规则单词的组成规则n描述方法：描述方法：BNF范式、正规式范式、正规式2.2 文法和语言的基本定义文法和语言的基本定义2.2.1 基本概念和术语基本概念和术语n字母表字母表（Alphabet）是一个非空有穷集合，）是一个非空有穷集合，字母

5、表中的元素称为该字母表的一个字母字母表中的元素称为该字母表的一个字母（Letter），也叫字符（），也叫字符（Character）n例例 以下是不同的字母表以下是不同的字母表 a，b，c，d a，b，c，z 0，1n相当于高级语言的字符集相当于高级语言的字符集2.2.1 基本概念和术语基本概念和术语n字母表上字母表上符号串符号串(String)的定义的定义 (1) 是是上的一个符号串，叫做空串。上的一个符号串，叫做空串。(2) 若若x是是上的符号串，而上的符号串，而a是是的元素的元素, 则则xa是是上的符号串。上的符号串。(3) y是是上的符号串上的符号串,当且仅当它由当且仅当它由(1)和和(

6、2)导出。导出。n由字母表中的符号所组成的的任何有穷序列由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串被称之为该字母表上的符号串,也称作也称作“字字”(Word)。2.2.1 基本概念和术语基本概念和术语n定义定义1 设设1、2是两个字母表，是两个字母表，1与与2 的乘积的乘积(Product)12=ab|a1，b2 n例例:1=0,1, 2=a,b, 12 =0a,0b,1a,1bn定义定义2 设设是一个字母表，是一个字母表，的的n次幂次幂(Power)递归地递归地定义为：定义为：n 0=n n=n-1 n1n例：例： 13 =000,001,010,011,100,101

7、,110,1112.2.1 基本概念和术语基本概念和术语n定义定义3 设设是一个字母表，是一个字母表，的正闭包的正闭包(Positive Closure)：n+=234n的克林闭包的克林闭包(Kleene Closure)：n*=0+n =023 2.2.1 基本概念和术语基本概念和术语n例例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 基本概念和术语基本概念和术语n例例0,1*=，0，1，00，01，11，000

8、，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 基本概念和术语基本概念和术语n定义定义 5 设设是一个字母表，是一个字母表， L *，L称为字母称为字母表表上的一个上的一个语言语言（Language），）， xL，x叫做叫做L的的一个一个句子句子。n例：例： 字母表字母表0，1上的语言上的语言0，100，110，1，00，110，1，00，11，01，1000，11*01，10*2.2.1 基本概念和术语基本概念和术语设设s是是符号串：符号串：01290

9、273前缀前缀：移走：移走s的尾部的零个或多于零个符号的尾部的零个或多于零个符号后缀后缀：删去：删去s的头部的零个或多于零个符号的头部的零个或多于零个符号子串子串：从：从s中删去一个前缀和一个后缀中删去一个前缀和一个后缀子序列子序列: 从从s中删去零个或多于零个符号中删去零个或多于零个符号(这些符号这些符号不要求是连续的）不要求是连续的）长度长度：是该符号串中的符号的数目。例如：是该符号串中的符号的数目。例如|aab|=3,|=0。2.2.1 基本概念和术语基本概念和术语符号串的连接和幂符号串的连接和幂1.连接：设连接：设x和和y是符号串，它们的连接是符号串，它们的连接xy是把是把y的符号写在

10、的符号写在x的的符号之后得到的符号串。例如，符号之后得到的符号串。例如，x=ba,y=nana,xy=banana.2.幂：幂：x0= ; x1=x; x2=xx; ;xn=xn-1x; 例如例如, x=ba, x1= ba, x2=baba, x3=bababa,.2.2.1 基本概念和术语基本概念和术语n符号串集合符号串集合的的和与和与积积n设设A A，B B为两个符号串之集，定义为两个符号串之集，定义 和和A+BA+B（或（或A ABB） =w | w=w | w A A，或，或 w w B B 积积A AB B（或（或 ABAB）= xy |x = xy |x A, y A, y B

11、B A+ A+ = = +A = A +A = A ； A A = = A = A = ； A = AA = A = A = An符号串符号串集合的方幂集合的方幂n符号串集合符号串集合A A，定义，定义A A0 0 =, A =, A1 1=A, A=A, A2 2=AA, A=AA, A3 3=A=A2 2A, , AA, , An nA An-1n-1A=AAA=AAn-1n-1，n0n0n符号串集合的正闭包符号串集合的正闭包nA A+ +=A=A1 1 AA2 2 A An n n符号串集合的自反闭包符号串集合的自反闭包nA A* * = A A+ +2.2.2 文法文法的形式化定义的形

12、式化定义如何实现语言结构如何实现语言结构的形式化描述？的形式化描述？考虑一个句子考虑一个句子文法要素的提取文法要素的提取分析分析：The gray wolf will eat the goat谓语谓语主语主语形容词形容词名词名词动词动词直接宾语直接宾语助动词助动词句子句子动原动原冠词冠词名词名词The gray wolf will eat the goat冠词冠词提取规则，写在黑板上提取规则，写在黑板上 句子句子 主语主语 谓语谓语 主语主语 冠词冠词 形容词形容词 名词名词 谓语谓语 动词动词 直接宾语直接宾语 动词动词 助动词助动词 动词原形动词原形 直接宾语直接宾语 冠词冠词 名词名词

13、产生句子的规则产生句子的规则从产生语言的角度从产生语言的角度 冠词冠词 the the 形容词形容词 gray gray 助动词助动词 will will 动词原形动词原形 eat eat 名词名词 wolfwolf 名词名词 goatgoat终结符号集终结符号集VT = the，gray, wolf,will, eat, goat非终结符号集非终结符号集VN = 句子句子 ， 主语主语 ， 谓语谓语 ， 冠词冠词 ， 形容词形容词 ， 名词名词 ， 动词动词 ， 直接宾语直接宾语 ， 助动词助动词 ， 动词原形动词原形 语法规则集语法规则集P = 句子句子 主语主语谓语谓语 ， 开始符号开始

14、符号S = 句子句子 句子的语法组成句子的语法组成终结符号集，非终结符号集，语法规则，开始符号终结符号集，非终结符号集，语法规则，开始符号文法文法G 的形式定义的形式定义文法文法G为一个四元组为一个四元组: = (T，N，)nT：终结符：终结符(Terminal)集集nN：非终结符：非终结符(Variable)集，集，TN=n语法范畴语法范畴某个语言结构某个语言结构n：开始符号：开始符号(Start Symbol)，SNn至少在产生式左侧出现一次至少在产生式左侧出现一次文法文法G 的形式定义的形式定义n：产生式产生式(Product)集合集合，被称为产生式（定义式），读作：，被称为产生式（定义

15、式），读作：定定义为义为。其中。其中(TN)+，且，且中至少有中至少有N中元素的一个出现。中元素的一个出现。(TN)*。称为产称为产生式生式的的左部左部(Left Part)，称为产生式称为产生式的的右部右部(Right Part)。 句子句子主语主语 谓语谓语 冠词冠词 形容词形容词 名词名词 谓语谓语 the the 形容词形容词 名词名词 谓语谓语 the graythe gray 名词名词 谓语谓语 the gray wolf the gray wolf 谓语谓语 the gray wolf the gray wolf 动词动词 直接宾语直接宾语 the gray wolf the g

16、ray wolf 助动词助动词 动词原形动词原形 直接宾语直接宾语 the gray wolf will the gray wolf will 动词原形动词原形 直接宾语直接宾语 the gray wolf will eat the gray wolf will eat 直接宾语直接宾语 the gray wolf will eat the gray wolf will eat 冠词冠词 名词名词 the gray wolf will eat the the gray wolf will eat the 名词名词 the gray wolf will eat the goatthe gray

17、wolf will eat the goat句子的派生（推导）句子的派生（推导）_根据规则根据规则 句子句子 the gray wolf will eat the goat the gray wolf will eat the wolf the gray goat will eat the wolf符合符合语法且符合语义的句子仅是：语法且符合语义的句子仅是： the gray wolf will eat the goat还可以还可以“得出得出”其他的句子其他的句子例例 算术表达式的文法算术表达式的文法n考虑简单算术表达式组成的语言考虑简单算术表达式组成的语言n递归定义递归定义中缀表示中缀表示n

18、标识符标识符(id)（常数、变量）是表达式；（常数、变量）是表达式；n表达式加一个表达式是表达式；表达式加一个表达式是表达式；n表达式减一个表达式是表达式；表达式减一个表达式是表达式；n表达式乘一个表达式是表达式；表达式乘一个表达式是表达式；n表达式除一个表达式是表达式；表达式除一个表达式是表达式；n表达式加上括号后是表达式。表达式加上括号后是表达式。例例 算术表达式的文法算术表达式的文法考虑用式子表示这个定义考虑用式子表示这个定义标识符标识符(id) (id) 是表达式是表达式表达式加一个表达式是表达式表达式加一个表达式是表达式EidEE + E表达式减一个表达式是表达式表达式减一个表达式是

19、表达式EE - E表达式乘一个表达式是表达式表达式乘一个表达式是表达式EE *E表达式除一个表达式是表达式表达式除一个表达式是表达式EE / E表达式加上括号后是表达式表达式加上括号后是表达式E(E)例例 算术表达式的文法算术表达式的文法nP: EE + E n EE - En EE * E n EE/ E n E( E )n EidnG =（id，+，-，*，/，(，)，E，P，E）n约定：只写产生式约定：只写产生式 n简写简写E E+E | E*E | E-E | E/E | (E) | id产生式的简写产生式的简写n对一组有相同左部的产生式对一组有相同左部的产生式1，2，n简单地记为：简

20、单地记为：1|2|n 读作：读作：定义为或者定义为或者1，或者，或者2，或，或者者n。并且称它们为。并且称它们为产生式产生式。1，2，n称为称为候选式候选式(Candidate)n文法如何实现对语言的刻画？产生式很关键！文法如何实现对语言的刻画？产生式很关键！产生式规定的一些变换产生式规定的一些变换nE由第由第1个候选式可以变成个候选式可以变成E+EnE+E中的第中的第1个个E由第由第2个候选式可以变成个候选式可以变成E*E，从而从而E+E变成变成E*E+En根据第根据第4个候选式，个候选式，E*E+E中的中的E都可以变成都可以变成id:nE*E+E 变成变成id*E+Enid*E+E变成变成

21、id*E+idnid*E+id变成变成id*id+idn也就是说，根据第也就是说，根据第4个候选式，个候选式， E*E+E经经3步步变换变成变换变成id*id+id表示依据文法表示依据文法进行的变换进行的变换E E + E （1） E * E + E （2） id * E + E （4） id * E + id （4） id * id + id（4）nE可以变成可以变成E+EnE+E中的第一个中的第一个E变成变成E*EnE*E+E 变成变成id*E+Enid*E+E变成变成id*E+idnid*E+id变成变成id*id+idE经经5步变换变成步变换变成id*id+id：E 5 id* id

22、+id实质是从实质是从E开始依据产生式对所得串中的开始依据产生式对所得串中的特定部特定部分分进行变换，不断获得新的串，最终得到目标进行变换，不断获得新的串，最终得到目标变换的分析变换的分析n实质是从实质是从E E开始依据产生式对所得串中的开始依据产生式对所得串中的特定部特定部分分进行变换，不断获得新的串，最终得到目标进行变换，不断获得新的串，最终得到目标 E*E 依据产生式依据产生式E E+EE*E+E A依据产生式依据产生式A 直接推导与归约直接推导与归约n根据产生式对符号串进行变换的过程根据产生式对符号串进行变换的过程n是文法的一个产生式，是文法的一个产生式，n且且、（TN）*，n称称的直

23、接的直接推导推导/派生派生(Derive)出出，也称，也称 直接直接归约归约(Reduce)为为。n记为记为 n例：例：nid + Eid + E * E（多步）推导（多步）推导/归约归约n012 n n记为记为 0n n (恰用恰用n步步)n 0+ n （至少一步）（至少一步）n 0* n （若干步（若干步:零步或多步）零步或多步）nE 5 id* id +id推导推导/归约回顾归约回顾E E + E （1） 串中含有变量串中含有变量n id + E （4） 串中含有变量串中含有变量n id + E * E （2） 串中含有变量串中含有变量n id + id * E（4） 串中含有变量串中含

24、有变量n id + id * id（4） 串中串中没有没有变量变量n到此串中已经没有（语法）变量了，不能再推到此串中已经没有（语法）变量了，不能再推了了得到得到句子句子句型与句子句型与句子nE E + E E + E * EnE 4 id + id * En定义定义:如果如果S*，(TN)*则称则称是是G产产生的一个生的一个句型句型(Sentential Form)nE 5 id + id * idn定义定义:如果如果S * x，且，且xT* ，则称，则称x是是G产产生的一个生的一个句子句子(Sentence)文法文法G产生的产生的语言语言定义：定义：L(G)=x|S*x and xVT*n文

25、法文法 EE+E|E*E|(E)|id可以派生出多少个句子？可以派生出多少个句子？n文法文法G的作用的作用语言的有穷描述语言的有穷描述n以有限的规则描述无限的语言现象以有限的规则描述无限的语言现象n有限有限:产生式集合、终结符集合、非终结符集合产生式集合、终结符集合、非终结符集合n无限：无限：可以导出无穷多个句子可以导出无穷多个句子n（注：（注：L也可是有穷）也可是有穷）当语言是无限集时，能否用有限的规则来描述呢？当语言是无限集时，能否用有限的规则来描述呢？回答是肯定的回答是肯定的, 只需使用文法的递归定义即可。只需使用文法的递归定义即可。例如，文法例如，文法G1： | A|B|Z 0|1|2

26、|9递归文法递归文法文法文法G2E：E E+E | E*E | E-E | E/E | (E) | id显然，显然，G1，G2都是递归定义的。所谓递归定义，都是递归定义的。所谓递归定义，指在定义一个语法成分时，直接或间接地使用了指在定义一个语法成分时，直接或间接地使用了语法成分自身。语法成分自身。.)/(.)/()/( ,;,6 . 2*终结符则称为递归文法至少含有一个递归的非一文法递归的非终结符号右左为称递归的右左是则称且若存在推导是直接递归的产生式则称的形式具有若为文法设定义AAAAAAPAG递归文法递归文法文法等价文法等价n若若L(G1)=L(G2)，则称文法，则称文法G1和和G2是等价的。是等价的。也就是说也就是说，如果两个文法定义的语言一样，则称，如果两个文法定义的语言一样，则称这两个文法是等价的。这两个文法是等价的