您好,欢迎访问三七文档
当前位置:首页 > 建筑/环境 > 工程监理 > 第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,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为一个四元组:G=(VT,VN,P,S)VT:终结符(Terminal)集VN:非终结符(Variable)集,VT∩VN=Φ语法范畴——某个语言结构S:开始符号(StartSymbol),S∈VN至少在产生式左侧出现一次文法G的形式定义P:产生式(Product)集合α→β,被称为产生式(定义式),读作:α定义为β。其中α∈(VT∪VN)+,且α中至少有VN中元素的一个出现。β∈(VT∪VN)*。α称为产生式α→β的左部(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→γαγβ直接推导与归约根据产生式对符号串进行变换的过程A→γ是文法G的一个产生式,且α、β∈(VT∪VN)*,称αAβ的直接推导/派生(Derive)出αγβ,也称αγβ直接归约(Reduce)为αAβ。记为αAβαγβ例: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*α,α∈(VT∪VN)*则称α是G产生的一个句型(SententialForm)E5id+id*id定义:如果S*x,且x∈VT*,则称x是G产生的一个句子(Sentence)文法G产生的语言定义:L(G)={x|S*xandx∈VT*}文法E→E+E|E*E|(E)
本文标题:第2章-1-文法的形式定义
链接地址:https://www.777doc.com/doc-2154673 .html