《编译原理》(陈火旺版)课后作业参考问题详解ch6-10

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

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

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

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

0.125。

【答案】

产生式

S→L

1

. L

2

S→L

L→L

1

B

L→B

B→0

B→1

语义规则

{ := L

1

.val + L

2

.val*2

{ := }

{ :=L

1

.val*2+;

L. length:= L

1

.length +1 }

{ :=;

L. length:= 1 }

{ := 0 }

{ :=1 }

－

S→L.L∣L

L→LB∣B

B→0∣1

}

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

L→ id L

L→, id L∣:T

T→ integer∣real

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

【答案】

产生式

L→ id L

1

L→, id L

1

L→ :T

T→ integer

T→ real

语义规则

{ := L

1

.val + L

2

.val*2

{ := }

{ :=L

1

.val*2+;

L. length:= L

1

.length +1 }

{ :=;

L. length:= 1 }

{ := 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)

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

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

then (a+b)↑c

else a↑b↑c

ab-c+*

abcde/+*+

a-bc-d+*+

A not C D not or not or

A B and C not D or or

A B or C D not E and or and

if xy+z*0=

then ab+c↑

else ab↑c↑

后缀式

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

【答案】

四元式

三元式

间接三元式

(1) + a b T1

(1) + a b

(1) + a b

(2) －

(3)

(4)

(5)

(6)

(7)

+

*

+

+

－

(1)

c

(2)

a

(5)

(4)

／

d

(3)

b

c

(6)

(2) －

(3)

(4)

(5)

(6)

(7)

(2) － (1) ／

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

T1 ／ T2

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

出所产生的三地址代码。

【答案】

四元式

(1)

(2)

(3)

(4)

uminus

+

*

:=

c

T1

B

T3

／

D

T2

／

T1

T2

T3

A

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

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

【答案】

中间代码

中间代码

(1) T

1

:=i*N

A2

(13) T

10

:=W

A

*T

8

(2) T

1

:=T

1

+j (14) T

11

:=T

9

[T

10

]

(3) T

2

:=A-C

A

(15) T

12

:=C-C

c

(4) T

3

:=W

A

*T

1

(16) T

13

:=W

c

*T

11

(5) T

4

:=i* N

B2

(17) T

14

:=T

12

[T

13

]

(6) T

4

:=T

4

+j (18) T

15

:=T

7

+ T

14

(7) T

5

:=B-C

B

(19) T

16

:=i+j

(8) T

6

:=W

B

*T

4

(20) T

17

:=d-C

d

(9) T

7

:=T

5

[T

6

] (21) T

18

:=W

d

*T

16

(10) T

8

:=k* N

A2

(22) T

19

:=T

17

[T

18

]

(11) T

8

:=T

8

+l (23) T

20

:=T

15

+ T

19

(12) T

9

:=A-C

A

(24) T

2

[T

3

]:=T

20

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

【答案】

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

四元式

(1)

(2)

(3)

(4)

or

not

and

or

C

T

1

B

A

D

／

T

2

T

3

T

1

T

2

T

3

T

4

(1)

(2)

(3)

(4)

四元式

( jnz, A, -, 0 )

( j, -, -, (3))

(jnz, B, -, (5))

( j, -, -, 0 )

(5)

(6)

(7)

(8)

四元式

( jnz, C, -, (4))

( j, -, -, (7))

( jnz, D, -, (5))

( j, -, -, (1))

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

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

While A

if A=1 then C:=C+1

else while A≦D do

A:=A+2;

【答案】

四元式

四元式

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

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

( j, -, -, 0)

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

( j, -, -, 0 )

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

( j, -, -, (10) )

(+, C, 1, T

1

)

(:=,T

1

, -, C )

(9)

(10)

(11)

(12)

(13)

(14)

(15)

( j, -, -, (1))

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

( j, -, -, (1))

(+, A, 2, T

2

)

(:=,T

2

, -, A )

( j, -, -, (10))

( j, -, -, (1))

第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 4 17 11

9 0 16 0

8 n(形参) 15 n(形参)

F 第2次F

7 1(形参个数) 14 1(形参个数)

6 2(全局display) 13 9(全局display)

5 返回地址 12 返回地址

4 0 11 4

3 k 10 4

2 0(display) 9 0

主程序P

1 返回地址 n(

8

形参

)

第1次F

0 0 1(

7

形参个数

)

6 2(全局display)

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

11

0

5

4

3

2

1

0

返回地址

0

k

0(display)

返回地址

0

主程序P

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) 时的运行栈：（静态链） 运行到(2) 时的运行栈：（静态链）

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

c

0(形参个数)

5

返回地址

5

p

k(形参)

1(形参个数)

0

返回地址

0

d

i

0

返回地址

0

15

c

14

0(形参个数)

B

13

5

12

返回地址

11

5

10

p

9

k(形参)

8

1(形参个数)

A

7

0

6

返回地址

5

0

4

d

3

i

2

0

Tr

1

返回地址

0

0

C

A

Tr

【答案】

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

20 c 20 t

19 13 19 13

18 5 18 5

17 0 17 0

B C

16 0(形参个数) 16 0(形参个数)

15 10(全局display) 15 10(全局display)

14 返回地址 14 返回地址

13 5 13 5

12 p 12 p

11 5 11 5

10 0 10 0

9 k(形参) 9 k(形参)

A A

8 1(形参个数) 8 1(形参个数)

7

6

5

4

3

2

1

0

2(全局display)

返回地址

0

d

i

0(display)

返回地址

0

主程序Tr

7

6

5

4

3

2

1

0

2(全局display)

返回地址

0

d

i

0(display)

返回地址

0

主程序Tr

6. 有如下示意的Pascal源程序，并已知在运行时刻，以过程为单位对程序中的变量进行动

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

Display的容。

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

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

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}

Begin

……

10: Y;

……

11: Z;

……

end; {X}

Begin { main }

……

X (a, b);

……

end. { main }

【答案】

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

j

24 g

26

23 f

25 i

22 16

24 h

21 6

23 16

Z

Y

20 0

22 6

19 0(形参个数)

21 0

18 12(全局display)

20 k

17 返回地址

19 1(形参个数)

16 6

18 12(全局display)

15 e

17 返回地址

14 d

16 6

13 6

15 e

12 0

14 d

X (a, b)

11 j

13 6

X (a, b)

10 i

12 0

9 2(形参个数)

11 j

8 2(全局display)

10 i

7 返回地址

9 2(形参个数)

6 0

8 2(全局display)

5 c

7 返回地址

4 b

6 0

3 a

5 c

main

2 0(display)

main

4 b

1 返回地址

3 a

0 0

2 0 (display)

1 返回地址

0 0

main → X(a,b) →Y

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

第10章 优化

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

【答案】

real C

real C

A:=0

A:=0

B:=1

B:=1

L1: A:=A+B

if B≧C goto L2

B:=B+1

L1: A:=A+B

goto L1

if B≧C goto L2

L2: write A

halt

B:=B+1 L2: write A

goto L1 halt

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

【答案】

real A, B

F:=1

real A,B

C:=A*A F:=1

D:=B*B C:=A*A

if C

E:=A*A if C

F:=F+1

E:=E+F

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

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

L1: E:=B*B E:=E+F E:=E+F

F:=F+2 write E write E

E:=E+F halt if E>100 goto L2

write E

if E>100 goto

L2

L2: F:=F-1

halt

halt goto L1

L2: F:=F-1

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

B1: A:=B*C

D:=B/C

E:=A+D

F:=2*E

G:=B*C

H:=G*G

F:=H*G

L:=F

M:=L

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

分别应用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 (2) H:=G*G

(3) L:=H*G (3) L:=H*G

(4) M:=L

B2基本块：(1)

G, L, M可用

(2)

L可用

(1) D:=A+C (1) D:=A+C

(2) E:=A*C (2) E:=A*C

(3) G:=3*F (3) J:=D+E

(4) J:=D+E (4) L:=15+J

(5) L:=15+J

(6) M:=L