28 #(T ,a)#
a)# )# )#
归
归 进 进 归
29 #(T, 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 g 5 5 5 2 （4） 栈 # #( #(a #(t
#（t,
#（t,（ #（t,（a #（t,（t #（t,（t,
#（t,（t,a #（t,（t,s #（t,（t
#（t,（t） #（t,s #（t
#（t ） # s
, 4 3 输入字符串 （a,(a,a)）#
a, (a,a))# , (a,a))# , (a,a))# (a,a)）#
a,a））# ,a））#
,a））#
a））#
））# ））# ））#
）#
）#
）#
#
#
动作 预备 进
进 归 进 进 进 归
进 进 归 归 进
归 归 进 归
success
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 7 8 9 S 0 10 ? a 1 ? A S 2 3 4 d 5 6 确定化： S A a b {0,2,5,7,1{1,2,5,7,8{2,3,5,7,1{11} {6} 0} ,10} 0} {1,2,5,7,8{2,5,7,8,1{2,3,5,7,9{11} {6} ,10} 0} ,10} {2,3,5,7,1{2,4,5,7,8{2,3,5,7,1{11} {6} 0} ,10} 0} {2,5,7,8,1{2,5,7,8,1{2,3,5,7,9{11} {6} ? 0} {2,3,5,7,9,10} {2,4,5,7,8,10} {11} {6} 0} {2,4,5,7,8,10} {2,5,7,8,10} φ φ ,10} {2,3,5,7,10} {2,3,5,7,9,10} φ φ φ φ φ φ {11} {6} {11} {6} A S
3:5:6: S ? A A?S? A ASA? S??S? a b
S a A S b S A b
a A
0:S???S 4:S?A?S 7:S?AS? A S b a a b b a
1:2: 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 GO(I0，A)={ S?A?S，S??AS，S??b，A??SA，A??a}=I4 GO(I3，a)={ A?a?}=I1 GO(I3，b)={ S?b?}=I2
GO(I3，S)={ A?S?A，S??AS，S??b，A??SA，A??a}=I5
GO(I3，A)={ A?SA?，S?A?S，S??AS，S??b，A??SA，A??a}=I6 GO(I4，a)={ A?a?}=I1 GO(I4，b)={ S?b?}=I2
GO(I4，S)={ S?AS?，A?S?A，S??AS，S??b，A??SA，A??a}=I7 GO(I4，A)={ S?A?S，S??AS，S??b，A??SA，A??a}=I4 GO(I5，a)={ A?a?}=I1 GO(I5，b)={ S?b?}=I2
GO(I5，S)={ A?S?A，S??AS，S??b，A??SA，A??a}=I5
GO(I5，A)={ A?SA?，S?A?S，S??AS，S??b，A??SA，A??a}=I6 GO(I6，a)={ A?a?}=I1 GO(I6，b)={ S?b?}=I2
GO(I6，S)={ S?AS?，A?S?A，S??AS，S??b，A??SA，A??a}=I7 GO(I6，A)={ S?A?S，S??AS，S??b，A??SA，A??a}=I4 GO(I7，a)={ A?a?}=I1 GO(I7，b)={ S?b?}=I2
GO(I7，S)={ A?S?A，S??AS，S??b，A??SA，A??a}=I5
GO(I7，A)={ A?SA?，S?A?S，S??AS，S??b，A??SA，A??a}=I6
项目集规范族为C={I1，I2，I3，I4，I5，I6，I7} (3)不是SLR文法
状态3，6，7有移进归约冲突 状态3：FOLLOW(S’)={#}不包含a,b
状态6：FOLLOW(S)={#,a,b}包含a,b,；移进归约冲突无法消解 状态7：FOLLOW(A)={a,b}包含a,b；移进归约冲突消解 所以不是SLR文法。
(4) 构造例如LR(1)项目集规范族 见下图：
编译原理第三版课后习题解答
