《第7章LR分析说课材料》由会员分享，可在线阅读，更多相关《第7章LR分析说课材料（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),定义 如果有Z (Z为开始符)，且为终极符串(或空)。称是规范前缀。若是含有句柄的规范前缀,且每个句柄是的后端，称是可归规
2、范前缀。,例子：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)项目(简称项目)。(圆点可在X1之前,也可在Xn之后)。,定义,称形如X1X2XnP的项目为归约项目。移进项目:除此外其它形式。,设I为项目集,
3、则定义 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 Sa .Ad SaA .d SaAd .,可归前缀图的构造算法,1.先产生初始项目集I1=Close(.P |ZPG,Z
4、为初始符)。 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.B2 b.a3 .dB4 .e5,ba.3,3:b.B2 b.a3 .dB4 .e5,e
5、.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,4:d.B4 .dB4 .e5,4:d.B4 .dB4 .e5,定义,二义性结点：可归前缀图的一个结点包含多个归约项目或同时包含移进项目和归约项目。,LR(0)文法：文法的可归前缀图不包含二义性结点(可用于判是否LR(0)文法)。,LR分析法的分析栈由两个栈组成：状态栈、符号栈。,例子：AaBc Ba Bab,LR分析法的步骤： 格局为(0 1i,#X0X1Xi,ajaj+1an#) 状态栈 符号栈 输入流,1.若ACTIONi,a
6、j=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 1.用形式化方法作可归前缀图。 2.求L
7、R(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,2:Ea.A A.d A.cA,0:S.E E.bB E.aA,6:EaA.,2:Ea.A A.d A.cA,10:Ad.,2:Ea.A A.d A.cA,4:Ac.A A.d A.cA,2:Ea.A A.d A.cA,4:Ac.A A.d A.cA,4:Ac.A A.d A.cA,8:AcA.,4:Ac.A A.d A.cA,0:S
8、.E E.bB E.aA,3:Eb.B B.d B.cB,7:EbB.,3:Eb.B B.d B.cB,11:Bd.,3:Eb.B B.d B.cB,5:Bc.B B.cB B.d,3:Eb.B B.d B.cB,5:Bc.B B.cB B.d,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 d 1)构造识别活前缀的DFA 2)构造它的LR(0)分析表。
9、 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. Sym
10、s. 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 input
11、action goto 1 0 # abbce# s2 2 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)
12、方法,7.3 SLR（1）分析,例子：SAa.bBc Ad. Be. 设：FOLLOW(A)=a，FOLLOW(B)c 所以：FOLLOW(A)FOLLOW(B)=, FOLLOW(A)b=； FOLLOW(B)b= 所以本文法是SLR(1)文法。,现举实型变量说明文法为例： real ，i i,将该文法缩写后并拓广为G如下： 1.SS 2.SrD 3.DD,i 4.Di 得图如下：,0:S.S S.rD,1:SS.,2:Sr.D D.D,i D.i,3:SrD. DD.,i,4:Di.,5:DD,.i,6:DD,i.,实数说明文法的LR(0)分析表如下：,follow(S)=follow(S
13、)=# follow(S),=#,=,满足上述条件则可利用SLR(1)方法。转化情况如下：,实数说明文法的SLR(1)分析表如下：,LR（1）项目( 配置）的一般形式 A . ， a 意味着处在栈顶是的相应状态，期望相应在栈顶的状态，然后只有当跟在后的token是终结符a时进行归约 。 a 称作该项目( 配置） 的向前搜索符（ lookahead ） 向前搜索符（ lookahead ）只对圆点在最后的项目起作用 A , a .意味着处在栈中是 的相应状态，但只有当下一个输入符是a时才能进行归约. a 要么是一个终结符，要么是输入结束标记# 有多个向前搜索符，比如a,b,c时，可写作 A u,
14、 a/b/c,7.4 LR（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为： 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）技术解决，但
15、能用LR（1）,I1:SS ,#,I5:Li ,=/#,I7:L*R ,=/#,I8:RL ,=/#,I9:SL=R ,#,I3:SR ,#,I12:Li ,#,I10:RL ,#,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方法：,同心项目集合： I0:S.S S .BB B .aB B .b I1:S S. I2:S B.B B.aB B.b
