编译原理课后答案(陈火旺)

课后答案网 http://www.khdaw.com

26 27 28 29 30 31 32 33 34

#((T) #(S #(T #(T, #(T,a #(T,S #(T #(T) #S

,a)# ,a)# ,a)# a)# )# )# )# 归 # # 归

进 归 归 进 进 归 进

P133–3

(1)

FIRSTVT(S)={a,^,(} FIRSTVT(T)={,,a,^,(} LASTVT(S)={a,^,)} LASTVT(T)={,,a,^,)} (2) a ^ ( ) , a < < ^ < < ( < < ) > > = > > , > > < > > G6是算符文法，并且是算符优先文法

(3)优先函数 f g

fa f^ f

(

ga （4） 栈 # #( #(a #(t

f f

),a 4 5 ^ 4 5 ( 2 5 ) 4 2 , 4 3 g g g g

^(),

输入字符串 （a,(a,a)）# a, (a,a))# , (a,a))# , (a,a))#

动作 预备 进 进 归

课后答案网 http://www.khdaw.com

课后答案网 http://www.khdaw.com

#（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 2 3 ? ?

d 5

确定化： {0,2,5,7,10} {1,2,5,7,8,10S {1,2,5,7,8,10} {2,5,7,8,10} A {2,3,5,7,10} {2,3,5,7,9,1011 4 6 a {11} {11} b {6} {6} 课后答案网 http://www.khdaw.com

课后答案网 http://www.khdaw.com

} {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

A??a S??AS

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

课后答案网 http://www.khdaw.com

课后答案网 http://www.khdaw.com

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)项目集规范族 见下图： 对于状态5，因为包含项目[A?AS? a/b]，所以遇到搜索符号a或b时，应该用A?AS归约。又因为状态5包含项目[A??a a/b]，所以遇到搜索符号a时，应该移进。因此存在“移进-归约”矛盾，所以这个文法不是LR(1)文法。

课后答案网 http://www.khdaw.com