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