. F F' P F?PF? F?PF? F?PF? F?PF? F??? F??*F? F??? F??? F??? F??? F??? F??? P?(E) P?a P?b P?^ (4)
procedure E; begin
if sym='(' or sym='a' or sym='b' or sym='^' then begin T; E' end else error end
procedure E'; begin
if sym='+'
then begin advance; E end
else if sym<>')' and sym<>'#' then error end
procedure T; begin
if sym='(' or sym='a' or sym='b' or sym='^' then begin F; T' end else error end
procedure T'; begin
if sym='(' or sym='a' or sym='b' or sym='^' then T
else if sym='*' then error end
procedure F; begin
if sym='(' or sym='a' or sym='b' or sym='^' then begin P; F' end else error end
procedure F'; begin
if sym='*'
then begin advance; F' end end
procedure P; begin
if sym='a' or sym='b' or sym='^' then advance
else if sym='(' then
11 / 28
. 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)
12 / 28
. (((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)# 归
13 / 28
. 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))#
14 / 28
动作 预备 进 进 归
. #（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 3 2 ? ?
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,1015 / 28
11 4 6 a {11} {11} b {6} {6}
编译原理第三版课后习题答案
