编译原理_平时作业(含答案)

1 对于下列语言分别写出它们的正规表达式。

(1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。 答： 令Letter表示除这五个元音外的其它字母。 ((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))*

(2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。 答： A*B*....Z*

(3) Σ={0,1}上的含偶数个1的所有串。 答： (0|10*1)*

(4) Σ={0,1}上的含奇数个1的所有串。 答：(0|10*1)*1

(5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。 答：设S是符合要求的串，|S|=2k+1 (k≥0）。 则 S→S10|S21，|S1|=2k (k>0），|S2|=2k (k≥0）。 且S1是{0,1}上的串，含有奇数个0和奇数个1。 S2是{0,1}上的串，含有偶数个0和偶数个1。 考虑有一个自动机M1接受S1，那么自动机M1如下：

和L(M1)等价的正规表达式，即S1为： ((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*

类似的考虑有一个自动机M2接受S2，那么自动机M2如下：

和L(M2)等价的正规表达式，即S2为： ((00|11)|(01|10)(00|11)*(01|10))* 因此，S为：

((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*0| ((00|11)|(01|10)(00|11)*(01|10))*1

(6) 不包含子串011的由0和1组成的符号串的全体。 答：1*|1*0(0|10)*(1|ε)

(7) 由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。 答： 假设w的自动机如下：

1 / 22

对应的正规表达式：(1(01*0)1|0)*

2 给出接受下列在字母表{0,1}上的语言的DFA。 (1) 所有以00结束的符号串的集合。 (2) 所有具有3个0的符号串的集合。 答：

(1) DFA M=({0，1}，{q0，q1，q2}，q0，{q2}，δ) 其中δ定义如下:

δ（q0，0）=q1 δ（q0，1）=q0 δ（q1，0）=q2 δ（q1，1）=q0 δ（q2，0）=q2 δ（q2，1）=q0

(2)正则表达式: 1*01*01*01*

DFA M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，δ) 其中δ定义如下:

δ（q0，0）=q1 δ（q0，1）=q0 δ（q1，0）=q2 δ（q1，1）=q1 δ（q2，0）=q3 δ（q2，1）=q2 δ（q3，1）=q3

3 下面是用正规式表示的变量声明：

( int | float ) id (, id )* ;

2 / 22

请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。

答：D  T L ; T  int | float

4 试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else (悬而未决的-else)文法的二义性：

stmt → if expr then stmt |matched-stmt

matched-stmt→ if expr then matched-stmt else stmt |other

试说明此文法仍然是二义性的。

答：考虑句子if e then if e then other else if e then other else other 它具有如下所示的两种分析树 stmt expr then e if stmt if matched-stmt expr then matched-stmt e other if esle stmt matched-stmt expr then matched-stmt e other esle stmt matched-stmt other stmt matched-stmt if expr then matched-stmt e if esle stmt esle stmt matched-stmt expr then e stmt other expr then matched-stmt e other if matched-stmt other 则上面给出的if-then-else文法仍是二义性的。

5 证明下面文法是SLR(1)文法，并构造其SLR分析表。 E→E+T|T T→TF|F F→F*|a|b

答：该文法的拓广文法G'为

(0) E' → E (2) E → T (4) T → F (6) F → a

(1) E → E+T (3) T → TF (5) F → F* (7) F → b

L  L, id | id

其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:

I0 = {E'→·E, E→·E+T, E→·T, T→·TF, T→·F, F→·F*, F→·a, F→·b} I1 = {E'→E·, E→E·+T}I2 = {E→T·, T→T·F, F→·F*, F→·a, F→·b} I3 = {T→F·, F→F·*} I4 = {F→a·} I5 = {F→b·}

I6 = {E→E+·T, T→·TF, T→·F, F→·F*, F→·a, F→·b} I7 = {T→TF·, F→F·*} I8 = {F→F*·} I9 = {E→E+T·, T→T·F, F→·F*, F→·a, F→·b}

求FOLLOW集： FOLLOW(E)={＋, ＄} FOLLOW(T)={＋, ＄, a, b} FOLLOW(F)={＋, ＄, a, b, *} 构造的SLR分析表如下：

3 / 22

显然，此分析表无多重定义入口，所以此文法是SLR文法。

6 为下面的文法构造LALR(1)分析表 S→E E→E+T|T T→(E)|a

答：其拓广文法G'：

(0) S' → S (2) E → E+T (4) T → (E)

(1) S → E (3) E → T (5) T → a

构造其LR(1)项目集规范族和goto函数(识别活前缀的DFA)如下:

I0 = {[S’→·S, $], [S→·E, $], [E→·E+T, $/+], [E→·T, $/+], [T→·(E), $/+], [T→·a, $/+]} I1 = {[S’→S·, $]} I2 = {[S→E·, $], [E→E·+T, $/+]} I3 = {[E→T·, $/+]} I4 = {[T→(·E), $/+], [E→·E+T, )/+], [E→·T, )/+], [T→·(E), )/+], [T→·a, )/+]} I5 = {[T→a·, $/+]} I6 = {[E→E+·T, $/+], [T→·(E), $/+], [T→·a, $/+]} I7 = {[T→(E·), $/+], [E→E·+T, )/+]} I8 = {[E→T·, )/+]}

I9 = {[T→(·E), )/+}, [E→·E+T, )/+], [E→·T, )/+], [T→·(E), )/+], [T→·a, )/+]} I10 = {[T→a·, )/+]} I11 = {[E→E+T·, $/+]} I12 = {[T→(E)·, $/+]}

I13 = {[E→E+·T, )/+], [T→·(E), )/+], [T→·a, )/+]} I14 = {[T→(E·), )/+], [E→E·+T, )/+]} I15 = {[E→E+T·, )/+]} I16 = {[T→(E)·, )/+]}

合并同心的LR(1)项目集，得到LALR的项目集和转移函数如下：

I0 = {[S’→·S, $], [S→·E, $], [E→·E+T, $/+], [E→·T, $/+], [T→··(E), $/+], [T→·a, $/+]}

I1 = {[S’→S·, $]} I2 = {[S→E·, $], [E→E·+T, $/+]} I3,8 = {[E→T·, $/+/)]}

I4,9 = {[T→(·E), $/+/)], [E→·E+T, )/+], [E→·T, )/+], [T→·(E), )/+], [T→·a, )/+]}

4 / 22

I5,10 = {[T→a·, $/+/)]} I6,13 = {[E→E+·T, $/+/)], [T→·(E), $/+/)], [T→·a, $/+/)]} I7,14 = {[T→(E·), $/+/)], [E→E·+T, )/+]} I11,15 = {[E→E+T·, $/+/)]} I12,16 = {[T→(E) ·, $/+/)]}

LALR分析表如下：

7 （1）通过构造识别活前缀的DFA和构造分析表，来证明文法E  E + id | id是SLR(1)文法。 答：先给出接受该文法活前缀的DFA如下：

E E id E  id· I2 E  + E  E +·id I3 id E  E + id· I4 再构造SLR分析表如下：

状态 0 1 s2 1 s3 acc 5 / 22

动作 转移 id + $ E 2 3 4

r2 r2 s4 r1 r1 表中没有多重定义的条目，因此该文法是SLR(1)的。 （2）下面左右两个文法都和（1）的文法等价

E  E + M id | id M  

E  M E + id | id

M  

请指出其中有几个文法不是LR(1)文法，并给出它们不是LR(1)文法的理由。 答：只有文法

E  M E + id | id M  

不是LR(1)文法。因为对于句子id+id+…+id来说，分析器在面临第一个id时需要做的空归约次数和句子中+id的个数一样多，而此时句子中+id的个数是未知的。 8

根据自上而下的语法分析方法，构造下面文法的LL（1）分析表。

D  TL T  int | real

L  id R R  , id R | 

答：先计算FIRST和FOLLOW FIRST(D) = FIRST(T) = {int,real} FIRST(L) = {id} FIRST(R) = {,,ε}

FOLLOW(D) = FOLLOW(L) = {$} FOLLOW(T) = {id} FOLLOW(R) = {$} LL(1)分析表如下： D T L R

9 下面的文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时，结果仍为整数，否则就是实数。 E→E+T|T T→num.num|num

（a）给出一个语法制导定义以确定每个子表达式的类型。

（b）扩充（a）中的语法制导定义把表达式翻译成前缀形式，并且决定类型。使用一元算符inttoreal把整型值转换成相等的实型值，以使得前缀形式中的+的两个操作对象是同类型的。 答： (a):

产生式 语义规则 6 / 22

int D -> TL T -> int real D -> TL T -> real id L -> idR , R -> ,idR $ R -> ε EE1+T IF (E1.type=integer) and (T.type=integer) THEN E.type:=integer ELSE E.type:=real ET Tnum.num Tnum (b):

产生式 EE1+T E.type:=T.type T.type:=real T.type:=integer 语义规则 IF (E1.type=integer) and (T.type=integer) THEN BEGIN E.type:=integer Print(‘+’,E1.val,T.val) END ELSE BEGIN E.type:=real IF E1.type=integer THEN Begin E1.type:=real E1.val:=inttoreal(E1.val) End IF T.type:=integer THEN Begin T.type:=real T.val:=inttoreal(T.val) End Print(‘+’,E1.val,T.val) END ET Tnum.num Tnum

10 假设说明是由下列文法产生的： D→id L L→,id L|:T T→integer |real

E.type:=T.type E.val:=T.val T.type:=real T.val:=num.num.lexval T.type:=integer T.val:=num.lexval （a）建立一个翻译模式，把每一个标识符的类型加入到符号表中。 （b）从（a）中的翻译模式构造一个预翻译程序。

答： (a)： 产生式 Did L

翻译模式 {D.Type:=L.Type} 7 / 22

{addtype(id.entry, D.type)} L,id L1 L:T Tinteger {L.Type:=L1.Type} {addtype(id.entry, L.type)} {L.type:=T.type} {T.type:=integer} Treal {T.type:=real} ： Procedure D; begin

If lookahead=id then Begin Match(id); D.type=L;

addtype(id.entry,D.type) end else error

end

Function L: DataType; Begin

If lookahead=’,’ then Begin

Match(‘,’); If lookahead=id then

begin

match(id);

L.Type=L;

addtype(id.entry,L.type); return(L.type) end Else error

End

Else if lookahead=’:’ then

Begin

Match(‘:’); L.Type=T; return(L.Type) end else

error

End

Function T: DataType; Begin

If lookahead=integer then Begin

8 / 22

(b)

Match(integer); return(integer) end

else If lookahead=real then

Begin Match(real); return(real) end else error

end

11 为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号（即值大于零还是小于零）记录在属性E.sign中（属性值分别用POS或NEG表示）。你可以假定所有的整数都不为零，这样就不用担心零的符号。

E  E *E | +E | E | unsigned_integer

答： E  E1 *E2{if E1.sign= E2.sign then E.sign := POS else E.sign := NEG }

E  +E1 { E.sign := E1.sign }

E  E1 {if E1.sign= POS then E.sign := NEG else E.sign := POS} E  unsigned_integer {E.sign := POS}

12 为下面文法写一个语法制导的定义，用S的综合属性val给出下面文法中S产生的二进制数的值。例如，输入101.101时，S. val := 5.625。（不得修改文法。）

S  L . R | L L  L B | B

R  B R | B B  0 | 1 S  L . R S  L L  B R  B B  0 B  1

L  L1 B R  B R1

S. val := L. val + R. val

S. val := L. val

L. val := L1. val 2 + B. val L. val := B. val R. val := B. val/2 B. val := 0 B. val := 1

答：

R. val := (R1. val + B. val)/2

13 试问下面的程序将有怎样的输出？分别假定： （a）传值调用（call-by-value）； （b）引用调用（call-by-reference）； （c）复制恢复（copy-restore）； （d）传名调用（call-by-name）。 program main(input,output）； procedure p（x,y,z）； begin y：＝y＋1； z：＝z＋x； end；

9 / 22

begin a：＝2； b：＝3； p(a＋b,a,a)； print a end.

答：1)．传地址：所谓传地址是指把实在参数的地址传递给相应的形式参数。在过程段中每

个形式参数都有一对应的单元，称为形式单元。形式单元将用来存放相应的实在参数的地址。 当调用一个过程时，调用段必须领先把实在参数的地址传递到一个为被调用段可以拿得到的 地方。当程序控制转入被调用段之后，被调用段首先把实参地址捎进自己相应的形式单元中，

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

2)．传结果：和“传地址”相似(但不等价)的另一种参数传递力法是所谓“传结果”。这种方法的实质是，每个形式参数对应有两个申元，第1个单元存放实参的地址，第2个单元

存放实参的值。在过程体中对形参的任何引用或赋值都看成是对它的第2个单元的直接访 问。但在过程工作完毕返回前必须把第2个单元的内容行放到第1个单元所指的那个实参单 元之中。

3)．传值：所谓传值，是一种简单的参数传递方法。调用段把实在参数的值计算出来并 存放在一个被调用段可以拿得到的地方。被调用段开始丁作时，首先把这些值抄入形式中元 中，然后就好像使用局部名一样使用这些形式单元。如果实在参数不为指示器，那末，在被 调用段中无法改变实参的值。

4)．传名：所谓传名，是一种特殊的形——实参数结合方式。解释“传名”参数的意义： 过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的形式

参数都替换成相应的实在参数(文字替换)。它与采用“传地址”或“传值”的方式所产生的结果均不相同。 (a)2； (b)8； (c)7；

14 对以下的Pascal程序画出过程c第二次被激活时的运行栈，控制链和访问链。说明在c中如何访问变量x。 program env；

procedure a； var x:integer； procedure b； procedure c；

begin x:=2；b end；{procedure c} begin c end；{procedure b} begin b end；{procedure a} begin a end. {main} 答：

control link env control link access link (d)9。

a control link access link x b 10 / 22

access link c control link access link b control link access link c control link access link 说明：c中沿着存取链向前走两步，到过程a的活动记录中就可以访问到变量x。

15 下面给出一个 C 语言程序及其在 SPARC/SUN 工作站上经某编译器编译后的运行结果。从运行结果看，函数 func中 4个局部变量 i1, j1, f1, e1的地址间隔和它们类型的大小是一致的，而 4个形式参数 i, j, f, e的地址间隔和它们的类型的大小不一致，试分析不一致的原因。注意，输出的数据是八进制的。 func (i, j, f, e) short i, j; float f, e; {

short i1, j1; float f1, e1;

printf( \"Address of i, j, f, e = %o, %o, %o, %o \\n\

printf( \"Address of i1, j1, f1, e1 = %o, %o, %o, %o \\n\ printf( \"Sizes of short, int, long, float, double = %d, %d, %d, %d, %d \\n\ sizeof(short), sizeof(int), sizeof(long), sizeof(float), sizeof(double) ); } main() {

short i, j; float f, e; func(i, j, f, e); }

运行结果是：

Address of i, j, f, e = 35777772536, 35777772542, 35777772544, 35777772554 Address of i1, j1, f1, e1 = 35777772426, 35777772424, 35777772420, 35777772414 Sizes of short, int, long, float, double = 2, 4, 4, 4, 8，请问为什么？

答：C语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的一致性。但是对于形式参数和实在参数是不同的整型（如一个是short型，另一个是long型），或者是不同的实型，编译器则试图保证目标代码运行时能得到正确的结果，条件是，当需要高级别类型数据向低级别类型数据转换时，不出现溢出。这样，C编译器作的约定是，当整型或实型数据作为实在参数时，分别将它们提升到long和double类型的数据传递到被调用函数。被调用函数根据形式参数所声明的类型，决定是否要将实在参数向低级别类型转换。

在本例中，long类型数据占4个字节，而short类型数据只占2个字节。因此被调用函数把实在参数的低位字节的内容当成是自己所需的数据，见图5.2

11 / 22

注意，对于SUN工作站来说，低地址存放整型数据的高位。

对于实型来说。double类型是8个字节，而float类型4个字节。被调用函数把实在参数的前4个字节作为自己所需的数据，因为double后面4个字节的内容都是为了增加精度用的，见图5.3。

这样在main函数中依次将参数提升后反序进栈，大小分别为8, 8, 4, 4。在func函数中，按形式参数的类型，把这些

存储单元的一部分看成是形式参数的存储单元，见图5.4。从这个图不难理解为什么形式参数的地址间隔和它们的类型大小不一致了。

注意，现在的编译器将需要进行类型转换的形式参数（类型是char、short、float等）另行分配在局部数据区，当控制进入被调用过程时，首先将调用过程压栈的需要进行类型转换的实在参数取出，把它们存入所分配的局部数据区存储单元，并同时完成必要的数据类型的转换。在这种情况下，不会出现本题所碰到的现象。

另外，在SPARC工作站上，整型数据的高位存放在低地址，而低位存放在高地址。如果是X86机器，数据的高低下面是某个编译器的类型提升函数，供读者理解用（备注：int和long的大小一样）。

Type promote(Type ty) {

switch(ty->op){

case ENUM:

return inttype;

if (ty->size < inttype->size)

12 / 22

位不是按这样的次序存放，那也不会出现本题所碰到的现象。

case INT:

}

}

return inttype;

break;

if (ty->size < inttype->size)

return inttype; break;

if (ty->size < doubletype->size)

return doubletype;

case UNSIGNED:

case FLOAT:

return ty;

16 试把下列C语言程序的可执行语句翻译为 (a)一棵语法树， (b)后缀式， (c)三地址代码。 main() { int i; int a[10]; while (i<=10) a[i]=0; }

答：(a).一棵语法树

(b) 后缀式为： i 10<= a i[] 0 = while

从理论上可以说while(i<=10) a[i]=0; 的后缀式如上面表示。但若这样表示，在执行while操作时，赋值语句已经执行，这显然与语义不符，因此改为：

i 10 <=< 下一个语句开始地址>BM a i [] 0 =< 本语句地址 > BRL

其中BM操作为当表达式为假时转向<下一个语句开始地址>，BRL是一个一目运算，无条件转向<本语句始址>。 (c) 三地址代码序列为： 100 if i <= 10 got 102 101 goto 106 102 t1:=4*i 103 t2:=a 104 t2[t1]:=0 105 goto 100

13 / 22

while 布尔表达式 赋值表达式 表达式 表达式 <= 数组元素表达式 1 10 a 下标表达式 0 1 106

17. Pascal语言中，语句： for v：＝initial to final do stmt 与下列代码序列有相同含义 begin

t1:=initial;t2:=final; if t1<=t2 then begin v:=t1; stmt

while v<>t2 do begin v：=succ（v)； stmt end end end

(a)试考虑下述Pascal程序 program forloop(input, output); var i,initial,final: integer; begin

read(initial, final); for i:= initial to final do write(i) end

对于initial=MAXINT-5和final= MAXINT，问此程序将做些什么？其中MAXINT为目标机器允许的最大整数。 (b)试构造一个翻译pascal的for语句为三地址代码的语法制导定义。

答：（a）程序将显示如下六个整数： MAXINT -5 MAXINT -4 MAXINT -3 MAXINT -2 MAXINT -1 MAXINT （b）为简单起见，for语句的三地址代码如下： t1 := initial t2 := final

if t1 > t2 goto S.next v := t1 stmt.code S.begin: if v > t2 goto S.next v := succ(v) stmt.code goto S.begin 语法制导定义如下：

产生式 动作 S→for E do S1 S.begin := newlabel S.first := newtemp S.last := newtemp S.curr:= newtemp S.code:=gen(S.first “:=” E.init) ||gen(S.last “:=” E.final) ||gen(“if” S.first “>” S.last “goto” S.next) ||gen(S.curr “:=” S.first) ||gen(S.begin “:” ) ||gen(“if ” S.curr “>” S.Last “goto” S.next) ||S1.code ||gen(S.curr := succ(S.curr)) ||gen(“goto” S.begin) E→v:=initial to final E.init := initial.place E.final := final.place

18. 对于下面C语言文件s.c

f1(int x) { } f2(int x) {

{

long x;

14 / 22

long x; x = 1;

}

}

x = 1;

某编译器编译时报错如下：

s.c: In function ‘f1’:

s.c:3: warning: declaration of ‘x’ shadows a parameter

请回答，对函数f2为什么没有类似的警告错误。

答： 对于函数f1，局部变量x声明的作用域是整个函数体，导致在函数体中不可能访问形式参数x。由于这是一个合法的C语言函数，因此编译器给出警告错误。

对于函数f2，由于局部变量x的作用域只是函数体的一部分，不会出现上述问题，因而编译器不报错。

19. 考虑一个简单语言，其中所有的变量都是整型（不需要显式声明），并且仅包含赋值语句、读语句和写语句。下面的产生式定义了该语言的语法（其中lit表示整型常量；OP的产生式没有给出，因为它和下面讨论的问题无关）。

Program  StmtList

StmtList  Stmt StmtList | Stmt

Stmt  id := Exp; | read (id ); | write ( Exp ); Exp

 id | lit | Exp OP Exp

我们把不影响write语句输出值的赋值（包括通过read语句来赋值）称为无用赋值，写一个语法指导定义，它确定

一个程序中出现过赋予无用值的变量集合（不需要知道无用赋值的位置）和没有置初值的变量集合（不影响write语句输出值的未置初值变量不在考虑之中）。

非终结符StmtList和Stmt用下面3个属性（你根据需要来定义其它文法符号的属性）： （1）uses_in：在本语句表或语句入口点的引用变量集合，它们的值影响在该程序点后的输出。 （2）uses_out：在本语句表或语句出口点的引用变量集合，它们的值影响在该程序点后的输出。 （3）useless：本语句表或语句中出现的无用赋值变量集合。

答：Exp的属性uses表示它引用的变量集合。Program的useless和no_initial分别表示程序的无用赋值变量集合和未置初值变量集合。

20. 为下列C程序生成目标代码。

15 / 22

Program  StmtList

StmtList.uses_out:=;

Program.useless := StmtList.useless; Program.no_initial := StmtList.uses_in; Stmt.uses_out := StmtList1.uses_in; StmtList.uses_in := Stmt.uses_in

StmtList.useless := StmtList1.useless  Stmt.useless;

StmtList  Stmt StmtList1 StmtList1.uses_out := StmtList.uses_out;

StmtList  Stmt Stmt.uses_out := StmlList.uses_out; StmlList.uses_in := Stmt.uses_in; StmtList.useless := Stmt.useless

Stmt.useless :=if id.lexemeStmt.uses_out then  else{id.lexeme}; then (Stmt.uses_out–{id.lexeme})Exp.uses else Stmt.uses_out Stmt.uses_in := Stmt.uses_out – {id.lexeme}

Stmt  id := Exp;

Stmt.uses_in := if id.lexemeStmt.uses_out

Stmt  read (id ); Stmt.useless:=if id.lexemeStmt.uses_out then  else{id.lexeme}; Stmt  write ( Exp ); Stmt.useless := , Stmt.uses_in := Stmt.uses_out  Exp.uses Exp  id Exp  lit

Exp.uses:= {id.lexeme}

Exp.uses:= 

Exp.uses:= Exp1.uses  Exp2.uses

Exp  Exp1 OP Exp2

main() { int i; int a[10]; while(i<=10) a[i]=0; } 答：

21. 试构造下面的程序的流图，并找出其中所有回边及循环。 read P x := 1 c := P * P if c < 100 goto L1 B := P * P x := x + 1 B := B + x write x halt L1: B:= 10 x := x + 2 B := B + x write B

if B < 100 goto L2 halt L2: x := x + 1 goto L1 答：

程序的流图如下

16 / 22

22. 试求出如下四元式程序中的循环并进行循环优化.

I := 1

read J, K

L: A := K * I B := J * I C := A * B

write C I := I + 1 if I < 100 goto L

halt

答：把本题的三地址代码划分成基本块并画出其程序流图显示在图9.4(1)中，其中有三个基本块B1，B2，B3，有一条回边B2 -> B2，相应的循环是{B2}。

17 / 22

（1）代码外提：由于循环中没有不变运算，故不做此项优化

（2）强度削弱：B2中A和B都是I的归纳变量。优化结果显示在图9.4(2)中。

（3）删除归纳变量：变换循环控制条件，删除归纳变量I后的流图显示在图9.4(3)中

23 考虑下面的三地址语句序列：

b := 1 b := 2

18 / 22

if w <= x goto L2 e := b goto L2

L1: goto L3 L2: c := 3

b := 4 c := 6 goto L5 h := 8 goto L1

L3: if y <= z goto L4 L4: g := g + 1

L5: h := 9

（1）在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序号。 （2）画出该代码的控制流图，每个基本块就用（1）的序号表示。 （3）若有循环的话，列出构成每个循环的结点。

（2）

（1）

（2） （3）

1 答： （1）

24. 对下面的程序片段作出其程序流图并计算： （1）各基本块的到达_定值集IN[B]； （2）各基本块中各变量引用点的ud链； （3）各基本块出口的活跃变量集V_OUT[B]； （4）各基本块中变量定值点的du链。 I := 1 J := 0 L1: J := J + I read I

if I < 100 goto L2 write J halt

19 / 22

b := 1 b := 2

if w <= x goto L2 e := b goto L2

2 4 5 L1: goto L3 L2: c := 3 b := 4 c := 6

（4） （5） （6）

6 7 L3: if y <= z goto L4 goto L5 h := 8 goto L1

L4: g := g + 1

8 3

（7） （8）

L5: h := 9

（3）结点5、7和3构成一个循环，其中5是入口结点。

L2 : I := I * I

答：本题程序的程序流图如图9.6(1)所示。

（1）计算各基本块的到达-定值集IN[B]。公式为： IN[B] = ∪ OUT[P]

P∈P[B]

OUT[B] = GEN[B] ∪ ( IN[B] - KILL[B] )

GEN[B]和KILL[B]由程序流图直接求出，显示在表9.6(1)中。 表9.6(1) 基本块 B1 B2 B3 B4 GEN[B] { d1, d2 } { d3, d4 } { d6 } { } 位向量 KILL[B] 位向量 11000000 { d3, d4, d6 } 00110100 00110000 { d1, d2, d6 } 11000100 00000100 00000000 { d1, d4 } 10010000 { } 00000000 求各基本块到达-定值的初值及各遍的执行结果显示在表9.6(2)中。 表9.6(2) 初值 第一遍后 第二遍后 第三遍后 基本块 IN[B] OUT[B] IN[B] OUT[B] IN[B] OUT[B] IN[B] OUT[B] B1 00000000 11000000 00000000 11000000 00000000 11000000 00000000 11000000 B2 00000000 00110000 11000100 00110000 11100100 00110000 11100100 00110000 B3 00000000 00000100 00110000 00100100 00110000 00100100 00110000 00100100 B4 00000000 00000000 00110000 00110000 00110000 00110000 00110000 00110000 （2）求各基本块中各变量引用点的ud链：

假设在程序中某点u引用了变量a，则把能到达u的a的所有定值点，称为a在引用点u的引用-定值链（简称ud链）。可以利用到达-定值信息来计算各个变量在任何引用点的ud链。

由图9.6(1)的程序流图可知，I的引用点是d3、d5和d6，J的引用点是d3和d8。

B2中I和J的引用点d3前面没有对I和J的定值点，其ud链在IN[B2]={ d1, d2, d3, d6 }中，所以I在引用点d3的ud链是{ d1, d6 }；J在引用点d3的ud链是{ d2, d3 }。

在B2中I的引用点d5前面有I的定值点d4，且在d4定值后到达d5，所以I在引用点d5的ud链是{ d4 }。 B3中I的引用点d6前面没有I的定值点，其ud链是IN[B3]中I的所有定值点，所以是{ d4 }。

B4中J的引用点d8前面没有对J的定值点，其ud链是IN[B4]中J的所有定值点。已知IN[B4] = { d3, d4 }，所以，J的引用点d8的ud链是{ d3 }。

（3）各基本块出口的活跃变量集v-OUT[B]：

对程序中某变量a和某点P，如果存在一条从P开始的道路，其中引用了a在P点的值，则称a在点P是活跃的。计算公式如下： V_IN[B] = USE[B] ∪ ( V_OUT[B] - DEF[B] )

20 / 22

V_OUT[B] = ∪ V_IN[S]

S∈S[B]

其中，S[B]是B的所有后继块组成的集合。

DEF[B]和USE[B]可以从给定流图直接求出。从图9.6(1)的流图中求出的各基本块的DEF[B]和USE[B]显示在表9.6(3)中。 表9.6(3) 基本块 USE[B] DEF[B] B1 Φ { I, J } B2 B3 { I, J } { I } Φ Φ B4 { J } Φ 计算次序为B4, B3, B2, B1，各次迭代结果显示在表9.6(4)中。 表9.6(4) 第一次迭代后 第二次迭代后 基本块 V_IN[B] V_OUT[B] V_IN[B] V_OUT[B] B1 B2 B3 Φ { I, J } { I } { I, J } { I, J } Φ Φ { I, J } { I, J } { I, J } { I, J } { I, J } 第三次迭代后 V_IN[B] Φ { I, J } { I, J } V_OUT[B] { I, J } { I, J } { I, J } B4 { J } Φ { J } Φ { J } Φ （4）各基本块变量定值点的du链 一个变量a在某点P定值后该定值到达a的那些引用点成为该定值点的定值-引用链（简称du链）。使用下面的方程式进行计算： D_IN[B] = D_USE[B] ∪ ( D_OUT[B] - D_DEF[B] ) D_OUT[B] = ∪ D_IN[S]

S∈S[B]

其中S[B]是B的后继基本块集。D_USE[B]和D_DEF[B]根据程序流图可直接求出。本题根据图9.6(1)的程序流图求出的D_USE[B]和D_DEF[B]显示在表9.6(5)中。 表9.6(6) 基本块 D_DEF[B] D_USE[B] B1 { (d3, I), (d5, I), (d6, I), (d3, J), (d8, J) } { } B2 B3 { (d6, I), (d8, J) } { (d3, I), (d5, I) } { (d3, I), (d3, J) } { (d6, I) } B4 { } { (d8, J) } 变量I和J的D_IN[B]和D_OUT[B]的计算结果分别显示在表9.6(6)和表9.6(7)中。 表9.6(6) 第一次迭代后 第二次迭代后 第三次迭代后 基本块 D_IN[B] D_OUT[B] D_IN[B] D_OUT[B] D_IN[B] D_OUT[B] B1 B2 B3 00000000 00100000 00000100 00100000 00000100 00000000 00000000 00100000 00000100 00100000 00000100 00100000 00000000 00100000 00000100 00100000 00000100 00100000 B4 00000000 00000000 00000000 00000000 00000000 00000000 根据表9.6(6)，D_OUT[B1] = 00100000，故I在B1中定值点d1的du链是{ d3 }。D_OUT[B2] = 00000100，故I在B2中定值点d4的du链是{ d5, d6 }。D_OUT[B3] = 00100000，故I在B3中定值点d6的du链是{ d3 }。 表9.6(7) 第一次迭代后 第二次迭代后 第三次迭代后 基本块 D_IN[B] D_OUT[B] D_IN[B] D_OUT[B] D_IN[B] D_OUT[B] B1 B2 B3 B4 00000000 00100000 00000000 00000001 00100000 00000001 00000000 00000000 00000000 00100000 00100000 00000001 00100000 00100001 00100000 00000000 21 / 22

00000000 00100000 00100000 00000001 00100000 00100001 00100000 00000000 根据表9.6(7)，D_OUT[B1] = 00100000，J在B1中定值点d2的du链是{ d3 }。D_OUT[B2] = 00100001，故J在B2中定值

点d3的du链是{ d3, d8 }。

22 / 22