编译原理第三版课后习题解答

P36-6

(1)

L(G1)是0~9组成的数字串

(2) 最左推导: 最右推导:

P36-7

G(S)

P36-8

文法： 最左推导: 最右推导:

语法树：/******************************** *****************/

P36-9

句子iiiei有两个语法树：

P36-10

/************** ***************/

P36-11

/***************

L1: L2: L3: L4:

***************/

第三章习题参考答案

P64–7

(1)

1(01|)*101 X 0 1   1 0 1 X 1 2 3 4 5 Y 1 确定化： {X} φ {1,2,3} {2,3} {2,3,4} {2,3,5} {2,3,4,Y} 0 φ φ {2,3} {2,3} {2,3,5} {2,3} {2,3,5} 1 {1,2,3} φ {2,3,4} {2,3,4} {2,3,4} {2,3,4,Y} {2,3,4,} Y 0 1 0 0 2 3 0 0 1 1 0 1 0 1 4 5 6 0 1 1 1 最小化：

0 1 0 2 0 0 1 0 1 0 1 3 4 5 0 1 1 1

P64–8

(1) (2) (3)

P64–12

(a)

a a,b 0 1 a 确定化： {0} {0,1} {1} φ 给状态编号： 0 1 2 3 a a 0 1 a b b b

2 3 b a 最小化：

a a b b 1 2 0 a 1 1 0 3 b 2 2 3 3 a {0,1} {0,1} {0} φ b {1} {1} φ φ a

b (b)

b b a 0 2 3 a b a a b

b a 1 4 5 a a 已经确定化了,进行最小化 最小化：

b b a 0 1 2 a b a

P64–14

(1) 0 1 0 1 0 (2):

X (010|)* Y

2 0

1   1 Y X 0 确定化： {X,1,Y} {1,Y} {2} φ 给状态编号： 0 1 2 3 0

0 1 0 1 1 1 3 1 2 2 3 3 0 {1,Y} {1,Y} {1,Y} φ 1 {2} {2} φ φ 0 1 0 1 1 2 3 1 0 最小化：

0 1 1 1 1 3 0 0 0

第四章

P81–1

(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)={)} 预测分析表

S T a ^ ( ) , # 是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)文法. (3) E + * ( ) a b ^ # E' T T' F F' 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

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 # 1 #( 2 #((

输入串

动作

(((a,a),^,(a)),a)# 预备 ((a,a),^,(a)),a)# 进 (a,a),^,(a)),a)# 进

a,a),^,(a)),a)# 进 ,a),^,(a)),a)# 进 ,a),^,(a)),a)# 归

3 #((( 4 #(((a 5 #(((S

6 #(((T 7 #(((T,

,a),^,(a)),a)# 归 a),^,(a)),a)#

进

8 #(((T,a 9 #(((T,S 10 #(((T 11 #(((T) 12 #((S 13 #((T 14 #((T, 15 #((T,^ 16 #((T,S 17 #((T 18 #((T, 19 #((T,(

),^,(a)),a)# 进 ),^,(a)),a)# 归

),^,(a)),a)# 归 ,^,(a)),a)# 进 ,^,(a)),a)# 归 ,^,(a)),a)# 归 ^,(a)),a)# ,(a)),a)# ,(a)),a)# ,(a)),a)# (a)),a)# a)),a)#

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

归 归 进

进 归 归 进 进 进 归 归 进

进

20 #((T,(a 21 #((T,(S 22 #((T,(T 23 #((T,(T) 24 #((T,S 25 #((T 26 #((T) 27 #(S

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

归

,a)#

28 #(T ,a)#

a)# )# )#

归

归 进 进 归

29 #(T, 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 g 5 5 5 2 （4） 栈 # #( #(a #(t

#（t,

#（t,（ #（t,（a #（t,（t #（t,（t,

#（t,（t,a #（t,（t,s #（t,（t

#（t,（t） #（t,s #（t

#（t ） # s

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

a, (a,a))# , (a,a))# , (a,a))# (a,a)）#

a,a））# ,a））#

,a））#

a））#

））# ））# ））#

）#

）#

）#

#

#

动作 预备 进

进 归 进 进 进 归

进 进 归 归 进

归 归 进 归

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)

1 S A 7 8 9 S 0 10  a 1  A S 2 3 4 d 5 6 确定化： S A a b {0,2,5,7,1{1,2,5,7,8{2,3,5,7,1{11} {6} 0} ,10} 0} {1,2,5,7,8{2,5,7,8,1{2,3,5,7,9{11} {6} ,10} 0} ,10} {2,3,5,7,1{2,4,5,7,8{2,3,5,7,1{11} {6} 0} ,10} 0} {2,5,7,8,1{2,5,7,8,1{2,3,5,7,9{11} {6}  0} {2,3,5,7,9,10} {2,4,5,7,8,10} {11} {6} 0} {2,4,5,7,8,10} {2,5,7,8,10} φ φ ,10} {2,3,5,7,10} {2,3,5,7,9,10} φ φ φ φ φ φ {11} {6} {11} {6} A S

3:5:6: S  A AS A ASA SS a b

S a A S b S A b

a A

0:SS 4:SAS 7:SAS A S b a a b b a

1: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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)文法。

b b b 1： 5： 8： A A A S a a S 3： S a S 0： 3： a a A a A 6： 9： S 4： b S A b

a a S b b 2： 7：

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)

10： 5： P164–7

SL1|L2 {:=+2L2.length)} 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, T1 (2) @, T1, -, T2 (3) +, c, d, T3 (4) *, T2, T3, T4 (5) +, a, b, T5 (6) +, T5, c, T6 (7) -, T4, T6, T7

P218–4

自下而上分析过程中把赋值句翻译成四元式的步骤:A:=B*(-C+D) 步骤 输入串

栈

PLACE

四元式

(1) A:=B*(-C+D) (2) :=B*(-C+D) i (3) B*(-C+D) i:= (4) *(-C+D) (5) *(-C+D) (6) *(-C+D) (7) (-C+D) (8) -C+D) (9) C+D) (10) (11) (12) (13) (14) (15) (16) (17) (18) (19)

A

A-

A-B A-B A-B

i:=i i:=E i:=E

i:=E* i:=E*(

A-B- A-B--

A-B---

i:=E*(-

+D) i:=E*(-i A-B---C

+D) i:=E*(-E A-B---C (@,C,-, T)

1+D) i:=E*(E A-B--T

1D) i:=E*(E+ A-B--T-

1) i:=E*(E+i A-B--T-D

1 ) i:=E*(E+E A-B--T-D (+,T,D,T)

112 ) i:=E(E A-B--T

2 i:=E*(E) A-B--T-

2 i:=E+E A-B-T (*,B,T,T)

223 i:=E A-T (:=,T,-,A)

33(20) A

产生的四元式：

(@,C,-, T)

1(+,T1,D,T2) (*,B,T,T)

23(:=,T3,-,A)

P218–5

/****************

设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 T17:=C–4 T18:=4*T16 T19:=T17[T18] T20:=T7+T19 Tn:=T20

******************/

P218–6

100. (jnz, A, -, 0) 101. (j, -, -, 102) 102. (jnz, B, -, 104) 103. (j, -, -, 0) 104. (jnz, C, -, 103) 105. (j, -, -, 106)

106. (jnz, D, -, 104) --107. (j, -, -, 100) --假链：{106,104，103} 真链：{107,100}

P218–7

100. (j<, A, C, 102)

假链链首真链链首 101. (j, -, -, 0) 102. (j<, B, D, 104) 103. (j, -, -, 101) 104. (j=, A, ‘1’, 106) 105. (j, -, -, 109) 106. (+, C, ‘1’, T1) 107. (:=, T1, -, C) 108. (j, -, -, 100) 109. (j≤, A, D, 111) 110. (j, -, -, 100) 111. (+, A, ‘2’, T2) 112. (:=, T2, -, A) 113. (j, -, -, 109) 114. (j, -, - 100)

P219–12

/******************** (1)

MAXINT – 5 MAXINT – 4 MAXINT – 3 MAXINT – 2 MAXINT – 1

MAXINT (2)翻译模式 方法1：

for E1 := E2 to E3 do S

SF do MS1

{backpatch,nextquad); backpatch,;

emit ‘:=’ ‘+’1);

emit(‘j,’ ‘,’ ‘,’; := ; }

FFor I:E1 to E2 {:= makelist(nextquad);

emit(‘j>,’ ‘,’ ‘,0’);

emit ‘:=’;

:= makelist(nextquad); emit(‘j,-,-,-’); := ; := ; }

{p:=lookup; if p <> nil then

:= p else error}

Iid

M { := nextquad}

****************/ 方法2：

S→ for id:=E1 to E2 do S1 S→ F S1

F→ for id:=E1 to E2 do Fforid:E1toE2do

{

INITIAL=NEWTEMP;

emit(‘:=，’’， -，’ INITIAL); FINAL=NEWTEMP;

emit(‘:=，’’， -，’ FINAL); p:= nextquad+2;

emit(‘j,’ INITIAL ‘,’ FINAL ’,’:=makelist(nextquad); emit(‘j,－,－,－’); :=lookup; if nil then

emit ‘:=’ INITIAL) :=nextquad; :=FINAL; }

p); {

backpatch, nextquad) p:=nextquad+2;

emit(‘j,’ ‘,’ ’,’ p ); := merge, makelist(nextquad)); emit(‘j,－,－,－’); emit(‘succ，’ ’， -，’ ; emit(‘j,－,－,’ ; }

第九章

P270–9

(1) 传名

即当过程调用时，其作用相当于把被调用段的过程体抄到调用出现处，但必须将其中出现的任一形式参数都代之以相应的实在参数。 A:=2; B:=3; A:=A+1; A:=A+(A+B); print A; ∴A=9 (2) 传地址

即当程序控制转入被调用段后，被调用段首先把实在参数抄进相应的形式参数的

形式单元中，过程体对形参的任何引用或赋值都被处理成对形式单元的间接访问。当被调用段工作完毕返回时，形式单元（都是指示器）所指的实参单元就持有所希望的值。

①A:=2;B:=3;T:=A+B

②把T,A,A的地址抄进已知单元J1,J2,J3

③x:＝J1;y:=J2;z:=J3 //把实参地址抄进形式单元，且J2=J3 ④Y↑:=y↑+1

Z↑:=z↑+x↑ // Y↑：对y的间接访问 Z↑：对z的间接访问 ⑤print A A=8 (3) 得结果

每个形参均对应两个单元，第一个存放实参地址，第二个存放实参值，在过程体中对形参的任何引用或赋值都看成是对它的第二个单元的直接访问，但在过程工作完毕返回前必须把第二个单元的内容放到第一个单元所指的那个实参单元中 ①A:=2;B:=3;T:=A+B

②把T,A,A的地址抄进已知单元J1,J2,J3 ③x1:=J1;x2:=T; y1:=J2;y2:=A;

z1:=J3;z2:=A; //将实参的地址和值分别放进两个形式单元中 ④y2:=y2+1; z2:=z2+x2; //对形参第二个单元的直接访问

⑤x1↑：＝x2; y1↑:=y2; z1↑:=z2 //返回前把第二个单元的内容存放到第一

个单元所指的实参地址中

⑥print A A=7 (4) 传值

即被调用段开始工作时，首先把实参的值写进相应的形参单元中，然后就好像使用局部变量一样使用这些形式单元A:=2; B:=3; x:=A+B y:=A z:=A y:=y+1 z:=z+x print A A=2

过程调用不改变A的值

P306-1 P306-2

read A,B F:=1

C:=A*A B1第十章B

D:=B*B

if CB--------------------------- E:=A*A F:=F+1

E:=E+F B2 write E halt

---------------------------

L1: E:=B*B

F:=F+2

E:=E+F B3 write E

if E>100 goto L2 --------------------------- halt B4 ---------------------------

L2: F:=F-1

goto L1 B5 --------------------------- 基本块为B1、B2、B3、B4、B5

P307-4

BBBI:=1 A:=K*I B:=J*I L: C:=A*B write C A:=A+K halt

B2有回路，所以{B2}是循环，B2既是入口节点，又是出口节点 （1） 代码外提：不存在不变运算，故无代码外提 （2） 强度削弱：A:=K*I B:=J*I *→+

（3） 删除基本归纳变量：I<100 可以用A<100*K或B<100*J代替

P307-5

A:=0 I:=1 {B2,B3}是循环，B2是入口节点，也是出口节点 （1） 代码外提：B:=J+1 B:=J+1 （2） 删除归纳变量 C:=B+I L1’: A:=C+A C:=C+1