编译原理第三版课后习题解答

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)项目集规范族 见下图：