东北大学秦皇岛分校编译原理课件第二章第七章.ppt

第7章LR分析法,7.1LR类分析法,LR分析法根据当前分析栈和输入串来确定句柄。LR分析过程是一种规范归约过程。LR分析法适用于大多数无二义性的上下文无关文法。常用的LR分析法有：（1）LR（0）分析法（2）SLR（1）分析法（3）LALR（1）分析法（4）LR（1）分析法,LR（K）的含义：L表示由左向右处理输入；R表示生成了最右推导；数字K表示使用了先行的K个符号。LR分析法同样要用到先行集合（FIRST集合）和后跟集合（FOLLOE集合）。SLR（1）是“简单LR（1）”的简写，是对LR（1）分析的改进。LALR（1）即先行LR（1），是比SLR（1）分析稍微强大但却比一般LR（1）分析简单的方法。,SEET|E+TTint|(E),Reduce:如能找到一产生式Aw且栈中的内容是qw(q可能为空),则可以将其归约为qA。即倒过来用这个产生式。如上例,若栈中内容是(int，我们使用产生式Tint并把栈中内容归约为(TShift:如不能执行一个归约且在输入串中还有token，就把它从输入串移到栈中。如上例,假定栈中内容是(,输入中还有int+int)#.不能对(执行一个归约，因为它不和任何产生式的右端匹配，所以把输入的第一个符号移到栈中,于是栈中内容是(int，而余留的输入是+int)#。,Reduce的一个特殊情况：栈中的全部内容w归约为开始符号S（即施用Sw），且没有余留输入了，意味着已成功分析了整个输入串.移进归约分析中还会出现一种情况，就是出错，比如当前的token不能构成一个合法句子的一部分，例如上面的文法，试分析int+)时就会发生错误。,STACKREMAININGINPUTPARSERACTION1(int+int)#Shift2(int+int)#Shift3(int+int)#Reduce:Tint4(T+int)#Reduce:ET5(E+int)#Shift6(E+int)#Shift7(E+int)#Reduce:Tint8(E+T)#Reduce:EE+T9(E)#Shift10(E)#Reduce:T(E)11T#Reduce:ET12E#Reduce:SE13S#,(E+T)#Reduce:EE+Twhy?不用ET(E)#若使用了ET，在栈中形成的(E+E不是规范句型的活前缀（viableprefixes）（E+E不能和任何产生式的右端匹配（E+E）不是规范句型活前缀：是规范句型（右句型）的前缀，但不超过句柄移进归约分析的栈中出现的内容加上余留输入构成规范句型,规范推导规范句型规范归约,最右推导：在推导的任何一步，其中、是句型，都是对中的最右非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型GS：SEEE+T|TT(E)|intSET(E)(E+T)(E+int)(T+int)(int+int)规范归约假定是G的一个句子，称序列n,n-1,0是的一个规范归约如果该序列满足：（1）n=（2）0为文法的开始符号（3）对任何j,0r是的前缀，则称r是G的一个活前缀1.活前缀已含有句柄的全部符号，表明产生式A的右部已出现在栈顶2.活前缀只含句柄的一部分符号表明A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号3.活前缀不含有句柄的任何符号，此时期望A的右部所推出的符号串,R,活前缀,与句柄,与LR(0)项目,为刻划这种分析过程中的文法G的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶）的情况，分别用标有圆点的产生式来指示位置。A刻划产生式A的右部已出现在栈顶A12刻划A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号A刻划没有句柄的任何符号在栈顶，此时期望A的右部所推出的符号串对于A的LR(0)项目只有A,构造识别活前缀的DFA,LR（0）项目集的闭包LOSURE,GO函数，functionCLOSURE(I);/*I是项目集*/J:=I;repeatforJ中的每个项目A.B和产生式B，若B.不在J中do将B.加到J中until再没有项目加到J中returnJ;GO(I,x)=CLOSURE(J);其中，I:项目集，x:文法符号，J=任何形如Ax.的项目|A.xI,LR（0）项目集的闭包LOSURE,若当前处于AXYZ刻划的情况，期望移进First(Y)中的某些符号，假如有产生式Yu|w.那么Yu和Yw这两个项目便是刻划期望移进First(Y)中的某些符号的情况.AXYZYuYw这三个项目对应移进归约分析的同一个状态,这三个项目构成一个配置集,对应每个配置集，分析表将有一个状态。,LR(0)项目集规范族,计算LR（0）项目集规范族C=I0，I1,.InProcedureitemsets(G);BeginC:=CLOSURE(S.S)RepeatForC中每一项目集I和每一文法符号xDoifGO(I,x)非空且不属于CThen把GO(I,x)放入C中UntilC不再增大End;,例：文法G:（0）SE(1)EaA(2)EbB(3)AcA(4)Ad(5)BcB(7)BdLR(0)项目集规范族（识别G的活前缀的DFA)：,I0：SEEaAEbB,I1：SE,I2：EaAA.cAAd,I3：EbBBcBBd,I4：Ac.AAcAA.d,I5：BcBBcBBd,I6：EaA,I7：EbB,I8：AcA,I9：BcB,I10：Ad,I11：BcB,LR(0)项目,根据圆点所在的位置和圆点后是终结符还是非终结符或为空把项目分为以下几种：移进项目，形如Aaa是终结符,V*以下同待约项目，形如AB归约项目，形如A接受项目，形如SSA的LR(0)项目只有A是归约项目,利用项目构造识别前缀的DFA,先根据项目按一定的规则画出其相应的NFA，然后再将该NFA确定化简为DFA：（1）如果状态i和状态j出自同一条规则：UX1X2Xn，并且状态j中的圆点只落后于状态i的圆点一个位置，即：如果状态i为：UX1X2Xi-1XiXn，状态j为：UX1X2Xi-1XiXi+1Xn，则从状态i出发，画一条标记为Xi的弧到状态j。（2）如果状态i的圆点之后的符号Xi为非终结符，则从状态i出发，画标记为的弧到所有形如Xi的项目。（3）将所得到的NFA进行确定化并化简，得到DFA。注意：对于规则U，其项目为U,项目集规范族,项目集规范族：构成识别一个文法活前缀的DFA项目集（状态）的全体称为该文法的LR(0)项目集规范族。用C=I0，I1，In表示。构造一个利用闭包函数求DFA一个状态的项目集：若文法G已拓广为G,而S为文法G的开始符号，拓广后增加产生式SS。如果I是文法G的一个项目集，定义和构造I的闭包CLOSURE（I）如下：（1）I的项目均在CLOSURE（I）中，（2）若AB属于CLOSURE（I），则每一形如B的项目也属于CLOSURE（I），（3）重复步骤（2）直到不出现新的项目为止。利用闭包函数和转向函数构造文法G的LR(0)项目集规范族：（1）置项目SS为初态集的核，然后对核求闭包，CLOSURE(SS)得到初态的项目集。（2）对初态集或其它所构造的项目集应用转换函数GO(I,X)=CLOSURE(J)求初新状态J的项目集。（3）重复步骤（2）直到不出现新的项目集为止。,构造识别可归前缀的有穷自动机,构造识别文法活前缀的有穷自动机（DFA）的三种方法：（1）一般方法：根据形式定义求出活前缀的正规表达式，然后由此正规表达式构造出相应的NFA，再确定化简为DFA。（2）利用项目直接构造：先求出文法的所有项目，按照一定规则构造识别活前缀的NFA，再将NFA确定化简为DFA。（3）通过求初态集的闭包来构造：把拓广文法的第一个项目SS作为初态集的核，通过求该核的闭包和转换函数，求出LR（0）项目集规范族，再由转换函数建立状态之间的连接关系得到识别前缀的DFA。,LR(0)分析表的构造,假定C=I0,I1,，In，令每个项目集Ik的下标k为分析器的一个状态，因此，G的LR(0)分析表含有状态0，1，n。令那个含有项目SS的Ik的下标k为初态。ACTION和GOTO可按如下方法构造：若项目Aa属于Ik且GO(Ik,a)=Ij,a为终结符，则置ACTIONk,a为“把状态j和符号a移进栈”，简记为“sj”;若项目A属于Ik,那么，对任何终结符a,置ACTIONk,a为“用产生式A进行归约”，简记为“rj”;其中，假定A为文法G的第j个产生式；若项目SS属于Ik,则置ACTIONk,#为“接受”，简记为“acc”;若GO(Ik,A)=Ij,A为非终结符，则置GOTO(k,A)=j;分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。,按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张LR(0)表。具有LR(0)表的文法G称为一个LR（0）文法。LR(0)文法是无二义的。,LR（0）文法,LR类分析法适用于大多数无二义性的上下文无关性文法。LR（0）分析方法对文法仍有一定限制：能够用LR（0）分析法进行分析的文法不能含有冲突项目。冲突项目的概念：如果一个项目集（状态）中既含有移进项目又含有归约项目，或者一个项目集中含有两（多）个不同的归约项目，则称为冲突项目。LR（0）文法的概念：如果由一个文法构造的识别可归前缀的DFA的每个项目集（状态）均不含有冲突项目，则称这样的文法为LR（0）文法。注：实际上，大多数适用的高级程序设计语言的文法都不能满足LR（0）文法的条件。,例：（0）SS(1)SrD(2)DD,i(3)DiLR（0）项目1.SS2.SS3.SrD4.SrD5.SrD6.DD,i7.DD,i8.DD,i9.DD,i10.Di11.Di,NFA,1,3,10,7,8,i,S,r,r,D,4,6,D,例：（0）SS(1)SrD(2)DD,i(3)DiLR（0）项目集规范族,I0:SSSrD,I1:SS,I5:DDi,I3:SrDDDi,I4:Di,I6:DDi,其中I3中含有移进/归约冲突,文法不是LR(0)的，如何解决？,I2:SrDDDiDi,其它LR类分析法,SLR（1）分析法SLR（1）分析法在一定程度上解决了LR（0）不能解决的含有冲突项目的问题。LR（1）分析法及分析表的构造SLR（1）分析法虽然在一定程度上解决了冲突项目的问题，但还存在下面两个问题：（1）SLR（1）分析法并没有彻底解决冲突问题；（2）SLR（1）分析法要求在出现冲突项目时，向前搜索符号集b1，b2，bn和FOLLOW（V1），FOLLOW（V2），FOLLOW（Vn）两两不相交，但并不是所有的上下文无关文法都满足这一要求。,SLR(1)技术,若LR(0)项目集规范族中有项目集IK含移进/归约归约/归约冲突：IK:.A.b,P.,Q.,若FOLLOWQA)FOLLOW(P)=FOLLOWP(P)b=FOLLOW(Q)b=则解决冲突的SLR(1)技术：actionk,b=移进对aFOLLOW(P)则actionk,a=用P归约对aFOLLOW(Q)则actionk,a=用Q归约能用SLR(1)技术解决冲突的文法称为SLR(1)文法。SLR(1)文法是无二义的。,SLR表,假定C=I0,I1,，In，令每个项目集Ik的下标k为分析器的一个状态，因此，G的SLR分析表含有状态0，1，n。令那个含有项目SS的Ik的下标k为初态。函数ACTION和GOTO可按如下方法构造：若项目Aa属于Ik且GO(Ik,a)=Ij,a为终结符，则置ACTIONk,a为“把状态j和符号a移进栈”，简记为“sj”;若项目A属于Ik,那么，对任何输入符号a,aFOLLOW(A),置ACTIONk,a为“用产生式A进行归约”，简记为“rj”;其中，假定A为文法G的第j个产生式；若项目SS属于Ik,则置ACTIONk,#为“接受”，简记为“acc”;若GO(Ik,A)=Ij,A为非终结符，则置GOTO(k,A)=j;分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张SLR表。具有SLR表的文法G称为一个SLR（1）文法。数字1的意思是，在分析过程中顶多只要向前看一个符号。,实数说明文法的SLR（1）分析表状态ACTIONGOTOr,i#SD0S211acc2S433r1S5r1r14r3r3r3r35S66r2r2r2r2,例：文法G:（0）SS(1)SaAd(2)SbAc(3)Saec(4)Sbed(5)AeLR(0)项目集规范族（识别G的活前缀的DFA)：I0