第二章前后文无关文法和语言

1、第二章第二章 u 在在20世纪世纪50年代，年代，N.Chomsky首先对语言首先对语言的描述问题进行了探讨。他提出了一种用来描的描述问题进行了探讨。他提出了一种用来描述语言的数学系统，并以此定义了四类性质不述语言的数学系统，并以此定义了四类性质不同的语言，称为同的语言，称为语言（文法）的语言（文法）的ChomskyChomsky分类分类。u 人们把用一组数学符号和规则来描述语言的方人们把用一组数学符号和规则来描述语言的方式称为形式描述，把所用的数学符号和规则称式称为形式描述，把所用的数学符号和规则称为为形式语言形式语言。u 目前，目前，形式语言与自动机理论形式语言与自动机理论已成为计算机科已

2、成为计算机科学中的一个重要分支。学中的一个重要分支。u 本章将初步介绍形式语言中的某些基本概念和本章将初步介绍形式语言中的某些基本概念和知识，重点是与编译技术密切相关的一些术语知识，重点是与编译技术密切相关的一些术语和概念，诸如和概念，诸如文法文法、语言语言、句子句子、句型句型、短语短语、句柄句柄以及以及句型分析句型分析等。等。2.1 u 首先，我们确定一个概念：什么是语言？首先，我们确定一个概念：什么是语言？u 据统计，目前在世界各地，人们所使用的语言达据统计，目前在世界各地，人们所使用的语言达27002700多种。多种。u WebsterWebster的定义：的定义：“为相当大地区的公众所

3、懂得并使用的为相当大地区的公众所懂得并使用的话话，以及组成这些，以及组成这些话话的方法的统一体的方法的统一体”u 上述定义对于建立语言的数学理论的目的而言不够精确。上述定义对于建立语言的数学理论的目的而言不够精确。u 所以，有人又将语言定义为：所以，有人又将语言定义为：“某一字母表上符号串（句某一字母表上符号串（句子）的集合子）的集合”u 此定义仍需精确化。因为：此定义仍需精确化。因为：1 1）还应为所定义的句子）还应为所定义的句子提供一种结构性的描述（提供一种结构性的描述（语法规则语法规则）；2 2）最好能再提供一种手段，以便）最好能再提供一种手段，以便能准确地判别什么是该语言能准确地判别什

4、么是该语言中的正确句子（中的正确句子（即识别方法、分析方法等即识别方法、分析方法等）。2.2 文法和语言的定义文法和语言的定义2.2.1 2.2.1 基本概念和术语基本概念和术语1。字母表（符号表、符号集）字母表（符号表、符号集） 由若干元素（符号、字母）组成的有限非由若干元素（符号、字母）组成的有限非空集合。空集合。例：=a，b，c2。符号串符号串 用字母表中符号所组成的任何有限序列。用字母表中符号所组成的任何有限序列。 例：a, aa, ac, abc，.符号串的长度符号串的长度 = 符号串中所含符号的个数符号串中所含符号的个数例：例：aba的长度为的长度为3。记为：。记为：|aba|=3

5、空串空串 不含任何符号的符号串，记为不含任何符号的符号串，记为 。显然，。显然，| |= 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, +, -, *, /, ,_,&

6、amp;, , ,:,”,;，.，?, (, ), , ,空格,!,#,% 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是集合上的两个符号串，则x

7、y iff（当且仅当）组成x的每一个符号和组成y的每一个每一个符号依次相等。 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 基本概念和术语（续）8.8.符号串集合的闭包运算符号串集合的闭包运算：设A是符号串集合，定义 A A1 A2 A3 An 称为集合A的正闭包。 A* A0 A称为集合A的闭包

8、。例：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 基本概念和术语（续） 为什么对符号、符号串、符号串集合以及它们为什么对符号、符号串、符号串集合以及它们的运算感兴趣？的运算感兴趣？若若A为某语言的基本字符集为某语言的基本字符集 Aa,b,z,0,1,9, +,_/, (

9、, ), =B为单词集为单词集 B =begin, end, if, then,else,for, 则则B A* 。语言的句子是定义在语言的句子是定义在B上的符号串。上的符号串。若令若令C为句子集合，则为句子集合，则C B * , 程序程序 C形式语言：是一个字母表上按照某种规则构成的所有的串的集合，它用文法和自动机所描述的没有语义的语言。（形式语言是数学范畴）2.2.2 u我们从我们从“产生语言产生语言”的角度的角度出发出发,讨论文法和语言的形式讨论文法和语言的形式定义。定义。u产生语言产生语言指制定出有限条指制定出有限条规则，借助它们就能产生出规则，借助它们就能产生出些语言的句子。些语言的

10、句子。u我们以几个英语句子构成的我们以几个英语句子构成的语言为例进行讨论。并设每语言为例进行讨论。并设每个句子都是个句子都是“主主-谓谓-宾宾”结结构。构。u语法规则见右。其中，每个语法规则见右。其中，每个用用括起来的部分是所要定括起来的部分是所要定义语言中的一个义语言中的一个语法实体语法实体（称为语法单位、语法结构、（称为语法单位、语法结构、语法范畴、语法变量等语法范畴、语法变量等）。）。“:=”是用于定义语法结构是用于定义语法结构的符号，其含义（并读作）的符号，其含义（并读作）“定义为定义为”.语法规则也称为语法规则也称为产生式产生式(Production):= := the :=:=:=

11、monkey:=banana:=eat:=has:= the:= a2.2.2 u 现在，我们讨论如何用上述规则现在，我们讨论如何用上述规则推导推导出相应语言的全部出相应语言的全部句子句子。u推导推导 从语言最大的一个从语言最大的一个语法范畴语法范畴（本例中是（本例中是 ）开始，反复用语法规则中开始，反复用语法规则中“:=:=” ” 右侧的符号串取代其左侧右侧的符号串取代其左侧符号，直到所得的符号串中不再含有可被替换符号，直到所得的符号串中不再含有可被替换语法范畴语法范畴。每。每次替换称为一步（直接）次替换称为一步（直接）推导推导，并用符号，并用符号“”表示。例如，表示。例如，u 我们首先用规

12、则我们首先用规则进行第一步推导进行第一步推导( (derivationderivation) )，就可得到，就可得到 ，记为记为 u 所得的符号串所得的符号串 含有两个含有两个语法范畴语法范畴，可，可对其中任一个（例如对对其中任一个（例如对 ）进行新的）进行新的推导推导（替换）：（替换）：u u 重复上述过程，可得到一个推导序列（见下页）。重复上述过程，可得到一个推导序列（见下页）。用语法规则进行推导所得的推导序列推导步骤推导步骤 所用规则所用规则所得的符号串所得的符号串 1 2 3 the 4 the 5 the monkey 6 the monkey eat 7 the monkey ea

13、t a 8 the monkey eat a banana2.2 .2 u 从前面的推导看，从出发，经8 8步推导步推导得到了一个英语句子。故前面的推导称为长度为长度为8 8的推导的推导。u 若不关心推导的中间过程，可将从一符号串到另一符号串的推导用记号名词冠词动词句子步的推导记为例如上例中经过表示monkeythe5,u 在前面的语法规则定义中，有些语法范畴（如、）有若干条不同的规则来定义它，为简明起见，我们可以将它们写在同一个左部语法范畴下，将其定义值用符号“ ”（读作）隔开。如、 、 的定义规则可简记为u 前面的语法规则可以产生16个不同的句子，。u 应指出，所产生的句子中，有些句子的含

14、义是荒谬的（如 the banana eat a monkey和the banana eat the banana等）。然而，若不考虑语义，则我们就必须承认它们是语法上合法的句子。 定义1. 文法GS=(VN，VT，P，S) VN ：非终结符号集 VT ：终结符号集 P：产生式或规则的集合 S：开始符号（识别符号） SVNVVN VT称为文法的字汇表规则：U xU VN, xV*非终结符是指在文法的语法范畴，出现在产生式P中，通常用大写字母或用大写字母或用“”括起来的符号串括起来的符号串表示，终结符是指不需要进一步定义的基本符号，通常用小写字母小写字母表示文法的定义文法的定义P = ； ； ；

15、 0； 1； 9；E = ；例：无符号整数的文法：G=（Vn，Vt，P，E）Vn, Vt = 0,1,2,3,9 我 我我是 我是 我是大学生 | 你你| |我我| |他他 王民王民| |大学生大学生| |工人工人| |英语英语 是是| |学习学习 | 推导方法：推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。 定义：设文法GS=(VN，VT，P，S)，若UuP，x、yV* ，则xUyV*若用规则Uu 的右部u替换U，即xuy V*, 则称xuy是xUy的直接推导。xUy是xuy的直接规约。记为xUy=xuy(推导) 和 xuy xUy(规

16、约)推导的形式定义推导的形式定义= 1 1 0= 当符号串已没有非终结符号时，推导就必须终止。例如：例如：G (1) ； (2) (3) (4) 0;0;(5) 1;1; (13) 9;9; 定义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，= *= 定义6：文法GS （1）句型句型：x是句型 S

17、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； 已知文法，求语言，通过推导； 已知语言，构造文法，无形式化方法，更多是凭经验。*语言的形式定义语言的形式定义例：abna|n1,构造其文法 G1S： SaBa, Bb|bB G2S： SaBa, Bb|Bb 定义7. G和G是两个不同的文法，若 L(G) = L(G) , 则G和G为等价文法。1.递归规则递归规则：规则右部有与左部相同的符号 对于 U xUy

18、 若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 文法的递归性文法的递归性4. 递归文法的优点：可用有穷条规则，定义无穷语言 例：对于前面给出的无符号整数的文法是有递归文法，用13条规则就可以定义出所有的无符号整数。若不用递归文法，那将要用多少条规则呢？!3. 左递归文法的缺点：不能用自顶向下的方法来进行语法分析会造成死循环（后面将详细论述）2.3 句型的分析句型的分析u 句型的分析句型的分析：构造一算法，用以判断所给的符

19、号串：构造一算法，用以判断所给的符号串是否为某文法的句型（句子）是否为某文法的句型（句子）u 常见分析方法有常见分析方法有自顶向下分析自顶向下分析和和自底向上分析自底向上分析两类；两类；u 自顶向下自顶向下 从开始符出发试图推导出给定的符号串；从开始符出发试图推导出给定的符号串；u 自底向上自底向上 推导的逆过程（称归约）：从已给的符推导的逆过程（称归约）：从已给的符号串出发，试图将其归约为开始符。号串出发，试图将其归约为开始符。2.3.1 规范推导和规范归约规范推导和规范归约u 对于一文法而言，从开始符到某句型的对于一文法而言，从开始符到某句型的推导过程可能不唯一推导过程可能不唯一。例如，文

20、法例如，文法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) 规范推导u 最左（右）推导最左（右）推导：在推导序列的每一步直接推导中，被替在推导序列的每一步直接推导中，被替换的总是当前句型中最左（右）的非终结符。换的总是当前句型中最左（右）的非终结符。u 形式上，形式上，从符号串从符号串

21、 到符号串到符号串 的推导序列的推导序列u * xUy xuy * 总有总有 x VT* (y VT*) 时，称为时，称为最左（右）推导最左（右）推导u 定义：最左（右）推导所得句型称为定义：最左（右）推导所得句型称为左（右）句型；左（右）句型；最右最右推导推导称为称为规范推导规范推导；右句型右句型称为称为规范句型规范句型。最左推导：若符号串中有两个以上的非终结符时，先推左边的。最右推导：若符号串中有两个以上的非终结符时，先推右边的。最右推导称为规范推导最右推导称为规范推导句子、句型的推导方法u 每个每个句子句子都有相应的最左和最右推导，因此，都有相应的最左和最右推导，因此，句子即是句子即是左

22、句型左句型也是也是右句型右句型（规范句型）（规范句型）u 并不是每个句型都有最左和最右推导并不是每个句型都有最左和最右推导u 例如，例如，E E + + E+i E+i* *T T即不是左句型，也不是右句型即不是左句型，也不是右句型u 对于给定的符号串对于给定的符号串w，采用，采用自顶向下自顶向下的分析来判断的分析来判断w是否为是否为L(GS)的句子的常见方法是：的句子的常见方法是：试图建立从开始符试图建立从开始符 S到到w最左最左推导推导:S* w u显然，每步推导时，对应于最左非终结符相应的产生式可能会显然，每步推导时，对应于最左非终结符相应的产生式可能会有多个，若无特殊的办法，只能一个一

23、个地试探。因此，推导有多个，若无特殊的办法，只能一个一个地试探。因此，推导过程可能是过程可能是带回溯带回溯的的。u 为提高效率，就应尽量避免回溯为提高效率，就应尽量避免回溯自底向上的语法分析自底向上的语法分析u 就是从已给的符号串就是从已给的符号串w出发，试图以相反的方向为出发，试图以相反的方向为w建立建立一个规范推导，最终得到文法的开始符。一个规范推导，最终得到文法的开始符。u 推导的逆过程称作推导的逆过程称作归约归约，它是把当前的符号串，它是把当前的符号串中的构成中的构成文法某个产生式文法某个产生式A右部的子串右部的子串 替换成产生式的左部符号替换成产生式的左部符号A，得到一个新的符号串，

24、得到一个新的符号串 A 。这样的一步动作，称为进行。这样的一步动作，称为进行了一步了一步归约归约。u 例如，符号串例如，符号串F+i*i中的中的F可按产生式可按产生式TF归约为归约为T，从而得，从而得到新的符号串到新的符号串T+i*i。u 若从给定的符号串若从给定的符号串w出发，一步步地将其归约，最终得到文出发，一步步地将其归约，最终得到文法的开始符号，则说明法的开始符号，则说明w是该文法定义的一个句子。归约成是该文法定义的一个句子。归约成功，否则，归约失败。功，否则，归约失败。u 若归约的每一步都归约的是当前符号串中最左边的某产生式若归约的每一步都归约的是当前符号串中最左边的某产生式的右部，

25、则称该归约是的右部，则称该归约是规范归约规范归约（即（即最左归约最左归约）。）。u 规范归约是规范推导的逆过程规范归约是规范推导的逆过程。由上表可以看出，归约过程是由上表可以看出，归约过程是最左最左归约，它恰好是归约，它恰好是规规范推导的逆过程范推导的逆过程。这正是把最左归约定义为规范归约。这正是把最左归约定义为规范归约的原因。的原因。关于归约的一点说明u 注意，前面例子中归约的第五步中，当前的符号串为注意，前面例子中归约的第五步中，当前的符号串为 E+T*i，除了可将除了可将i归约成归约成F外，还可将外，还可将E+T或或T归约成归约成E，分别得到符号，分别得到符号串串E*i和和E+E*i。但

26、是，若真按这两个方案进行归约，则当我。但是，若真按这两个方案进行归约，则当我们把其归约成们把其归约成E*E或或E+E*E时，就再也归约不下去了。这就告时，就再也归约不下去了。这就告诉我们在第五步时，唯一正确的归约是将诉我们在第五步时，唯一正确的归约是将i归约为归约为F，也就是说，也就是说，i是唯一可被归约的最左子串。是唯一可被归约的最左子串。u 那么，对于规范归约的每一步，如何确定符号串中的当前应被那么，对于规范归约的每一步，如何确定符号串中的当前应被归约的最左子串呢？归约的最左子串呢？2.3.2 2.3.2 语法树和二义性语法树和二义性u语法树用于直接地描述一个句型右句子的语法结构语法树用于

27、直接地描述一个句型右句子的语法结构u语法树是一有向树（连通的）语法树是一有向树（连通的）1）有且仅有一个无任何前驱的结点，称为根）有且仅有一个无任何前驱的结点，称为根 （S）；）；2）除根外，每个结点恰有一个直接前驱；）除根外，每个结点恰有一个直接前驱；3）对于任一结点）对于任一结点m，从根到从根到m可达可达;4) 每个结点的后继是有序的（从左到右）每个结点的后继是有序的（从左到右）设设G=(VN,VT,P,S)是一文法，则满足下述条件的树称为语法树：是一文法，则满足下述条件的树称为语法树：1）每个结点有一标记）每个结点有一标记X， X V；2）根的标记为）根的标记为S（开始符）；（开始符）；

28、3）若结点）若结点X有后继，则有后继，则X VN；4）A有有k个后继，自左至右为个后继，自左至右为X1, X2, , Xk，则，则A X1X2Xk P语法树的所有叶结点自语法树的所有叶结点自左至右排列构成了文法左至右排列构成了文法G的一个句型的一个句型 对一语法树而言，其构对一语法树而言，其构造过程不同对应了不同造过程不同对应了不同的推导（归约）过程的推导（归约）过程 例如，文法例如，文法GE的句型的句型 i+i*i相应的语法树见右图相应的语法树见右图。EE+TTFiT*FFiiu 存在这样的文法存在这样的文法G，其某个句子，其某个句子w L(G),可对应结构不同的可对应结构不同的语法树，即语

29、法树，即w对应了多个不同的最左（右）推导，这类文法称对应了多个不同的最左（右）推导，这类文法称为为。u 例如，例如，G3E：EE+E|E*E|(E)|i 的句型的句型及文法及文法u Cif B then C|if B then C else CC S的句型：的句型：if B1 then if B2 then S1 else S2u 上面两个句型均有两个不同的语法推导树（见下页），所以，上面两个句型均有两个不同的语法推导树（见下页），所以，它们是二义性文法它们是二义性文法文法的二义性EEEEE+*iiiEEEEE+*iiiif B1 then C else C S1 S2Cif B2 then

30、CCif B1 then CS1 S2if B1 then C else C关于二义性文法u 应指出应指出，二义性，二义性是一种常见的语法现象，然而，对于编译程序是一种常见的语法现象，然而，对于编译程序而言，而言，二义性文法二义性文法是是有害有害的。的。u 为解决二义性文法带来的不确定性问题，通常的方法一是为解决二义性文法带来的不确定性问题，通常的方法一是修改修改文法文法，例如，文法例如，文法G3可用本章（可用本章（P20 (2.2)式式）定义的文法）定义的文法G2E取代，而取代，而G2不是二义性的不是二义性的。u 二是二是利用附加条件利用附加条件。例如，例如， i+ii+i* *i i的归约

31、过程中，若规定的归约过程中，若规定* *比比+ +优先级高，则可强制性地让系统先按优先级高，则可强制性地让系统先按E E* *E E进行归约，而不是先进行归约，而不是先按按E+EE+E进行归约；进行归约；又比如，若又比如，若强制规定强制规定elseelse只能和距其最近的只能和距其最近的尚未被匹配的尚未被匹配的thenthen进行匹配，就可解决进行匹配，就可解决elseelse悬空的问题。悬空的问题。2.3.3 短语和句柄短语和句柄u问题问题: : 在自底向上在自底向上( (简记为简记为 ) )的语法分析中的语法分析中, ,对于每一步直接归约对于每一步直接归约, ,应如何正确地确定当应如何正确

32、地确定当前句型中应被归约的前句型中应被归约的最左子串最左子串? ?u考虑文法考虑文法G G2 2EE的句型的句型 = E+T= E+T* *F+iF+i, ,从开始符从开始符E E 推导出推导出 的语法树见右图的语法树见右图u该树中含有若干子树该树中含有若干子树, ,如如T T(2)(2)为根的子树对应为根的子树对应的叶结点为的叶结点为T T(3)(3)* *F F(3),(3),由于它是一直接子树由于它是一直接子树, ,文文法中必有产生式法中必有产生式T-TT-T* *F F; ;因此因此, ,称称T T* *F F是句型是句型 相对于产生式相对于产生式T-TT-T* *F F的的直接短语直

33、接短语. .同理同理, ,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)的的短语短语短语、直接短语及句柄的定义短语、直接短语及句柄的定义u例如，对句型例如，对句型 = E+T= E+T* *F+iF+i，由定义，有：由定义，有：(1)E(1)E* * E+T+i( E+T+i( =E+,A=T, =E

34、+,A=T, =+i)=+i)及及T TT T* *F(=F(= ),),故故T T* *F F是是 相对于产生相对于产生式式T-TT-T* *F F的的直接短语直接短语; ;(2)E(2)E* * E+T E+T* *F+F FF+F Fi,i,i i是是 相对于产生式相对于产生式F-iF-i的的直接短语直接短语; ;(3)E(3)E* * E+i E+i与与 E E + + E+T E+T* *F,F,E+TE+T* *F F是是相对于非终结符相对于非终结符E E的的短语短语; ;(4)E(4)E* * E E及及E E* * E+T E+T* *F+i(= F+i(= ), ), 是是

35、相对于相对于E E的的短语短语注注: :由定义可知由定义可知, ,直接短语也是短语直接短语也是短语, ,但短语不一定是直接短语但短语不一定是直接短语. .)()(),(,8 . 2*直接短语的短语产生式相对于非终结符是句型则称及有对于若的一个句型其中是文法设定义AAAAASVAVVSGN归约时被替换子串的选择u从句型 =E+T=E+T* *F+iF+i的语法树可知,E+T绝不是它的一个直接短语,因为虽然E-E+T是G2的一个产生式,但不存在从E到E*F+i的推导,所以,当判断一符串是否为某一句型的短语时,须检查定义2.8的两个条件是否同时满足.u采用采用 分析时分析时, ,每步每步归约归约就是

36、将一个产生式就是将一个产生式右部右部替换替换其其左部左部, ,也就是把也就是把该句型的语法树中的该句型的语法树中的一棵直接子树的末端结点剪去一棵直接子树的末端结点剪去. .即每次归约的符即每次归约的符号串必是当前句型的一个直接短语号串必是当前句型的一个直接短语. .u但是但是, ,对一句型而言对一句型而言, ,其其直接短语可能不唯一直接短语可能不唯一. .为了让分析能够机械地为了让分析能够机械地进行进行, ,我们只考虑规范归约我们只考虑规范归约( (最左归约最左归约),),即归约过程替换的是归左直接即归约过程替换的是归左直接短语短语. .u我们以L(G2)的句子i+i*i+i为例,给出其最右推

37、导(规范归约的逆过程),来说明每次规范归约的子符号串句柄的定义句柄的定义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 一个句型的最左直接短语称为此一个句型的最左直接短语

38、称为此句型的句型的句柄句柄。u问题问题：如何确定一规范句型的句柄？句柄如何确定一规范句型的句柄？句柄应被归约成哪个非终结符？应被归约成哪个非终结符？EE + TE + TT * FTFiFFiii1234567891011( 3 ) 子树与短语 子树：语法树中的某个结点（子树的根）连同它向下派生的部分所组成。 某子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对于该子树根的短语。定理定理定义：简单子树：仅有父子两代的子树。 句柄：该语法树的最左简单子树的末端结点从左到右排列的字符串是该句型的句柄。 某简单子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对

39、于该简单子树根的直接短语。定理定理 只需画出句型的语法树，然后根据子树找 短语短语直接短语直接短语句柄句柄。句型推导过程句型语法树的生长过程 由推导构造语法树由推导构造语法树1从识别符号开始，自左向右建立推导序列。由根结点开始，自上而下建立语法树。语法树与推导 由语法树构造推导由语法树构造推导2自上而下地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次规约。从句型开始，自右向左地逐步进行规约，建立推导序列。2.4 2.4 文法的化简与改造文法的化简与改造2.4.1 无用符号和无用产生式的删除无用符号和无用产生式的删除设设G=(VN,VT,P,S)是一文法是一文法,X VN VT,

40、X称为是称为是有用的有用的,若若X至少至少出现在一个句子的推导过程中出现在一个句子的推导过程中,即即X满足满足:(1) 存在存在 , V* ,有有 S* X (2.12)(2)存在存在w VT*,使使 X * w(2.13)否则否则,称称X是是无用的无用的.若一产生式含有无用符号若一产生式含有无用符号,则此产生式称为则此产生式称为无用无用产生式产生式.u 无用产生式给语法分析带来了许多麻烦无用产生式给语法分析带来了许多麻烦,应予以删除应予以删除.消除无用产生式的算法消除无用产生式的算法算法算法2.1 将文法将文法G = (VN,VT,P,S),改造为改造为G1=(VN,VT,P,S),使得使得

41、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 ;(

42、3)重复重复(2),直到直到V不再增大不再增大;(4)令令P=A | A P, (VN VT)*,A VN消除无用产生式的例子消除无用产生式的例子例例 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将将

43、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所得文法不一定所得文法不一定“干净干净”2.4.2 -产生式的消除u -产生式产生式是指右部为一空符号串是指右部为一空符号串 的产生式。因为某些语法分析的产生式。因为某些语法分析算

44、法要求不含算法要求不含，此时应消除之，此时应消除之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)情

45、况时的情况时的 -产生式产生式;u 算法算法2.5可消除可消除L(G)情况时的情况时的 -产生式产生式.2.5 文法和语言的文法和语言的ChomskyChomsky分类分类u文法的四元组表示是由文法的四元组表示是由N.ChomskyN.Chomsky于于19561956年描述形式语言时给出年描述形式语言时给出的。他还对产生式的形式给予不同的限制而定义了的。他还对产生式的形式给予不同的限制而定义了四类基本文法四类基本文法。u0 0型文法型文法: :若若P P中任一产生式都有一般形式中任一产生式都有一般形式 V+ V+ V V* * 且对且对 ， 不加任何限制，则称不加任何限制，则称GG为为0 0型文法型文法（短语结构文法，记为短语结构文法，记为PSG: PSG: Phrase Structure GrammarPhrase Structure Grammar) )。由。由0 0型文法生成（或者说：定义）型文法生成（或者说：定义）的语言称为的语言称为0 0型型（递归可枚举递归可枚举）语言语言。它可由。它可由图灵图灵（TuringTuring）机机识识别。别。u例如：例如：S SACaB CaACaB CaaaC CBaaC CBDB CBDB CBE aDE aDDa Da ADADAC aEAC aEEa AEEa AE 就