编译原理-蒋立源第2章文法和语言.ppt

第二章第二章 文法和语言文法和语言 编译过程的核心就是翻译，就是把一种语言翻译成为另一种语言，与自然语言的翻译类似，只不过其工作对象是某种程序设计语言。两个重要的前提：1）描述和定义程序设计语言2）识别或分析这种语言20世纪50年代，语言学家Noam Chomsky（乔姆斯基）提出了一个用来描述语言的数学系统，把用一组数学符号和规则来描述语言的方式叫做形式描述，而把能用数学符号和规则描述的语言称为形式语言形式语言。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。程序设计语言就是形式语言。2.1 2.1 文法及语言的表示文法及语言的表示 如何来描述一种语言？1）当一个语言仅含有有限个句子时，可采用枚举法来表示这种语言。对于无限的语言寻找出有限的表示，有两种途径：1.2）生成方式（文法）：制定有限条规则，用来生成所要描述的语言中的全部句子。2.3）识别方式（自动机）：建立一种装置（更确切的说，是构造一种算法或过程），此装置以某一字母表上的所有符号串作为输入，并识别这些符号串，当一个符号串是此字母表上某给定语言中的句子时，就接受它，反之，则拒绝接受。语言的定义：Webster定义：为相当大地区的公众所懂得并使用的“话”，以及组成这些“话”的方法的统一体。另一种定义：某一字母表上符号串（句子）的集合一种精确化的语言的要求：（1）为所定义语言中的句子提供一种结构性的描述（2）提供一种手段，准确地判别什么是该语言的正确句子，而什么又不是基本概念和术语基本概念和术语 字字母母表表：元素的非空有穷集合。字母表中的每个元素称为“符号”，因此“字母表”也可称为“符号集”。典型的符号有字母、数字、各种标点符号和各种运算符。例如，集合a，b，c，+，*是一个含有5个符号的字母表，而字母表0，1只有2个符号。符号串符号串：由字母表上0个或多个符号所组成的任何有穷序列。特别地，把不包含任何符号的符号串称为空符号串。例如有字母表a，b，c，+，*，则a,b,c,+,*,aa,ab,ac,a+,a*,ba,bb,bc,b+,b*,aaa,bbb等等都是该字母表上的符号串。而所有二进制数都是定义在字母表0，1上的符号串。显然，一个字母表上的全部符号串所组成的集合是无穷的。2.2 2.2 文法和语言的定义文法和语言的定义 符号串及其集合的运算符号串及其集合的运算1 11.符号串的长度符号串的长度：指符号串x中所含符号的个数，记为|x|。如：|abc|=3，|abc+*abc|=8，|=？2.符符号号串串的的前前缀缀：指从符号串x的末尾删除0或多个符号后得到的符号串，如、a、ab、abc都是abc的前缀。符号串的后缀符号串的后缀：指从符号串x的开头删除0或多个符号后得到的符号串，如、c、bc、abc都是abc的后缀。符号串的子串符号串的子串：指从符号串x的开头和末尾删除0或多个符号后得到的符号串，如abc的子串？符号串的前缀、后缀都是它的子串。、a、b、c、ab、bc、abc|=0符号串及其集合的运算符号串及其集合的运算2 23.3.符号串的连接符号串的连接：若x、y是两个符号串，则xy表示连接，是将符号串y连接在符号串x的后面。若x、y是字母表上的两个符号串，则xy也是字母表上的符号串。如：x=ab，y=ba，那么 xy=abba注意：连接没有交换律，即 xy yx 对于空串有 x=x=x 符号串的方幂符号串的方幂：一个符号串x与其自身的n-1次连接称为x的n次方幂，即：X0=,x1=x,x2=xx,，xn=xxx=xxn-1=xn-1x如：x=abc,x0=,x1=abc,x2=abcabc,符号串及其集合的运算符号串及其集合的运算3 34.符符号号串串集集合合的的乘乘积积：令A、B为两个符号串集合，A和B的乘积AB定义为：AB=xy|x A，y B例如：A=a，b B=c，d，则AB=ac，ad，bc，bd对于有：A=A=A符号串集合的方幂符号串集合的方幂：设A为符号串集合，则A的方幂定义为：A0=，A1=A，A2=AAAn=AAA=AAn-1=An-1A例如：A=a，b，c A0=A1=a，b，c A2=AA=aa，ab，ac，ba，bb，bc，ca，cb，cc符号串及其集合的运算符号串及其集合的运算4 45.符符号号串串集集合合的的闭闭包包：设设A为为一一个个集集合合，则则集集合合A的的正正闭闭包包用用A+表示，定义为：表示，定义为：A+=A1A2.An集合集合A的闭包用的闭包用A*表示，定义为：表示，定义为：A*=A0A+例如：A=a，b，c则A+=a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,A*=,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,可可见见，字字母母表表A的的正正闭闭包包A+就就是是由由A中中字字母母所所构构成成的的一一切切符符号号串的集合，而串的集合，而A*仅比比A+多个多个。2.2.2 2.2.2 文法和语言的形式定义文法和语言的形式定义 在学习英语时，我们知道句子由主语、谓语组成，主语由冠词、形容词及名词组成等等，这就是说明句子组成的规则。而在形式语言里，这种规则可采用“:=”、“:=”这种形式来表示。分析一个句子是否正确，就是根据这些规则进行的。实际上，文法就是描述语言语法结构的形式规则。从“产生语言”的角度出发，给出方法和语言的形式定义。产生语言：指制定出有限个规则，借助这些规则可以产生此语言的全部句子。文法形式定义文法形式定义1 1 在表示文法时，要说明语言的语法成分(语法范畴），句子中的符号以及语法结构。例如，能够描述句子例如，能够描述句子“themonkeyateabanana”的文法如下：的文法如下：在这个文法里，其中用“”符号括起来的部分，表示评议的一个语法实体。符号“:=”是一个整体，其含义是“定义为”，也就是左边的语法实体可进一步定义为右边的符号串。在推导过程中，就是一种“替换”关系。而像the、ate、banana这样的符号只在规则中:=的右边出现，不需要进一步定义，这些符号不能用其它符号代替。我们最终需定义的语法成分是。每条规则的形式都是:=。1):=2):=the3):=4):=5):=monkey6):=banana 7):=ate8):=has9):=the10):=a“:=”表示“定义为”文法形式定义文法形式定义2 2=the=the=themonkey=themonkeyate=themonkeyatea=themonkeyateabanana如何用上述规则去产生或推导出相应语言的句子呢？=+themonkeyateabanana“=”表示一步推导“=+”表示多步推导文法形式定义文法形式定义3 3文法的形式定义：文法的形式定义：文法可表示为一个四元组文法可表示为一个四元组GS=（VN，VT，P，S）VN是是一一个个非非空空有有穷穷集集合合，该该集集合合中中的的每每个个元元素素称称为为非非终终结结符符号号。如如上上例例中中VN=、VT是是一一个个非非空空有有穷穷集集合合，该该集集合合中中的的每每个个元元素素称称为为终终结结符符号号。如如上上例例中中VT=monkey、banana、ate、has、the、a并且并且VNVT=，而，而VNVT称为该文法的字汇表。称为该文法的字汇表。P是是一一个个非非空空的的有有穷穷集集合合，它它的的每每个个元元素素叫叫做做产产生生式式或或规规则则。产产生生式式的的形形式式为：为：或或:=是产生式的左部且不能为空，是产生式的左部且不能为空，是产生式的右部，并且是产生式的右部，并且、V。S是是VN集集合合的的一一个个特特殊殊的的非非终终结结符符号号，称称为为文文法法的的开开始始符符号号。它它至至少少必必须须在在某个产生式的左部出现一次。某个产生式的左部出现一次。就是上例文法的识别符号。就是上例文法的识别符号。文法形式定义文法形式定义4 4文法分文法分4种类型（见种类型（见2.5小节），程序设计语言文法主要为小节），程序设计语言文法主要为2型型文法，这种文法也叫文法，这种文法也叫前后文无关文法前后文无关文法，本书后面说的文法都，本书后面说的文法都是指这种文法。是指这种文法。在前后文无关文法中，产生式的左部在前后文无关文法中，产生式的左部是一个非终结符号，而是一个非终结符号，而右部右部是由终结符号和非终结符号组成的有穷符号串。这样只是由终结符号和非终结符号组成的有穷符号串。这样只要给出产生式集合，所有产生式的左部符号就构成了非终结要给出产生式集合，所有产生式的左部符号就构成了非终结符号集合符号集合VN，而只出现在产生式右部的那些符号构成终结符，而只出现在产生式右部的那些符号构成终结符号集合号集合VT，因此，在表示文法时只需给出规则集合并指定识，因此，在表示文法时只需给出规则集合并指定识别符号即可。别符号即可。为了进一步简化，在给出规则集时，可约定将为了进一步简化，在给出规则集时，可约定将左部符号为开始符号的规则作为规则集合的第一条规则，这左部符号为开始符号的规则作为规则集合的第一条规则，这样表示文法时只需给出规则的集合即可。显然，上例就是一样表示文法时只需给出规则的集合即可。显然，上例就是一个简化的文法表示。个简化的文法表示。文法形式定义文法形式定义5 5 例2.2，有如下简化表示文法，只给出规则集，写出该文法的终结符号集合、非终结符号集合和开始符号。1.2.3.4.05.16.27.38.49.510.611.712.813.9解：根据简化约定，可确定：解：根据简化约定，可确定：非终结符号集合：非终结符号集合：VN=,终结符号集合：终结符号集合：VT=0,1,2,3,4,5,6,7,8,9开始符号开始符号S：文法的文法的EBNFEBNF表示表示 所谓文法的所谓文法的EBNF表示，就是在书写文法的规则时，可采用一些特殊的符表示，就是在书写文法的规则时，可采用一些特殊的符号号“|”、“”和和“”、“（”和和“）”、“”和和“”来表示文法，来表示文法，这些符号叫做元符号。其中这些符号叫做元符号。其中“”和和“”、“（”和和“）”、“”和和“”这些元符号总是成对出现。下面介绍各种元符号的含义。这些元符号总是成对出现。下面介绍各种元符号的含义。1.元符号元符号“|”：表示：表示“或或”.对于具有相同左部的那些规则对于具有相同左部的那些规则如如1、n，可以缩写为，可以缩写为:1|2|n例例2.3，对例，对例2.2文法的文法的13条规则可缩写成：条规则可缩写成：|0|1|2|3|4|5|6|7|8|9文法的文法的EBNFEBNF表示表示2.元符号元符号“”和和“”：表示可重复：表示可重复连接连接，tnm表示符号串表示符号串t可可重复重复连接连接n到到m次，而次，而t表示符号串表示符号串t可重复可重复连接连接0到无穷次。到无穷次。例如，例如，13与与|相同相同EE+T|T与与ET+T相同相同而字母打头、后面可跟数字或字母的不超过而字母打头、后面可跟数字或字母的不超过8个字符的标识符文法则为：个字符的标识符文法则为：|07文法的文法的EBNFEBNF表示表示3.元元符符号号“”和和“”：表表示示括括起起的的内内容容可可有有可可无无。如如t表表示示符号串符号串t可有可无。可有可无。例如：例如：IFTHENIFTHENELSE可写成：可写成：IFTHENELSE4.元元符符号号“（”和和“）”：表表示示括括号号内内的的成成分分优优先先。常常用用于于在在规规则中提取公因子。则中提取公因子。例如，例如，Uxy|xw|xz可写成：可写成：Ux（y|w|z）从从上上述述有有关关元元符符号号的的定定义义和和例例子子可可看看出出，这这些些元元符符号号为为表表示示文文法法提供了很大方便。提供了很大方便。直接推导直接推导 设设GS是一文法是一文法,是该文法的一个产生式，对于符号串是该文法的一个产生式，对于符号串xy xy，其中，其中x x和和y y是该文法的任意符号串是该文法的任意符号串(可为空可为空),推导就是用推导就是用产生式产生式的右部替换左部，从而得到新的符号串的右部替换左部，从而得到新的符号串xyxy。表。表示为：示为：xy=xyxy=xy其中其中“=”“=”表示一步推导。我们称表示一步推导。我们称xyxy直接推导出直接推导出xyxy,或或xyxy直接产生直接产生xyxy。若从反方向看，则。若从反方向看，则称称xyxy直接归约到直接归约到xyxy。x,yV*直接推导直接推导例如有文法例如有文法1）2）|3）0|1|2|3|4|5|6|7|8|9对符号串对符号串利用规则利用规则1可直接推导出可直接推导出：=对符号串对符号串利用规则利用规则2可直接推导出可直接推导出：=对符号串对符号串利用规则利用规则3可直接推导出可直接推导出2：=2将上述三个推导连接起来，可得如下推导过程：将上述三个推导连接起来，可得如下推导过程：=2推导推导 如如果果文文法法GS存存在在一一直直接接推推导导序序列列0=1=n，其其中中n0,那那么么我我们们说说0推导出推导出n或或n归约到归约到0,并记作并记作0=+n,推导长度为推导长度为n。如果有如果有0=+n或或0=n,即即n0,则记作则记作0=*n。可见，可见，n0的推导和的推导和n=0分别称为分别称为“+推导推导”和和“*推导推导”。例如，从开始，分别利用规则1、2、2、3、3，可产生如下推导过程：=2=23这个推导过程可记作：=+23，其推导长度n=5，而从到的推导，无须使用任何规则，可记作：=*，其推导长度n=0。句型和句子句型和句子 推导产生的结果可能是句型，也可能是句子。设文法G的识别符号为S，则句型、句子的定义如下：1.如果如果S=*,且且V*,则称则称是文法是文法GSGS的一个句型。的一个句型。2.如果如果S=+,且且 VVt t*,则称则称是文法是文法GSGS的一个句子。的一个句子。从文法的开始符号利用规则进行推导，一旦推导出句子，推导过程就不能再继续进行，因为句子中没有非终结符号。假设符号串是某一推导的结果，那么，是句子的必要条件是从S到的推导长度大于等于，即 S=+x,而不可能是S=*x。这是因为识别符号S是非终结符号，而是终结符号串，显然，S不可能与相等，所以S不可能经过步推导就等于。为何这里是“+推导”？句型是从识别符号开始经过0步或多步推导出的可由终结符号和非终结符号组成的符号串而句子是从文法的识别符号推导出的完全由终结符号组成的符号串句子是从文法的识别符号推导出的完全由终结符号组成的符号串。句子是特殊的句型，是完全由终结符号组成的句型。语言语言 一个文法一个文法GS所产生的所有句子的集合所产生的所有句子的集合L(GS),称为文法称为文法GS所定义的语言所定义的语言,即即:L(GS)=x|S=+x,且且xVt*,一一个个文文法法所所定定义义的的语语言言是是该该文文法法的的终终结结符符号号集集合合Vt上上的的所所有有符符号号串串组组成成的的集集合合的的一一个个子子集集,该该子子集集中中的的每每个个符符号号串串都都可可从从识识别别符符号号开开始始经经过过至至少少一一步步推推导导出出来，即来，即:L(GS)Vt*例如，对例2.1的文法G，其语言有16个句子：the monkey ate the banana the banana ate the monkey the monkey ate the monkey the banana ate the banana而例2.3中的文法，其语言是所有无符号整数，句子是无穷的。文法和语言有如下关系：文法和语言有如下关系：1)给定一个文法给定一个文法,就能从结构上唯一的确定其语言就能从结构上唯一的确定其语言,即即:GL(G)2)给定一种语言给定一种语言,能确定其文法能确定其文法,但不唯一但不唯一,即即:LG1或或G2或或。语言语言例例2.4，已知文法，已知文法GS为：为：1)SaSb2)Sab或写成或写成SaSb|ab求该文法确定的语言。求该文法确定的语言。解：从识别符号开始推导，反复用规则解：从识别符号开始推导，反复用规则1,最后用规则最后用规则2可得可得:S=aSb=a2Sb2=an-1Sbn-1=anbn（n 2)直接用规则直接用规则2可得可得:S=ab所以该文法确定的语言为：所以该文法确定的语言为：L(GS)=an nb bn n|n1|n1 反之，试构造产生下列语言的文法anbn|n0SaSb|语言语言例2.5，已知语言为:L(G)=abna|n1，构造产生该语言的文法。解：根据语言的形式，可构造其文法G为:SaBaBBb|b还可以构造文法G1为:SaBaBbB|b可见，G与G1是两个不同的文法，但它们都可以描述语abna|n1。如果两个不同的文法可描述相同的语言如果两个不同的文法可描述相同的语言,那么我们称那么我们称这两个文法为等价文法。前后文无关文法的等价问这两个文法为等价文法。前后文无关文法的等价问题是不可判定的。等价文法的存在，对编译技术的题是不可判定的。等价文法的存在，对编译技术的实现有很大帮助，使我们能在不改变文法所确定的实现有很大帮助，使我们能在不改变文法所确定的语言前提下，为了某种目的而改写文法。语言前提下，为了某种目的而改写文法。引理引理2.1设设G=(Vn,Vt,P,S)为一文法，并设为一文法，并设AxBy是是P中的一个产生式。而中的一个产生式。而B1,B2,Bk是是P中的全部中的全部B-产生式，又设产生式，又设G1=(Vn,Vt,P1,S)是是这样的文法，其中，这样的文法，其中，P1是从是从P中删去中删去AxBy并添加产生式并添加产生式Ax1y,Ax2y,Axky所组成的集合，则所组成的集合，则L(G1)=L(G)。递归规则与递归文法递归规则与递归文法递归规则是指在规则的右部含有与规则左部相同符号的规则。设文法GS，x，y是V上的符号串，若U xUy是文法的规则，且xy!=，则称U xUy为直接递归规则，称U为直接递归的非终结符。特别，若x=，即这个相同的符号出现在右部的最左端，则为左递归规则。如 U Uy若y=，即这个相同的符号出现在右部的最右端，则为右递归规则。如 U xU 若文法GS存在推导U=+xUy，则称U为递归的非终结符。给定了文法，就确定了语言。句子的个数是有穷还是无穷取决于文法是否是递归的。若文法若文法GS中至少包含一个递归的非终结符号中至少包含一个递归的非终结符号,则称此文法是递归则称此文法是递归文法。递归文法使我们能用有穷的文法刻画无穷的语言。文法。递归文法使我们能用有穷的文法刻画无穷的语言。2.32.3句型的分析句型的分析所所谓谓句句型型的的分分析析，是是指指构构造造一一种种算算法法，用用以以判判定定给给定定的的符符号号串是否为某一文法的句型（或句子）。串是否为某一文法的句型（或句子）。通通常常，句句型型分分析析的的方方法法可可大大致致分分为为两两类类，即即自自顶顶向向下下的的分分析析和和自自底底向向上上的的分分析析。前前者者是是从从文文法法的的开开始始符符号号出出发发，以以给给定定的的符符号号串串为为目目标标，试试图图推推导导出出此此符符号号串串；后后者者恰恰好好和和前前者者相相反反，它它从从给给定定的的符符号号串串出出发发，反反复复用用文文法法中中规规则则的的左左部部去去替替换换当当前前符符号号串串中中的的相相应应子子串串，以以期期最最后后“归归约约”到到文文法法的的开开始符号。这与分析过程中构造句型相应语法树的方向有关。始符号。这与分析过程中构造句型相应语法树的方向有关。规范推导规范推导 规范推导（最右推导），每步推导只替换最右边的非终结符号。定义为：规范推导（最右推导），每步推导只替换最右边的非终结符号。定义为：对于直接推导对于直接推导xUy=xuy来说，如果来说，如果y只包含终结符号或为空符号串只包含终结符号或为空符号串,那么就那么就把这种推导称为规范推导或最右推导（如果只包含终结符号或为空符号把这种推导称为规范推导或最右推导（如果只包含终结符号或为空符号串串,则为最左推导），且记作则为最左推导），且记作:xUy=rxuy,其中其中yVt*。例例2.6算术表达式文法算术表达式文法GE：EE+T|TTT*F|FF(E)|i给出句子给出句子i+i*i的最左推导和最右推导。的最左推导和最右推导。解：最左推导：解：最左推导：E=lE+T=lT+T=lF+T=li+T=li+T*F=li+F*F=li+i*F=li+i*i最右推导：最右推导：E=rE+T=rE+T*F=rE+T*i=rE+F*i=rE+i*i=rT+i*i=rF+i*i=ri+i*i2.3.1 2.3.1 规范推导规范推导每每一一个个句句子子都都有有一一个个规规范范推推导导,但但并并非非每每一一个个句句型型都都有有规规范范推推导导，只有那些能用规范推导产生的句型才是规范句型只有那些能用规范推导产生的句型才是规范句型。例如，对于例例如，对于例2.3中的文法，有句型中的文法，有句型“2”,其推导过程如下其推导过程如下:=2其其中中第第3,步步推推导导变变换换的的不不是是最最右右边边的的非非终终结结符符号号，不不满满足足规规范范推推导导的的要要求求，所以句型所以句型“2”不是规范句型。不是规范句型。而对于句型而对于句型“3”，其推导过程如下，其推导过程如下:=3=3其中的每一步推导都变换的是最右边的非终结符号，所以，其中的每一步推导都变换的是最右边的非终结符号，所以，句型句型“3”3”是规范句型是规范句型。2.3.1 2.3.1 规范推导规范推导给给定定终终结结符符号号串串w，通通过过语语法法分分析析判判定定w是是否否为为某某一一语语言言L(G)中中的句子：的句子：自自顶顶向向下下：试试图图为为w建建立立一一个个从从G的的开开始始符符号号S到到w的的最最左左推推导导。显显然然，若若某某步步推推导导中中被被替替换换的的非非终终结结符符号号U是是由由若若干干个个后后选选式式定定义义的的，即即有有U1|2|n，那那么么就就会会出出现现如如何何选选用用后后选选式式的的问问题题。一一种种办办法法是是逐逐个个用用这这些些后后选选式式试试探探。若若用用某某个个i 替替换换U能能使使分分析析继继续续，则则沿沿此此路路径径继继续续；若若发发现现有有错错，则则退退回回出出错错点点再再用用下下一一个个i+1继继续续试试探探。故故称称为为带带回回溯溯的的自自顶顶向向下下的的分分析析方方法法。回回溯溯效率低，应设法避免。效率低，应设法避免。2.3.1 2.3.1 规范推导规范推导自低向上：试图从自低向上：试图从w出发，以相反方向为出发，以相反方向为w建立一个规范推导。建立一个规范推导。从左到右扫视从左到右扫视wi中各个符号，找到一个和中各个符号，找到一个和G中某一产生式的右部相同的最左子中某一产生式的右部相同的最左子串，用此产生式的左部替换此最左子串进行直接归约。例如符号串串，用此产生式的左部替换此最左子串进行直接归约。例如符号串i+i*i的归约的归约过程过程步序步序i当前符号串当前符号串Wi所用产生式所用产生式归约后的符号串归约后的符号串wi+10i+i*iFiF+i*i1F+i*iTFT+i*i2T+i*iETE+i*i3E+i*iFiE+F*i4E+F*iTFE+T*i5E+T*iFiE+T*F6E+T*FTT*FE+T7E+TEE+TE最右推导：最右推导：E=rE+T=rE+T*F=rE+T*i=rE+F*i=rE+i*i=rT+i*i=rF+i*i=ri+i*i可见，最右（左）推导的逆过程是最左（右）归约，反之亦然。可见，最右（左）推导的逆过程是最左（右）归约，反之亦然。如何确如何确定可归定可归约的最约的最左子串左子串？2.3.2 2.3.2 语法树和二义性语法树和二义性 推导过程可用图来表示，这就是语法树，也叫分析树。语法树是一棵有序有推导过程可用图来表示，这就是语法树，也叫分析树。语法树是一棵有序有向树，每个节点都有标记。根节点代表文法的识别符号；每个内部节点（非向树，每个节点都有标记。根节点代表文法的识别符号；每个内部节点（非叶节点）表示一个非终结符号，其子节点由这个非终结符号在这次推导中所叶节点）表示一个非终结符号，其子节点由这个非终结符号在这次推导中所用产生式的右部各个符号代表的节点组成；每个用产生式的右部各个符号代表的节点组成；每个末端节点（叶节点）代表终末端节点（叶节点）代表终结符号或非终结符号，它们从左向右排列起来，构成句型。如果叶节点都是结符号或非终结符号，它们从左向右排列起来，构成句型。如果叶节点都是终结符号，则从左向右构成句子。推导过程不同，生成语法树的过程也不同，终结符号，则从左向右构成句子。推导过程不同，生成语法树的过程也不同，但最终生成的语法树是相同的。但最终生成的语法树是相同的。例2.8 根据如下推导过程构造语法树。=3 =3 =23 =23 =123数字串数字串无符号整数无符号整数 数字串数字串数字串数字串数字数字数字数字3数字数字2 1 图2.1 语法树 返回1返回22.3.2 2.3.2 语法树和二义性语法树和二义性算术表达式的运算规则是乘除高于加减，if语句规定else就近配对，为什么呢？这是为了解决文法的二义性问题。前面我们介绍语法树时说过，推导过程不同，生成语法树的过程也不同，但最终生成的语法树是相同的，这是在文法没有二义的条件下才成立。如果一个文法所定义的句子中有某个句子或句型，它存在两棵不同的语法树，那么这个句子或句型是二义性的，该文法是二义性文法。例2.9 有文法GE：E E+E|E*E|（E）|i，分析该文法是否为二义性文法。解：为了判断该文法是否为二义性文法，我们找一个句子i+i*i，如果能够构造出两个不同的语法树，则说明该文法是二义性文法。下面两个图是为句子i+i*i构造的两棵语法树，如图2.2(a)、(b)所示。由于这两棵语法树不同，所以可以肯定文法GE 是二义性文法。2.3.2 2.3.2 语法树和二义性语法树和二义性EE+EE*EiiiEE*EEEiii+图2.2(a)语法树1 图2.2(b)语法树2 二义性产生的后果会导致分析结果不同，导致对句子的理解不同。在图2.2(a)语法树1中，根据规范归约构造的推导过程为：E=E+E=E+E*E=E+E*i=E+i*i=i+i*i在图2.2(b)语法树1中，根据规范归约构造的推导过程为：E=E*E=E*i=E+E*i=E+i*i=i+i*i由于图2.2(a)语法树1中的*先作为句柄归约，可理解成*优先于+进行运算，而图2.2(b)语法树2中的+先作为句柄归约，表示+优先于*进行运算。2.3.2 2.3.2 语法树和二义性语法树和二义性例2.10，IF语句文法如下：IFTHEN|IFTHENELSE|说明该文法是二义性文法。解：假设有一个IF语句嵌套的句型为：IFTHEN IFTHENELSE 根据文法可构造两棵语法树如图2.3(a)和图2.3(b)所示：2.3.2 2.3.2 语法树和二义性语法树和二义性语句语句 布尔表达式布尔表达式 IF THEN 语句语句 布尔表达式布尔表达式 IF THEN 语句语句 ELSE 语句语句 语句语句 布尔表达式布尔表达式 IF THEN 语句语句 布尔表达式布尔表达式 IF THEN 语句语句 ELSE 语句语句 图2.3(a)IF语句语法树1 图2.3(b)IF语句语法树2 由于这两棵语法树不同，所以该文法是二义性文法。图2.3(a)IF语句的语法树意味着ELSE和第2个THEN配对（就近配对），而图2.3(b)IF语句的语法树表示ELSE和第1个THEN配对。2.3.2 2.3.2 语法树和二义性语法树和二义性文法的二义性是不可判定的，即不存在一种算法，它能够在有限步内判定一个文法的二义性是不可判定的，即不存在一种算法，它能够在有限步内判定一个文法是否是二义性的。第文法是否是二义性的。第4章讨论的章讨论的LL，LR等几类重要文法都是无二义性的。等几类重要文法都是无二义性的。同时，还存在这样一些算法，可判定任一前后文无关文法是否为同时，还存在这样一些算法，可判定任一前后文无关文法是否为LL，LR文法。文法。不过，文法的不过，文法的LL性，性，LR性只是文法无二义性的充分条件。另一方面，还存在性只是文法无二义性的充分条件。另一方面，还存在一些用来检查文法二义性的其他充分条件。若一个文法一些用来检查文法二义性的其他充分条件。若一个文法G含有既是左递归又是含有既是左递归又是右递归的非终结符号右递归的非终结符号A，即有，即有A=AuAuV*或或A=A或或A=A及及A=A则则G必定是二义性文法。必定是二义性文法。有时，我们还可以把一个二义性文法变换成一个等价的无二义性文法。有时，我们还可以把一个二义性文法变换成一个等价的无二义性文法。例2.11，改写文法GE：E E+E|E*E|（E）|i，使其无二义性。解：新添非终结符号T和F，将文法写成：E T|E+T，T F|T*F，F (E)|i2.3.3 2.3.3 短语和句柄短语和句柄 短语、简单短语和句柄在分析中有着重要的作用，后面介绍自底向上的语法分析时就可看到如何找句柄是非常关键的。短语是句型的子串，是在句型的推导过程中能由某个非终结符号推导出的子串，而简单短语则是能由某个非终结符号直接推导出的子串。它们的形式定义如下：1.短语短语：设GS是一文法,w=xuy是一句型,如果有 S=*xUy且且U=+u,其中UVn,uV+，那么,我们称u是句型w相对于非终结符号U的短语。2.简简单单短短语语：若有 S=*xUy且且U=u，那么,我们称u是句型w相对于非终结符号U的简单短语。3.句柄句柄：任一句型的最左简单短语（即规范分析中，最先被规约的子串）称为该句型句柄。S=*xUy=+xuy2.3.3 2.3.3 短语和句柄短语和句柄例2.7 对于文法G,确定句型1的短语、简单短语和句柄。解：首先构造句型1的推导过程如下：=11)由于=*,而=+1,对照定义，子串1是由非终结符号推出的，所以是相对的短语。2)由于=*,而=+1,所以子串1是相对的短语。3)由于=*,而=1，且1是由非终结符号直接推出的，所以子串1是相对的短语,而且是简单短语。在句型1中,只有一个简单短语1,所以它就是该句型的句柄。2.3.3 2.3.3 短语和句柄短语和句柄 语法树的子树是由该树的某个节点（子树的根）连同它所有的后裔构成。子树与短语一一对应。要找一个句型的短语，可先画出该句型的语法树。判明语法树中的每棵子树，那么每棵子树的末端节点自左向右组成的符号串，就是相对于子树根符号的短语。原则上语法树中有多少棵子树，就有多少个短语。123的语法树例例2.8根据文法根据文法G，找句子，找句子123的短语、简单短语和句柄。的短语、简单短语和句柄。解：首先画出产生句子123的语法树，见图2.1。该语法树共有7棵子树。子树1：树根，末端节点1、2、3，短语为123子树2：树根，末端节点1、2、3，短语为123子树3：树根，末端节点1、2，短语为12子树4：树根，末端节点1，短语为1子树5：树根，末端节点1，短语为1，且为简单短语、句柄子树6：树根，末端节点2，短语为2，且为简单短语子树7：树根，末端节点3，短语为3，且为简单短语在这7个子树中，只有子树5、6、7的根节点与末端节点都是父子关系，所以这几个子树的末端节点形成的短语1、2、3都是简单短语。而子树5位于其中的最左端，所以短语1还是句柄。2.3.3 2.3.3 短语和句柄短语和句柄前面分析过，采用自底向上的语法分析时，每按一个产生式进前面分析过，采用自底向上的语法分析时，每按一个产生式进行一次归约，就用该产生式的左部去替换当前句型中的子串。行一次归约，就用该产生式的左部去替换当前句型中的子串。从语法树的角度来看，就是把该句型的语法树的一棵直接子树从语法树的角度来看，就是把该句型的语法树的一棵直接子树的末端节点剪去。换言之，语法分析每次所归约的符号串必然的末端节点剪去。换言之，语法分析每次所归约的符号串必然是当前句型的某一直接短语。但是，由于一个句型中的直接短是当前句型的某一直接短语。但是，由于一个句型中的直接短语可能不止一个，故为了使语法分析按一种确定的方式来进行，语可能不止一个，故为了使语法分析按一种确定的方式来进行，通常我们只考虑最左归约即规范归约。通常我们只考虑最左归约即规范归约。123的规范推导的规范推导1.如何确定一个规范句型的句柄？2.应将句柄归约为哪个非终结符号？2.4 2.4 文法的化简和改造文法的化简和改造 实用限制就是从实用的观点出发，对文法做一些必要的限制。实用限制就是从实用的观点出发，对文法做一些必要的限制。本节讨论如下三个问题：本节讨论如下三个问题：1)无用符号和无用产生式的删除。无用符号和无用产生式的删除。2)-产生式的删除。产生式的删除。3)单产生式的删除。单产生式的删除。（消除文法的左递归在后面讨论）（消除文法的左递归在后面讨论）2.4.1 2.4.1 无用符号和无用产生式的删除无用符号和无用产生式的删除 设设G是一文法，我们说是一文法，我们说G中一符号中一符号X是有用的，是指是有用的，是指X至少出至少出现在一个句子的推导过程中，即现在一个句子的推导过程中，即X必须同时满足以下两个条必须同时满足以下两个条件：件：1)X必须在某个句型中出现，必须在某个句型中出现，2)即存在即存在，V*，有，有S=*X2)必须能够从必须能够从X推导出终结符号串，推导出终结符号串，即存在即存在wVt*，使，使X=*w否则，就说否则，就说X是无用的。是无用的。含有无用符号的产生式称为无用产生式。含有无用符号的产生式称为无用产生式。2.4.1 2.4.1 无用符号和无用产生式的删除无用符号和无用产生式的删除 算法算法2.1用来将文法用来将文法G=(Vn,Vt,P,S)改造为等价的文法改造为等价的文法G1=(Vn1,Vt,P1,S)，使得对于每个，使得对于每个XVn1,都有都有w1Vt*，满足，满足X=*w1。（即改造为满足条件（即改造为满足条件2的文法）的文法）算法算法2.1分别置分别置Vn1，P1为空；为空；对于对于P中的每一产生式中的每一产生式A，若，若Vt*，则将，则将A置于置于Vn1中；中；对于对于P中的每一产生式中的每一产生式AX1X2Xm，若每一个，若每一个Xi都属于都属于Vt或或Vn1，则将则将A置于置于Vn1中；中；重复步骤重复步骤3，直到，直到Vn1不再增大为止；不再增大为止；对于对于P中的每一产生式中的每一产生式BY1Y2Yn，若，若B及每一个及每一个Yi都属于都属于Vt或或Vn1，则将此产生式置于则将此产生式置于P1中。中。2.4.1 2.4.1 无用符号和无用产生式的删除无用符号和无用产生式的删除 对于给定的文法对于给定的文法G，若执行算法，若执行算法2.2，便能得到一等价的文法，便能得到一等价的文法G=(Vn,Vt,P,S)，使得对于每个，使得对于每个XVnVt,都存在都存在，（VnVt）*,有有S=*X。（即改造为满足条件。（即改造为满足条件1的的文法）文法）算法算法2.2分别置分别置Vn，Vt，P为空；为空；将文法将文法G的开始符号的开始符号S置于置于Vn中；中；对于对于G中任何形如中任何形如A 1 2 m的产生式，若的产生式，若A属于属于Vn，则将符号串，则将符号串 1，2，m中的全部非终结符置于中的全部非终结符置于Vn中，中，而将其中的全部终结符置于而将其中的全部终结符置于Vt中中；重复步骤重复步骤3，直到，直到Vn和和Vt都都不再增大为止；不再增大为止；将将P中左右部仅含中左右部仅含VnVt中的符号的所有中的符号的所有产生式置于产生式置于P中。中。2.4.1 2.4.1 无用符号和无用产生式的删除无用符号和无用产生式的删除 例如，对于文法例如，对于文法G=(S,U,V,W,a,b,c,P,S)其中，其中，P为为SaSSWSUUaVbVVacWaW对对G执行算法执行算法.步骤如下：步骤如下：由于由于Ua及及Vac，故，故Vn1U,V;对于产生式对于产生式SU，由于，由于UVn1，故，故Vn1S,U,V;V