编译原理课后习题答案(陈火旺+第三版)

由天下分享时间：2024/12/21 16:10:44 加入收藏我要投稿点赞

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)

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