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→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(1),LALR(1)
Review 识别活前缀的 DFA
启示,LR分析使用的信息之一是句柄左部的内容,
定义 (非终结符的左文 )
LC(A)={? | S’A?,V*,Vt*},
对拓广文法的开始符号 S’:
LC(S’)={?}
若有 BA? 则,LC(A)?LC(B).{?}因为,
S’BA
又,LC(B),LC(A) 即 LC(B).{?}?
LC(A)
R
*
R
*
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?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 (? =Vn?Vt)上的正规式
R
*
R
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
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) 项目集规范族中某个项目集 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={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） 文法 。
（ 0） S`→S (1)S→rD
(2) D→D,i (3) D→I
I3,S→r D,D→D.,i FOLLOW(S)={# }
I4,D→i,FOLLOW(D)={,# }
例 1文法的 SLR（ 1） 分析表状态 ACTION GOTO
r,i # S D．
0 S2 1
1 acc
2 S4 3
3 S5 r1
4 r3 r3
5 S6
6 r2 r2
二义性文法在ＬＲ分析中的应用
例 2表达式文法：
E’?E
E?E+E
E?E*E
E?(E)
E?i
二义性文法不是 LR文法，
但是对某些二义性文法,人为地给出优先性和结合性可能构造出更有效的 LR分析器如,规定在表达式文法中
i的 优先性最高
‘ *’ ·＞ ‘＋’
‘ *’和 ‘＋’ 都 服从左结合当前符号状态
+ * ( ) i # E
I
0
:
E’ E
E E+ E
E E * E
E ( E)
E i
I
2
:
E? (? E)
E E+ E
E E * E
E ( E)
E i
I
3
:
E? i?
I
1
:
E’? E?
E? E? +E
E? E? *E
I
1
,I
4
:
E? E+? E
E E+ E
E E * E
E ( E)
E i
I
5
:
E? E*? E
E E+ E
E E * E
E ( E)
E i
acc算术表达式二义性文法的
LR(0)项目集及状态转换矩阵当前符号状态
+ * (
)
i #
E
I
2
,I
2
,I
3
,I
6
:
E? (E? )
E? E? +E
E? E? *E
I
3
:
I
4
,I
2
,I
3
,I
7
:
E? E+ E?
E? E? +E
E? E? *E
I
5
,I
2
,I
3
,I
8
:
E? E * E?
E? E? +E
E? E? *E
I
6
,I
4
,I
5
,I
9
:
E? ( E)?
I
7
,I
4
,I
5
:
I
8
,I
4
,I
5
:
I
9
:
在 I1,I7,I8中 存在 移进 -归约 冲突在 I1,I7,I8中 存在移进 -归 约冲突
I1,E’?E?
E?E?+E
E?E?*E
I7,E?E+E?
E?E?+E
E?E?*E
I8,E?E*E?
E?E?+E
E?E?*E
I1,移进 和 接受 无 冲突
I7,I8用 优先关系 和 结合性 解决冲突。
规定：‘ *’ 优先于‘ +’，
都服从 左 结合
I7,遇‘ *’ 移进遇‘ +’ 归 约
I8,遇‘ +’，‘ *’ 都 归 约
0 S2 S3 1
1 S4 S5 acc
2 S2 S2 6
3 r4 r4 r4 r4
4 S2 S3 7
5 S2 S3 8
6 S4 S5 S9
7 r1 S5 r1 r1
8 r2 r2 r2 r1
9 r3 r3 r3 r3
ACTION GOTO
+ * ( ) i # E
状态二义性表达式文法的 LR分析表
1 0 # i+i*i# S3
2 03 #i +i* i# r4 1
3 01 #E +i*i# S4
4 014 #E+ i*i# S3
5 0143 #E+i *i# r4
6 0147 #E+E *i# S5
7 01475 #E+E* i# S3
8 014753 #E+E*i # r4 8
9 014758 #E+E*E # r2
10 0147 #E+E # r1 1
11 01 #E # acc
步骤 状态栈 符号栈 输入串 ACTION GOTO
对输入串 i+i*i的分析过程