《编译原理》西北工业大学第三版课后答案

/*计算并填写数组内情向量的C值*/

}

5.16 解：在此种情况下，可以通过使用堆栈，从左到右依次处理各下标表达式，

且每当处理完一个下标表达式Ei时，就将相应的推入堆栈，待全部下

标表达式处理完毕之后，再产生按从右到左累计VARPART的四元式序列。这需要

在有关的语义子程序中用一段循环程序来实现。属性翻译文法略。

5.17 解：

•

Condition→if (Expr)

{BackPatch($,NXQ);$$.Chain=$;}

•

Statement→Condition Statement

{$$.Chain=Merge($,$);}

•

CondStElse→Condition Statement ; else

{int q=NXQ;

GEN(j,0,0,0);

BackPatch($,NXQ);

$$.Chain=Merge($,q);}

•

Statement→CondStElse Statement ;

{$$.Chain=Merge($,$);}

第六章 符 号 表

6.1在通常的程序设计语言中，都设置了诸如SIN，COS，LOG等标准函数，而

且这些函数无须定义即可引用，因此，可将这些标准函数名事先放在编译程

序的符号表区。试问：对于一种有嵌套分程序结构的程序设计语言的编译程

序而言，可采用何种方式来存放这些标准函数名。

6.2设有PASCAL程序：

PROGRAM ex62;

VAR a,b,c,d,e:real;

PROCEDURE a;

VAR c,e,f,g:real;

PROCEDURE b;

VAR e, d:integer;

PROCEDURE c;

VAR h:real;

f:ARRAY[1··10] OF integer;

BEGIN

…

END;

BEGIN

…

c;

…

END;

BEGIN;

…

END;

BEGIN

…

END.

试给出编译程序对此程序建立过程表及符号表的过程。

6.3在一个多遍扫描的FORTRAN语言编译程序中，对源程序中的一个程序段

而言，当一遍扫描结束时，一般都应将它的局部名表送入外存(当内存容量较

大时，也可送至内存的其它地方)保存起来，而当下一遍扫描开始时，又需要

将上一遍扫描所保存的该程序段的局部名表的内容再传送至编译程序的局部

名表区。试设计一种方案，用以正确地实现上述局部名表的传出和调进。

第二章 习题解答

1．答：对于有嵌套分程序结构的程序设计语言的编译程序而言，可将sin、cos

等标准函数的名字视为最外层分程序定义的全局变量名，这样对其的任何引用均

可在最外层符号表中找到其相关信息。另一种解决方案是，在文法定义中就将其

定义为一类特殊（类似于关键字）的终结符，并为其定义专门的调用标准函数的

文法，这样在词法分析阶段就可区分出它与其它标识符的不同。

2．解：（1）当扫描到PROCEDURE a时，符号表如图6-1：

（2）当扫描到PROCEDURE b所在行时，符号表如图6-2。

（3）当扫描到PROCEDURE c所在行时，符号表如图6-3。

（4）当扫描到PROCEDURE c的begin语句时，符号表如图6-4。

（5）当扫描到PROCEDURE b的begin语句时，符号表如图6-5。

（6）

当扫

描到

PROCE

DURE

A的begin语句时，符号表如图6-6。

（7）当扫描到PROGRAM ex62的begin语句时，符号表如图6-7。

（8）因主程序外层再无其它程序，所以，主程序的变量在符号表中的位置不必

再挪动。也就是说，图`6-7即为最终符号表的状态。

3．略

第七章 运行时的存储组织与分配

7.1设有由5个程序段所组成的FORTRAN程序，各程序段间的相互调用关系如

下面的有向图所示。题图71试按程序71所示的算法为此程序的各程序段划

定局部数据区。

7.2设F(X，Y)是一个FORTRAN函数过程，试写出过程调用

F(F(A+B，C)+D，E)的中间代码。

7.3设临时变量Ti的作用域为(Fi,Li)，其中，Fi是对Ti首次赋值的四元式

的编号，Li是最末一次引用Ti的四元式的编号，试设计一种为临时变量分

配存储单元的算法，使得所占用的存储单元最少(假定各临时变量是按它们第

1次被赋值的顺序来分配的，即假定，若i

7.4对于以整数或整型简单变量为运算对象的简单算术表达式，试给出一个

算法，用以确定为计算这种表达式所需临时单元的最小数。假定不允许用代

数运算规则来改变表达式的计值顺序(例如：为计算A+B*C，需一个临时单元

存放B*C之值；为计算(A+B)*(C+D)+E，需用两个单元，一个用来存放C+D之

值，另一个则既用来存放A+B，也用来存放(A+B)*(C+D)之值)。

7.5设有PASCAL程序：

program ex75

var a,b,c:integer;

L1: procedure p1(var z:integer);

var a,x,y:integer;

b:array[1··5,1··10] of real;

function f(var t:integer):boolean;

var x:integer;

L2: begin

x∶=a+t;

f∶=x+2

end;

begin

…

L3: …f(y)…

…

end;

L4: procedure p2(var y: integer);

var x,z:real;

begin

…

L5: pl(x)

…

end;

begin

…

L6:p2(a)

…

L7: end.

试用图示法说明，在程序执行过程中，当控制到达各标号处时数据空间

栈的存储分配情况。

7.6对下面的PASCAL程序：

program ex76;

var k:real;

function f(n:integer):real;

begin

if n=0 then f∶=1

else f∶=n*f(n-1)

end;

begin

k∶=f(10);

write(k)

end.

试指出：当递归调用函数f(n)时，在第二次进入f之后，数据空间栈所

存放的内容是什么?

7.7试设计一种PASCAL编译器的动态存储分配方案，它给每一分程序和过程

都分配一个数据区，且每一数据区都必须保存有它的外围分程序和外围过程

当前数据区的首地址。

第七章 习题解答

7．1设有由五个程序段组成的FORTRAN程序，各程序段间的的相互调用关系如下

图所示。试为此程序的各程序段合理地分配局部数据区。

解：假定数据区从1号单元开始分配，则名程序段所占单元情况为：

5：1~84：1~12

2：9~233：13~22

1：24~44

整个程序占用单元数为 44

7．2 解：（提示）一般来说，FORTRAN语言不允许递归调用，但嵌套调用是允

许的。其产生中间代码的方式与其它语言别无二致。

7．3解：设每个变量均占用一个单元，临时变量的个数≤m。定义一个数组a[m]

记录每个临时变量（按出现顺序编号命名）分配单元的地址（≤n≤m，按1、2、

3…编号），初值均为0。用另一数组T[n]标记每个单元被使用的最后期限，初

值为0。引入全局变量LAST记录当前被使用的最后一个单元的地址，初值为1。

令i=1；

•

取出有序对（Fi，Li）；

•

令j=1;

•

若(T[j]

•

则令: T[j]= Li;a[i]=j; 即将第j单元分配给变量i,T[j]中存放i的失效时间

Li。转7）；

否则，j++;

j≤LAST，转4);

•

为变量i分配单元：令T[LAST]= Li;a[i]=LAST; LAST++;

•

i++; 若i≤m,转2);否则，终止。

•

7．4解：假定在运算过程中每个临时变量的值只使用一次，即当其被用作运算

对象后便成为无用量。则可按下述方法计算临时变量的使用个数：

引入变量int TmpVarNum记录所求临时单元的最小个数，当表达式计算到

当前位置时占用的临时单元数用int CurTmpVarNum记录，初始值都是0；

•

在处理表达式过程中，目前正在运算的两个对象有以下三种情况：

•

①若两个运算对象均是用户定义的变量或常数，则必须引入临时变量存放运算结

果：

CurTmpVarNum++；

if(CurTmpVarNum>TmpVarNum)TmpVarNum= CurTmpVarNum;

②若两个运算对象均为临时变量，则只需用其中之一存放运算结果，另一临时变

量可释放之：CurTmpVarNum--;

③若运算对象之一为临时变量，则只需用该临时变量存放运算结果即可，使用临

时变量的个数不变。

5．解：为便于描述，我们用过程名代表其相应的活动记录，并视主程序ex75

亦为一过程（0层）。则程序运行至各标号处的运行栈情况如下：

1）运行至L6处：

ex75

2)运行至L4处：

ex75

•

p2

运行至L5处与至L4处相同；

•

运行至L1处：

ex75

•

P2 P1

运行至L3处与至L5处相同；

•

运行至L2处：

ex75

•

P2 P1 F

从函数F返回时：

P2 P1 ex75

8）从P1返回时：

ex75 P2

9）从P2返回时直至L7处时：

ex75

6．解：与上题描述方法相同：

•

调用f(10)后，栈内容为：

f(10) ex76

2) 在函数f()内，又一次调用了函数f自身（即第二次进入f）：

ex76 f(10) f(9)

7.略

第八章 代码优化

8.1设有如下的三地址码(四元式)序列：

readN

I∶=N

J∶=2

L1：if I≤J goto L3

L2：I∶=I-J

if I>J goto L2

if I=0 goto L4

J∶=J+1

I∶=N

goto L1

L3：Print ′YES′

halt

L4：Print ′NO′

halt

试将它划分为基本块，并作控制流程图。

8.2设已给如下的PASCAL程序：

program Cancelfactors (input, putput);

var numerator, denominator： integer;

prcedure lowterm (var num, den： integer);

var numcopy, dencopy, remainder： integer;

begin

numcopy∶=num;

dencopy∶=den;

while dencopy<>0 do

begin

remainder∶=numcopy mod dencopy;

numcopy∶=dencopy;

dencopy∶=remainder

end; {while}

if numcopy>1 then

begin

num∶=num div numcopy;

den∶=den div numcopy

end

end; {lowterm}

begin {cancelfactors}

read (numerator, denominator);

lowterm (numerator, denominator);

writern (numerator, denominator)

end. {cancelfactors}

(1) 试写出上述程序相应的四元式序列；

(2) 将所得的四元式序列划分为基本块，并作出控制流程图。

8.3考虑如下计算两矩阵乘积的程序：

begin

for i∶=1 to n do

for j∶=1 to n do

C[i,j]∶=0;

for i∶=1 to n do

for j∶=1 to n do

for k∶=1 to n do

C[i,j]∶=C[i,j]+A[i,k]*B[k,j]

end;

(1) 假定数组A，B和C均按静态分配其存储单元，对上述程序写出三地址(四

元式)代码序列；

(2) 将所得的三地址码序列划分为基本块，并画出相应的控制流程图。

8.4考虑如下的基本块：

D∶=B*C

E∶=A+B

B∶=B*C

A∶=E+D

(1) 构造相应的DAG；

(2) 对于所得的DAG，重建基本块，以得到更有效的四元式序列。

8.5对于如下的两个基本块：

(1)A∶=B*C(2)B∶=3

D∶=B/CD∶=A+C

E∶=A+DE∶=A*C

F∶=2*EF∶=E+D

G∶=B*CG∶=B*F

H∶=G*GH∶=A+C

F∶=H*GI∶=A*C

L∶=FJ∶=H+I

M∶=LK∶=B*5

L∶=K+J

M∶=L

分别构造相应的DAG，并根据所得的DAG重建经优化后的四元式序列。在进行

优化时，须分别考虑如下两种情况：

(1) 变量G，L，M在基本块出口之后活跃；

(2) 仅变量L在基本块出口之后活跃。

8.6对于题图86所示的控制流程图：

(1) 分别求出它们各个结点的必经结点集；

(2) 分别求出它们的各个回边；

(3) 找出各流程图的全部循环。

8.7对于如下的程序：

(一)I∶=1

J∶=0

L1：J∶=J+1

readI

if I<100 go to L2

write J

halt

L2：I∶=I*I

goto L1

(二)N∶=0

L1：I∶=2

L2：if I

write N

L3：N∶=N+1

goto L1

L4：J∶=N MOD I

if J=0 goto L3

I∶=I+1

goto L2

分别画出控制流程图，并分别对各基本块B计算：

(1) 能到达基本块B入口之前的各变量诸定值点的集合IN[B]；

(2) 基本块B中各变量引用点的ud链；

(3) 在基本块出口之后活跃的变量集OUTL[B]；

(4) 基本块B中各变量定值点的du链。

(a)(b)(c)

题图86

8.8对于如下的循环

for I∶=1tondo

A[I,J]∶=A[I,J]+A[J,I]

(1) 写出相应的四元式序列(假定数组A各维下标的下界为1，上界分别是d1

和d2)，作出控制流程图；

(2) 进行循环不变量外提；

(3) 进行运算强度的削弱。

8.9

I∶=1

read J, K

L∶A∶=K*I

B∶=J*I

C∶=A*B

write C

I∶=I+1

if I<100 go to L

halt

试对其中的循环进行可能的优化。

8.10设以下的程序片段是某一程序的最内层循环，试对它进行优化。

A∶=0

I∶=1

L1：B∶=J+1

C∶=B+I

A∶=C+A

if I=100 go to L2

I∶=I+1

go to L1

L2：

8.11对于习题8.3所得的控制流程图，进行各种循环优化。

8.12设有如下的程序片段：

I∶=1;

J∶=1;

K∶=1;

L1：if I>N go to L2;

if J>N go to L3;

if A[I]≤B[J] go to L3;

L2：C[K] ∶=B[J];

J∶=J+1;

go to L4;

L3：C[K]∶=A[I];

I∶=I+1;

L4：K∶=K+1;

if K≤2*N go to L1;

…

其中，A和B为具有N个元素的一维数组，C为具有2N个元素的一维数组，它

们都在数据空间栈中得到存储分配，而整型变量N，I，J，K则采用静态存储

分配。试对上述程序段，写出相应的四元式序列，将这些四元式划分为基本

块，画出控制流程图，找出其中的循环，并对所找到的循环进行各种可能的

优化。

8.13对于如下利用筛法求从2到给定整数N间的素数个数的程序片段：

begin

read N;

for i∶=2 to N do

A[i]∶=true;

COUNT∶=0;

for i∶=2 to N** 0.5 do

if A[i] then

begin

COUNT∶=COUNT+1;

for j∶=2*i to N by i do

A[j]∶=false

end;

Print COUNT

end.

(1) 将上述程序翻译为四元式序列(假定数组A按静态分配其存储空间)；

(2) 画出控制流程图；

(3) 对流程图中的每一结点n，求出必经结点集D(n)；

(4) 找出回边及循环；

(5) 进行不变运算外提；

(6) 削弱循环中的运算强度；

(7) 消除归纳变量。

上 机 实 习 题

(一) 试编写和调试一个程序，它把由四元式序列表示的基本块改造为相应的

DAG，并在构造DAG的过程中，进行合并已知量、删除无用赋值及消去公共子

表达式等局部优化处理，最后再从所得到的DAG出发，按原来生成DAG各个

结点的顺序重建四元式序列形式的基本块。

要求和提示：

(1) 假定基本块中仅含有如表81所示的三种四元式形式；

(2) 由基本块构造DAG的步骤见算法82。

(二) 利用C语言编写并调试一个解“到达定值”数据流方程的程序。

要求和提示：

(1) 程序的输入为一控制流程图，其中各基本块的KILL集和GEN集均已求出；

(2) 求解到达定值数据流方程的算法见程序81；

(3) 程序的输出为各基本块的IN集和OUT集。

第八章 习题解答

8.1 解：划分情况及控制流程如下图：

8.2 解：四元式序列如下（省略临时变量使用及形实结合代码）：

goto prog

lowterm: numcopy:=num

dencopy:=den

loop: if dencopt<>0 goto L1

goto L2

L1: remainder:=numcopy mod dencopy

numcopy:=dencopy

dencopy:=remainder

goto loop

L2: if numcopy>1 goto L3

goto L4

L3: num:=num div numcopy

den:=den div numcopy

L4: return

prog: input numerator

input denominator

par numerator

par denominator

call lowterm

output nmerator

output denominator

8.3解：四元式序列为：

i:=1

goto CHECKi

LOOPi: i:=i+1

CHECKi: if i<=n goto L1

goto OUTi

L1: j:=1

goto CHECKj

LOOPj: j:=j+1

CHECKj: if j<=n goto L2

goto OUTj

L2: T1:=i-1

t1:=T1*n

T1:=T1+j

T2:=addr(C)

T1[T2]:=0

goto LOOPj

OUTj: goto LOOPi

OUTi: i:=1

goto CHKi

LPi: i:=i+1

CHKi: if i<=n goto L3

goto OTi

L3: j:=1

goto CHKj

LPj: j:=j+1

CHKj: if j<=n goto L4

goto OTj

L4: k:=1

goto CHKk

LPk: k:=k+1

LLk: if k<=n goto L5

goto OTk

L5: T1:=i-1

T1:=T1*n

T1:=T1+j

T2:=addr(C)

T3:=i-1

T3:=T3*n

T3:=T3+j

T4:=addr(C)

TT1:=T3[T4]

T5:=i-1

T5:=T5*n

T5:=T5+k

T6:=addr(A)

TT2:=T5[T6]

T7:=k-1

T7:=T7*n

T7:=T7+j

T8:=addr(B)

TT3:=T7[T8]

T9:=TT2*TT3

T10:=TT1+TT2

T1[T2]:=T10

goto LPk

OTk: goto LPj

OTj: goto LPi

OTi: halt

基本块划分与流程图略

8.4 解：DAG图见右，优化后的代码为

D:=B*C

E:=A+B

B:=D

A:=E+D

8.5 解：

（1）DAG图见下图。

化后的代码为：

若只有G、L、M在出口之后活跃，则优

G:=B*C

H:=G*G

L:=H*G

M:=L

若只有L在出口之后活跃，则代码为

G:=B*C

H:=G*G

L:=H*G

（2）DAG见右图。若只有G、L、M活跃，则代码为

D:=A+C

E:=A*C

F:=D+E

G:=3+F

L:=F+15

M:=L

若只有L活跃，则代码为

D:=A+C

E:=A*C

F:=D+E

L:=F+15

8．6解：(a)必经结点集：D2={2}D3={2,3}， D4={2,4}D5={2,4,5}

D6={2,4,6}D7={2,4,7}D8={2,4,7,8}

回边及相应循环：7→4：{4,5,6,7}

8→2：{2,3,4,5,6,7,8}

(b) 必经结点集：D1={1}D2={1,2}D3={1,2,3}D4={1,2,3,4}D5={1,2,3,5}

D6={1,2,3,6}D7={1,2,7}D8={1,2,7,8}

回边及相应循环：7→2：{2,3,4,5,6,7}

(c) 必经结点集：D1={1}, D2={1,2}, D3={1,2,3}, D4={1,2,4}, D5=1,2,5},

D6={1,2,3,6}, D7={1,2,7}

回边及相应循环：5→2：{2，3，4，5}

6→6： {6}

注意：5→4不是回边。因为4不是5的控制结点。

8.7 略

8.8 解

（1）四元式序列：

I:=1

goto CHECK

LOOP: I:=I+1

CHECK: if I<=n goto L

goto OUT

L: T1:=I-1

T1:=T1*n

T1:=T1+J

T2:=addr(A)

T3:=I-1

T3:=T3*n

T3:=T3+J

T4:=addr(A)

T5:=T3[T4]

T6:=J-1

T6:=T6*n

T6:=T6+I

T7:=addr(A)

T8:=T6[T7]

T9:=T7+T8

T1[T2]:=T9

goto LOOP

OUT: halt

（2）无循环不变量；

（3）优化后代码：

I:=1

goto CHECK

LOOP: I:=I+1

CHECK: if I<=n goto L

goto OUT

L: T1:=I-1

T1:=T1*n

T1:=T1+J

T2:=addr(A)

T3:=T1[T2]

T6:=J-1

T6:=T6*n

T6:=T6+I

T6:=T6[T2]

T3:=T3+T8

T1[T2]:=T3

goto LOOP

OUT: halt

8.9 优化后的代码为

read J,K

A:=0

B:=0

I:=100*K

L: A:=A+K

B:=B+J

C:=A*B

write C

if A

halt

10.~13略

第八章 代码优化

8.1设有如下的三地址码(四元式)序列：

readN

I∶=N

J∶=2

L1：if I≤J goto L3

L2：I∶=I-J

if I>J goto L2

if I=0 goto L4

J∶=J+1

I∶=N

goto L1

L3：Print ′YES′

halt

L4：Print ′NO′

halt

试将它划分为基本块，并作控制流程图。

8.2设已给如下的PASCAL程序：

program Cancelfactors (input, putput);

var numerator, denominator： integer;

prcedure lowterm (var num, den： integer);

var numcopy, dencopy, remainder： integer;

begin

numcopy∶=num;

dencopy∶=den;

while dencopy<>0 do

begin

remainder∶=numcopy mod dencopy;

numcopy∶=dencopy;

dencopy∶=remainder

end; {while}

if numcopy>1 then

begin

num∶=num div numcopy;

den∶=den div numcopy

end

end; {lowterm}

begin {cancelfactors}

read (numerator, denominator);

lowterm (numerator, denominator);

writern (numerator, denominator)

end. {cancelfactors}

(1) 试写出上述程序相应的四元式序列；

(2) 将所得的四元式序列划分为基本块，并作出控制流程图。

8.3考虑如下计算两矩阵乘积的程序：

begin

for i∶=1 to n do

for j∶=1 to n do

C[i,j]∶=0;

for i∶=1 to n do

for j∶=1 to n do

for k∶=1 to n do

C[i,j]∶=C[i,j]+A[i,k]*B[k,j]

end;

(1) 假定数组A，B和C均按静态分配其存储单元，对上述程序写出三地址(四

元式)代码序列；

(2) 将所得的三地址码序列划分为基本块，并画出相应的控制流程图。

8.4考虑如下的基本块：

D∶=B*C

E∶=A+B

B∶=B*C

A∶=E+D

(1) 构造相应的DAG；

(2) 对于所得的DAG，重建基本块，以得到更有效的四元式序列。

8.5对于如下的两个基本块：

(1)A∶=B*C(2)B∶=3

D∶=B/CD∶=A+C

E∶=A+DE∶=A*C

F∶=2*EF∶=E+D

G∶=B*CG∶=B*F

H∶=G*GH∶=A+C

F∶=H*GI∶=A*C

L∶=FJ∶=H+I

M∶=LK∶=B*5

L∶=K+J

M∶=L

分别构造相应的DAG，并根据所得的DAG重建经优化后的四元式序列。在进行

优化时，须分别考虑如下两种情况：

(1) 变量G，L，M在基本块出口之后活跃；

(2) 仅变量L在基本块出口之后活跃。

8.6对于题图86所示的控制流程图：

(1) 分别求出它们各个结点的必经结点集；

(2) 分别求出它们的各个回边；

(3) 找出各流程图的全部循环。

8.7对于如下的程序：

(一)I∶=1

J∶=0

L1：J∶=J+1

readI

if I<100 go to L2

write J

halt

L2：I∶=I*I

goto L1

(二)N∶=0

L1：I∶=2

L2：if I

write N

L3：N∶=N+1

goto L1

L4：J∶=N MOD I

if J=0 goto L3

I∶=I+1

goto L2

分别画出控制流程图，并分别对各基本块B计算：

(1) 能到达基本块B入口之前的各变量诸定值点的集合IN[B]；

(2) 基本块B中各变量引用点的ud链；

(3) 在基本块出口之后活跃的变量集OUTL[B]；

(4) 基本块B中各变量定值点的du链。

(a)(b)(c)

题图86

8.8对于如下的循环

for I∶=1tondo

A[I,J]∶=A[I,J]+A[J,I]

(1) 写出相应的四元式序列(假定数组A各维下标的下界为1，上界分别是d1

和d2)，作出控制流程图；

(2) 进行循环不变量外提；

(3) 进行运算强度的削弱。

8.9

I∶=1

read J, K

L∶A∶=K*I

B∶=J*I

C∶=A*B

write C

I∶=I+1

if I<100 go to L

halt

试对其中的循环进行可能的优化。

8.10设以下的程序片段是某一程序的最内层循环，试对它进行优化。

A∶=0

I∶=1

L1：B∶=J+1

C∶=B+I

A∶=C+A

if I=100 go to L2

I∶=I+1

go to L1

L2：

8.11对于习题8.3所得的控制流程图，进行各种循环优化。

8.12设有如下的程序片段：

I∶=1;

J∶=1;

K∶=1;

L1：if I>N go to L2;

if J>N go to L3;

if A[I]≤B[J] go to L3;

L2：C[K] ∶=B[J];

J∶=J+1;

go to L4;

L3：C[K]∶=A[I];

I∶=I+1;

L4：K∶=K+1;

if K≤2*N go to L1;

…

其中，A和B为具有N个元素的一维数组，C为具有2N个元素的一维数组，它

们都在数据空间栈中得到存储分配，而整型变量N，I，J，K则采用静态存储

分配。试对上述程序段，写出相应的四元式序列，将这些四元式划分为基本

块，画出控制流程图，找出其中的循环，并对所找到的循环进行各种可能的

优化。

8.13对于如下利用筛法求从2到给定整数N间的素数个数的程序片段：

begin

read N;

for i∶=2 to N do

A[i]∶=true;

COUNT∶=0;

for i∶=2 to N** 0.5 do

if A[i] then

begin

COUNT∶=COUNT+1;

for j∶=2*i to N by i do

A[j]∶=false

end;

Print COUNT

end.

(1) 将上述程序翻译为四元式序列(假定数组A按静态分配其存储空间)；

(2) 画出控制流程图；

(3) 对流程图中的每一结点n，求出必经结点集D(n)；

(4) 找出回边及循环；

(5) 进行不变运算外提；

(6) 削弱循环中的运算强度；

(7) 消除归纳变量。

上 机 实 习 题

(一) 试编写和调试一个程序，它把由四元式序列表示的基本块改造为相应的

DAG，并在构造DAG的过程中，进行合并已知量、删除无用赋值及消去公共子

表达式等局部优化处理，最后再从所得到的DAG出发，按原来生成DAG各个

结点的顺序重建四元式序列形式的基本块。

要求和提示：

(1) 假定基本块中仅含有如表81所示的三种四元式形式；

(2) 由基本块构造DAG的步骤见算法82。

(二) 利用C语言编写并调试一个解“到达定值”数据流方程的程序。

要求和提示：

(1) 程序的输入为一控制流程图，其中各基本块的KILL集和GEN集均已求出；

(2) 求解到达定值数据流方程的算法见程序81；

(3) 程序的输出为各基本块的IN集和OUT集。

第八章 习题解答

8.1 解：划分情况及控制流程如下图：

8.2 解：四元式序列如下（省略临时变量使用及形实结合代码）：

goto prog

lowterm: numcopy:=num

dencopy:=den

loop: if dencopt<>0 goto L1

goto L2

L1: remainder:=numcopy mod dencopy

numcopy:=dencopy

dencopy:=remainder

goto loop

L2: if numcopy>1 goto L3

goto L4

L3: num:=num div numcopy

den:=den div numcopy

L4: return

prog: input numerator

input denominator

par numerator

par denominator

call lowterm

output nmerator

output denominator

8.3解：四元式序列为：

i:=1

goto CHECKi

LOOPi: i:=i+1

CHECKi: if i<=n goto L1

goto OUTi

L1: j:=1

goto CHECKj

LOOPj: j:=j+1

CHECKj: if j<=n goto L2

goto OUTj

L2: T1:=i-1

t1:=T1*n

T1:=T1+j

T2:=addr(C)

T1[T2]:=0

goto LOOPj

OUTj: goto LOOPi

OUTi: i:=1

goto CHKi

LPi: i:=i+1

CHKi: if i<=n goto L3

goto OTi

L3: j:=1

goto CHKj

LPj: j:=j+1

CHKj: if j<=n goto L4

goto OTj

L4: k:=1

goto CHKk

LPk: k:=k+1

LLk: if k<=n goto L5

goto OTk

L5: T1:=i-1

T1:=T1*n

T1:=T1+j

T2:=addr(C)

T3:=i-1

T3:=T3*n

T3:=T3+j

T4:=addr(C)

TT1:=T3[T4]

T5:=i-1

T5:=T5*n

T5:=T5+k

T6:=addr(A)

TT2:=T5[T6]

T7:=k-1

T7:=T7*n

T7:=T7+j

T8:=addr(B)

TT3:=T7[T8]

T9:=TT2*TT3

T10:=TT1+TT2

T1[T2]:=T10

goto LPk

OTk: goto LPj

OTj: goto LPi

OTi: halt

基本块划分与流程图略

8.4 解：DAG图见右，优化后的代码为

D:=B*C

E:=A+B

B:=D

A:=E+D

8.5 解：

（1）DAG图见下图。

化后的代码为：

若只有G、L、M在出口之后活跃，则优

G:=B*C

H:=G*G

L:=H*G

M:=L

若只有L在出口之后活跃，则代码为

G:=B*C

H:=G*G

L:=H*G

（2）DAG见右图。若只有G、L、M活跃，则代码为

D:=A+C

E:=A*C

F:=D+E

G:=3+F

L:=F+15

M:=L

若只有L活跃，则代码为

D:=A+C

E:=A*C

F:=D+E

L:=F+15

8．6解：(a)必经结点集：D2={2}D3={2,3}， D4={2,4}D5={2,4,5}

D6={2,4,6}D7={2,4,7}D8={2,4,7,8}

回边及相应循环：7→4：{4,5,6,7}

8→2：{2,3,4,5,6,7,8}

(b) 必经结点集：D1={1}D2={1,2}D3={1,2,3}D4={1,2,3,4}D5={1,2,3,5}

D6={1,2,3,6}D7={1,2,7}D8={1,2,7,8}

回边及相应循环：7→2：{2,3,4,5,6,7}

(c) 必经结点集：D1={1}, D2={1,2}, D3={1,2,3}, D4={1,2,4}, D5=1,2,5},

D6={1,2,3,6}, D7={1,2,7}

回边及相应循环：5→2：{2，3，4，5}

6→6： {6}

注意：5→4不是回边。因为4不是5的控制结点。

8.7 略

8.8 解

（1）四元式序列：

I:=1

goto CHECK

LOOP: I:=I+1

CHECK: if I<=n goto L

goto OUT

L: T1:=I-1

T1:=T1*n

T1:=T1+J

T2:=addr(A)

T3:=I-1

T3:=T3*n

T3:=T3+J

T4:=addr(A)

T5:=T3[T4]

T6:=J-1

T6:=T6*n

T6:=T6+I

T7:=addr(A)

T8:=T6[T7]

T9:=T7+T8

T1[T2]:=T9

goto LOOP

OUT: halt

（2）无循环不变量；

（3）优化后代码：

I:=1

goto CHECK

LOOP: I:=I+1

CHECK: if I<=n goto L

goto OUT

L: T1:=I-1

T1:=T1*n

T1:=T1+J

T2:=addr(A)

T3:=T1[T2]

T6:=J-1

T6:=T6*n

T6:=T6+I

T6:=T6[T2]

T3:=T3+T8

T1[T2]:=T3

goto LOOP

OUT: halt

8.9 优化后的代码为

read J,K

A:=0

B:=0

I:=100*K

L: A:=A+K

B:=B+J

C:=A*B

write C

if A

halt

10.~13略