第七章LR分析.

第7章LR分析7.1LR分析概述ZaBDcaBdcabdcZaBDcabDcabdcrrrlllLR(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为开始符)，且β为终极符串(或空)。称α是规范前缀。若α是含有句柄的规范前缀,且每个句柄是α的后端，称α是可归规范前缀。r*例子：SmABcde-mABcdeemABcddemABccdemAB后缀规范前缀若其中Abc是句柄，根据定义有mABc是可归规范前缀。定理设α1Aα2为可归前缀，A∈VN，A→u为一产生式，则α1u也为可归前缀。例:G[Z]:Z→abAdA→c若abAd是可归前缀，根据此定理abc也是可归前缀。例:G(S):S→aAc[1]A→Abb[2]A→b[3][1]bcAa[3]bbA[2]S:A:子自动机123[2]0[3]cabbAb[1]可归前缀图生成过程：12,34[2]0[3]cabbAb[1][1]bcAa[3]bA[2]b34120构造可归前缀图方法自动机直观法形式化方法形式化方法,设B→X1X2…Xn[P]是产生式P，则称形如X1X2…XiXi+1…Xn[P]的侯选式为LR(0)项目(简称项目)。(圆点可在X1之前,也可在Xn之后)。定义称形如X1X2…Xn●[P]的项目为归约项目。移进项目:除此外其它形式。设I为项目集,则定义Close(I)=I∪{.u[P]|A→u[P]∈G,α●Aβ[1]∈Close(I)}且称Close(I)为I的闭包集。设I为项目集,则GO(I,X)=CLOSE(IX)其中IX={αX.β[P]|α.Xβ[P]∈I}构造LR(0)项目集规范族LR(0)项目集规范族(构成识别一个文法的活前缀的DFA的状态的全体)。LR（0）项目或配置（itemorconfiguration）.---在右端某一位置有圆点的G的产生式AxyzA.xyzAx.yzAxy.zAxyz.如：S→aAdS→.aAdS→a.AdS→aA.dS→aAd.例子：U→XYZ，求项目U→XYZU→XYZU→XYZU→XYZ移进项目归约项目可归前缀图的构造算法1.先产生初始项目集I1=Close({.α[P]|Z→α[P]∈G,Z为初始符})。2.若I是新项目集,则对每X∈(VN∪VT),产生项目集GO(I,X)。若两项目集完全相同,则作为一项目集。3.重复2至不产生新项目集为止。4.图的结点由上述项目集组成,且若GO(Ii,X)=Ij,则有IiIj。x例:G(S):S→aAc[1]A→bB[2]|ba[3]B→dB[4]|c[5]0:.aAc[1]a1:a.Ac[1].bB[2].ba[3]A2:aA.c[1]1:a.Ac[1].bB[2].ba[3]caAc.[1]b1:a.Ac[1].bB[2].ba[3]3:b.B[2]b.a[3].dB[4].e[5]BbB.[2]3:b.B[2]b.a[3].dB[4].e[5]aba.[3]3:b.B[2]b.a[3].dB[4].e[5]ee.[5]3:b.B[2]b.a[3].dB[4].e[5]d4:d.B[4].dB[4].e[5]3:b.B[2]b.a[3].dB[4].e[5]BdB.[4]4:d.B[4].dB[4].e[5]e4:d.B[4].dB[4].e[5]d4:d.B[4].dB[4].e[5]定义二义性结点：可归前缀图的一个结点包含多个归约项目或同时包含移进项目和归约项目。A→a.SB→D.移进、归约冲突A→aS.B→D.归约、归约冲突例：LR(0)文法：文法的可归前缀图不包含二义性结点(可用于判是否LR(0)文法)。LR分析法的分析栈由两个栈组成：状态栈、符号栈。例子：A→aBcB→aB→abLR分析法的步骤：格局为(01…i,#X0X1…Xi,ajaj+1…an#)状态栈符号栈输入流1.若ACTION[i,aj]=sk,则有(01…K,#X0X1…Xi,ajaj+1……an#)。2.若ACTION[i,aj]=rp,则先把符号栈归约Ap(P产生式的左部),从状态栈删除np(为侯选式的长度)个状态(后端),再压入=Goto[i-np,Ap]有(0…i-np,#X0…XiAp,ajaj+1…an#)。3.若ACTION[i,aj]=ok,则成功。4.若ACTION[i,aj]=en,则失败。分析法的动作:Sj—s表示“移进”,j表压入编号rj—r表示“归约”,j表产生式号ok—表示分析成功ej—e表示错误,j表错误编号例：G(E):E→aA|bBA→cA|dB→cB|d1.用形式化方法作可归前缀图。2.求LR(0)矩阵。3.写出输入串bccd的LR(0)分析过程。解：可归前缀图G(S):S→E[0]E→aA[1]E→bB[2]A→cA[3]A→d[4]B→cB[5]B→d[6]解：拓展文法的新文法如下：0:S→.EE→.bBE→.aAE1:S→E.0:S→.EE→.bBE→.aAa2:E→a.AA→.dA→.cA0:S→.EE→.bBE→.aAA6:E→aA.2:E→a.AA→.dA→.cAd10:A→d.2:E→a.AA→.dA→.cAc4:A→c.AA→.dA→.cA2:E→a.AA→.dA→.cAd4:A→c.AA→.dA→.cAc4:A→c.AA→.dA→.cAA8:A→cA.4:A→c.AA→.dA→.cAb0:S→.EE→.bBE→.aA3:E→b.BB→.dB→.cBB7:E→bB.3:E→b.BB→.dB→.cBd11:B→d.3:E→b.BB→.dB→.cBc5:B→c.BB→.cBB→.d3:E→b.BB→.dB→.cBd5:B→c.BB→.cBB→.dc5:B→c.BB→.cBB→.dB9:B→cB.5:B→c.BB→.cBB→.d解：LR(0)矩阵s表示状态r表示归约r4r4r4r4r410r6r6r6r6r611r5r5r5r5r59r3r3r3r3r38r2r2r2r2r27r1r1r1r1r169S11S558S10S447S11S536S10S42Acc11S3S20BAE#dcbaGotoAction状态第5步：d，(11)出栈，B进栈；5对B查表得9。动画演示S11d##bcc03554S5cd##bc0353S5ccd##b032S3bccd##01GOTOAction输入串符号栈状态栈步骤r6##bccd0355(11)59r6##bccB03555r5##bccB0355969r5##bcB0356解：串bccd的LR(0)分析过程acc##E0191r2##bB03787r5##bcB035979r5##bccB0355969r6##bccd0355(11)5S11d##bcc03554S5cd##bc0353S5ccd##b032S3bccd##01GOTOAction输入串符号栈状态栈步骤ＬＲ分析器模型总控程序outputInput#S1Xm…S1…X1S0#栈状态文法符号ACTIONGOTOLR分析表产生式表例G[S]为:SaAcBeAbAAbBd1)构造识别活前缀的DFA2)构造它的LR(0)分析表。3)分别给出对输入符号串abbcde和Abbce的LR(0)分析步骤。G[S]拓广为:S’SSaAcBeAbAAbBdI0:S’•SS•aAcBeI1:S’S•I2:Sa•AcBeA•bA•AbI3:SaA•cBeAA•bI4:Ab•I5:SaAc•BeB•dI7:SaAcB•eI8:Bd•I9:SaAcBe•I6:AAb•SaAbbcBedG[L]=ab+cdeG[S]的LR(0)分析表ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1Stepstates.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文法G[S]的句子对输入串abbce#的分析过程SLR(1)方法:是只在LR(0)可归前缀图的二义性状态下向前看一符。当有I={x→●bA→r●B→●}FOLLOW(A)∩FOLLOW(B)=,FOLLOW(A)∩b=；FOLLOW(B)∩b=则称该冲突可以解决。满足上述条件则可利用SLR(1)方法7.3SLR（1）分析例子：S→Aa.bBcA→d.B→e.设：FOLLOW(A)=a，FOLLOW(B)＝c所以：FOLLOW(A)∩FOLLOW(B)=,FOLLOW(A)∩b=；FOLLOW(B)∩b=所以本文法是SLR(1)文法。现举实型变量说明文法为例：实型变量说明→real标识符表标识符表→标识符表，i标识符表→i将该文法缩写后并拓广为G’如下：1.S’→S2.S→rD3.D→D,i4.D→i得图如下：0:S’→.SS→.rDS1:S’→S.r2:S→r.DD→.D,iD→.iD3:S→rD.D→D.,ii4:D→i.,5:D→D,.ii6:D→D,i.冲突实数说明文法的LR(0)分析表如下：r2r2r2r26S65r3r3r3r34r1r1r1,S5r133S42Acc11S20DS#i,rGotoAction状态解释冲突：S→rD●D→D●,i为归约项为移进项follow(S)=follow(S’)={#}follow(S)∩{,}={#}∩{,}=φ满足上述条件则可利用SLR(1)方法。转化情况如下：实数说明文法的SLR(1)分析表如下：r2r2r2r26S65r3r3r3r34r1S533S42Acc11S20DS#i,rGotoAction状态LR（1）项目(配置）的一般形式[A.，a]意味着处在栈顶是的相应状态，期望相应在栈顶的状态，然后只有当跟在后的token是终结符a时进行归约。a称作该项目(配置）的向前搜索符（lookahead）向前搜索符（lookahead）只对圆点在最后的项目起作用A–•,a.意味着处在栈中是的相应状态，但只有当下一个输入符是a时才能进行归约.a要么是一个终结符，要么是输入结束标记#有多个向前搜索符，比如a,b,c时，可写作A–u•,a/b/c7.4LR（1）分析LR(1)项目:即为二元组[α,a],其中α是LR(0)项目,a∈VT∪｛#｝。定义3.17设I为LR(1)项目集,则定义Close(I)=I∪{[.β[p],b]|B→β[p]∈G,[α.Bω[e],a]∈Close(I