主要内容,
? SLR(1)分析方法
LR(0)分析方法的不足
?LR(0)方法对文法的要求严格。
?LR(0)方法容易出现冲突状态。
一个文法例,
? GE,S→E # [1]
? E→E + T [2]
? E→T [3]
? T→T ? P [4]
? T→P [5]
? P→id [6]
? P→( E ) [7]
图 4.5.5.3 G?E 的 LRSM0
+
E
P
id
#
+
P
id
(T
T
id
(
?
?
id E
(
P )
4
E→ T ?
T→ T ? ? P
7 P→ id ?
5
E→ E + ? T
T→ ? T ? P
T→ ? P
P→ ? id
P→ ? (E)
3
T→ P ?
4
S→ E ? #
E→ E ? + T
1
S→ ? E # [1]
E→ ? E+T [2]
E→ ? T [3]
T→ ? T?P [4]
T→ ? P [5]
P→ ? id [6]
P→ ? (E) [7]
0
T→ T ? ? P
P→ ? id
P→ ? (E)
8
T→ T * P ?
9
E→ E+T ?
T→ T ? ?P
11
P→ (E ? )
E→ E ? +T
12
P→(E) ?
10P
( T
P → ( ? E )
E→ ? E+T
E→ ? T
T→ ? T?P
T→ ? P
P→ ? id
P→ ? (E)
6
7
8
S→ E# ?
2
如果某个状态有如下项目集：
{ A → ??,B → ? ?,D→ ?? d ? },则存在
着归约 -归约，归约 -移入冲突
? 若用 A → ??归约，则当前输入符应在 A
的 Follow集中
? 若用 B → ? ?归约，则当前输入符应在 B
的 Follow集
? 若移入，则当前输入符应为 d。
SLR(1)分析条件
? LRSM0中存在着状态
{ A1 → ?1?,…, An → ?n?，
B1→ ?1 ?a1r1,…, Bn→ ? n?anrn}
Follow(A1)?… ? Follow(An)
?{a1,…,a n}=?
SLR(1)文法的定义
? SLR(1)文法的投影函数 ?1定义如下：
? ?1,StateSet? (VT∪ {#})→ 2?
? ?1 (S,a) =
{Reduce j |B→ ???S,a?Follow(B),B→ ??P}
∪ (if存在 X→ ??a??S且 a?VT then {Shift})
?如果 LRSM0中的每个状态 S,对任意 a?VT，
使得 |?1(S,a)|?1,则称相应文法为 SLR(1)文法。
SLR(1)__Action表的构造
? 若 ?1(S,#)={Shift} Action( S,# )=Accept
? 若 ?1(S,a)={Shift }且 a?# Action( S,a) =Shift
? 若 ?1(S,a)={Reduce j} Action( S,a) =Reduce j
? 若 ?1(S,a)=? Action( S,a) = Error
SLR(1)__GoTo表的构造
? GoTo( S,X) = S ?, 当 LRSM0中有 S S?
? GoTo( S,X) = error,否则
? 合并的 SLR(1)分析表, 合并方法,
Action?( S,a) = Shift i,
当 Action?(S,a)= Shift且 GoTo(S,a)=Si
GoTo?( S,X) = Si,
当 GoTo(S,X)=Si 且 X?VN
X
图 4.5.5.3 G?E 的 LRSM0
+
E
P
id
#
+
P
id
(T
T
id
(
?
?
id E
(
P )
4
E→ T ?
T→ T ? ? P
7 P→ id ?
5
E→ E + ? T
T→ ? T ? P
T→ ? P
P→ ? id
P→ ? (E)
3
T→ P ?
4
S→ E ? #
E→ E ? + T
1
S→ ? E # [1]
E→ ? E+T [2]
E→ ? T [3]
T→ ? T?P [4]
T→ ? P [5]
P→ ? id [6]
P→ ? (E) [7]
0
T→ T ? ? P
P→ ? id
P→ ? (E)
8
T→ T * P ?
9
E→ E+T ?
T→ T ? ?P
11
P→ (E ? )
E→ E ? +T
12
P→(E) ?
10P
( T
P → ( ? E )
E→ ? E+T
E→ ? T
T→ ? T?P
T→ ? P
P→ ? id
P→ ? (E)
6
7
8
S→ E# ?
2
+ ? id ( ) #
0 S S
1 S A
2
3 S S
4 R5 R5 R5 R5
5 R6 R6 R6 R6
6 S S
7 R3 S R3 R3
8 S S
9 R4 R4 R4 R4
10 R7 R7 R7 R7
11 R2 S R7 R7
12 S S
State Action－ Lookahead
＋ ? id ( ) # E T P
0 S5 S6 1 7 4
1 S3 A
2
3 S5 S6 11 4
4 R5 R5 R5 R5
5 R6 R6 R6 R6
6 S5 S6 12 7 4
7 R3 S R3 R3
8 S5 S6 9
9 R4 R4 R4 R4
10 R7 R7 R7 R7
11 R2 S8 R2 R2
12 S3 S10
State Action－ Lookahead GoTo
SLR(1)驱动器
[1],Push(S0,-) ；
[2],Scan(a)；
[3],S,= TopOf( StateStack)；
[4],case Action( S,a ) of
? Error ? ErrorProcess；
? Accept ? Finish；
? Shift i ? begin Push(Si,a)； goto2 end ;
? Reduce j ?begin
Pop(JJ)；
Push( GoTo(S- JJ,Lj),Lj);
goto 3 end
end
分析栈 符号栈 输入串 分析动作 转向状态
0 id ?id+id# S5
0,5 id ?id+id# R6 4
0,4 P ?id+id# R5 7
0,7 T ?id+id# S8
0,7,8 T? id+id# S5
0,7,8,5 T?id +id# R6 9
0,7,8,9 T?P +id# R4 7
0,7 T +id# R3 1
0,1 E +id# S3
0,1,3 E+ id# S5
0,1,3,5 E+id # R6 4
0,1,3,4 E+P # R5 11
0,1,3,11 E+T # R2 1
0,1 E # Accept
SLR(1)与 LR(0)
?SLR(1)和 LR(0)具有相同的状态机
?LR(0)只看分析栈的内容，不考虑当前输入符
SLR(1)考虑输入符，用 follow集来解决冲突，
因此 SLR(1)要比 LR(0)分析能力强
? 括号文法定义如下：
Z → S ＃
S → (S) S | ?
构造该文法的 SLR(1)分析表，并给出输
入流 ( )( )＃的 SLR(1)分析过程。
? SLR(1)分析方法
LR(0)分析方法的不足
?LR(0)方法对文法的要求严格。
?LR(0)方法容易出现冲突状态。
一个文法例,
? GE,S→E # [1]
? E→E + T [2]
? E→T [3]
? T→T ? P [4]
? T→P [5]
? P→id [6]
? P→( E ) [7]
图 4.5.5.3 G?E 的 LRSM0
+
E
P
id
#
+
P
id
(T
T
id
(
?
?
id E
(
P )
4
E→ T ?
T→ T ? ? P
7 P→ id ?
5
E→ E + ? T
T→ ? T ? P
T→ ? P
P→ ? id
P→ ? (E)
3
T→ P ?
4
S→ E ? #
E→ E ? + T
1
S→ ? E # [1]
E→ ? E+T [2]
E→ ? T [3]
T→ ? T?P [4]
T→ ? P [5]
P→ ? id [6]
P→ ? (E) [7]
0
T→ T ? ? P
P→ ? id
P→ ? (E)
8
T→ T * P ?
9
E→ E+T ?
T→ T ? ?P
11
P→ (E ? )
E→ E ? +T
12
P→(E) ?
10P
( T
P → ( ? E )
E→ ? E+T
E→ ? T
T→ ? T?P
T→ ? P
P→ ? id
P→ ? (E)
6
7
8
S→ E# ?
2
如果某个状态有如下项目集：
{ A → ??,B → ? ?,D→ ?? d ? },则存在
着归约 -归约，归约 -移入冲突
? 若用 A → ??归约，则当前输入符应在 A
的 Follow集中
? 若用 B → ? ?归约，则当前输入符应在 B
的 Follow集
? 若移入，则当前输入符应为 d。
SLR(1)分析条件
? LRSM0中存在着状态
{ A1 → ?1?,…, An → ?n?，
B1→ ?1 ?a1r1,…, Bn→ ? n?anrn}
Follow(A1)?… ? Follow(An)
?{a1,…,a n}=?
SLR(1)文法的定义
? SLR(1)文法的投影函数 ?1定义如下：
? ?1,StateSet? (VT∪ {#})→ 2?
? ?1 (S,a) =
{Reduce j |B→ ???S,a?Follow(B),B→ ??P}
∪ (if存在 X→ ??a??S且 a?VT then {Shift})
?如果 LRSM0中的每个状态 S,对任意 a?VT，
使得 |?1(S,a)|?1,则称相应文法为 SLR(1)文法。
SLR(1)__Action表的构造
? 若 ?1(S,#)={Shift} Action( S,# )=Accept
? 若 ?1(S,a)={Shift }且 a?# Action( S,a) =Shift
? 若 ?1(S,a)={Reduce j} Action( S,a) =Reduce j
? 若 ?1(S,a)=? Action( S,a) = Error
SLR(1)__GoTo表的构造
? GoTo( S,X) = S ?, 当 LRSM0中有 S S?
? GoTo( S,X) = error,否则
? 合并的 SLR(1)分析表, 合并方法,
Action?( S,a) = Shift i,
当 Action?(S,a)= Shift且 GoTo(S,a)=Si
GoTo?( S,X) = Si,
当 GoTo(S,X)=Si 且 X?VN
X
图 4.5.5.3 G?E 的 LRSM0
+
E
P
id
#
+
P
id
(T
T
id
(
?
?
id E
(
P )
4
E→ T ?
T→ T ? ? P
7 P→ id ?
5
E→ E + ? T
T→ ? T ? P
T→ ? P
P→ ? id
P→ ? (E)
3
T→ P ?
4
S→ E ? #
E→ E ? + T
1
S→ ? E # [1]
E→ ? E+T [2]
E→ ? T [3]
T→ ? T?P [4]
T→ ? P [5]
P→ ? id [6]
P→ ? (E) [7]
0
T→ T ? ? P
P→ ? id
P→ ? (E)
8
T→ T * P ?
9
E→ E+T ?
T→ T ? ?P
11
P→ (E ? )
E→ E ? +T
12
P→(E) ?
10P
( T
P → ( ? E )
E→ ? E+T
E→ ? T
T→ ? T?P
T→ ? P
P→ ? id
P→ ? (E)
6
7
8
S→ E# ?
2
+ ? id ( ) #
0 S S
1 S A
2
3 S S
4 R5 R5 R5 R5
5 R6 R6 R6 R6
6 S S
7 R3 S R3 R3
8 S S
9 R4 R4 R4 R4
10 R7 R7 R7 R7
11 R2 S R7 R7
12 S S
State Action－ Lookahead
＋ ? id ( ) # E T P
0 S5 S6 1 7 4
1 S3 A
2
3 S5 S6 11 4
4 R5 R5 R5 R5
5 R6 R6 R6 R6
6 S5 S6 12 7 4
7 R3 S R3 R3
8 S5 S6 9
9 R4 R4 R4 R4
10 R7 R7 R7 R7
11 R2 S8 R2 R2
12 S3 S10
State Action－ Lookahead GoTo
SLR(1)驱动器
[1],Push(S0,-) ；
[2],Scan(a)；
[3],S,= TopOf( StateStack)；
[4],case Action( S,a ) of
? Error ? ErrorProcess；
? Accept ? Finish；
? Shift i ? begin Push(Si,a)； goto2 end ;
? Reduce j ?begin
Pop(JJ)；
Push( GoTo(S- JJ,Lj),Lj);
goto 3 end
end
分析栈 符号栈 输入串 分析动作 转向状态
0 id ?id+id# S5
0,5 id ?id+id# R6 4
0,4 P ?id+id# R5 7
0,7 T ?id+id# S8
0,7,8 T? id+id# S5
0,7,8,5 T?id +id# R6 9
0,7,8,9 T?P +id# R4 7
0,7 T +id# R3 1
0,1 E +id# S3
0,1,3 E+ id# S5
0,1,3,5 E+id # R6 4
0,1,3,4 E+P # R5 11
0,1,3,11 E+T # R2 1
0,1 E # Accept
SLR(1)与 LR(0)
?SLR(1)和 LR(0)具有相同的状态机
?LR(0)只看分析栈的内容，不考虑当前输入符
SLR(1)考虑输入符，用 follow集来解决冲突，
因此 SLR(1)要比 LR(0)分析能力强
? 括号文法定义如下：
Z → S ＃
S → (S) S | ?
构造该文法的 SLR(1)分析表，并给出输
入流 ( )( )＃的 SLR(1)分析过程。
