kubvu6-SLR.pptVIP免费

6.3SLR(1)分析技术例1：（0）S`→S(1)S→rD(2)D→D,i(3)D→iRealx,y,…LR（0）项目1)S`→．S2)S`→S．3)S→．rD4)S→r．D5)S→rD．6)D→．D,i7)D→D．,i8)D→D,．i9)D→D,i．10)D→．i11)D→i．例：（0）S`→S(1)S→rD(2)D→D,i(3)D→iLR（0）项目集规范族I0:S`→．SI3:S→rD．S→．rDD→D．，iI1:S`→S．I4:D→i．I2:S→r．DI5:D→D,.iD→．D，iI6:D→D，i．D→．i其中I3中含有移进/归约冲突文法不是LR(0)的，如何解决？LR(0)技术的局限性没有查看下一符号(Token),决定分析动作仅仅根据到目前已经看到的东西.能力弱.改进办法:向前查看下一符号---SLR(1),LR(1),LALR(1)识别活前缀的DFA•启示:LR分析使用的信息之一是句柄左部的内容.•定义(非终结符的左文)LC(A)={|S’A,V*,Vt*},对拓广文法的开始符号S’:LC(S’)={}若有BA则:LC(A)LC(B).{}因为:S’BA又:LC(B),LC(A)即LC(B).{}LC(A)R*R*G[S]:(0)S’S(1)SaAcBe(2)Ab(3)AAb(4)Bd每个非终结符的左文方程组•LC(S’)={}•LC(S)=LC(S’).{}•LC(A)=LC(S).{a}LC(A){}•LC(B)=LC(S).{aAc}化简为：•[S’]=•[S]=[S’]•[A]=[S]a+[A]•[B]=[S]aAc用代入法求解得：•[S’]=•[S]=•[A]=a+[A]•[B]=aAc令={[S’]，[S]，[A]，[B]，a，A,c}则方程两边都是上的正规式而[A]=a+[A]即为[A]=a|[A]由正规式所表示的正规集•得：[A]=aG[S]:(0)S’S(1)SaAcBe(2)Ab(3)AAb(4)Bd定义(产生式的LR(0)左文)LR(0)LC(A)={|=且S’A,Vt*}有推论：LR(0)LC(A)=LC(A).{}则有:LR(0)LC(S’S)=SLR(0)(LC(SaAcBe)=aAcBeLR(0)LC(Ab)=abLR(0)LC(AAb)=aAbLR(0)LC(Bd)=aAcd(=VnVt)上的正规式R*RI3:S→rD．D→D．，i例1文法的LR（0）分析表有多重入口状态ACTIONGOTOr,i#SD．0S211acc2S433r1S5r1r1r14r3r3r3r35S66r2r2r2r2I3:S→rD．D→D．，i使用FOLLOW(S){,}=信息解决冲突例1文法的（改进的）SLR（1）分析表状态ACTIONGOTOr,i#SD．0S211acc2S433r1S5r1r14r3r3r3r35S66r2r2r2r2SLR(1)技术•如果LR(0)项目集规范族中某个项目集IK含移进/归约归约/归约冲突：IK:{...A→α.bβ,Pω.,Q.,…}若FOLLOW(Q)FOLLOW(P)=FOLLOW(P){b}=FOLLOW(Q){b}=则解决冲突的SLR(1)技术：action[k,b]=移进对aFOLLOW(P)则action[k,a]=用Pω归约对cFOLLOW(Q)则action[k,c]=用Q归约...