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

P36-6

(1)

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

(2)

最左推导:

N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒0010120127334

556568

最右推导:

N ND N ND N ND N D N ND N D N ND N ND N D ⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒⇒77272712712701274434

886868568

P36-7

G(S)

O N O D N S O AO A AD N

→→→→→1357924680|||||||||||

P36-8

文法：

E T E T E T T

F T F T F F E i

→+-→→|||*|/()| 最左推导:

E E T T T

F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+********()*()*()*()*()*()*()

最右推导:

E E T E T

F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒+⇒⇒⇒⇒⇒+⇒+⇒+⇒+⇒+⇒+⇒+**********()*()*()*()*()*()*()*()

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

E

E F

T

E +

T F F T +i

i

i

E

E

F

T

E

-T F F T -i

i

i

E E

F

T

+T F F

T

i

i

i

*i+i+i

i-i-i

i+i*i

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

P36-9

句子iiiei 有两个语法树：

S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ⇒⇒⇒⇒⇒⇒⇒⇒

P36-10

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

)

(|)(|S T T

TS S →→

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

P36-11

/*************** L1:

ε

||cC C ab aAb A AC

S →→→ L2:

bc

bBc B aA A AB S ||→→→ε

L3:

ε

ε||aBb B aAb A AB

S →→→ L4:

A

B B A A B A S |01|10|→→→ε ***************/

第三章习题参

P–7

(1)

101101(|)*

1 ε ε 1 0 1

1 确定化：

0 1 {X} φ {1,2,3} φ φ φ {1,2,3} {2,3} {2,3,4} {2,3} {2,3} {2,3,4} {2,3,4} {2,3,5} {2,3,4}

{2,3,5} {2,3} {2,3,4,Y} {2,3,4,Y}

{2,3,5}

{2,3,4,}

1 0

0 0 1 1 0

0 1 0 1 1 1 最小化：

X 1 2 3 4 Y

5 X

Y

6

0 1

2 3

5 4

{,,,,,},{}

{,,,,,}{,,}{,,,,,}{,,,}{,,,,},{},{}{,,,,}{,,}

{,,,},{},{},{}

{,,,}{,01234560123451350123451246012345601234135012345601231010

0==== 301231240123456011011223323401234561

01

01

}{,,,}{,,}

{,},{,}{},{},{}

{,}{}{,}{,}

{,}{}{,}{}

{},{},{,},{},{},{}

===== 0

1

0 0 1 0

0 1 0 1 1 1

P–8

(1)

01)0|1(*

(2)

)5|0(|)5|0()9|8|7|6|5|4|3|2|1|0)(9|8|7|6|5|4|3|2|1(*

(3)

******)110|0(01|)110|0(10

P–12

(a)

a

a,b a

确定化：

a b {0} {0,1} {1} {0,1} {0,1} {1} {1}

{0}

φ

5 0

1 2 4 3 0

1

φ

φ

φ

给状态编号：

a b 0 1 2 1 1 2 2 0 3 3

3

3

a

a

a b b b

b

a

最小化：

{,},{,}

{,}{}{,}{}

{,}{,}{,}{}{,},{},{}

012301101223032330123a b

a b ====

a a

b b

a

b (b)

b b a

a b

a

a b

b a

a a

已经确定化了,进行最小化

0 1 2 3 0

1 2 0 2 3 1

4 5

最小化：

{{,}, {,,,}}

012345011012423451305234523452410243535353524012435011012424{,}{}{,}{,}

{,,,}{,,,}{,,,}{,,,}{,}{,}{,}{,}{,}{,}{,}{,}{{,},{,},{,}}

{,}{}{,}{,}{,}a b a b a b a b a b a =============={,}{,}{,}{,}{,}{,}{,}

10243535353524 b a b

b b a

a b

a

P–14

(1) 0

1 0 (2):

(|)*010

0 1 ε ε

确定化：

0 1 {X,1,Y}

{1,Y}

{2}

0 1 2 0

1

Y

X Y

X

2 1

{1,Y} {1,Y} {2} {2} {1,Y} φ φ

φ

φ

给状态编号：

0 1 0 1 2 1 1 2 2 1 3 3

3

3

0 1 0

1 1 1

0 最小化：

{,},{,}

{,}{}{,}{}{,}{,}{,}{}{,},{},{}

0123011012231323301230101====

1 1 1 0

第四章

P81–1

(1) 按照T,S 的顺序消除左递归

ε

|,)

(||^)(T S T T S T T a S S G '→''→→' 递归子程序：

procedure S; begin

if sym='a' or sym='^' then abvance else if sym='('

0 2 1

3 0

1 3

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

a

^

(

) , # S S a → S →^

S T →() T

T ST →' T ST →' T ST →'

'T

'→T ε '→'T ST ,

是LL(1)文法

P81–2

文法：

|^

||)(|*||b a E P F F F P F T T T F T E E E T E →'→''→→''→+→''→εεε

(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)

考虑下列产生式:

'→+'→'→'→E E T T F F P E a b ||*|()|^||εεε

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)

+ * (

) a b ^ # E

E TE →'

E TE →' E TE →' E TE →'

E' '→+E E

'→E ε

'→E ε

T

T FT →'

T FT →' T FT →' T FT →'

T'

'→T ε

'→T T '→T ε '→T T '→T T '→T T '→T ε

F

F PF →' F PF →' F PF →' F PF →'

F' '→F ε '→'F F * '→F ε '→F ε '→F ε '→F ε '→F ε '→F ε

P

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

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

(((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 > > ^ > > ( < < < = < ) > > , < < < > >

6

G是算符文法，并且是算符优先文法

(3)优先函数

a ^ ( ) ,

f 4 4 2 4 4

g 5 5 5 2 3

f a f

^

f

(

f

)

f

,

g a g

^

g

(

g

)

g

,

（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 A ε

S

ε ε ε ε a

ε ε ε

A S ε ε

d

确定化：

S A a b {0,2,5,7,10} {1,2,5,7,8,10

} {2,3,5,7,10} {11} {6} {1,2,5,7,8,10

{2,5,7,8,10}

{2,3,5,7,9,10

{11}

{6}

0 10 5 7 6

1 11

2 3 4

8 9

}

} {2,3,5,7,10} {11} {6} {2,5,7,8,10} {2,5,7,8,10} {2,3,5,7,9,10

} {11} {6} {2,3,5,7,9,10

} {2,4,5,7,8,10

} {2,3,5,7,10} {11} {6} {2,4,5,7,8,10

}

{2,5,7,8,10}

{2,3,5,7,9,10

}

{11} {6} {11} φ φ φ φ {6}

φ

φ

φ

φ

A S

S A a

b

S a A S b S A b a A

A S

b

a a

b b a

DFA

构造LR(0)项目集规范族也可以用GO 函数来计算得到。所得到的项目集规范族与上图中的项目集一样:

0I ={'→⋅S S ，S AS →⋅，S b →⋅，A SA →⋅，A a →⋅} GO(0I ，a)={ A a →⋅}=1I GO(0I ，b)={ S b →⋅}=2I

GO(0I ，S)={ '→⋅S S ，A S A →⋅，A SA →⋅，A a →⋅，S AS →⋅，S b →⋅}=3I

0:'→⋅S S

S AS →⋅ S b →⋅ A SA →⋅ A a →⋅ 4:S A S →⋅ S AS →⋅ S b →⋅

A SA →⋅ A a →⋅

3:'→⋅S S

A S A →⋅ A SA →⋅ A a →⋅

S AS

→⋅S b →⋅

2:S b →⋅

1:A a →⋅ 5:A S A →⋅ S AS →⋅

S b →⋅

A SA →⋅ A a →⋅ 6:A SA →⋅

S A S →⋅ S AS →⋅ S b →⋅

A SA →⋅ A a →⋅ 7:S AS →⋅ A S A →⋅

S AS →⋅ S b →⋅

A SA →⋅ A a →⋅

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 AS A / ⋅→]，所以遇到搜索符号a 或b 时，应该用AS A →归约。又因为状态5包含项目[b a a A / ⋅→]，所以遇到搜索符号a 时，应该移进。因此存在“移进-归约”矛盾，所以这个文法不是LR(1)文法。

b b b

A A A

S

a

a S

S a S

a a A a

A S b S A b

a a S

b b

S b

A A 0： a/b a A a/b SA A #/a/b b S #/a/b AS S S S # ⋅→⋅→⋅→⋅→⋅→' 2： a/b

a A a/

b SA A #/a/b b S #/a/b AS S #/a/b

S A S ⋅→⋅→⋅→⋅→⋅→

1： a/b b S a/b AS S a/b a A a/b SA A a/b A S A S S # ⋅→⋅→⋅→⋅→⋅→⋅→'3： a/b a A ⋅→4：

a/b b S /# ⋅→

5： a/b a A a/b SA A a/b b S a/b AS S a/b S A S a/b SA A ⋅→⋅→⋅→⋅→⋅→⋅→6：

a/b b S a/b

AS S a/b a A a/b SA A a/b A S A ⋅→⋅→⋅→⋅→⋅→

7： a/b b S a/b AS S a/b a A a/b SA A a/b A S A a/b AS S /# ⋅→⋅→⋅→⋅→⋅→⋅→ 9： a/b

b S a/b

AS S a/b a A a/b SA A a/b A S A a/b AS S ⋅→⋅→⋅→⋅→⋅→⋅→8： a/b

a A a/b

SA A a/b b S a/b AS S a/b S A S ⋅→⋅→⋅→⋅→⋅→ 10： a/b b S ⋅→ 3： 5：

第六章

/********************第六章会有点难

P1–5

(1)

E →E1＋T {if (E1.type = int) and (T.type = int ) then E.type := int else E.type := real} E →T {E.type := T.type} T →num.num {T.type := real} T →num {T.type := int} (2)

P1–7

S →L1|L2

{S.val:=L1.val+(L2.val/2

length

L .2)}

S →L {S.val:=L.val}

L →L1B {L.val:=2*L1.val + B.val; L.length:=L1.length+1} L →B {L.val:=B.c;

L.length :=1} B →0 {B.c:=0} B →1 {B.c:=1} ***********************/

第七章

P217–1

a*(-b+c) ab@c+* a+b*(c+d/e) abcde/+*+ -a+b*(-c+d)

a@bc@d+*+ )(D C A ⌝∨⌝∨⌝

∨⌝∨⌝⌝CD A )()(D C B A ∨⌝∨∧

∨∨∧D C AB @ )()(E D C B A ∧⌝∨∧∨

∧∨∧∨E CD AB @

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

(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)

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–4T19:=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

方法1：

for E1 := E2 to E3 do S

ε→→=→→M id

I E E I F MS F S 2

11

to :For do

1 do MS F S →

{backpatch(S1.nextlist,nextquad);

backpatch(F.truelist,M.quad); emit(F.place ‘:=’F.place ‘+’1);

emit(‘j ≤,’F.place ‘,’F.end ‘,’M.quad);

S.nextlist := F.falselist; }

21 to :For E E I F =→

{F.falselist:= makelist(nextquad); emit(‘j>,’E1.place ‘,’E2.place ‘,0’);

emit(I.Place ‘:=’E1.place);

F.truelist := makelist(nextquad);

emit(‘j,-,-,-’);

F.place := I.place;

F.end := E2.place;

} id I →

{p:=lookup(id.name);

if p <> nil then I.place := p else error} ε→M

{M.quad := nextquad}

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

方法2：

S → for id:=E1 to E2 do S1

S → F S1

F → for id:=E1 to E2 do

21:toE E forid F =→do {

INITIAL=NEWTEMP;

emit(‘:=，’E1.PLACE ’， -，’ INITIAL);

FINAL=NEWTEMP;

emit(‘:=，’E2.PLACE ’， -，’ FINAL);

p:= nextquad+2; emit(‘j ,’ INITIAL ‘,’ FINAL ’,’ p);

F.nextlist:=makelist(nextquad);

F.place:=lookup(id.name);

if F.place nil then

emit(F.place ‘:=’ INITIAL)

F.quad:=nextquad;

F.final:=FINAL;

}

S

1

FS

{

backpatch(S1.nextlist, nextquad)

p:=nextquad+2;

emit(‘j,’ F.place‘,’ F.final ’,’ p );

S.nextlist := merge(F.nextlist, makelist(nextquad));

emit(‘j,－,－,－’);

emit(‘succ，’ F.place ’， -，’ F.place);

emit(‘j,－,－,’ F.quad);

}

第九章

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 1

B

D:=B*B

if C---------------------------

E:=A*A

F:=F+1

E:=E+F 2B

write E

halt

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

1L : E:=B*B

F:=F+2

E:=E+F 3B

write E

if E>100 goto 2L B B B B B

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

halt 4B

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

2L : F:=F-1

goto 1L 5B

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

基本块为1B 、2B 、3B 、4B 、5B

P307-4

B2有回路，所以{B2}是循环，B2既是入口节点，又是出口节点

（1） 代码外提：不存在不变运算，故无代码外提

（2） 强度削弱：A:=K*I B:=J*I *→+

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

I:=1

read J,K A:=K*I

B:=J*I

T :=K*100

L: C:=A*B

write C

A:=A+K

B:=B+J

if AA:=0

I:=1

B:=J+1

C:=B+I

T:=B+100

L1’: A:=C+A

if C=T goto L2

C:=C+1

goto L1’

L2’:

{B2,B3}是循环，B2是入口节点，也是出口节点（1）代码外提：B:=J+1

（2）删除归纳变量