第2章前后文无关文法和语言优秀课件.ppt

第2章前后文无关文法和语言第1页，本讲稿共52页2.1 文法及语言的表示文法及语言的表示u首先，我们确定一个概念：什么是语言？首先，我们确定一个概念：什么是语言？u据统计，目前在世界各地，人们所使用的语言达据统计，目前在世界各地，人们所使用的语言达27002700多种。多种。uWebsterWebster的定义：的定义：“为相当大地区的公众所懂得并使用的为相当大地区的公众所懂得并使用的话话，以及组成这些以及组成这些话话的方法的统一体的方法的统一体”u上述定义对于建立语言的数学理论的目的而言不够精确。上述定义对于建立语言的数学理论的目的而言不够精确。u所以，有人又将语言定义为：所以，有人又将语言定义为：“某一字母表上符号串（句子）的某一字母表上符号串（句子）的集合集合”u此定义仍需精确化。因为：此定义仍需精确化。因为：1 1）还应为所定义的句子）还应为所定义的句子提供一种结构性的描述（提供一种结构性的描述（语法规则语法规则）；2 2）最好能再提供一种手段，以便）最好能再提供一种手段，以便能准确地判别什么是该语言中的正确能准确地判别什么是该语言中的正确句子（句子（即识别方法、分析方法等即识别方法、分析方法等）。第2页，本讲稿共52页2.2 文法和语言的定义文法和语言的定义2.2.1 2.2.1 基本概念和术语基本概念和术语1。字母表（符号表、符号集）字母表（符号表、符号集）由若干元素（符号、字母）组成的有限非空集合。由若干元素（符号、字母）组成的有限非空集合。例：=a，b，c2。符号串符号串 用字母表中符号所组成的任何有限序列。用字母表中符号所组成的任何有限序列。例：a,aa,ac,abc，.符号串的长度符号串的长度 =符号串中所含符号的个数符号串中所含符号的个数例：例：aba的长度为的长度为3。记为：。记为：|aba|=3空串空串 不含任何符号的符号串，记为不含任何符号的符号串，记为 。显然，。显然，|=0。本课约定本课约定 用用A、B、C、等表示字母表或符号串集；用等表示字母表或符号串集；用a,b,c,S,T,U 等表示符号；用等表示符号；用s,t,u,x,y,z,等表示符号串。等表示符号串。任何程序语言都有自己的字母表。1.计算机语言:由符号“0”和“1”组成的字母表:=0，1 2.Pascal语言字母表：=AZ,az,09,+,-,*,/,:,”,;，.，,(,),3.C语言字母表：=AZ,az,09,+,-,*,/,_,&,:,”,;，.，?,(,),空格,!,#,%第3页，本讲稿共52页2.2.1 基本概念和术语（续）3.符号串的前（后）缀及子串符号串的前（后）缀及子串 设设,，x是符号串，若是符号串，若x=,则称则称 是是x的的子串子串；特别地，当；特别地，当=（=）时，称）时，称 是是x的的前（后）缀前（后）缀。（符号串s=banana）前 缀：,b,ba,ban,bana,banan,banana后 缀：banana,anana,nana,ana,na,a,子 串:banana,anana,banan,anan,4.符号串相等符号串相等：若x、y是集合上的两个符号串，则xy iff（当且仅当）组成x的每一个符号和组成y的每一个每一个符号依次相等。第4页，本讲稿共52页6.符号串集合的乘积运算符号串集合的乘积运算：令A、B为符号串集合，定义AB xy|xA,yB例：Aa,b,B=c,d,AB=？ac，ad，bc，bd 因为xxx，所以A=A=A5.符号串的联接符号串的联接：若x、y是定义在是上的符号串，且xXY，yYX，则x和y的联接 xyXYYX也是上的符号串。注意：一般xyyx，而xx2.2.1 基本概念和术语（续）第5页，本讲稿共52页8.8.符号串集合的闭包运算符号串集合的闭包运算：设A是符号串集合，定义 A A1 A2 A3 An 称为集合A的正闭包。A*A0 A称为集合A的闭包。例：A=x,y A？A*？7.符号串集合的幂运算符号串集合的幂运算：有符号串集合A，定义A0=,A1=A,A2=AA,A3=AAA,AnAn-1A=AAn-1 ，n0 x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A1 A2 A3,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,A0 A1 A2 A32.2.1 基本概念和术语（续）第6页，本讲稿共52页 为什么对符号、符号串、符号串集合以及它们的运为什么对符号、符号串、符号串集合以及它们的运算感兴趣？算感兴趣？若若A为某语言的基本字符集为某语言的基本字符集 Aa,b,z,0,1,9,+,_/,(,),=B为单词集为单词集 B=begin,end,if,then,else,for,则则B A*。语言的句子是定义在语言的句子是定义在B上的符号串。上的符号串。若令若令C为句子集合，则为句子集合，则C B*,程序程序 C形式语言：是一个字母表上按照某种规则构成的所有的串的集合，它用文法和自动机所描述的没有语义的语言。（形式语言是数学范畴）第7页，本讲稿共52页2.2.2 文法和语言的形式定义u我们从我们从“产生语言产生语言”的角度出发的角度出发,讨论文法和语言的形式定义。讨论文法和语言的形式定义。u产生语言产生语言指制定出有限条规指制定出有限条规则，借助它们就能产生出些语言的则，借助它们就能产生出些语言的句子。句子。u我们以几个英语句子构成的语言为例我们以几个英语句子构成的语言为例进行讨论。并设每个句子都是进行讨论。并设每个句子都是“主主-谓谓-宾宾”结构。结构。u语法规则见右。其中，每个用语法规则见右。其中，每个用括起来的部分是所要定义语括起来的部分是所要定义语言中的一个言中的一个语法实体（称为语语法实体（称为语法单位、语法结构、语法范畴、法单位、语法结构、语法范畴、语法变量等语法变量等）。）。“:=”是用于定是用于定义语法结构的符号，其含义（并读作）义语法结构的符号，其含义（并读作）“定义为定义为”.语法规则也称为产语法规则也称为产生式生式(Production):=:=the:=:=:=monkey:=banana:=eat:=has:=the:=a第8页，本讲稿共52页2.2.2 文法和语言的形式定义u现在，我们讨论如何用上述规则现在，我们讨论如何用上述规则推导推导出相应语言的全部出相应语言的全部句子句子。u推导推导 从语言最大的一个从语言最大的一个语法范畴语法范畴（本例中是（本例中是 ）开始，）开始，反复用语法规则中反复用语法规则中“:=:=”右侧的符号串取代其左侧符号，直到右侧的符号串取代其左侧符号，直到所得的符号串中不再含有可被替换所得的符号串中不再含有可被替换语法范畴语法范畴。每次替换称为一步。每次替换称为一步（直接）（直接）推导推导，并用符号，并用符号“”表示。例如，表示。例如，u我们首先用规则我们首先用规则进行第一步推导进行第一步推导(derivationderivation)，就可得到，就可得到 ，记为记为 u所得的符号串所得的符号串 含有两个含有两个语法范畴语法范畴，可对其中，可对其中任一个（例如对任一个（例如对 ）进行新的）进行新的推导推导（替换）：（替换）：u u重复上述过程，可得到一个推导序列（见下页）。重复上述过程，可得到一个推导序列（见下页）。第9页，本讲稿共52页用语法规则进行推导所得的推导序列推导步骤推导步骤 所用规则所用规则所得的符号串所得的符号串 1 2 3 the 4 the 5 the monkey 6 the monkey eat 7 the monkey eat a 8 the monkey eat a banana第10页，本讲稿共52页2.2.2 文法和语言的形式定义u从前面的推导看，从 出发，经8 8步推导步推导得到了一个英语句子。故前面的推导称为长度为长度为8 8的推导的推导。u若不关心推导的中间过程，可将从一符号串到另一符号串的推导用记号第11页，本讲稿共52页规则的简化表示规则的简化表示u在前面的语法规则定义中，有些语法范畴（如、）有若干条不同的规则来定义它，为简明起见，我们可以将它们写在同一个左部语法范畴下，将其定义值用符号“|”（读作或或）隔开。如、的定义规则可简记为uu:=monkey|banana:=monkey|bananauu:=eat|has:=eat|hasuu:=the|a:=the|a第12页，本讲稿共52页语法规则及其产生的语言u前面的语法规则可以产生16个不同的句子，由这16个句子组成的集合，就是该规则所定义（或所产生）的语言。u应指出，所产生的句子中，有些句子的含义是荒谬的（如 the banana eat a monkey和the banana eat the banana等）。然而，若不考虑语义，则我们就必须承认它们是语法上合法的句子。第13页，本讲稿共52页 定义1.文法GS=(VN，VT，P，S)VN：非终结符号集 VT：终结符号集 P：产生式或规则的集合 S：开始符号（识别符号）SVNVVN VT称为文法的字汇表规则：U xU VN,xV*非终结符是指在文法的语法范畴，出现在产生式P中，通常用大写字母或用大写字母或用“”括起来的符号串括起来的符号串表示，终结符是指不需要进一步定义的基本符号，通常用小写字母小写字母表示文法的定义文法的定义第14页，本讲稿共52页P=；0；1；9；E=；例：无符号整数的文法：G=（Vn，Vt，P，E）Vn,Vt =0,1,2,3,9第15页，本讲稿共52页 我 我我是 我是 我是大学生|你你|我我|他他 王民王民|大学生大学生|工人工人|英语英语 是是|学习学习|推导方法：推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。第16页，本讲稿共52页 定义：设文法GS=(VN，VT，P，S)，若UuP，x、yV*，则xUyV*若用规则Uu 的右部u替换U，即xuy V*,则称xuy是xUy的直接推导。xUy是xuy的直接规约。记为xUy=xuy(推导)和 xuy xUy(规约)推导的形式定义推导的形式定义=第17页，本讲稿共52页 1 1 0=当符号串已没有非终结符号时，推导就必须终止。例如：例如：G (1)；(2)(3)(4)0;0;(5)1;1;(13)9;9;第18页，本讲稿共52页 定义3：文法G，U0,U1,U2,，Un V+if v=U0=U1=U2=Unw(n0)则称v推导出w,或w规约到v，或v经+推导出w，或w+规约到v，分别记为：v w 或w v=例：=1 =1 0即 10=定义4：文法G，v，w V+if v w,或v=w，则v w则称v经*推导出w，或w经*规约到v，=*=第19页，本讲稿共52页 定义6：文法GS （1）句型句型：x是句型 S x,且xV*；（2）句子句子：x是句子 S x,且xVT*；（3）语言语言：L（GS）=x|xVT*,S x；+文法GS所产生的所有句子的集合 形式语言理论可以证明以下两点：（1）G L（G）；（2）L(G)G1，G2，Gn；已知文法，求语言，通过推导；已知语言，构造文法，无形式化方法，更多是凭经验。*语言的形式定义语言的形式定义第20页，本讲稿共52页例：abna|n1,构造其文法 G1S：SaBa,Bb|bB G2S：SaBa,Bb|Bb 定义7.G和G是两个不同的文法，若 L(G)=L(G),则G和G为等价文法。第21页，本讲稿共52页1.递归规则递归规则：规则右部有与左部相同的符号 对于 U xUy 若x=,即U Uy，左递归；若y=,即U xU，右递归；2.递归文法递归文法：文法G，存在U Vn if U=U,则G为递归文法；if U=U,则G为左递归文法；if U=U,则G为右递归文法；+2.2.4 文法的递归性文法的递归性第22页，本讲稿共52页4.递归文法的优点：可用有穷条规则，定义无穷语言 例：对于前面给出的无符号整数的文法是有递归文法，用13条规则就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条规则呢？!3.左递归文法的缺点：不能用自顶向下的方法来进行语法分析会造成死循环（后面将详细论述）第23页，本讲稿共52页2.3 句型的分析句型的分析u句型的分析句型的分析：构造一算法，用以判断所给的符号串是：构造一算法，用以判断所给的符号串是否为某文法的句型（句子）否为某文法的句型（句子）u常见分析方法有常见分析方法有自顶向下分析自顶向下分析和和自底向上分析自底向上分析两类；两类；u自顶向下自顶向下 从开始符出发试图推导出给定的符号串；从开始符出发试图推导出给定的符号串；u自底向上自底向上 推导的逆过程（称归约）：从已给的符号串出发，推导的逆过程（称归约）：从已给的符号串出发，试图将其归约为开始符。试图将其归约为开始符。第24页，本讲稿共52页2.3.1 规范推导和规范归约规范推导和规范归约u对于一文法而言，从开始符到某句型的对于一文法而言，从开始符到某句型的推导过程可能不唯一推导过程可能不唯一。例如，文。例如，文法法GE中从中从 E 到到 i+i*i 的推导有：的推导有：(1)E E+T E+T*F T+T*F T+T*i F+T*i i+T*i i+F*ii+i*i(2)E E+T T+T F+T i+T i+T*F i+F*F i+i*F i+i*F i+i*i(3)E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i(4)第25页，本讲稿共52页规范推导u最左（右）推导最左（右）推导：在推导序列的每一步直接推导中，被替换的在推导序列的每一步直接推导中，被替换的总是当前句型中最左（右）的非终结符。总是当前句型中最左（右）的非终结符。u形式上，形式上，从符号串从符号串 到符号串到符号串 的推导序列的推导序列u *xUy xuy*总有总有 x VT*(y VT*)时，时，称为称为最左（右）推导最左（右）推导u定义：最左（右）推导所得句型称为定义：最左（右）推导所得句型称为左（右）句型；左（右）句型；最右推导最右推导称为称为规范推导规范推导；右句型右句型称为称为规范句型规范句型。最左推导：若符号串中有两个以上的非终结符时，先推左边的。最右推导：若符号串中有两个以上的非终结符时，先推右边的。最右推导称为规范推导最右推导称为规范推导第26页，本讲稿共52页句子、句型的推导方法u每个每个句子句子都有相应的最左和最右推导，因此，都有相应的最左和最右推导，因此，句子即是句子即是左句型左句型也是也是右句型右句型（规范句型）（规范句型）u并不是每个句型都有最左和最右推导并不是每个句型都有最左和最右推导u例如，例如，E E+E+i*T E+i*T即不是左句型，也不是右句型即不是左句型，也不是右句型u对于给定的符号串对于给定的符号串w，采用，采用自顶向下自顶向下的分析来判断的分析来判断w是否为是否为L(GS)的句子的常见方法是：的句子的常见方法是：试图建立从开始符试图建立从开始符 S到到w最左推导最左推导:S*w u显然，每步推导时，对应于最左非终结符相应的产生式可能会有显然，每步推导时，对应于最左非终结符相应的产生式可能会有多个，若无特殊的办法，只能一个一个地试探。因此，推导过程多个，若无特殊的办法，只能一个一个地试探。因此，推导过程可能是可能是带回溯带回溯的的。u为提高效率，就应尽量避免回溯为提高效率，就应尽量避免回溯第27页，本讲稿共52页自底向上的语法分析自底向上的语法分析u就是从已给的符号串就是从已给的符号串w出发，试图以相反的方向为出发，试图以相反的方向为w建立一个规范建立一个规范推导，最终得到文法的开始符。推导，最终得到文法的开始符。u推导的逆过程称作推导的逆过程称作归约归约，它是把当前的符号串，它是把当前的符号串中的构成文法某个中的构成文法某个产生式产生式A右部的子串右部的子串 替换成产生式的左部符号替换成产生式的左部符号A，得到一个新的，得到一个新的符号串符号串 A 。这样的一步动作，称为进行了一步。这样的一步动作，称为进行了一步归约归约。u例如，符号串例如，符号串F+i*i中的中的F可按产生式可按产生式TF归约为归约为T，从而得到新的，从而得到新的符号串符号串T+i*i。u若从给定的符号串若从给定的符号串w出发，一步步地将其归约，最终得到文法的开始符出发，一步步地将其归约，最终得到文法的开始符号，则说明号，则说明w是该文法定义的一个句子。归约成功，否则，归约失败。是该文法定义的一个句子。归约成功，否则，归约失败。u若归约的每一步都归约的是当前符号串中最左边的某产生式的右部，若归约的每一步都归约的是当前符号串中最左边的某产生式的右部，则称该归约是则称该归约是规范归约规范归约（即（即最左归约最左归约）。）。u规范归约是规范推导的逆过程规范归约是规范推导的逆过程。第28页，本讲稿共52页符号串i+i*i的归约过程由上表可以看出，归约过程是由上表可以看出，归约过程是最左最左归约，它恰好是归约，它恰好是规范推导规范推导的逆过程的逆过程。这正是把最左归约定义为规范归约的原因。这正是把最左归约定义为规范归约的原因。第29页，本讲稿共52页关于归约的一点说明u注意，前面例子中归约的第五步中，当前的符号串为注意，前面例子中归约的第五步中，当前的符号串为 E+T*i，除了，除了可将可将i归约成归约成F外，还可将外，还可将E+T或或T归约成归约成E，分别得到符号串，分别得到符号串E*i和和E+E*i。但是，若真按这两个方案进行归约，则当我们把其归约成。但是，若真按这两个方案进行归约，则当我们把其归约成E*E或或E+E*E时，就再也归约不下去了。这就告诉我们在第五步时，唯时，就再也归约不下去了。这就告诉我们在第五步时，唯一正确的归约是将一正确的归约是将i归约为归约为F，也就是说，也就是说，i是唯一可被归约的最左子串。是唯一可被归约的最左子串。u那么，对于规范归约的每一步，如何确定符号串中的当前应被归约的那么，对于规范归约的每一步，如何确定符号串中的当前应被归约的最左子串呢？最左子串呢？第30页，本讲稿共52页2.3.2 2.3.2 语法树和二义性语法树和二义性u语法树用于直接地描述一个句型右句子的语法结构语法树用于直接地描述一个句型右句子的语法结构u语法树是一有向树（连通的）语法树是一有向树（连通的）1）有且仅有一个无任何前驱的结点，称为根）有且仅有一个无任何前驱的结点，称为根（S）；）；2）除根外，每个结点恰有一个直接前驱；）除根外，每个结点恰有一个直接前驱；3）对于任一结点）对于任一结点m，从根到从根到m可达可达;4)每个结点的后继是有序的（从左到右）每个结点的后继是有序的（从左到右）设设G=(VN,VT,P,S)是一文法，则满足下述条件的树称为语法树：是一文法，则满足下述条件的树称为语法树：1）每个结点有一标记）每个结点有一标记X，X V；2）根的标记为）根的标记为S（开始符）；（开始符）；3）若结点）若结点X有后继，则有后继，则X VN；4）A有有k个后继，自左至右为个后继，自左至右为X1,X2,Xk，则，则A X1X2Xk P第31页，本讲稿共52页语法树的性质及实例语法树的所有叶结点自左至右语法树的所有叶结点自左至右排列构成了文法排列构成了文法G的一个句型的一个句型对一语法树而言，其构造过对一语法树而言，其构造过程不同对应了不同的推导程不同对应了不同的推导（归约）过程（归约）过程例如，文法例如，文法GE的句型的句型 i+i*i相应的语法树见右图相应的语法树见右图。EE+TTFiT*FFii第32页，本讲稿共52页u存在这样的文法存在这样的文法G，其某个句子，其某个句子w L(G),可对应结构不同的语法树，即可对应结构不同的语法树，即w对应了多个不同的最左（右）推导，这类文法称为对应了多个不同的最左（右）推导，这类文法称为二义性文法二义性文法二义性文法二义性文法。u例如，例如，G3E：EE+E|E*E|(E)|i 的句型的句型i+i*ii+i*i及文法及文法uCif B then C|if B then C else CC S的句型：的句型：if B1 then if B2 then S1 else S2u上面两个句型均有两个不同的语法推导树（见下页），所以，它上面两个句型均有两个不同的语法推导树（见下页），所以，它们是二义性文法们是二义性文法文法的二义性第33页，本讲稿共52页EEEEE+*iiiEEEEE+*iiiif B1 then C else C S1 S2Cif B2 then CCif B1 then CS1 S2if B1 then C else C二义性语法的例子第34页，本讲稿共52页关于二义性文法u应指出应指出，二义性，二义性是一种常见的语法现象，然而，对于编译程序而言，是一种常见的语法现象，然而，对于编译程序而言，二义性文法二义性文法是是有害有害的。的。u为解决二义性文法带来的不确定性问题，通常的方法一是为解决二义性文法带来的不确定性问题，通常的方法一是修改文法修改文法，例如，文法例如，文法G3可用本章（可用本章（P20(2.2)式式）定义的文法）定义的文法G2E取代，而取代，而G2不是二义性的不是二义性的。u二是二是利用附加条件利用附加条件。例如，例如，i+i*ii+i*i的的归约过程中，若程中，若规定定*比比+优先先级高，高，则可可强制性地制性地让系系统先按先按E*EE*E进行行归约，而不是先按，而不是先按E+EE+E进行行归约；又又比如，若比如，若强制规定强制规定elseelse只能和距其最近的尚未被匹配的只能和距其最近的尚未被匹配的thenthen进行匹进行匹配，就可解决配，就可解决elseelse悬空的问题。悬空的问题。第35页，本讲稿共52页2.3.3 短语和句柄短语和句柄u问题问题:在自底向上在自底向上(简记为简记为)的语法分析中的语法分析中,对于对于每一步直接归约每一步直接归约,应如何正确地确定当前句型中应被归应如何正确地确定当前句型中应被归约的约的最左子串最左子串?u考虑文法考虑文法G G2 2EE的句型的句型=E+T*F+i=E+T*F+i,从开始符从开始符E E 推导出推导出 的语法树见右图的语法树见右图u该树中含有若干子树该树中含有若干子树,如如T T(2)(2)为根的子树对应的为根的子树对应的叶结点为叶结点为T T(3)(3)*F*F(3),(3),由于它是一直接子树由于它是一直接子树,文法中必文法中必有产生式有产生式T-T*FT-T*F;因此因此,称称T*FT*F是句型是句型 相对于产相对于产生式生式T-T*FT-T*F的的直接短语直接短语.同理同理,F F(1)(1)对应的对应的直接短语直接短语为为i i.u以以E E(1)(1)为根的子树相应的叶结点为为根的子树相应的叶结点为 E E(2)(2)+T+T(3)(3)*F*F(3)(3),所以所以,称为句型称为句型 相对于非终结符相对于非终结符E E 的的短语短语.同理同理,i i是相对于是相对于T T(1)(1)的的短语短语E EE E(1)(1)+T+T(1)(1)E E(2)(2)+T +T(2)(2)T T(3)(3)*F *F(3)(3)F F(1)(1)i i第36页，本讲稿共52页短语、直接短语及句柄的定义短语、直接短语及句柄的定义u例如，对句型例如，对句型=E+T*F+i=E+T*F+i，由定义，有：由定义，有：(1)E(1)E*E+T+i(E+T+i(=E+,A=T,=E+,A=T,=+i)=+i)及及T TT*F(=T*F(=),),故故T*FT*F是是 相对于产生式相对于产生式T-T*FT-T*F的的直接短语直接短语;(2)E(2)E*E+T*F+F F E+T*F+F Fi,i,i i是是 相对于产生式相对于产生式F-iF-i的的直接短语直接短语;(3)E(3)E*E+i E+i与与 E E+E+T*F,E+T*F,E+T*FE+T*F是是相对于非终结符相对于非终结符E E的的短语短语;(4)E(4)E*E E及及E E*E+T*F+i(=E+T*F+i(=),),是是 相对于相对于E E的的短语短语注注:由定义可知由定义可知,直接短语也是短语直接短语也是短语,但短语不一定是直接短语但短语不一定是直接短语.第37页，本讲稿共52页归约时被替换子串的选择u从句型=E+T*F+i=E+T*F+i的语法树可知,E+T绝不是它的一个直接短语,因为虽然E-E+T是G2的一个产生式,但不存在从E到E*F+i的推导,所以,当判断一符串是否为某一句型的短语时,须检查定义2.8的两个条件是否同时满足.u采用采用 分析分析时,每步每步归约就是将一个就是将一个产生式生式右部右部替替换其其左部左部,也就是把也就是把该句型句型的的语法法树中的中的一棵直接子一棵直接子树的末端的末端结点剪去点剪去.即每次即每次归约的符号串必是当前的符号串必是当前句型的一个直接短句型的一个直接短语.u但是但是,对一句型而言对一句型而言,其其直接短语可能不唯一直接短语可能不唯一.为了让分析能够机械地进行为了让分析能够机械地进行,我们只我们只考虑规范归约考虑规范归约(最左归约最左归约),),即归约过程替换的是归左直接短语即归约过程替换的是归左直接短语.u我们以L(G2)的句子i+i*i+i为例,给出其最右推导(规范归约的逆过程),来说明每次规范归约的子符号串第38页，本讲稿共52页句柄的定义句柄的定义uEE+T E+F E+i E+T+i E+T*F+i E+T*i+i E+F*i+i E+i*i+i T+i*i+i F+i*i+i i+i*i+i u上面的推导过程的逆过程就是规范归约的过程。从其上面的推导过程的逆过程就是规范归约的过程。从其逆过程可看出，每步归约的均是逆过程可看出，每步归约的均是当前句型当前句型的的最左直最左直接短语接短语（最左直接子树的叶结点）。我们把它称（最左直接子树的叶结点）。我们把它称为为当前句型当前句型的的句柄句柄。u定义定义2.92.9 一个句型的最左直接短语称为此句型的一个句型的最左直接短语称为此句型的句柄句柄。u问题问题：如何确定一规范句型的句柄？句柄应被归如何确定一规范句型的句柄？句柄应被归约成哪个非终结符？约成哪个非终结符？EE +TE +TT *FTFiFFiii1234567891011第39页，本讲稿共52页(3)子树与短语 子树：语法树中的某个结点（子树的根）连同它向下派生的部分所组成。某子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对于该子树根的短语。定理定理定义：简单子树：仅有父子两代的子树。第40页，本讲稿共52页 句柄：该语法树的最左简单子树的末端结点从左到右排列的字符串是该句型的句柄。某简单子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对于该简单子树根的直接短语。定理定理 只需画出句型的语法树，然后根据子树找 短语短语直接短语直接短语句柄句柄。第41页，本讲稿共52页句型推导过程句型语法树的生长过程 由推导构造语法树由推导构造语法树1从识别符号开始，自左向右建立推导序列。由根结点开始，自上而下建立语法树。语法树与推导第42页，本讲稿共52页 由语法树构造推导由语法树构造推导2自上而下地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次规约。从句型开始，自右向左地逐步进行规约，建立推导序列。第43页，本讲稿共52页2.4 2.4 文法的化简与改造文法的化简与改造2.4.1 无用符号和无用产生式的删除无用符号和无用产生式的删除设设G=(VN,VT,P,S)是一文法是一文法,X VN VT,X称为是称为是有用的有用的,若若X至少出现在一个至少出现在一个句子的推导过程中句子的推导过程中,即即X满足满足:(1)存在存在,V*,有有 S*X(2.12)(2)存在存在w VT*,使使 X *w(2.13)否则否则,称称X是是无用的无用的.若一产生式含有无用符号若一产生式含有无用符号,则此产生式称为则此产生式称为无用产生式无用产生式.u无用产生式给语法分析带来了许多麻烦无用产生式给语法分析带来了许多麻烦,应予以删除应予以删除.第44页，本讲稿共52页消除无用产生式的算法消除无用产生式的算法算法算法2.1 将文法将文法G=(VN,VT,P,S),改造为改造为G1=(VN,VT,P,S),使使得得L(G)=L(G1)(1)置置VN,P为空为空;(2)对于对于P中每个产生式中每个产生式A,若若 (VN VT)*,则将则将A加入加入VN中中;(3)重复重复(2),直到直到VN不再增大不再增大;(4)对于每个对于每个A P,若若 (VN VT)*,则置则置A 于于P中中.算法算法2.2 任给文法任给文法G=(VN,VT,P,S),构造构造G=(VN,VT,P,S),使使 x (VN VT),(VN VT)*,有有 S*x(1)置置VT为空为空,VN=S;(2)对于对于 A P,若若 A VN则置则置 中所有非终结符入中所有非终结符入VN,所有终结符入所有终结符入VT;(3)重复重复(2),直到直到V不再增大不再增大;(4)令令P=A|A P,(VN VT)*,A VN第45页，本讲稿共52页消除无用产生式的例子消除无用产生式的例子例例 G=(S,U,V,W,a,b,c,P,S),其中其中,P:SaS|W|U Ua V bV|ac W aW现对现对G执行执行算法算法2.1:1.由由Ua 和和Vac右部都是终结符右部都是终结符,VN=U,V;2.对于对于SU,由由U VN 有有VN=S,U,V;此外再无可放入此外再无可放入VN的符号的符号;P1为为S aS|U Ua V bV|ac现对现对G1执行执行算法算法2.2:1.置置VN=S;2.由由SU及及U a将将U及及a分别放入分别放入VN(=S,U)和和VT(=a)中中;3.此外此外,VN 和和VT不再增大不再增大;4.最后结果为最后结果为:S aS|U Ua注意注意,在删除无用符和无用产生式时在删除无用符和无用产生式时,应先执行算法应先执行算法2.12.1再执行算法再执行算法2.2,2.2,就可得到就可得到“干净干净”的文法的文法;若若先执行算法先执行算法2.2,2.2,再执行算法再执行算法2.12.1所所得文法不一定得文法不一定“干净干净”第46页，本讲稿共52页2.4.2-产生式的消除u-产生式产生式是指右部为一空符号串是指右部为一空符号串 的产生式。因为某些语法分析算法要求的产生式。因为某些语法分析算法要求不含不含，此时应消除之，此时应消除之u若一语言不含若一语言不含（即（即L(G),则可将其完全消除；则可将其完全消除；u若若L(G),则可将文法改造为只有开始符则可将文法改造为只有开始符S可推导出可推导出(即即S P),而而且且,S不出现在任何产生式的右部不出现在任何产生式的右部,此外再无其它此外再无其它-产生式产生式.u本节中的本节中的算法算法2.3可用于找出所有可推导出可用于找出所有可推导出 的非终结符的非终结符W=A|A*,A VNu执行完执行完算法算法2.3,通过检验通过检验S W与否可知与否可知L(G)与否与否;u算法算法2.4可消除可消除L(G)情况时的情况时的-产生式产生式;u算法算法2.5可消除可消除L(G)情况时的情况时的-产生式产生式.第47页，本讲稿共52页2.5 文法和语言的文法和语言的ChomskyChomsky分类分类u文法的四元组表示是由文法的四元组表示是由N.ChomskyN.Chomsky于于19561956年描述形式语言时给出的。他还对年描述形式语言时给出的。他还对产生式的形式给予不同的限制而定义了产生式的形式给予不同的限制而定义了四类基本文法四类基本文法。u0 0型文法型文法:若若P P中任一产生式都有一般形式中任一产生式都有一般形式 V+V+V*V*且对且对，不加不加任何限制，则称任何限制，则称G G为为0 0型文法型文法（短语结构文法，记为短语结构文法，记为PSG:Phrase Structure PSG:Phrase Structure GrammarGrammar)。由。由0 0型文法生成（或者说：定义）的语言称为型文法生成（或者说：定义）的语言称为0 0型型（递归可枚举递归可枚举）语言语言。它可由。它可由图灵图灵（TuringTuring）机机识别。识别。u例如：例如：S SACaB CaACaB CaaaC CBaaC CBDB CBDB CBE aDE aDDa ADDa ADAC aEAC aEEa AEEa AE 就是一个就是一个0 0型文法型文法，它所产生的语言为，它所产生的语言为对于程序设计语言来，对于程序设计语言来，0 0型文法型文法有很大的随意性有很大的随意性，还须加以限制，还须加以限制第48页，本讲稿共52页1 1型文法和语言型文法和语言u1 型文法定义形式：型文法定义形式：G的每个产的每个产生式形为生式形为且满足且满足：|,V+则则G是是1型文法型文法(前后文有关前后文有关)文法文法，记，记为为CSG(Context Sensitive Grammar)。u1型文法型文法产生的语言称为产生的语言称为前后文有前后文有关语言关语言CSL，它可由，它可由线性限界自线性限界自动机动机识别。识别。u注注：根据定义，含有根据定义，含有 产生式的产生式的文法不是文法不是1型文法。由于实际型文法。由于实际需要，我们将需要，我们将-产生式作为产生式作为1型文法的特例而接受之。型文法的特例而接受之。u例例 文法文法G：S|A AaABC AabC CBBC bBbb bCbc cCccu因因G含有含有-产生式产生式，所以它不，所以它不是一个严格意义下的是一个严格意义下的1型文法。型文法。它所产生的语言为它所产生的语言为第49页，本讲稿共52页2 2型文法和语言型文法和语言u若一若一1型文法型文法G中所有产生式具有形式中所有产生式具有形式:A V+A VN 则则称称G为为2型型(前后文无关前后文无关)文法文法，记为，记为CFG(Context Free Grammar)。u2型文法产生的语言称为型文法产生的语言称为前后文无关语言前后文无关语言CFL，它可由，它可由下推自下推自动机动机识别。识别。u2型文法是型文法是语法分析语法分析的基础的基础u若允许若允许-产生式存在，则产生式存在，则CFG产生式形式为产生式形式为 A V*A VN u例：例：GS=(S,a,b,SaSb Sab,S)产生产生的语言为的语言为第50页，本讲稿共52页3 3型文法和语言型文法和语言u若一若一2型文法型文法G中仅含有形如中仅含有形如AaB Aa 的产生式，其中的产生式，其中 A,B VN,a VT 则称则称G为为右线性文法右线性文法。u类似地，若类似地，若G中仅含有形如中仅含有形如 ABa Aa的产生式，则称的产生式，则称G为为左线性文左线性文法法。u通常，把通常，把左线性文法左线性文法和和右线性文法右线性文法都称为都称为3型文法型文法（正规文法正规文法）u3型文法型文法产生的语言称为产生的语言称为3型（型（正规正规）语言）语言，它可由，它可由有限自动机有限自动机识别。识别。正规语言正规语言可用可用正规表达式正规表达式表示。表示。u注：注：若一文法即含若一文法即含左线性左线性又含又含右线性产生式右线性产生式，则它，则它不一定是不一定是3型文法型文法！u3型文法型文法还可拓广定义为还可拓广定义为 AB A （VT+）第51页，本讲稿共52页四类语言之间的关系由各类文法的定义可知，由各类文法的定义可知，3 3型语言一定是型语言一定是2 2型语言，而反之不型语言，而反之不一定成立；同理，一定成立；同理，2 2型语言是型语言是1 1型的也是型的也是0 0型的，反之不真。型的，反之不真。若把各类语言视为语言族若把各类语言视为语言族L LK K ，K=0,1,2,3 K=0,1,2,3 则它们之间有真包含关则它们之间有真包含关系：系：第52页，本讲稿共52页