编译原理第三版课后习题解答
编译原理第三版课后习题
解答
Last revision on 21 December 2020
第二章习题解答P36-6
(1)
L G
()
1是0~9组成的数字串
(2)
最左推导:
最右推导:
P36-7
G(S)
P36-8
文法：
最左推导:
最右推导:
语法树：/********************************
*****************/
P36-9
句子iiiei有两个语法树：
P36-10
/**************
***************/
P36-11
/***************
L1:
L2:
L3:
L4:
***************/
第三章习题参考答案P64–7
(1)
最小化：
P64–8
(1)
(2)
(3)
P64–12
(a)
a
a,b a 确定化：
给状态编号： a a a b b b
最小化：
a a
b b a b (b)
已经确定化了,进行最小化 最小化：
0 0
(1) 0
1 0 (2):
(|)*010
εε
确定化：
给状态编号：
最小化：
1 1 1 0 0
第四章
0 Y Y 0
(1) 按照T,S的顺序消除左递归
递归子程序：
procedure S;
begin
if sym='a' or sym='^'
then abvance
else if sym='('
then begin
advance;T;
if sym=')' then advance;
else error;
end
else error
end;
procedure T;
begin
S;'T
end;
procedure 'T;
begin
if sym=','
then begin
advance;
S;'T
end
end;
其中:
sym:是输入串指针IP所指的符号
advance:是把IP调至下一个输入符号
error:是出错诊察程序
(2)
FIRST(S)={a,^,(}
FIRST(T)={a,^,(}
FIRST('T)={,,ε}
FOLLOW(S)={),,,#}
FOLLOW(T)={)}
FOLLOW('T)={)}
是LL(1)文法
P81–2
文法：
(1)
FIRST(E)={(,a,b,^}
FIRST(E')={+,ε}
FIRST(T)={(,a,b,^}
FIRST(T')={(,a,b,^,ε}
FIRST(F)={(,a,b,^}
FIRST(F')={*,ε}
FIRST(P)={(,a,b,^}
FOLLOW(E)={#,)}
FOLLOW(E')={#,)}
FOLLOW(T)={+,),#}
FOLLOW(T')={+,),#}
FOLLOW(F)={(,a,b,^,+,),#}
FOLLOW(F')={(,a,b,^,+,),#}
FOLLOW(P)={*,(,a,b,^,+,),#}
(2)
考虑下列产生式:
FIRST(+E)∩FIRST(ε)={+}∩{ε}=φ
FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ
FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ
FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φ
FIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ
FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ
所以,该文法式LL(1)文法.
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
begin
advance; E;
if sym=')' then advance
else error
end
else error
end;
P81–3
/***************
(1)是，满足三个条件。
(2)不是，对于A不满足条件3。
(3)不是，A、B均不满足条件3。
(4)是，满足三个条件。
***************/
第五章P133–1
短语: E+T*F, T*F,
直接短语: T*F
句柄: T*F
P133–2
文法：
(1)
最左推导:
最右推导:
(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,^,)}
G是算符文法，并且是算符优先文法
6
(3)优先函数
（4）
栈输入字符串动作
# （a,(a,a)）#
预备
#( a, (a,a))# 进
#(a , (a,a))#
进
#(t , (a,a))# 归
#（t, (a,a)）# 进
#（t,（a,a））# 进
#（t,（a ,a））# 进
#（t,（t ,a））# 归
#（t,（t, a））#
进
#（t,（t,a ））#
进
#（t,（t,s ））#
归
#（t,（t ））#
归
#（t,（t））#
进
#（t,s ）#
归 #（t
）#
归 #（t ）
#
进 # s
#
归
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)
ε S 确定化：
GO(0I ，b)={ S b →?}=2I
GO(0I ，S)={ '→?S S ，A S A →?，A SA →?，A a →?，S AS →?，S b →?}=3I GO(0I ，A)={ S A S →?，S AS →?，S b →?，A SA →?，A a →?}=4I GO(3I ，a)={ A a →?}=1I GO(3I ，b)={ S b →?}=2I
GO(3I ，S)={ A S A →?，S AS →?，S b →?，A SA →?，A a →?}=5I
GO(3I ，A)={ A SA →?，S A S →?，S AS →?，S b →?，A SA →?，A a →?}=6I GO(4I ，a)={ A a →?}=1I GO(4I ，b)={ S b →?}=2I
GO(4I ，S)={ S AS →?，A S A →?，S AS →?，S b →?，A SA →?，A a →?}=7I GO(4I ，A)={ S A S →?，S AS →?，S b →?，A SA →?，A a →?}=4I GO(5I ，a)={ A a →?}=1I GO(5I ，b)={ S b →?}=2I
GO(5I ，S)={ A S A →?，S AS →?，S b →?，A SA →?，A a →?}=5I
GO(5I ，A)={ A SA →?，S A S →?，S AS →?，S b →?，A SA →?，A a →?}=6I GO(6I ，a)={ A a →?}=1I GO(6I ，b)={ S b →?}=2I
GO(6I ，S)={ S AS →?，A S A →?，S AS →?，S b →?，A SA →?，A a →?}=7I GO(6I ，A)={ S A S →?，S AS →?，S b →?，A SA →?，A a →?}=4I GO(7I ，a)={ A a →?}=1I GO(7I ，b)={ S b →?}=2I
GO(7I ，S)={ A S A →?，S AS →?，S b →?，A SA →?，A a →?}=5I
GO(7I ，A)={ A SA →?，S A S →?，S AS →?，S b →?，A SA →?，A a →?}=6I
项目集规范族为C={1I ，2I ，3I ，4I ，5I ，6I ，7I }
(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，因为包含项目[b
?
→]，所以遇到搜索符号a或b时，应该用
A/
AS
a
A/
→]，所以遇到搜索符号a时，应该
?
a
a
AS
A→归约。又因为状态5包含项目[b
移进。因此存在“移进-归约”矛盾，所以这个文法不是LR(1)文法。
b b b
S b
A
A
第六章
/********************第六章会有点难
P164–5
(1)
E →E1＋T {if = int) and = int ) then := int
else := real}
E →T { := }
→ { := real}
T →num { := int}
(2)
P164–7
S →L1|L2 {:=+2length L .2)} S →L {:=} L →L1B {:=2* + ;
:=+1}
L →B
{:=; :=1} B →0 {:=0} B →1
{:=1}
***********************/
第七章
P217–1
a*(-b+c) ab@c+*
a+b*(c+d/e) abcde/+*+
-a+b*(-c+d) a@bc@d+*+
if (x+y)*z =0 then (a+b)↑c else a↑b↑c xy+z*0= ab+c↑abc↑↑￥
或 xy+z*0= P1 jez ab+c↑ P2 jump abc↑↑
P1 P2
P217–3
-(a+b)*(c+d)-(a+b+c)的
三元式序列:
(1)+, a, b
(2)@, (1), -
(3)+, c, d
(4)*, (2), (3)
(5)+, a, b
(6)+, (5), c
(7)-, (4), (6)
间接三元式序列:
三元式表：
(1)+, a, b
(2)@, (1), -
(3)+, c, d
(4)*, (2), (3)
(5)+, (1), c
(6)-, (4), (5)
间接码表：
(1)
(2)
(3)
(4)
(1)
(5) (6) 四元式序列: (1) +, a, b, 1T (2) @, 1T , -, 2T (3) +, c, d, 3T (4) *, 2T , 3T , 4T (5) +, a, b, 5T (6) +, 5T , c, 6T (7)
-, 4T , 6T , 7T
P218–4
自下而上分析过程中把赋值句翻译成四元式的步骤:A:=B*(-C+D) 步骤 输入串
栈
PLACE
四元式
(1) A:=B*(-C+D) (2) :=B*(-C+D) i A (3) B*(-C+D) i:= A- (4) *(-C+D) i:=i A-B
(5) *(-C+D) i:=E A-B
(6) *(-C+D) i:=E A-B (7) (-C+D) i:=E* A-B- (8) -C+D) i:=E*( A-B-- (9) C+D) i:=E*(- A-B--- (10) +D) i:=E*(-i A-B---C (11) +D) i:=E*(-E A-B---C (@,C,-, T 1
)
(12) +D) i:=E*(E A-B--T 1
(13) D) i:=E*(E+ A-B--T 1
-
(14) ) i:=E*(E+i A-B--T 1
-D
(15) ) i:=E*(E+E A-B--T 1-D (+,T 1,D,T 2
)
(16) ) i:=E(E A-B--T 2
(17) i:=E*(E) A-B--T 2
-
(18) i:=E+E A-B-T 2 (*,B,T 2,T 3
)
(19)
i:=E A-T 3 (:=,T 3
,-,A)
(20) A
产生的四元式： (@,C,-, T 1
)
(+,T 1,D,T 2) (*,B,T 2,T 3
)
(:=,T 3,-,A)
/****************
设A ：10*20，B、C、D：20，宽度为w＝4 则T1:= i * 20
T1:=T1+j
T2:=A–84
T3:=4*T1
Tn:=T2[T3] //这一步是多余的
T4:= i + j
T5:=B–4
T6:=4*T4
T7:=T5[T6]
T8:= i * 20
T8:=T8+j
T9:=A–84
T10:=4*T8
T11:=T9[T10]
T12:= i + j
T13:=D–4
T14:=4*T12
T15:= T13[T14]
T16:=T11+T15