编译原理5.3.4-规范LR分析表的构造

5.3.4规范LR分析表的构造通过例子引入LR(k)项目1.LR(k)项目定义2.有效LR(1)项目3.构造LR(1)项目集规范族4.构造LR(1)分析表5.LR(1)文法文法5.9p113(0)S'S(1)SL=R(2)SR(3)L*R(4)Li(5)RLI2:移进-归约冲突例:I0:S'•SS•L=RS•RL•*RL•iR•LI6:SL=•RR•LL•*RL•iI2:SL•=RRL•I4:L*•RR•LL•*RL•iI1:S'S•I3:SR•I7:L*R•I8:RL•I5:Li•I9:SL=R•=R*RLiRS*iiL*LFOLOW(R)={#,=}文法不含有以R=为前缀的规范句型,因此不能用RL对于栈顶的L进行归约(0)S'S(1)SaAd(2)SbAc(3)Saec(4)Sbed(5)AeI0:S'•SS•aAdS•bAcS•aecS•bedI1:S'S•SI2:Sa•AdSa•ecA•eI3:Sb•AcSb•edA•eabAeI4:SaA•dI5:Sae•cAe•AeI6:SbA•cI7:Sbe•dAe•dI8:SaAd•cI9:Saec•cI10:SbAc•dI11:Sbed•FOLLOW(A)={c,d}I5,I7中冲突不能用SLR(1)方法解决补充例1(0)S'S(1)SaAd(2)SbAc(3)Saec(4)Sbed(5)AeI5:Sae•cAe•I7:Sbe•dAe•所有可能的规范推导序列:S'=S=aAd=aedS'=S=bAc=becS'=S=aecS'=S=bedI5识别活前缀ae,不存在规范句型aAc,•当面临输入符号为c时应移进•面临d时应用产生式A→e归约I7识别活前缀be,不存在规范句型bAd,•当面临输入符号为d时应移进•面临c时应用产生式A→e归约结论:并不是FOLLOW(A)的每个元素,在含A的所有句型中,在A的后面都会出现小结:SLR(1)分析法中的无效归约I2:SL•=RRL•(0)S'S(1)SL=R(2)SR(3)L*R(4)Li(5)RLFOLLOW(R)={#,=}(0)S'S(1)SaAd(2)SbAc(3)Saec(4)Sbed(5)AeI5:Sae•cAe•I7:Sbe•dAe•FOLLOW(A)={c,d}•在SLR(1)方法中,,若项目集Ik含有A→α·,则在状态k时,只要所面临的输入符号a∈FOLLOW(A)，就用A→α归约•栈里的符号串所构成的活前缀βα未必允许把α归约为A，因为可能没有一个规范句型含有前缀βAa。因此，在这种情况下，用A→α进行归约未必有效。1.LR(K)项目定义•重新定义项目:[A→α·β，a1a2…ak]A→α·β是一个LR(0)项目,称为心,a1a2…ak称为它的向前搜索符串(展望串),ai是终结符,这样的一个项目称为一个LR(k)项目。•向前搜索符串仅对归约项目[A→α·，a1a2…ak]有意义.对于任何移进或待约项目不起作用。若存在规范推导则项目A•对活前缀是有效的。若aFirst()，若=则a=#则LR(1)项目[A•,a]对于活前缀是有效的。注:1)如果aFirst(),即使aFollow(A),项目[A•,a]也是无效的。2)规范LR分析法仅考虑有效的LR(1)项目。2.有效LR(1)项目*RRAS'例5.12:SBBBaB|bSRBBRBaBRBabRaBabRaaBabRaaaBabRS*RaaBabaaaBab[Ba·B,a]对活前缀=aaa是有效的*RRAS'RS*RBaBBaaB[Ba·B,#]对活前缀=Baa是有效的3.构造LR(1)项目集规范族一、项目集I的闭包CLOSURE(I)(1)I的任何项目都属于CLOSURE(I)(2)若项目[A→α·Bβ，a]属于CLOSURE(I)如果[B→·γ,b]原来不在CLOSURE(I)中，则把它加进去。B→γ是一个产生式,b∈FIRST(βa)(3)重复执行步骤(2),直到CLOSURE(I)不再增大为止二、GO函数令I是一个项目集，X是一个文法符号，GO(I,X)=CLOSURE(J)，其中J={任何形如[AX•,a]的项目|[A•X,a]I}注：在执行转换函数GO时，搜索符并不改变。三、构造G'的LR(1)项目集族C的算法BEGINC:={CLOSURE({[S'•S,#]})};REPEATFORC中的每个项目集I和G'的每个文法符号XIFGO(I,X)非空且不属于CTHEN把GO(I,X)加入C中；UNTILLC不再增大；END例5.13考虑如下拓广文法p115(0)S'S(1)SBB(2)BaB(3)Bb构造LR(1)项目集规范族I0:CLOSURE({[S'•S,#]})S'•S,#S•BB,#B•aB,a/bB•b,a/bSI0：S→·S,#S→·BB,#B→·aB,a/bB→·b,a/b′BI2：S→B·B,#B→·aB,#B→·b,#I4：B→b·,a/bbI3：B→a·B,a/bB→·aB,a/bB→·b,a/bbbI7：B→b·,#I8：B→aB·,a/baBI5：S→BB·,#I6：B→a·B,#B→·aB,#B→·b,#BaaI9：B→aB·,#baB图5.10LR(1)项目集和GO函数p116更正教材(0)S'S(1)SBB(2)BaB(3)BbI1：S→S·,#′4.构造LR(1)分析表(1)若项目[A→α·aβ,b]Ik且GO(Ik,a)=Ij，置ACTION[k,a]为sj。(2)若项目[A→α·,a]Ik，j是产生式A→α的编号置ACTION[k,a]为rj，(3)若项目[S'→S·，#]Ik，置ACTION[k,#]为acc。(4)若GO(Ik,A)=Ij，置GOTO[k,A]=j。(5)分析表中凡不能用规则(1)～(4)填入的空白格均置为“出错标志”。表5.5例5.13的LR分析表p116状态ACTIONGOTOab#SB0s3s4121acc2s6s753s3S484r3r35r16s6s797r38r2r29r25.LR(1)文法•若文法G'按构造LR(1)分析表算法构造出来的分析表不包含多重定义项，则该文法G'是LR(1)文法。•注:1）每个SLR(1)文法都是LR(1)文法，反之不一定成立；2）一个文法的规范LR分析表☆比其SLR分析表含有更多的状态。在严重的情况下，状态数可能成倍增长。因此需要简化。文法5.9p113(0)S'S(1)SL=R(2)SR(3)L*R(4)Li(5)RL例求LR(1)项目集规范族S'•S,#S•L=R,#S•R,#L•*R,=/#L•i,=/#R•L,#I0初态简化为S'•S,#S•L=R,#S•R,#L•*R,=L•i,=R•L,#L•*R,#L•i,#I0初态I1:Go(I0,S)SS•,#I2:Go(I0,L)SL•=R,#RL•,#I3:Go(I0,R)SR•,#I4:Go(I0,*)L*•R,=/#R•L,=/#L•*R,=/#L•i•,=/#I5:Go(I0,i)Li•,=/#I6:Go(I2,=)SL=•R,#R•L,#L•*R,#L•i•,#I7:Go(I4,R)L*R•,=/#I8:Go(I4,L)RL•,=/#Go(I4,*)同I4Go(I4,i)同I5I9:Go(I6,R)SL=R•,#I10:Go(I6,L)RL•,#I11:Go(I6,*)L*•R,#R•L,#L•*R,#L•i•,#I12:Go(I6,i)Li•,#I13:Go(I11,R)L*R•,#Go(I11,L)同I10Go(I11,*)同I11Go(I11,i)同I12S'•S,#S•L=R,#S•R,#L•*R,=/#L•i,=/#R•L,#I0初态状态ACTIONGOTO=i*#SLR0S5S41231acc2S6r53r24S5S4875r4r46S12S111097r3r38r5r59r110r511S12S11101312r413r3补充练习LR(0)分析,归约时向前查看的符号为____________SLR(1)分析,归约时向前查看的符号为____________LR(1)分析,归约时向前查看的符号为____________向前搜索符无FOLLOW集