编译原理平时作业答案

1、编译原理平时作业1对于下列语言分别写出它们的正规表达式。(1)英文字母组成的所有符号用，要求符号用中顺序包含五个元音。 答：令Letter表示除这五个元音外的其它字母。(letter) A(letter) E(letter) I(letter) O(letter) U(letter)(2)英文字母组成的所有符号用，要求符号用中的字母依照词典顺序排列。 答：A*B*.Z*(3) 2 =0,1上的含偶数个1的所有用。答：(0|10*1)*(4) 2 =0,1上的含奇数个1的所有申。答：(0|10*1)*1(5)具有偶数个0和奇数个1的有0和1组成的符号用的全体。答：设S是符合要求的串，|S|=2k

2、+1 (k分0。则 Sf s 1。|&1, |S1|=2k (k>0) , |S2|=2k (k且S1是0,1上的串，含有奇数个 0和奇数个1。0和偶数个1。那么自动机Mi如下:S2是0,1上的串，含有偶数个 考虑有一个自动机 Mi接受Si,011000|11ai|io00|11和L(M 1)等价的正规表达式，即* *Si为:*(00|11)|(01|10)(00|11) (01|10) (01|10)(00|11)类似的考虑有一个自动机M2接受S2,那么自动机 M2如下:和L(M 2)等价的正规表达式，即 (00|11)|(01|10)(00|11)*(01|10) 因此，S为

3、：(00|11)|(01|10)(00|11)*(01|10)(00|11)|(01|10)(00|11)*(01|10)S2为:(01|10)(00|11)*0|1(6)不包含子用011的由0和1组成的符号用的全体。答: 答:1 |1 0(0|10) (1| £)由0和1组成的符号用，把它看成二进制数，能被3整除的符号用的全体。 假设w的自动机如下：对应的正规表达式：(1(01*0)1|0)*2给出接受下列在字母表0,1上的语言的DFA 所有以00结束的符号用的集合。DFA M=(0 , 1, qo, qi, q2 , q。, q 2 , 8)其中8定义如下：状态转换图(2)所有具

4、有3个0的符号用的集合 正则表达式:1*01*01*01*8 (q0,0)=q18 (q0,1)=q08 (q1，0)=q28 (q1，1)=q08 (q2,0)=q26 (q2,1)=q0DFA M=(0 , 1, q0, q1, q2, q3, q0，q 3, 8)其中8定义如下:S (q0,0)=q18 (q1，0)=q28 (q2,0)=q36 (q3,1)=q38 (q0, 1) =q08 (q1，1) 二q18 (q2, 1) =q2状态转换图3下面是用正规式表示的变量声明：(int | float ) id (, id )* ;请改用上下文无关文法表示，也就是写一个上下文无关文法

5、，它和该正规式等价。 答：D - T L ;T. int | floatL .，L, id | id4试分析下面给出的if-then-else 语句的文法，它的提出原本是为了矫正dangling-else (悬而未决的-else)文法的二义性：stmt f if expr then stmt|matched-stmtmatched- stmt f if expr then matched -stmt else stmt|other试说明此文法仍然是二义性的。答： 考虑句子 if e then if e then other else if e then other else other它具有如

6、下所示的两种分析树 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 stmtmatched-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 oth

7、er if matched-stmt other则上面给出的if-then-else文法仍是二义性的。5证明下面文法是SLR(1)文法，并构造其SLR分析表。E- E+T|TTf TF|FF-F*|a|b答：该文法的拓广文法G'为(0) E' 一 E (1) E - E+T(2) E T (3) T 一 TF(4) T F (5) F F*(6) F a (7) F 一 b其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下：Io= E'一 E, E 一 E+T, E 一 T, T 一 TF, T 一FF- -a, -F F*- bI1 = E'-

8、E , E 一E +TI2 = E 一 T , T 一 T F, F 一 F*, F一 a,F一 bI3 = T一 F , F 一 F斗4 = F - a I5 = F 一b I6 = E - E+- T,TTFTf FF F*,F aFb 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, bFOLLOW(F尸+ , $ , a, b, *构造的SLR分析表如下：状态actiongoto+.ab*ETF0

9、S4S517311S6acc2r?1S4S5r厂73kAS8r4r4r44r6r6r6r6r65r7r7r7r7r76S4S5937出SBr3r3r38r55r5r5r59r1S495n7显然，此分析表无多重定义入口，所以此文法是SLR文法。6为下面的文法构造LALR(1)分析表SfEE- E+T|TT- (E)|a答：其拓广文法G':(0) S' 一 S (1) S 一 E(2) E E+T(3) E一 T(4) T- (E) (5) T- a构造其LR(1)项目集规范族和goto函数(识别活前缀的DFA)如下：|0= S S, $, SE, $, EE+T, $/+1 E

10、(守 $/+T, $/+,- a, $/+Ii = S，- S , $ I2 = S - E -，$, E - E +T, $/+3= E -T ,$/+I4 = T -( E), $/+, E- E+T, )/+, E T - - TE)/+/+, T - a, )/+15 = T - a , $/+ 16 = E - E+ T, $/+, T -(E), $/+, T - a, $/+17 = T -(E ), $/+, E- E +T, )/+8 = E - T)/+19 = T -( E), )/+, E - E+T,)/+, E - T,)/+, T -(E), )/+, T - a

11、,)/+110 = T- a -，)/+ I11 = E- E+T -，$/+Ii2 = T -(E) , $/+Ii3 = E-E+T, )/+, T-(E), )/+, T T14 aT+L (E ),)/+, E -E +T, )/+115 = E - E+Tj )/+116 = T -(E) , )/+合并同心的LR 项目集，得到LALR的项目集和转移函数如下：|0 = S S, $, SE, $, EE+T, $/+, ET, $/+, T - (E), $/+, TIi = S '- S , $ 2 = S -E -，$, E -E +T, $/+8= E -T , $/+

12、/)I4,9 = T -( E), $/+/), E- E+T, )/+, E T (3)阿,丁一 a, )/+15,10 = T -a , $/+/)I6,13 = E-E+ T, $/+/), T -(E), $/+/), T - a, $/+/)I7,14 = T -(E ), $/+/), E- E - +TI )/+5= E - E+，$/+/)I 12,16 = T -(E). , $/+/)LALR分析表如下:STATEactiongotoA+()$sET0S5,10P S4,9123#1acc2S6,13r138r3r3r34,9S5.10S4.97J43.85,10r5r5r

13、56,13S5J0%. 9111157,14S6.13S12.1611,15r2r2r212316r4r4r47 (1)通过构造识别活前缀的DFA和构造分析表，来证明文法 E t E + id | id 是SLR(1)文法。答：先给出接受该文法活前缀的DFA如下：再构造SLR分析表如下:状态动作转移id+$E0s211s3acc2r2r23s44riri表中没有多重定义的条目，因此该文法是SLR(1)的。(2)下面左右两个文法都和(1)的文法等价E > E + M id | idE > M E + id | idM M ；请指出其中有几个文法不是LR(1)文法，并给出它们不是LR(

14、1)文法的理由。答：只有文法E > M E + id | idM r ；：不是LR(1)文法。因为对于句子id+id+id来说，分析器在面临第一个id时需要做的空归约次数和句子中+id的个数一样多，而此时句子中+id的个数是未知的。8 根据自上而下的语法分析方法，构造下面文法的 LL (1)分析表。D > TLT int | realL ) id RR > , id R | ；答：先计算 FIRST和FOLLOWFIRST(D) = FIRST(T) = int,realFIRST(L) = idFIRST(R) = , eFOLLOW(D) = FOLLOW(L) = $F

15、OLLOW(T) = idFOLLOW(R) = $LL(1)分析表如下：intrealid,$DD -> TLD -> TLTT -> intT -> realLL -> idRRR -> ,idRR -> &9下面的文法产生的表达式是对整型和实型常数应用算符 +形成的。当两个整数 相加时，结果仍为整数，否则就是实数。E- E+T|TTf num.num|num(a)给出一个语法制导定义以确定每个子表达式的类型。(b)扩充(a)中的语法制导定义把表达式翻译成前缀形式，并且决定类型。使用一元算符inttoreal把整型值转换成相等的实型值，以使

16、得前缀形式中的 +的 两个操作对象是同类型的。(a)：产生式语义规则E E1+TIF (E1.type=integer) and (T.type=integer) THENE.type:=integerELSEE.type:=realE TE.type:=T.typeT num.numT.type:=realT numT.type:=integer(b)：产生式语义规则E E1+TIF (E1.type=integer) and (T.type=integer) THENBEGINE.type:=integerPrint( +',E1.val,T.val)ENDELSE BEGINE.

17、type:=realIF E1.type=integer THENBeginE1.type:=realE1.val:=inttoreal(E1.val)EndIF T.type:=integer THENBeginT.type:=realT.val:=inttoreal(T.val)EndPrint( +',E1.val,T.val)ENDE TE.type:=T.typeE.val:=T.valT num.numT.type:=realT.val:=num.num.lexvalT numT.type:=integerT.val:=num.lexval10假设说明是由下列文法产生的:A

18、 id LL-,id L|:TTf integer |real(a)建立一个翻译模式，把每一个标识符的类型加入到符号表中(b)从(a)中的翻译模式构造一个预翻译程序。答：(a)：产生式翻译模式D idLD.Type:=L.Typeaddtype(id.entry, D.type)L ,idL1L.Type:=L1.Typeaddtype(id.entry, L.type)L :TL.type:=T.typeT integerT.type:=integerT realT.type:=real(b)：Procedure D;beginIf lookahead=id thenBeginMatch(i

19、d);D.type=L;addtype(id.entry,D.type) endelseerrorendFunction L: DataType;BeginIf lookahead= ',' thenBeginMatch( ,");If lookahead=id thenbeginmatch(id);L.Type=L;addtype(id.entry,L.type); return(L.type)endElseerrorEndElse if lookahead= 'thenBeginMatch( :")；L.Type=T;return(L.Type)

20、 endelseerrorEndFunction T: DataType;BeginIf lookahead=integer thenBeginMatch(integer);return(integer) endelse If lookahead=real thenBeginMatch(real);return(real) endelseerrorend11为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号（即值大于零还是小于零）记录在属性 E.sign中（属性值分别用POS或 NEG表示）。你可以假定所有的整数都不为零，这样就不用担心零的符号。Et E *E | +E

21、| -E | unsigned_integerErEi *E2if Ei.sign= E2.sign then E.sign := POS elseE.sign := NEG Er +E1 E.sign := E1.sign E-Ei if E1.sign= POS thenE.sign := NEG else E.sign := POSEt unsigned_integer E.sign := POS12为下面文法写一个语法制导的定义，用 S的综合属性val给出下面文法中S 产生的二进制数的值。例如，输入101.101时，S. val := 5.625。（不得修改文法。）S > L .

22、 R | LL > L B | BR > B R | BB > 0 | 1S. val := L. val + R. valS ，LS. val :：=L. valL >L1 BL. val :：=L1. val 2 + B. valL >BL. val :：=B. valR >B R1R. val :=(R1. val + B. val)/2R >BR. val :=B. val/2B >0B. val :=0B )1B. val :=113试问下面的程序将有怎样的输出？分别假定：(a)传值调用(call-by-value)；(b)弓I用调用(

23、call-by-reference);(c)复制恢复(copy-restore ;(d)传名调用(call-by-name)。program main(input,output)；procedurep (x,y,z)；beginy： =y+1;z： =z + x；end;begina： =2；b: = 3;p(a+ b,a,a)；print aend.答：1) .传地址：所谓传地址是指把实在参数的地址传递给相应的形式参数。在过程段中每个形式参数都有一对应的单元，称为形式单元。形式单元将用来存放相应的实在参 数的地址。当调用一个过程时，调用段必须领先把实在参数的地址传递到一个为被调用段可 以拿得

24、到的地方。当程序控制转入被调用段之后，被调用段首先把实参地址捎进 自己相应的形式单元中，过程体对形式参数的任何引用1或赋值都被处理成对形 式单元的间接访问。当调用段工作完毕返回时，形式单元(它们都是指示器)所指 的实在参数单元就持有所指望的值。2) .传结果：和“传地址”相似(但不等价)的另一种参数传递力法是所谓“传结 果”。这种方法的实质是，每个形式参数对应有两个中元，第1个单元存放实参 的地址，第2个单元存放实参的值。在过程体中对形参的任何引用或赋值都看成 是对它的第2个单元的直接访问。但在过程工作完毕返回前必须把第 2个单元的 内容行放到第1个单元所指的那个实参单元之中。3) .传值：所

25、谓传值，是一种简单的参数传递方法。调用段把实在参数的值计算 出来并存放在一个被调用段可以拿得到的地方。被调用段开始丁作时，首先把这 些值抄入形式中元中，然后就好像使用局部名一样使用这些形式单元。如果实在 参数不为指示器，那末，在被调用段中无法改变实参的值。4) .传名：所谓传名，是一种特殊的形一一实参数结合方式。解释“传名”参数 的意义：过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任-出现的形式参数都替换成相应的实在参数(文字替换)。它与采用“传地址”或“传值”的方式所产生的结果均不相同。(a)2 ;(b)8 ;(c)7 ；(d)9。14对以下的Pascal程序画出过程c

26、第二次被激活时的运行栈，控制链和访问链 说明在c中如何访问变量X。program env ；procedure a ；var x:integer ；procedure b ;procedure c ;begin x:=2 ； b end; procedure cbegin c end; procedure bbegin b end; procedure abegin a end. main答：envS control link access - link 二a二八control linkjaccess link/control link access - linknzzzzj control

27、link aaccess link/control link 匚. access link.V c ) control link/二 access .Jink.二二二二1J说明：c中沿着存取链向前走两步，到过程 a的活动记录中就可以访问到变量 X。15下面给出一个 C语言程序及其在 SPARC/SUN工作站上经某编译器编译后 的运行结果。从运行结果看，函数 func中4个局部变量i1, j1, f1, el的地址问 隔和它们类型的大小是一致的，而4个形式参数i, j, f, e的地址间隔和它们的类 型的大小不一致，试分析不一致的原因。注意，输出的数据是八进制的。func (i, j, f, e

28、)short i, j; float f, e;short i1, j1; float f1, e1;printf( "Address of i, j, f, e = %o, %o, %o, %o n", &i, &j, &f, &e);printf( "Address of i1, j1, f1, e1 = %o, %o, %o, %o n", &i1, &j1, &f1, &e1);printf( "Sizes of short, int, long, float, doubl

29、e = %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, el = 35777772426, 35777772424, 35777772420, 35

30、777772414 Sizes of short, int, long, float, double = 2, 4, 4, 4, 8 请问为什么?答：c语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的一致性。但是对于形式参数和实在参数是不同的整型(如一个是short型，另一个是long型)，或者是不同的实型，编译器则试图保证目标代码运行时能得到正确的结果，条件是，当需要高级别类型数据向低级别类型数据转换时，不出现溢出。这样，C编译器作的约定是，当整型或实型数据作为实在参数时，分别将它们提升到long和double类型的数据传递到被调用函数。被调用函数根据形

31、式参数所声明的类型，决定是否要将实在参数向低级别类型转换。在本例中，10ng类型数据占4个字节，而short类型数据只占2个字节。因此被调用函数把实在参数的低位字节的内容当成是自己所需的数据，见图5.2低地址放高位longshorttWj地址 放低位图5.2长整型和短整型注意，对于SUN工作站来说，低地址存放整型数据的高位。对于实型来说。double类型是8个字节，而float类型4个字节。被调用函数把实在参 数的前4个字节作为自己所需的数据，因为 double后面4个字节的内容都是为了增加精度 用的，见图5.3。doublefloat图5.3双精度型和浮点型这样在main函数中依次将参数提升

32、后反序进栈，大小分别为8, 8, 4, 4。在func函数中,按形式参数的类型，把这些存储单元的一部分看成是形式参数的存储单元，见图5.4。从这个图不难理解为什么形式参数的地址间隔和它们的类型大小不一致了。注意，现在的编译器将需要进行类型转换的形式参数（类型是char、short、float等）另行分配在局部数据区，当控制进入被调用过程时， 首先将调用过程压栈的需要进行类型转换的实在参数取出，把它们存入所分配的局部数据区存储单元，并同时完成必要的数据类型的转换。在这种情况下，不会出现本题所碰到的现象。另外，在SPARC工作站上，整型数据的高位存放在低地址，而低位存放在高地址。如栈的增 长方向在

33、main函数中参数压栈时的观点在func四数中存取形 式参数时的观点i, 4个字节2 2个字节，起始地址 35777772536j, 4个字节”>2个字节，起始地址 35777772542 a 4个字节，起始地址 35777772544_ 1f, 8个字节*e, 8个字节 4个字节，起始地址 35777772554图5.4参数在栈中的情况果是X86机器，数据的高低位不是按这样的次序存放，那也不会出现本题所碰到的现象。下面是某个编译器的类型提升函数，供读者理解用（备注： int和long的大小一样）。Type promote(Type ty)switch(ty->op)case EN

34、UM:return inttype;case INT:if (ty->size < inttype->size) return inttype;break;case UNSIGNED:if (ty->size < inttype->size) return inttype;break;case FLOAT:if (ty->size < doubletype->size) return doubletype;return ty;16试把下列C语言程序的可执行语句翻译为 （a）一棵语法树，(b)后缀式，(c)三地址代码。main() int i

35、;int a10;while (i<=10)ai=0；(b)后缀式为：i 10<= a i 0 = while从理论上可以说 while(i<=10) ai=0;的后缀式如上面表示。但若这样表示，在执行 while操 作时，赋值语句已经执行，这显然与语义不符，因此改为：i 10 <=<下一个语句开始地址 >BM a i 0 =< 本语句地址 > BRL其中BM操作为当表达式为假时转向<下一个语句开始地址>,BRL是一个一目运算，无条件转向V本语句始址>。(c)三地址代码序列为：100 if i <= 10 got 1021

36、01 goto 106102 t1:=4*i103 t2:=a104 t2t1:=0105 goto 10010617 Pascal 语言中，语句：for v : = initial to final do stmt与下列代码序列有相同含义begint1:=initial;t2:=final;if t1<=t2 then beginv:=t1;stmtwhile v<>t2 do begin:=succ (v);stmtend end end(a) 试考虑下述Pascal 程序program forloop(input, output);var i,initial,final

37、: integer;beginread(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 := fi

38、nalif 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语法制导定义如下：产生式 动作 Sf for E do S1 S.begin := newlabel S.first := newtemp S.la st := newtemp S.curr:= newtemp S.code:=gen(S.first “ := ”E.init) |gen(S.last “ := ” E.final) |gen( “ Sif.fi”rs

39、t “ >” S.last “ goto S” .next) |gen(S.curr “ := ”S.first) |gen(S.begin “ : ”) |gen( “” iSf .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.place18 对于下面C 语言文件s.cf1(int x) lo

40、ng x;x = 1; f2(int x) long x;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考虑一个简单语言，其中所有的变量都是整型（不需要显式声明

41、），并且仅包含赋值语句、读语句和写语句。下面的产生式定义了该语言的语法（其中 lit表示整型常量；OP的产生式没有给出，因为它和下面讨论的问题无关）。Program > StmtListStmtList Stmt StmtList | StmtStmt id := Exp; | read Qd ）; | write （ Exp ）;Exp > id | lit | Exp OP Exp我们把不影响write语句输出值的赋值（包括通过read语句来赋值）称为无 用赋值，写一个语法指导定义，它确定一个程序中出现过赋予无用值的变量集合（不需要知道无用赋值的位置）和没有置初值的变量集合（不

42、影响write语句输出值的未置初值变量不在考虑之中）。非终结符StmtList和Stmt用下面3个属性（你根据需要来定义其它文法符号 的属性）：（1） uses_in：在本语句表或语句入口点的引用变量集合，它们的值影响在 该程序点后的输出。（2） uses_out在本语句表或语句出口点的引用变量集合，它们的值影响在 该程序点后的输出。（3） useless本语句表或语句中出现的无用赋值变量集合。答：Exp的属性uses表示它引用的变量集合。 Program的useless和no_initial分别表示程序 的无用赋值变量集合和未置初值变量集合。Program t StmtList StmtLi

43、st.uses_out:=0;Program.useless := StmtList.useless;Program.no_initial := StmtList.uses_in;StmtList t Stmt StmtList 1 StmtListi.uses_out := StmtList.uses_out;Stmt.uses_out := StmtList i.uses_in;StmtList.uses_in := Stmt.uses_inStmtList.useless := StmtList i.useless 一 Stmt.useless;StmtList StmtStmt.use

44、s_out := StmlList.uses_out;StmlList.uses_in := Stmt.uses_in;StmtList.useless := Stmt.uselessStmtrid := Exp;Stmt.useless :=if id.lexeme S Stmt.uses_out then 0 elseid.lexeme;Stmt.uses_in := if id.lexeme Stmt.uses_outthen (Stmt.uses_out id.lexeme) oExp.uses else Stmt.uses_outStmtread (id );Stmt.useless

45、:=if id.lexeme S Stmt.uses_out then 0 elseid.lexeme;Stmt.uses_in := Stmt.uses_out - id.lexemeStmt write ( Exp );Stmt.useless := Stmt.uses_in := Stmt.uses_out 2 Exp.usesExp r idExp.uses:= id.lexemeExp . litExp.uses:=*'Exp . Expi OP Exp2 Exp.uses:= Expi.usesExp2.uses20为下列C程序生成目标代码 main()int i;int

46、a10;while(i<=10)ai=0；21试构造下面的程序的流图，并找出其中所有回边及循环 read Px := 1c := P * P if c < 100 goto L1B := P * x := x + 1B := B + x write x haltL1: B:= 10 x := x + 2 B := B + x write B if B < 100 goto L2 haltL2: x := x + 1 goto L1 答：程序的流图如下22试求出如下四元式程序中的循环并进行循环优化.I := 1read J, KL: A := K * IB := J * IC

47、:= A * Bwrite CI := I + 1if I < 100 goto Lhalt答：把本题的三地址代码划分成基本块并画出其程序流图显示在图9.4(1)中，其中有三个基本块B1, B2, B3,有一条回边 B2 -> B2 ,相应的循环是B2。read J, K图9. 4(1)程序流图(2)强度削弱：B2中A和B(1)代码外提：由于循环中没有不变运算，故不做此项优化 都是I的归纳变量。优化结果显示在图9.4(2)中。图±4(二殳强度由弱后的流图I后的流图显示在图 9.4(3)中(3)删除归纳变量：变换循环控制条件，删除归纳变量图9. 4(外删除归纳巧足的程序流回

48、23考虑下面的三地址语句序列：b := 1b := 2if w <= x goto L2e := bgoto L2L1: goto L3L2: c := 3b := 4c := 6L3: if y <= z goto L4goto L5L4: g := g + 1h := 8goto L1L5: h := 9(1)在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序 号。(2)画出该代码的控制流图，每个基本块就用(1)的序号表示。(3)若有循环的话，列出构成每个循环的结点。答：(1)b := 1b := 2if w <= x goto L2(1)e := bgoto

49、L2(2)L1:goto L3(3)L2:c:= 3b := 4c := 6(4)L3: if y <= z goto L4(5)goto L5(6)L4: g := g + 1h := 8goto L1L5: h := 9(8)(2)(3)结点5、7和3构成一个循环，其中 5是入口结点。24对下面的程序片段作出其程序流图并计算：(1)各基本块的到达_定值集INB;(2)各基本块中各变量引用点的ud链；(3)各基本块出口的活跃变量集 V_OUTB;(4)各基本块中变量定值点的du标。I := 1J := 0II : J := J + Iread Iif I < 100 goto L

50、2write J haltL2 : I := I * I答：本题程序的程序流图如图9.6(1)所示。II 1J := 1图g.6(D程序法图(1)计算各基本块的到达-定值集INB。公式为:INB = U OUTPPC PBOUTB = GENB U ( INB - KILLB)GENB和KILLB由程序流图直接求出，显示在表 9.6(1)中。表 9.6(1)基本块GENB位向量KILLB位向量B d 1, d 2 11000000 d 3, d 4, d6 ()0110100R d 3, d 4 00110000 d 1, d 2, d6 -1000100B d 6 00000100 d 1,

51、 d 410010000 00000000 00000000求各基本块到达-定值的初值及各遍的执行结果显示在表9.6(2)中。表 9.6(2)“本块初值A遍后第二遍后第三遍后NBOUTBINBOUTBINBOUTBINBOUTBB0000000011000000000000001100000000000000110000000000000011000000B20000000000110000110001000011000011100100001100001110010000110000Bb0000000000000100001100000010010000110000001001000011000000100100B00000000000000000011000000110