《编译基本知识》(陈火旺版)课后作业任务参备考资料答案解析

* *

第6章 属性文法和语法制导翻译

7. 下列文法由开始符号S产生一个二进制数，令综合属性val给出该数的值：

S→L.L∣L

L→LB∣B

B→0∣1

试设计求的属性文法，其中，已知B的综合属性c, 给出由B产生的二进位的结果值。

例如，输入101.101时，=5.625，其中第一个二进位的值是4，最后一个二进位的

值是0.125。

【答案】

产生式 语义规则

{ := L

1

.val + L

2

.val*2

－

S→L

1

. L

2

}

S→L { := }

{ :=L

1

.val*2+;

L→L

1

B

L. length:= L

1

.length +1 }

{ :=;

L→B

L. length:= 1 }

B→0

B→1

{ := 0 }

{ :=1 }

11. 设下列文法生成变量的类型说明：

L→ id L

L→, id L∣:T

T→ integer∣real

* *

(1) 构造一下翻译模式，把每个标识符的类型存入符号表；参考例6.2。

【答案】

产生式 语义规则

{ := L

1

.val + L

2

.val*2

L→ id L

1

}

－

L→, id L

1

{ := }

{ :=L

1

.val*2+;

L→ :T

L. length:= L

1

.length +1 }

{ :=;

T→ integer

L. length:= 1 }

T→ real { := 0 }

第7章 语义分析和中间代码产生

1. 给出下面表达式的逆波兰表示（后缀式）：

【答案】

原式

(1) a*(-b+c)

(2) a+b*(c+d/e)

(3) –a+b*(-c+d)

(4) not A or not (C or not D)

(5) (A and B) or (not C or D)

ab-c+*

abcde/+*+

a-bc-d+*+

A not C D not or not or

A B and C not D or or

后缀式

* *

(6) (A or B) and (C or not D and A B or C D not E and or and

E)

(7) if (x+y)*z=0

then (a+b)↑c

else a↑b↑c

if xy+z*0=

then ab+c↑

else ab↑c↑

3. 请将表达式－(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。

【答案】

三元式

(1

)

(2

)

(3

)

(4

)

(5

)

(6

)

+ (5) c

+ a b

* (2) (3)

+ c d

－ (1) ／

+ a b

* *

(7

)

－ (4) (6)

(1

)

+

四元式

a b T1

间接三元式

(1

)

(2

)

－ (1) ／

+ a b

(2

)

(3

)

(4

)

(5

)

(6

)

(7

)

－ T1 ／ T2

+ c d T3

(3

)

+ c d

* T2 T3 T4

(4

)

* (2) (3)

+ a b T5

(5

)

+ (1) c

+ T5 c T6

(6

)

－ (4) (5)

－ T4 T6 T7

间接码表：(1)→(2)→(3)→(4)→(1)→(5)

→(6)

4. 按7.3节所说的办法，写出下面赋值句A:=B*(－C+D) 的自下而上语法制导翻译过程。

给出所产生的三地址代码。

四元式

* *

【答案】

(1

)

(2

)

(3

)

(4

)

uminus c ／ T1

+ T1 D T2

* B T2 T3

:= T3 ／ A

5. 按照7.3.2节所给的翻译模式，把下列赋值句翻译为三地址代码：

A[i, j]:=B [i, j] + C[A [k, l]] + d [ i+j]

【答案】

中间代码

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

T

1

:=i*N

A2

T

1

:=T

1

+j

T

2

:=A-C

A

T

3

:=W

A

*T

1

T

4

:=i* N

B2

T

4

:=T

4

+j

T

5

:=B-C

B

T

6

:=W

B

*T

4

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

中间代码

T

10

:=W

A

*T

8

T

11

:=T

9

[T

10

]

T

12

:=C-C

c

T

13

:=W

c

*T

11

T

14

:=T

12

[T

13

]

T

15

:=T

7

+ T

14

T

16

:=i+j

T

17

:=d-C

d

* *

(9) T

7

:=T

5

[T

6

] (21)

(22)

(23)

(24)

T

18

:=W

d

*T

16

T

19

:=T

17

[T

18

]

T

20

:=T

15

+ T

19

T

2

[T

3

]:=T

20

(10) T

8

:=k* N

A2

(11) T

8

:=T

8

+l

(12) T

9

:=A-C

A

6. 按7.4.1和7.4.2节的翻译办法，分别写出布尔式A or ( B and not (C or D) )的四元

式序列。

* *

【答案】

用作数值计算时产生的四元式： 用作条件控制时产生的四元式：

四元式

(1

)

(2

)

(3

)

(4

)

列：

While A

if A=1 then C:=C+1

else while A≦D do

A:=A+2;

【答案】

or A T

3

T

4

and B T

2

T

3

not T

1

／ T

2

or C D T

1

(1)

(2)

(3)

(4)

四元式 四元式

( jnz, A, -, 0 ) (5) ( jnz, C, -, (4))

( j, -, -, (3)) (6) ( j, -, -, (7))

(jnz, B, -, (5)) (7) ( jnz, D, -, (5))

( j, -, -, 0 ) (8) ( j, -, -, (1))

其中：右图中(1)和(8)为真出口，(4)(5)(7)为假出口。

7. 用7.5.1节的办法，把下面的语句翻译成四元式序

四元式

(1)

(2)

(j<, A, C, (3)) (9)

( j, -, -, 0) (10)

四元式

( j, -, -, (1))

( j≦, A, D,(12))

* *

(3)

(4)

(5)

(6)

(7)

(8)

(j<, B, D, (5)) (11)

( j, -, -, 0 ) (12)

( j, -, -, (1))

(+, A, 2, T

2

)

(:=,T

2

, -, A )

( j, -, -, (10))

( j, -, -, (1))

(j=, A, 1, (7)) (13)

( j, -, -, (10) )

(+, C, 1, T

1

)

(:=,T

1

, -, C )

(14)

(15)

* *

* *

第9章 运行时存储空间组织

4. 下面是一个Pascal程序：

program PP (input, output);

VAR k: integer;

FUNCTION F (n: integer): integer;

begin

if n<=0 then F:=1

else F:=n*F(n-1);

end;

begin

K:=F(10);

…

end.

当第二次( 递归地) 进入F后，DISPLAY的内容是什么？当时整个运行栈的内容是什么？

【答案】

第1次进入F后，运行栈的内容： 第2次进入F后，运行栈的内容：

10

9

8

7

6

5

4

3

2

1

4

0

n(形参)

1(形参个数)

2(全局display)

返回地址

0

k

0(display)

返回地址

主程序P

F

* *

0 0

17 11

16 0

第2次F

15 n(形参)

14

13

12

11

10

9

8

1(形参个数)

9(全局display)

返回地址

4

4

主程序P

0

n(形参)

第1次F

7 1(形参个数)

6 2(全局display)

5

第2次进入F后，Display内容为：

4

11

0

3

2

1

0

0

返回地址

0(display)

k

0

返回地址

5. 对如下的Pascal程序，画出程序执行到(1)和(2)点时的运行栈。

program Tr (input, output);

VAR i: integer; d: integer;

procedure A ( k: real );

VAR p: char;

* *

procedure B;

VAR c: char;

Begin

…(1)…

end; {B}

procedure C;

VAR t: real;

Begin

…(2)…

end; {C}

Begin

……

B;

C;

……

end; {A }

Begin { main }

…

A(d);

…

end.

【答案】

运行到(1) 时的运行栈：（静态链）

15

c

14

0(形参个数)

13

5

12

返回地址

11

5

10

p

9

k(形参)

8

1(形参个数)

7

0

6

返回地址

5

0

4

d

3

i

2

0

1

返回地址

* *

运行到(2) 时的运行栈：（静态链）

* *

0

0

15

B

A

Tr

【答案】

运行到(1) 时的运行栈：（Display表）

c

14

0(形参个数)

C

13

5

12

返回地址

11

A

5

10

p

9

k(形参)

Tr

8

1(形参个数)

7

0

6

返回地址

5

0

4

d

3

i

2

0

1

返回地址

0

0

运行到(2) 时的运行栈：（Display表）

20 c

19 13

B

18 5

17 0

16 0(形参个数)

15 10(全局display)

A

14 返回地址

13 5

12 p

11 5

主程序Tr

10 0

9 k(形参)

8 1(形参个数)

7 2(全局display)

6 返回地址

5 0

4 d

3 i

6. 有如下示

2 0(display)

源程序，并已

1 返回地址

刻，以过程为

0 0

中的变量进

* *

20 t

19 13

C

18 5

17 0

16 0(形参个数)

15 10(全局display)

A

14 返回地址

13 5

12 p

11 5

主程序Tr

10 0

9 k(形参)

8 1(形参个数)

7 2(全局display)

6 返回地址

5 0

4 d

3 i

意的Pascal

2 0(display)

知在运行时

1 返回地址

单位对程序

0 0

行动态存储

* *

分配。当运行主程序而调用过程语句X时，试分别给出以下时刻的运行栈的内容和

Display的内容。

(1) 已开始而尚未执行完毕标号为10的语句；

(2) 已开始而尚未执行完毕标号为11的语句；

Begin

……

10: Y;

……

11: Z;

……

end; {X}

Begin { main }

……

X (a, b);

……

end. { main }

program main;

VAR a, b, c: integer;

procedure X ( i, j: integer); {X}

VAR d, e: real;

procedure Y; {Y}

VAR f, g: real;

Begin

……

end; {Y}

procedure Z( k: integer); {Z}

VAR h, i, j: real;

Begin

……

end; {Z}

【答案】

(1) 运行到标号10时，运行栈的内容：

* *

(2) 运行到标号11时，运行栈的内容：

26 j

Z

25 i

24 h

23 16

22 6

21 0

X (a, b)

20 k

19 1(形参个数)

18 12(全局display)

17 返回地址

16 6

main

* *

24

23

22

21

20

19

18

17

16

15

14

13

12

11

10

9

8

7

6

5

4

g

f

16

6

0

0(形参个数)

12(全局display)

返回地址

6

e

d

main

6

0

j

i

2(形参个数)

2(全局display)

返回地址

0

c

b

X (a, b)

Y

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

e

d

6

0

j

i

2(形参个数)

2(全局display)

返回地址

0

c

b

a

0 (display)

返回地址

0

* *

3

2

1

0

a

0(display)

返回地址

0

* *

main → X(a,b) →Y

main → X(a,b) →Y →Z

第10章 优化

1. 试把以下程序划分为基本块并作出其程序流图。

real C

【答案】

A:=0

real C

B:=1

A:=0

L1: A:=A+B

if B

≧

C goto L2

B:=1

B:=B+1

goto L1

L1: A:=A+B

L2: write A

if B≧C goto L2

halt

B:=B+1

goto L1

L2: write A

halt

* *

2. 试把以下程序划分为基本块并作出其程序流图。

real A, B

F:=1

C:=A*A

D:=B*B

if C

E:=A*A

F:=F+1

E:=E+F

write E

halt

L1: E:=B*B

F:=F+2

E:=E+F

write E

if E>100 goto

L2

halt

L2: F:=F-1

【答案】

real A,B

F:=1

C:=A*A

D:=B*B

if C

E:=A*A L1: E:=B*B

F:=F+1 F:=F+2

E:=E+F E:=E+F

write E write E

halt if E>100 goto L2

L2: F:=F-1 halt

goto L1

* *

3. 试对以下基本块B1和B2：

B1: A:=B*C

B2: B:=3

D:=A+C

E:=A*C

G:=B*F

H:=A+C

I:=A*C

J:=H+I

K:=B*5

L:=K+J

M:=L

D:=B/C

E:=A+D

F:=2*E

G:=B*C

H:=G*G

F:=H*G

L:=F

M:=L

分别应用DAG对它们进行优化，并就以下两种情况分别写出优化后的四元式序列：

(1) 假设只有G,L,M在基本块后面还要被引用；

(2) 假设只有L在基本块后面还要被引用。

* *

【答案】

B1基本块：(1)

G, L, M可用

(2)

L可用

(1) G:=B*C

(1) G:=B*C

(2) H:=G*G

(3) L:=H*G

(4) M:=L

B2基本块：(1)

G, L, M可用

(1) D:=A+C

(2) E:=A*C

(3) G:=3*F

(4) J:=D+E

(5) L:=15+J

(6) M:=L

(2) H:=G*G

(3) L:=H*G

(2)

L可用

(1) D:=A+C

(2) E:=A*C

(3) J:=D+E

(4) L:=15+J

* *