精品课程《编译原理》PPT课件第7章LR分析

7.1LR分析概述,设有文法GZ:ZaBDcBbDd,LR(K)的含义:L表示从左到右扫描输入串，R表示最左规约(即最右推导的逆过程)，K表示向右查看输入串符号的个数。当K=1时，能满足当前绝大多数高级语言编译程序的需要，所以着重介绍LR(0)，SLR(1)，LR(1)，LALR(1)方法。,分析,特征:规范的符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号(活前缀)分析决策依据栈顶状态和现行输入符号识别活前缀的DFA.四种技术LR(0)SLR(1)LR(1)LALR(1),LR(0)文法能力最弱，理论上最重要存在FA识别活前缀识别活前缀的DFA如何构造（LR(0)项目集规范族的构造）LR(0)分析表的构造,7.2LR（0）分析,定义如果有Z(Z为开始符)，且为终极符串(或空)。称是规范前缀。若是含有句柄的规范前缀,且每个句柄是的后端，称是可归规范前缀。,例子：SmABcde,若其中Abc是句柄，根据定义有mABc是可归规范前缀。,定理设1A2为可归前缀，AVN，Au为一产生式，则1u也为可归前缀。,例:GZ:ZabAdAc若abAd是可归前缀，根据此定理abc也是可归前缀。,即：1A21u2,例:GS:SaAc1AAbb2Ab3求：该文法的可归前缀图,生成过程：,构造可归前缀图方法,自动机直观法,形式化方法,形式化方法,设BX1X2XnP是产生式P，则称形如X1X2XiXi+1XnP的侯选式为LR(0)项目(简称项目)。(圆点可在X1之前,也可在Xn之后)。,定义,称形如X1X2XnP的项目为归约项目。移进项目:除归约项目外的其它形式。,设I为项目集,则定义Close(I)=I.uP|AuPG,A1Close(I)称Close(I)为I的闭包集。,设I为项目集,则GO(I,X)=CLOSE(IX)其中IX=X.P|.XPI,构造LR(0)项目集规范族,LR(0)项目集规范族(构成识别一个文法的活前缀的DFA的状态的全体)。LR（0）项目或配置（itemorconfiguration）.-在右端某一位置有圆点的G的产生式AxyzA.xyzAx.yzAxy.zAxyz.如：SaAdS.aAdSa.AdSaA.dSaAd.,可归前缀图的构造算法,1.先产生初始项目集I1=Close(.P|ZPG,Z为初始符)。2.若I是新项目集,则对每X(VNVT),产生项目集GO(I,X)。若两项目集完全相同,则作为一项目集。3.重复2至不产生新项目集为止。4.图的结点由上述项目集组成,且若GO(Ii,X)=Ij,则有IiIj。,例:G(S):SaAc1AbB2|ba3BdB4|e5,0:S.aAc1,1:a.Ac1.bB2.ba3,2:aA.c1,1:a.Ac1.bB2.ba3,aAc.1,1:a.Ac1.bB2.ba3,3:b.B2b.a3.dB4.e5,bB.2,3:b.B2b.a3.dB4.e5,ba.3,3:b.B2b.a3.dB4.e5,e.5,3:b.B2b.a3.dB4.e5,4:d.B4.dB4.e5,3:b.B2b.a3.dB4.e5,dB.4,4:d.B4.dB4.e5,e,4:d.B4.dB4.e5,d,4:d.B4.dB4.e5,定义,二义性结点：可归前缀图的一个结点包含多个归约项目或同时包含移进项目和归约项目。,LR(0)文法：文法的可归前缀图不包含二义性结点(可用于判是否LR(0)文法)。,LR分析法的分析栈由两个栈组成：状态栈、符号栈。,例子：AaBcBaBab,LR分析法的步骤：格局为(01i,#X0X1Xi,ajaj+1an#)状态栈符号栈输入流,1.若ACTIONi,aj=sk,则有(01K,#X0X1Xi,ajaj+1an#)。,2.若ACTIONi,aj=rp,则先把符号栈归约Ap(P产生式的左部),从状态栈删除np(为侯选式的长度)个状态(后端),再压入=Gotoi-np,Ap有(0i-np,#X0XiAp,ajaj+1an#)。,3.若ACTIONi,aj=ok,则成功。4.若ACTIONi,aj=en,则失败。,分析法的动作:Sjs表示“移进”,j表压入编号rjr表示“归约”,j表产生式号ok表示分析成功eje表示错误,j表错误编号,例：G(E):EaA|bBAcA|dBcB|d1.用形式化方法作可归前缀图。2.求LR(0)矩阵。3.写出输入串bccd的LR(0)分析过程。,解：可归前缀图,G(S):SE0EaA1EbB2AcA3Ad4BcB5Bd6,解：拓展文法的新文法如下：,0:S.EE.bBE.aA,1:SE.,0:S.EE.bBE.aA,a,2:Ea.AA.dA.cA,0:S.EE.bBE.aA,A,6:EaA.,2:Ea.AA.dA.cA,d,10:Ad.,2:Ea.AA.dA.cA,4:Ac.AA.dA.cA,2:Ea.AA.dA.cA,d,4:Ac.AA.dA.cA,4:Ac.AA.dA.cA,A,8:AcA.,4:Ac.AA.dA.cA,0:S.EE.bBE.aA,3:Eb.BB.dB.cB,7:EbB.,3:Eb.BB.dB.cB,d,11:Bd.,3:Eb.BB.dB.cB,5:Bc.BB.cBB.d,3:Eb.BB.dB.cB,d,5:Bc.BB.cBB.d,c,5:Bc.BB.cBB.d,9:BcB.,5:Bc.BB.cBB.d,解：LR(0)矩阵s表示状态r表示归约,LR(0)分析过程的关键点：1.用分析栈的栈顶元素对输入串的第一个元素查矩阵，以确定下一步的动作。2.每一步都要保持分析栈和符号栈长度一致。3.归约时，符号栈的元素（产生式的右部）弹出栈时，等长的分析栈元素同时弹出栈，以保持两栈长度一致。4.归约时，产生式的左部压进符号栈时，分析栈压进分析栈栈顶元素对产生式左边查goto矩阵得到的状态编号。例如：第5步：用Bd归约,d，(11)出栈，B进栈；5对B查表得9。,动画演示,解：串bccd的LR(0)分析过程,分析器模型,例GS为:SaAcBeAbAAbBd1)构造识别活前缀的DFA2)构造它的LR(0)分析表。3)分别给出对输入符号串abbcde和Abbce的LR(0)分析步骤。,GS拓广为:SSSaAcBeAbAAbBd,I0:SSSaAcBe,I1:SS,I2:SaAcBeAbAAb,I3:SaAcBeAAb,I4:Ab,I5:SaAcBeBd,I7:SaAcBe,I8:Bd,I9:SaAcBe,I6:AAb,S,a,A,b,b,c,B,e,d,GL=abbcde,GS的LR(0)分析表,Stepstates.Syms.Therestofinputactiongoto10#abbcde#s2202#abbcde#s43024#abbcde#r234023#aAbcde#s650236#aAbcde#r336023#aAcde#s570235#aAcde#s8802358#aAcde#r47902357#aAcBe#s910023579#aAcBe#r111101#S#acc,对输入串abbcde#的分析过程,Stepstates.Syms.Therestofinputactiongoto10#abbce#s2202#abbce#s43024#abbce#r234023#aAbce#s650236#aAbce#r336023#aAce#s570235#aAce#出错说明abbce#不是例6.1文法GS的句子,对输入串abbce#的分析过程,当有I=xbAr时，为移进-归约冲突，如果FOLLOW(A)b=；或当有I=ArB时，为归约-归约冲突，如果FOLLOW(A)FOLLOW(B)=,则称该冲突可以解决。,7.3SLR（1）分析,SLR(1)方法:是只在LR(0)可归前缀图的二义性状态下向前看一符。当有I=xbArBFOLLOW(A)FOLLOW(B)=,FOLLOW(A)b=；FOLLOW(B)b=则称该冲突可以解决。满足上述条件则可利用SLR(1)方法,例：有项目集SAa.bBcAd.Be.设：FOLLOW(A)=a，FOLLOW(B)c所以：FOLLOW(A)FOLLOW(B)=,FOLLOW(A)b=；FOLLOW(B)b=所以本文法是SLR(1)文法。,现举实型变量说明文法为例：real，ii,将该文法缩写后并拓广为G如下：1.SS02.SrD13.DD,i24.Di3得图如下：,0:S.SS.rD,S,1:SS.,r,2:Sr.DD.D,iD.i,D,3:SrD.DD.,i,i,4:Di.,5:DD,.i,i,6:DD,i.,冲突,实数说明文法的LR(0)分析表如下：,follow(S)=follow(S)=#follow(S),=#,=,满足上述条件则可利用SLR(1)方法。转化情况如下：,实数说明文法的SLR(1)分析表如下：,LR（1）项目(配置）的一般形式A.，a意味着处在栈顶是的相应状态，期望相应在栈顶的状态，然后只有当跟在后的token是终结符a时进行归约。a称作该项目(配置）的向前搜索符（lookahead）向前搜索符（lookahead）只对圆点在最后的项目起作用A,a.意味着处在栈中是的相应状态，但只有当下一个输入符是a时才能进行归约.a要么是一个终结符，要么是输入结束标记#有多个向前搜索符，比如a,b,c时，可写作Au,a/b/c,7.4LR（1）分析,LR(1)项目:即为二元组,a,其中是LR(0)项目,aVT#。,定义3.17设I为LR(1)项目集,则定义Close(I)=I.p,b|BpG,.Be,aClose(I),bfirst(a)称Close(I)为I的闭包。,GO(I,X)=Close(IX)其中IX=X.p,b|.Xp,bI,例子：若文法GS为：SS0SBB1BaB2Bb3则其转换图和分析表如下：,I0:SS,#,I0:SS,#SBB,#BaB,a|bBb,a|b,求初始项目集：,求初始项目集的闭包集：,LR(1)比SLR（1）能力强,例设有文法GS(0)SS(1)SL=R(2)SR(3)L*R(4)Lid(5)RL该文法不能用SLR（1）技术解决，但能用LR（1）,I1:SS,#,I5:Li,=/#,I7:L*R,=/#,I8:RL,=/#,I9:SL=R,#,I3:SR,#,I12:Li,#,I10:RL,#,I13:L*R,#,I0:SS,#SL=R,#SR,#L*R,=/#Li,=/#RL,#,I4:L*R,=/#RL,=/#Li,=/#L*R,=/#,I6:SL=R,#RL,#L*R,#Li,#,I11:L*R,#RL,#L*R,#Li,#,I2:SL=R,#RL,#,s,R,=,L,R,i,i,*,i,i,R,L,L,R,L,*,*,*,例LR(1)项目集及转换函数,每个SLR（1）文法都是LR（1）的，一个SLR（1）文法的规范LR分析器比其SLR（1）分析器的状态要多。,例子：若文法GS为：SS0SBB1BaB2Bb3（注：与前例文法同）,LALR1方法：,同心项目集合：I0:S.SS.BBB.aBB.bI1:SS.I2:SB.BB.aBB.bI3:Ba.BB.aBB.bI4:BaB.I5:Bb.I6:SBB.,I0:SS,#SBB,#BaB,a/bBb,a/b,I1:SS,#,I2:SBB,#BaB,#Bb,#,I5:SBB,#,I6:SaB,#BaB,#Bb,#,I3:BaB,a/bBaB,a/bBb,a/b,I4:Bb,a/b,I7:Bb,#,I9:BaB,#,I8:BaB,a/b,s,B,B,a,b,b,b,B,B,a,a,a,LR(1)项目集和转换函数,b,LALR在SLR（1）和LR（1）间寻找折衷办法（状态数目，分析能力）,LALR(lookaheadLR)合并同心集I36I47I89,I3:BaB,a/bBaB,a/bBb,a/b,I6:SaB,#BaB,#Bb,#,I4:Bb,a/b,I7:Bb,#,I8:BaB,a/b,I9:BaB,#,构造LALR(1)分析表.方法1,1.构造文法G的规范LR(1)状态.2.合并同心集（除搜索符外两个集合是相同的）的状态.3.新LALR(1)状态的GO函数是合并的同心集状态的GO函数的并.4.LALR(1)分析表的action和goto登录方法与LR(1)分析表一样.经上述步骤构造的表若不存在冲突，则称它为G的LALR(1)分析表。存在这种分析表的文法称为LALR（1）文法。,LR(0)、SLR(1)、LR(1)、LALR(1)方法比较实际上不同LR方法之间的主要区别就在于归约的判定方法上：LR(0)是不看展望符判定归约；SLR(1)是看展望符，但把所有B的展望符集均定义为Follow(B)。即把符号栈顶上的句柄归约为B的条件是：展望符为Follow(B)中的元素。换句话说，归约任何位置上的B，都用统一的展望符集；LR(1)也是看展望符，但归约不同位置上的B时，采用不同的展望符集。每个项由心与向前搜索符组成，搜索符长度为1。由于LR(1)方法对于归约条件的判定比SLR(1)更