精品文档
end;
begin
advance; E;
if sym=')' then advance else error end
else error
P81–3
/***************
(1) 是，满足三个条件。
(2) 不是，对于A不满足条件3。 (3) 不是，A、B均不满足条件3。 (4) 是，满足三个条件。 ***************/
第五章
P133–1
E?E?T?E?T*F
短语: E+T*F, T*F, 直接短语: T*F 句柄: T*F
P133–2
文法：
S?a|^|(T)T?T,S|S
(1)
最左推导:
S?(T)?(T,S)?(S,S)?(a,S)?(a,(T))?(a,(T,S))?(a,(S,S))?(a,(a,S))?(a,(a,a))S?(T,S)?(S,S)?((T),S)?((T,S),S)?((T,S,S),S)?((S,S,S),S)?(((T),S,S),S)?(((T,S),S,S)),S)?(((S,S),S,S),S)?(((a,S),S,S),S)?(((a,a),S,S),S)?(((a,a),^,S),S)?(((a,a),^,(T)),S)?(((a,a),^,(S)),S)?(((a,a),^,(a)),S)?(((a,a),^,(a)),a) 最右推导:
S?(T)?(T,S)?(T,(T))?(T,(T,S))?(T,(T,a))?(T,(S,a))?(T,(a,a))?(S,(a,a))?(a,(a,a))S?(T,S)?(T,a)?(S,a)?((T),a)?((T,S),a)?((T,(T)),a)?((T,(S)),a)?((T,(a)),a)?((T,S,(a)),a)?((T,^,(a)),a)?((S,^,(a)),a)?(((T),^,(a)),a)?(((T,S),^,(a)),a)?(((T,a),^,(a)),a)?(((S,a),^,(a)),a)?(((a,a),^,(a)),a)
(2)
(((a,a),^,(a)),a)
.
精品文档
(((S,a),^,(a)),a) (((T,a),^,(a)),a) (((T,S),^,(a)),a) (((T),^,(a)),a) ((S,^,(a)),a) ((T,^,(a)),a) ((T,S,(a)),a) ((T,(a)),a) ((T,(S)),a) ((T,(T)),a) ((T,S),a) ((T),a) (S,a) (T,S) (T) S
“移进-归约”过程：
步骤 栈 输入串 动作 0 # (((a,a),^,(a)),a)# 预备 1 #( ((a,a),^,(a)),a)# 进 2 #(( (a,a),^,(a)),a)# 进 3 #((( a,a),^,(a)),a)# 进 4 #(((a ,a),^,(a)),a)# 进 5 #(((S ,a),^,(a)),a)# 归 6 #(((T ,a),^,(a)),a)# 归 7 #(((T, a),^,(a)),a)# 进 8 #(((T,a ),^,(a)),a)# 进 9 #(((T,S ),^,(a)),a)# 归 10 #(((T ),^,(a)),a)# 归 11 #(((T) ,^,(a)),a)# 进 12 #((S ,^,(a)),a)# 归
13 #((T ,^,(a)),a)# 归 14 #((T, ^,(a)),a)# 进 15 #((T,^ ,(a)),a)# 进 16 #((T,S ,(a)),a)# 归 17 #((T ,(a)),a)# 归 18 #((T, (a)),a)# 进 19 #((T,( a)),a)# 进 20 #((T,(a )),a)# 进 21 #((T,(S )),a)# 归 22 #((T,(T )),a)# 归 23 #((T,(T) ),a)# 进 24 #((T,S ),a)# 归 25 #((T ),a)# 归
.
26 #((T) ,a)# 进 27 #(S ,a)# 归 28 #(T ,a)# 归 29 #(T, a)# 进 30 #(T,a )# 进 31 #(T,S )# 归 32 #(T )# 归 33 #(T) # 进
34 #S # 归
P133–3
(1)
FIRSTVT(S)={a,^,(} FIRSTVT(T)={,,a,^,(} LASTVT(S)={a,^,)} LASTVT(T)={,,a,^,)} (2) a ^ ( ) , a > > ^ > > ( < < < = < ) > > , < < < > > G6是算符文法，并且是算符优先文法
(3)优先函数 a ^ ( ) , f 4 4 2 4 4 g 5 5 5 2 3
fa f^ f(
f) f,
ga g^ g( g) g,（4） 栈 输入字符串 # （a,(a,a)）# #( a, (a,a))# #(a , (a,a))# #(t
, (a,a))#
.
精品文档
动作 预备 进 进 归
精品文档
#（t, #（t,（ #（t,（a #（t,（t #（t,（t, #（t,（t,a #（t,（t,s #（t,（t #（t,（t） #（t,s #（t #（t ） # s success
(a,a)）# a,a））# ,a））# ,a））# a））# ））# ））# ））# ）# ）# ）# # # 进 进 进 归 归
进 进 归 进 归 归
归 进
P134–5
(1)
0.S???S 1.S??S? 2.S??AS 3.S?A?S 4.S?AS? 5.S??b 6.S?b? 7.A??SA 8.A?S?A 9.A?SA? 10.A??a 11.A?a? (2)
1
S A ? 8 7 9 S ? ? ? ? a 10 0
? ? ? A S 3 2 ? ?
d 5
确定化： {0,2,5,7,10} {1,2,5,7,8,10.
11 4 6 S {1,2,5,7,8,10} {2,5,7,8,10} A {2,3,5,7,10} {2,3,5,7,9,10a {11} {11} b {6} {6} 精品文档
} {2,3,5,7,10} {2,5,7,8,10} {2,3,5,7,9,10} {2,4,5,7,8,10} {11} {6} {2,4,5,7,8,10} {2,5,7,8,10} {2,4,5,7,8,10} {2,5,7,8,10} φ φ } {2,3,5,7,10} {2,3,5,7,9,10} {2,3,5,7,10} {2,3,5,7,9,10} φ φ {11} {11} {11} {11} φ φ {6} {6} {6} {6} φ φ
A S
5:A?S?A 6:A?SA? 3:S??S? S??AS S?A?S S A a A?S?A S??AS S??b
A??SA A??SA S??b b A??a A??a A??SA
S??ASA??a
S??b
S a A S b S A b a A
4:S?A?S 7:S?AS? 0:S???S
S??AS S??AS A?S?A A S S??AS S??b S??b
A??SA A??SA S??b b A??a A??a A??SA A??a
a a b b a
1:A?a? 2:S?b?
DFA
构造LR(0)项目集规范族也可以用GO函数来计算得到。所得到的项目集规范族与上图中的项目集一样:
I0={S???S，S??AS，S??b，A??SA，A??a} GO(I0，a)={ A?a?}=I1 GO(I0，b)={ S?b?}=I2
GO(I0，S)={ S??S?，A?S?A，A??SA，A??a，S??AS，S??b}=I3
.