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

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

#（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)

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

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 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 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 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 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 项目集规范族为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)文法。

a}=I6

a}=I7

a}=I6

a}=I7

a}=I6

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