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