第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|wA，或wB}积A•B（或AB）={xy|xA,yB}A+=+A=A；A=A=；{}A=A{}=A符号串集合的方幂符号串集合A，定义A0={ε},A1=A,A2=AA,A3=A2A,…,An＝An-1A=AAn-1，n0符号串集合的正闭包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+EE→E-EE→E*EE→E/EE→(E)E→id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)文法如何实现对语言的刻画？产生式很关键！产生式规定的一些变换E由第1个候选式可以变成E+EE+E中的第1个E由第2个候选式可以变成E*E，从而E+E变成E*E+E根据第4个候选式，E*E+E中的E都可以变成id:E*E+E变成id*E+Eid*E+E变成id*E+idid*E+id变成id*id+id也就是说，根据第4个候选式，E*E+E经3步变换变成id*id+id1E→E+E2E→E*E3E→(E)4E→id5E→E-E6E→E/E表示依据文法进行的变换EE+E（1）E*E+E（2）id*E+E（4）id*E+id（4）id*id+id（4）4E→id5E→E-E6E→E/EE可以变成E+EE+E中的第一个E变成E*EE*E+E变成id*E+Eid*E+E变成id*E+idid*E+id变成id*id+idE经5步变换变成id*id+id：E5id*id+id1E→E+E2E→E*E3E→(E)实质是从E开始依据产生式对所得串中的特定部分进行变换，不断获得新的串，最终得到目标变换的分析实质是从E开始依据产生式对所得串中的特定部分进行变换，不断获得新的串，最终得到目标E*E依据产生式E→E+EE*E+EαAβ依据产生式A→γαγβ直接推导与归约根据产生式对符号串进行变换的过程Ａ→γ是文法Ｇ的一个产生式，且α、β∈（ＶT∪ＶN）*，称αＡβ的直接推导/派生(Derive)出αγβ，也称αγβ直接归约(Reduce)为αＡβ。记为αＡβαγβ例：id+Eid+E*E（多步）推导/归约α0α1α2…αn记为α0nαn(恰用n步)α0+αn（至少一步）α0*αn（若干步:零步或多步）E5id*id+id推导/归约回顾EE+E（1）串中含有变量id+E（4）串中含有变量id+E*E（2）串中含有变量id+id*E（4）串中含有变量id+id*id（4）串中没有变量到此串中已经没有（语法）变量了，不能再推了——得到句子1E→E+E2E→E*E3E→(E)4E→id句型与句子EE+EE+E*EE4id+id*E定义:如果S*α，α∈(ＶT∪ＶN)*则称α是G产生的一个句型(SententialForm)E5id+id*id定义:如果S*x，且x∈ＶT*，则称x是G产生的一个句子(Sentence)文法G产生的语言定义：L(G)={x|S*xandx∈VT*}文法E→E+E|E*E|(E)