第7章LR分析.ppt

《第7章LR分析.ppt》由会员分享，可在线阅读，更多相关《第7章LR分析.ppt（59页珍藏版）》请在三一办公上搜索。

1、7.1 LR分析概述,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)分析表的构造,

2、7.2 LR（0）分析,定义 如果有Z(Z为开始符)，且为终极符串(或空)。称是规范前缀。若是含有句柄的规范前缀,且每个句柄是的后端，称是可归规范前缀。,例子：SmABcde,若其中Abc是句柄，根据定义有mABc是可归规范前缀。,定理 设1A2为可归前缀，AVN，Au为一产生式，则1u也为可归前缀。,例:GZ:ZabAd Ac 若abAd是可归前缀，根据此定理abc也是可归前缀。,例:G(S):SaAc 1 AAbb 2 Ab 3,生成过程：,构造可归前缀图方法,自动机直观法,形式化方法,形式化方法,设BX1X2XnP是产生式P，则称形如X1X2XiXi+1XnP的侯选式为LR(0)项目(简

3、称项目)。(圆点可在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）项目或配置（item or configuration）.-在右端某一位置有圆点的G的产生式 A xyz A.xyz Ax.yz Axy.z Axyz.如：SaAd S.aAd

4、 Sa.Ad SaA.d SaAd.,可归前缀图的构造算法,1.先产生初始项目集I1=Close(.P|ZPG,Z为初始符)。2.若I是新项目集,则对每X(VNVT),产生项目集GO(I,X)。若两项目集完全相同,则作为一项目集。3.重复2至不产生新项目集为止。4.图的结点由上述项目集组成,且若GO(Ii,X)=Ij,则有Ii Ij。,例:G(S):SaAc 1 AbB2|ba3 BdB4|c 5,0:.aAc 1,1:a.Ac1.bB2.ba3,2:aA.c1,1:a.Ac1.bB2.ba3,aAc.1,1:a.Ac1.bB2.ba3,3:b.B2 b.a3.dB4.e5,bB.2,3:b.

5、B2 b.a3.dB4.e5,ba.3,3:b.B2 b.a3.dB4.e5,e.5,3:b.B2 b.a3.dB4.e5,4:d.B4.dB4.e5,3:b.B2 b.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分析法的分析栈由两个栈组成：状态栈、符号栈。,例子：AaBc Ba Bab,LR分析法的步骤：格局为(0 1i,#X0X1Xi,ajaj

6、+1an#)状态栈 符号栈 输入流,1.若ACTIONi,aj=sk,则有(0 1K,#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|bB AcA|d BcB|d

7、1.用形式化方法作可归前缀图。2.求LR(0)矩阵。3.写出输入串bccd的LR(0)分析过程。,解：可归前缀图,G(S):SE 0 EaA1 EbB2 AcA3 Ad 4 BcB5 Bd 6,解：拓展文法的新文法如下：,0:S.E E.bB E.aA,1:SE.,0:S.E E.bB E.aA,a,2:Ea.A A.d A.cA,0:S.E E.bB E.aA,A,6:EaA.,2:Ea.A A.d A.cA,d,10:Ad.,2:Ea.A A.d A.cA,4:Ac.A A.d A.cA,2:Ea.A A.d A.cA,d,4:Ac.A A.d A.cA,4:Ac.A A.d A.cA,A

8、,8:AcA.,4:Ac.A A.d A.cA,0:S.E E.bB E.aA,3:Eb.B B.d B.cB,7:EbB.,3:Eb.B B.d B.cB,d,11:Bd.,3:Eb.B B.d B.cB,5:Bc.B B.cB B.d,3:Eb.B B.d B.cB,d,5:Bc.B B.cB B.d,c,5:Bc.B B.cB B.d,9:BcB.,5:Bc.B B.cB B.d,解：LR(0)矩阵 s表示状态 r表示归约,第5步：d，(11)出栈，B进栈；5对B查表得9。,动画演示,解：串bccd的LR(0)分析过程,分析器模型,例 GS为:S a A c B e A b A Ab B

9、 d 1)构造识别活前缀的DFA 2)构造它的LR(0)分析表。3)分别给出对输入符号串abbcde和 Abbce的LR(0)分析步骤。,GS拓广为:S S S a A c B e A b A Ab B d,I0:S S S a A c B e,I1:S S,I2:S a A c B e A b A Ab,I3:S a A c B e A A b,I4:A b,I5:S a A c B e B d,I7:S a A c B e,I8:B d,I9:S a A c B e,I6:A A b,S,a,A,b,b,c,B,e,d,GL=ab+cde,GS的LR(0)分析表,Step states.S

10、yms.The rest of inputaction goto 1 0#abbcde#s2 2 02#a bbcde#s4 3 024#ab bcde#r2 3 4 023#aA bcde#s6 5 0236#aAb cde#r3 3 6 023#aA cde#s5 7 0235#aAc de#s8 8 02358#aAcd e#r4 7 9 02357#aAcB e#s9 10 023579#aAcBe#r1 1 11 01#S#acc,对输入串abbcde#的分析过程,Step states.Syms.The rest of inputaction goto 1 0#abbce#s2 2

11、 02#a bbce#s4 3 024#ab bce#r2 3 4 023#aA bce#s6 5 0236#aAb ce#r3 3 6 023#aA ce#s5 7 0235#aAc e#出错说明abbce#不是例6.1 文法 GS的句子,对输入串abbce#的分析过程,SLR(1)方法:是只在LR(0)可归前缀图的二义性状态下向前看一符。当有I=xb Ar B FOLLOW(A)FOLLOW(B)=,FOLLOW(A)b=；FOLLOW(B)b=则称该冲突可以解决。满足上述条件则可利用SLR(1)方法,7.3 SLR（1）分析,例子：SAa.bBc Ad.Be.设：FOLLOW(A)=a，

12、FOLLOW(B)c所以：FOLLOW(A)FOLLOW(B)=,FOLLOW(A)b=；FOLLOW(B)b=所以本文法是SLR(1)文法。,现举实型变量说明文法为例：real，ii,将该文法缩写后并拓广为G如下：1.SS 2.SrD 3.DD,i 4.Di 得图如下：,0:S.S S.rD,S,1:SS.,r,2:Sr.D D.D,i D.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)方法。转化情况如下：,

13、实数说明文法的SLR(1)分析表如下：,LR（1）项目(配置）的一般形式 A.，a 意味着处在栈顶是的相应状态，期望相应在栈顶的状态，然后只有当跟在后的token是终结符a时进行归约。a 称作该项目(配置）的向前搜索符（lookahead）向前搜索符（lookahead）只对圆点在最后的项目起作用A,a.意味着处在栈中是 的相应状态，但只有当下一个输入符是a时才能进行归约.a 要么是一个终结符，要么是输入结束标记#有多个向前搜索符，比如a,b,c时，可写作 A u,a/b/c,7.4 LR（1）分析,LR(1)项目:即为二元组,a,其中是LR(0)项目,aVT#。,定义3.17 设I为LR(1

14、)项目集,则定义 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为：SS0 SBB1 BaB2 Bb3则其转换图和分析表如下：,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,#

15、,I13:L*R,#,I0:S S,#S L=R,#S R,#L*R,=/#L i,=/#R L,#,I4:L*R,=/#R L,=/#L i,=/#L*R,=/#,I6:S L=R,#R L,#L*R,#L i,#,I11:L*R,#R L,#L*R,#L i,#,I2:S L=R,#R L,#,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为：SS0 SBB1 BaB2 Bb3（注：与前例文法同）,LALR1

16、方法：,同心项目集合：I0:S.S S.BB B.aB B.bI1:S S.I2:S B.B B.aB B.bI3:Ba.B B.aB B.b I4:BaB.I5:Bb.I6:SBB.,I0:S S,#S BB,#B aB,a/bB b,a/b,I1:S S,#,I2:S BB,#B aB,#B b,#,I5:S BB,#,I6:S aB,#B aB,#B b,#,I3:B aB,a/b B aB,a/b B b,a/b,I4:B b,a/b,I7:B b,#,I9:B aB,#,I8:B aB,a/b,s,B,B,a,b,b,b,B,B,a,a,a,LR(1)项目集和转换函数,b,LALR在

17、SLR（1）和LR（1）间寻找折衷办法（状态数目，分析能力）,LALR(lookahead LR)合并同心集I36 I47 I89,I3:B aB,a/b B aB,a/b B b,a/b,I6:S aB,#B aB,#B b,#,I4:B b,a/b,I7:B b,#,I8:B aB,a/b,I9:B aB,#,构造 LALR(1)分析表.方法1,1.构造文法G的规范 LR(1)状态.2.合并同心集（除搜索符外两个集合是相同的）的状态.3.新 LALR(1)状态的GO函数是合并的同心集状态的GO函数的并.4.LALR(1)分析表的action 和 goto 登录方法与LR(1)分析表一样.经

18、上述步骤构造的表若不存在冲突，则称它为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)更精确，可大大减少移入/归约冲突；LALR(1):对LR(1)项目集规范族合并同心集,LR(0)、SLR(1)、LR(1)、LALR(1)分析表比较LR(0)分析表局限性大，但其构造方法是其他构造方法的基础；SLR分析表虽然不是对所有文法都存在，但这种分析表较易实现又极有使用价值；LR分析表的分析能力最强，能适用于一大类文法，但是，实现代价过高（表过大）；LALR分析表的能力介于SLR和LR之间，实现效率较高。,总结：,语法分析,自顶向下,递归子程序法,LL(1)方法,自底向上,简单优先方法,算符优先法,LR方法,LR(0),SLR(1),LR(1),LALR(1),