63SLR(1)分析技术 例1:(0)S→S (1)S→rD (2)D→D,i (3)D→i Real X, y,.. LR(0)项目 S2)S→S 3)S→.rD 4)S→r.D5)S→rD 6)D 7)D→D.,i8)D→D,i9)D→D,i. 10)D→.i11)D→i
6.3 SLR(1)分析技术 例1：（0）S`→S (1) S→rD (2) D→D,i (3) D→i Real x,y,… LR（0）项目 1) S`→．S 2) S`→S． 3) S→．rD 4) S→r．D 5) S→rD． 6) D→．D,i 7) D→D．,i 8) D→D,．i 9) D→D,i． 10) D→．i 11) D→i．
例:(0)S→S (1)S→rD (2)D→D,i (3)D→ LR(0)项目集规范族 S S→r S→,rD D→] S→S 4 S→r.D DDip D D. i D→.D,i 6 D, i D 其中I3中含有移进/归约冲突 文法不是LR(0)的,如何解决?
例：（0）S`→S (1) S→rD (2) D→D,i (3) D→i LR（0）项目集规范族 I0: S`→．S I3: S→r D． S→．r D D→D．，i I1: S`→S． I4: D→i． I2: S→r．D I5: D→D ,.i D→．D， i I6: D→D，i． D→．i 其中I3中含有移进/归约冲突 文法不是LR(0)的，如何解决？
LR(0)技术的局限性 没有查看下一符号( Token),决定分析动作仅 仅根据到目前已经看到的东西 能力弱 改进办法 向前查看下一符号-SLR(1)LR(1LALR(1)
LR(0)技术的局限性 没有查看下一符号(Token),决定分析动作仅 仅根据到目前已经看到的东西. 能力弱. 改进办法: 向前查看下一符号---SLR(1),LR(1),LALR(1)
Review识别活前缀的DFA 启示LR分析使用的信息之一是句柄左部 的内容 定义(非终结符的左文 LC(A={β|S’→βAO,B∈V*,O∈V} 对拓广文法的开始符号S: LC(S=(8 若有B→YA8则LC(ALC(B)、{y}因为 SOBO→ayA6o R 又:∈LC(B),OY∈LC(A)即LC(B).{y}∈ LC(A)
Review 识别活前缀的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 *
Review Gs:()S>s()s>aACBe (2)A->b(3)A→>Ab(4)B→>d 每个非终结符的左文方程组 用代入法求解得 LC(S=e [S」=ε LC(S=LC(S).8 Is LC(A=LC(S).aU LC(A)e. LAFa+LAI LC(B=LC(S).aAc) BaAc 化简为: 令∑={[S,[S],[A],[B],a, A, c) °[S]=E 则方程两边都是∑上的正规式 [S]=[S 而[A]=a+[A]即为[A]=a|[A]由 °[A]=[S]at[A 正规式所表示的正规集 BISAc 得:[A]
Review G[S]: (0) S’→S (1) S →a A c B e (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]=a
Review g[S]:(0)S→>S(1)S→ aacbe (2)A->b(3)A→>Ab(4)B→>d 定义(产生式的LR(0)左文) LR(OLC(A-a){Yy=a且S含BA0→βcO,O∈Vt} 有推论:LR(0LC(A→>)=LC(A).{a} 则有 LR(OLCIS >S)=S LR(O(C(S>aAcBe=aAcBe LR(OLC(A>b=ab LR(OLC(A>Ab=aAb LR(OLCB->d)F=aAcd (Σ=VnVt)上的正规式
Review G[S]: (0) S’→S (1) S →a A c B e (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)=S LR(0)(LC(S→aAcBe)=aAcBe LR(0)LC(A→b)=ab LR(0)LC(A→Ab)=aAb LR(0)LC(B→d)=aAcd ( =VnVt)上的正规式 R * R
S→rD.D→D.,i 例1文法的LR(0)分析表有多重入口 状态 ACTION GOTO # acc rI 3456
I3: S→r D． D→D．，i 例1文法的LR（0）分析表有多重入口 状态 ACTION GOTO r , i # S D． 0 S2 1 1 acc 2 S4 3 3 r1 S5 r1 r1 r1 4 r3 r3 r3 r3 5 S6 6 r2 r2 r2 r2
I2:S→rD.D→D.,i 使用FOLw(S)∩{,}=信息、解决冲突 例1文法的(改进的)SLR(1)分析表 状态 ACTION GOTO # 0123456 acc
I3: S→r D． D→D．，i 使用FOLLOW(S) {, } = 信息 解决冲突 例1文法的（改进的）SLR（1）分析表 状态 ACTION GOTO r , i # S D． 0 S2 1 1 acc 2 S4 3 3 r1 S5 r1 r1 4 r3 r3 r3 r3 5 S6 6 r2 r2 r2 r2
SLR(1)技术 如果LR(0)项目集规范族中某个项目集I含移进/归约 归约/归约冲突: I:{…A→a.bβ,P→ω,,Q→γ.,…} A FOLLOW(Q)n FOLLOW(P)=Op FOLLOW(P)∩{b}=φ FOLLOV(Q∩{b} 则解决冲突的SLR(1)技术 action[kb]=移进 对a∈ FOLLOW(P则 action[k,a]=用P→o归约 对c∈ FOLLOW(Q则 action[kc]=用Q→y归约 能用SLR(1技术解决冲突的文法称为SLR(1)文法 SLR(1)文法是无二义的
SLR(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 → 归约 • 能用SLR(1)技术解决冲突的文法称为SLR(1)文法。 • SLR(1)文法是无二义的
SLR表 状态,因,C∴I},令每个项目集L的下标k为分析器的一个 假定C={,I1 的SLR分析表含有状态0 ,n。令那个 含有项目S→.S的L的下标k为初态。 ACTION表和GOTO表可 按如下方法构造: 若项目A→α.aβ属于I且GO(la)=Ia为终结符,则置 ACTION[k,a为“把状态和符号a移进栈”,简记为“s”; 若项目A→α.属于I,那么,对任何输入符号a,a∈ FOLLOW(A), 置 ACTIONkk,a为“用产生式A→a进行规约”,简记为 “rj”;其中,假定A→α为文法G的第j个产生式; 若项目S→S.属于L则置 ACTIONIK,#为“接受”,简记为 acc 若GO(L,A1,A为非终结符,则置GOTO(kA)=; 分析表中凡不能用规则1至4填入信息的空白格均置上“出错标 未” 按上述算法构造的含有 ACTION和GOTO两部分的分析表,如果每 个入口不含多重定义,则称它为文法G的一张SLR表。具有SLR 表的文法G称为一个SLR(1)文法
SLR表 假定C={I0 , I1 ,……，In }，令每个项目集Ik的下标k 为分析器的一个 状态，因此，G’ 的SLR分析表含有状态0，1，……，n。令那个 含有项目S’→．S的Ik的下标k为初态。ACTION表和GOTO表可 按如下方法构造： 若项目A→α．aβ属于Ik且GO (Ik , a)= Ij , a为终结符，则置 ACTION[k, a]为“把状态j和符号a移进栈” ，简记为“sj”; 若项目A→α．属于Ik , 那么，对任何输入符号a, a∈FOLLOW(A), 置ACTION[k, a]为“用产生式A→α进行规约” ，简记为 “rj”;其中，假定A→α为文法G’的第j个产生式； 若项目S’→S．属于Ik , 则置ACTION[k, #]为“接受” ，简记为 “acc”; 若GO (Ik , A)= Ij , A为非终结符，则置GOTO(k, A)=j; 分析表中凡不能用规则1至4填入信息的空白格均置上“出错标 志” 。 按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每 个入口不含多重定义，则称它为文法G的一张SLR表。具有SLR 表的文法G称为一个SLR（1）文法