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

第2章前后文无关文法和语言本章主要内容2.1语言及文法概述2.2文法(Grammar)和语言的形式定义2.3句型分析2.4文法的分类2.5文法的构造2.1语言概述什么是语言自然语言(NaturalLanguage)是人与人的通讯工具语义(Semantics):环境、背景知识、语气、二义性——难以形式化计算机语言(ComputerLanguage)计算机系统间、人机间通讯工具严格的语法(Grammar)、语义(Semantics)——易于形式化：严格语言是用来交换信息的工具——功能性描述2.1语言概述语言的描述方法——现状自然语言：自然、方便-非形式化数学语言（符号）：严格、准确-形式化形式化描述高度的抽象，严格的理论基础和方便的计算机表示。2.1语言概述语言——形式化的内容提取单词(Token)：满足一定规则字符(Character)串句子(Sentence)：满足一定规则单词序列语言(Language)：满足一定条件的句子集合语言是字和组合字的规则——结构性描述例：一译开天第课今始编节上今天开始上第一节编译课2.1语言概述程序设计语言——形式化的内容提取程序设计语言(ProgrammingLanguage)：组成程序的所有语句的集合程序(Program)：满足语法规则的语句序列语句(Sentence)：满足语法规则的单词序列单词(Token)：满足词法规则的字符串例变量=表达式if条件then语句while条件do语句call过程名(参数表)2.1语言概述描述形式——文法语法——语句语句的组成规则描述方法：BNF范式、语法(描述)图词法——单词单词的组成规则描述方法：BNF范式、正规式2.2文法和语言的基本定义

2.2.1基本概念和术语字母表（Alphabet）是一个非空有穷集合，字母表中的元素称为该字母表的一个字母（Letter），也叫字符（Character）例以下是不同的字母表 ⑴{a，b，c，d} ⑵{a，b，c，……，z} ⑶{0，1}相当于高级语言的字符集2.2.1基本概念和术语字母表上符号串(String)的定义

(1)ε是∑上的一个符号串，叫做空串。(2)若x是∑上的符号串，而a是∑的元素,

则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作“字”(Word)。2.2.1基本概念和术语定义1设∑1、∑2是两个字母表，∑1与∑2

的乘积(Product)∑1∑2={ab|a∈∑1，b∈∑2}例:∑1={0,1},∑2={a,b},∑1∑2={0a,0b,1a,1b}定义2设∑是一个字母表，∑的n次幂(Power)递归地定义为：⑴∑0={ε}⑵∑n=∑n-1∑ n≥1例：∑13={000,001,010,011,100,101,110,111}2.2.1基本概念和术语定义3设∑是一个字母表，∑的正闭包(PositiveClosure)：∑+=∑∪∑2∪∑3∪∑4∪……∑的克林闭包(KleeneClosure)：∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪……2.2.1基本概念和术语例{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基本概念和术语例{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基本概念和术语定义5设∑是一个字母表，L∑*，L称为字母表∑上的一个语言（Language），x∈L，x叫做L的一个句子。例：字母表{0，1}上的语言{0，1}{00，11}{0，1，00，11}{0，1，00，11，01，10}{00，11}*{01，10}*2.2.1基本概念和术语设s是符号串：01290273前缀：移走s的尾部的零个或多于零个符号后缀：删去s的头部的零个或多于零个符号子串：从s中删去一个前缀和一个后缀子序列:从s中删去零个或多于零个符号(这些符号不要求是连续的）长度：是该符号串中的符号的数目。例如|aab|=3,|ε|=0。2.2.1基本概念和术语符号串的连接和幂1.连接：设x和y是符号串，它们的连接xy是把y的符号写在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基本概念和术语符号串集合的和与积设A，B为两个符号串之集，定义

和 A+B（或A∪B）

={w|wA，或wB}

积 A•B（或AB）={xy|xA,yB} A+=+A=A；

A=A=；{}A=A{}=A符号串集合的方幂符号串集合A，定义A0={ε},A1=A,A2=AA,A3=A2A,…,An＝An-1A=AAn-1，n>0符号串集合的正闭包A+=A1∪A2∪…∪An…符号串集合的自反闭包A*={ε}∪A+2.2.2文法的形式化定义如何实现语言结构的形式化描述？考虑一个句子——文法要素的提取分析：Thegraywolfwilleatthegoat〈谓语〉〈主语〉〈形容词〉〈名词〉〈动词〉〈直接宾语〉助动词〈句子〉动原冠词名词Thegraywolfwilleatthegoat〈冠词〉提取规则，写在黑板上句子

→

主语

谓语主语

→

冠词

形容词

名词谓语

→

动词

直接宾语动词

→

助动词

动词原形直接宾语

→

冠词

名词产生句子的规则——从产生语言的角度冠词

→

the形容词

→

gray助动词

→

will动词原形

→

eat名词

→

wolf名词

→

goat终结符号集VT={the，gray,wolf,will,eat,goat}非终结符号集VN={句子，主语，谓语，冠词，形容词，名词，动词，直接宾语，助动词，动词原形

}语法规则集P={句子→主语谓语，……}开始符号S=句子句子的语法组成

——终结符号集，非终结符号集，语法规则，开始符号文法G的形式定义文法G为一个四元组:

Ｇ=(ＶT，ＶN，Ｐ，Ｓ)ＶT：终结符(Terminal)集ＶN：非终结符(Variable)集，ＶT∩ＶN=Φ语法范畴——某个语言结构Ｓ：开始符号(StartSymbol)，S∈ＶN至少在产生式左侧出现一次文法G的形式定义Ｐ：产生式(Product)集合α→β，被称为产生式（定义式），读作：α定义为β。其中α∈(ＶT∪ＶN)+，且α中至少有ＶN中元素的一个出现。β∈(ＶT∪ＶN)*。α称为产生式α→β的左部(LeftPart)，β称为产生式α→β的右部(RightPart)。

句子主语

谓语

冠词

形容词

名词

谓语

the形容词

名词

谓语

thegray名词

谓语

thegraywolf谓语

thegraywolf

动词

直接宾语

thegraywolf助动词

动词原形

直接宾语

thegraywolfwill动词原形

直接宾语

thegraywolfwilleat直接宾语

thegraywolfwilleat

冠词

名词

thegraywolfwilleatthe名词

thegraywolfwilleatthegoat句子的派生（推导）___根据规则句子

thegraywolfwilleatthegoatthegraywolfwilleatthewolfthegraygoatwilleatthewolf符合语法且符合语义的句子仅是：

thegraywolfwilleatthegoat还可以“得出”其他的句子例

算术表达式的文法考虑简单算术表达式组成的语言递归定义——中缀表示标识符(id)（常数、变量）是表达式；表达式加一个表达式是表达式；表达式减一个表达式是表达式；表达式乘一个表达式是表达式；表达式除一个表达式是表达式；表达式加上括号后是表达式。例

算术表达式的文法考虑用式子表示这个定义标识符(id)是表达式表达式加一个表达式是表达式E→idE→E+E表达式减一个表达式是表达式E→E-E表达式乘一个表达式是表达式E→E*E表达式除一个表达式是表达式E→E/E表达式加上括号后是表达式E→(E)例

算术表达式的文法P:E→E+EE→E-EE→E*EE→E/EE→(E)E→idG=（{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)文法如何实现对语言的刻画？产生式很关键！产生式规定的一些变换E由第1个候选式可以变成E+EE+E中的第1个E由第2个候选式可以变成E*E，从而E+E变成E*E+E根据第4个候选式，E*E+E中的E都可以变成id:E*E+E变成id*E+Eid*E+E变成id*E+idid*E+id变成id*id+id也就是说，根据第4个候选式，E*E+E经3步变换变成id*id+id1E→E+E2E→E*E3E→(E)4E→id5E→E-E6E→E/E表示依据文法进行的变换EE+E （1）

E*E+E （2）

id*E+E （4）

id*E+id （4）

id*id+id （4）4E→id5E→E-E6E→E/EE可以变成E+EE+E中的第一个E变成E*EE*E+E变成id*E+Eid*E+E变成id*E+idid*E+id变成id*id+idE经5步变换变成id*id+id：E5id*id+id1E→E+E2E→E*E3E→(E)实质是从E开始依据产生式对所得串中的特定部分进行变换，不断获得新的串，最终得到目标变换的分析实质是从E开始依据产生式对所得串中的特定部分进行变换，不断获得新的串，最终得到目标

E*E

依据产生式E→E+EE*E+EαAβ依据产生式A→γαγβ直接推导与归约根据产生式对符号串进行变换的过程Ａ→γ是文法Ｇ的一个产生式，且α、β∈（ＶT∪ＶN）*，称αＡβ的直接推导/派生(Derive)出αγβ，也称αγβ直接归约(Reduce)为αＡβ。记为αＡβαγβ例：id+Eid+E*E（多步）推导/归约α0α1α2…αn记为α0nαn

(恰用n步)α0+αn

（至少一步）

α0*αn

（若干步:零步或多步）E5id*id+id推导/归约回顾EE+E （1）串中含有变量

id+E （4）串中含有变量

id+E*E （2）串中含有变量

id+id*E （4）串中含有变量

id+id*id （4）串中没有变量到此串中已经没有（语法）变量了，不能再推了——得到句子1E→E+E2E→E*E3E→(E)4E→id句型与句子EE+EE+E*EE4id+id*E定义:如果S*α，α∈(ＶT∪ＶN)*则称α是G产生的一个句型(SententialForm)E5id+id*id定义:如果S*x，且x∈ＶT*，则称x是G产生的一个句子(Sentence)文法G产生的语言定义： L(G)={x|S*xandx∈VT*}文法E→E+E|E*E|(E)|id可以派生出多少个句子？文法G的作用——语言的有穷描述以有限的规则描述无限的语言现象有限:产生式集合、终结符集合、非终结符集合无限：可以导出无穷多个句子（注：L也可是有穷）当语言是无限集时，能否用有限的规则来描述呢？回答是肯定的,只需使用文法的递归定义即可。例如，文法G1[<标识符>]：<标识符><字母>|<标识符><字母>|<标识符><数字><字母>A|B|…|Z<数字>0|1|2|…|9递归文法文法G2[E]：

E→E+E|E*E|E-E|E/E|(E)|id显然，G1，G2都是递归定义的。所谓递归定义，指在定义一个语法成分时，直接或间接地使用了语法成分自身。递归文法文法等价若L(G1)=L(G2)，则称文法