网络学院编译原理平时作业

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

2、+1 (k第0。则 Sf 10|S21, |S1|=2k (k0 0, |S?|=2k (k 00且S1是0,1上的串，含有奇数个0和奇数个1。S2是0,1上的串，含有偶数个 0和偶数个1。 考虑有一个自动机M1接受S1，那么自动机 M1如下:0111000|1100(11和L(M 1)等价的正规表达式，即S1为: (00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*类似的考虑有一个自动机 M2接受S2,那么自动机 M2如下:和L(M 2)等价的正规表达式，即 S2为：(00|11)|(01|10)(00|11)*(01|10)*因此，S为：(00|11

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

4、0，1) =q03(q1，1) =q03 (qo，0)=qi3(qi, 0) =q23(q2，1) =q01 01*01*01*013 (q2, 0) =q2状态转换图(2)正则表达式DFA M=(0 , 1 , q0, qi, q2, qa, q。，q 3, 3)状倉转换图1111其中3定义如下：3 (q0,0) =q13 (q0,1) =q03 (q1,0) =q23 (q1,1) =q13 (q2,0) =q33 (q2,1) =q23 (q3,1) =q33下面是用正规式表示的变量声明：(int | float ) id (, id )* ;请改用上下文无关文法表示，也就是写一个上下文

5、无关文法，它和该正规式等价。答：D TL;Tint | floatLL, id | id4试分析下面给出的if-the n-else语句的文法，它的提出原本是为了矫正dan gli ng-else ( 悬而未决的-else)文法的二义性：stmt f if expr then stmt|matched-stmtmatched- stmt f if expr the n matched -stmt else stmt|other试说明此文法仍然是二义性的答：考虑句子if e then if e then other else if e then other else othei它具有如下所示的两

6、种分析树stmtexpr the n e if stmt if matched-stmt expr the n matched-stmt e other if esle stmt matched-stmt expr the n matched-stmt e other esle stmt matched-stmt other stmt matched-stmt if expr the n matched-stmt e if esle stmt esle stmt matched-stmt expr the n e stmt other expr the n matched-stmt e oth

7、er if matched-stmt other 则上面给出的if-then-else文法仍是二义性的。5证明下面文法是SLR(1)文法，并构造其SLR分析表。E E+T|TT TF|FF F*|a|b答:该文法的拓广文法 G为(0) EE(1) EE+TET(3) TTFTF(5) FF*Fa(7) Fb其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下：10 = E E, E E+T, E T, T TF, T F-pF-,F F b11 =E E, E E +TI2 = E T , T T F, F F*,F a,FbI3 =T F ,F *F I4 = F a I5 =

8、F b I6 =E E+T, T TF, TF, F F*, F7 pJF TFb, F FI8*=F F* I9 =E E+T，T T F, FF*, F a, F b求 FOLLOW 集： FOLLOW(E)= + , $ FOLLOW(T)= + , $ , a, b FOLLOW(F)= + , $ , a, b, *构造的SLR分析表如下：狀态actionflotx+ab$ETF034S51231S6a cc2S4S5r r2134SB4r444r6r6r6r66r?r7r7 nnP r76S4S5937r3SBr3r3r3r 8r5r5r5r5P rS9r!34S517显然，此分析

9、表无多重定义入口，所以此文法是SLR文法。6为下面的文法构造LALR分析表S EE E+T|TT (E)|a答：其拓广文法G:(0) SS(1) SE(2) EE+T(3) ET(4) T(E)(5) Ta构造其LR(1)项目集规范族和goto函数(识别活前缀的DFA)如下：I0= S S, $, S E, $, E E+T, $/+T (E$/+T，凹+, a, $/+Ii = S S，$ 12= S E，$, E E +T, $/+= E T , $/+I4 = T ( E), $/+, E E+T, )/+, E T TE )/+/+, T a, )/+15= T a , $/+ I6

10、= E E+ T, $/+, T (E), $/+, T a, $/+17 = T (E ), $/+, E E +T, )/+I8 = E T, )/+19 = T ( E), )/+, E E+T, )/+, E T, )/+, T (E), )/+, T a, )/+110 = T a ,)/+ I11 = E E+T，$/+ 112 = T (E) , $/+I13 = E E+ T, )/+, T (E), )/+, T 14 =aT+ (E ),)/+, E E +T, )/+115 = E ET ；)/+116 = T (E) ,)/+合并同心的LR(1)项目集，得到LALR的项

11、目集和转移函数如下：10= Sf S, $, Sf E, $, Ef E+T, $/+, E f T, $/+, $/+宀(E), $/+, TIi = S f S，$2 = Sf E，$, Ef E +T, $I/+= Ef T , $/+/)14.9 = T f ( E), $/+/), E f E+T, )/+, E T 亠(町,)卿,T f a, )/+15.10 = T f a , $/+/) I6,13 = E f E+ T, $/+/), T f (E), $/+/), Tf a, $/+/)17,14 = T f (E ), $/+/), E f E +TI ”+5= E f

12、E+T , $/+/)112,16 = T f (E) , $/+/)LALR分析表如下:STATEactiongotoA4()$sET035,10123.61act2S6.13r133r3r3r34355,10S497,145,10r5r5r5気MS5.1011J57.14S6.13S12.1611,15r2r2r212.16r447 (1)通过构造识别活前缀的 DFA和构造分析表，来证明文法 E E + id | id是SLR文法 答：先给出接受该文法活前缀的 DFA如下：EE + id I4再构造SLR分析表如下:状态动作转移id+$E0s211s3acc2r2r23s44r1r1表中没

13、有多重定义的条目，因此该文法是SLR(1)的。(2)下面左右两个文法都和(1)的文法等价E E + M id | idE M E + id | idMM请指出其中有几个文法不是LR(1)文法，并给出它们不是LR(1)文法的理由。 答:只有文法E M E + id | idM不是LR(1)文法。因为对于句子id+id +id来说，分析器在面临第一个id时需要做的空归约次数和句子中+id的个数一样多，而此时句子中 +id的个数是未知的。8根据自上而下的语法分析方法，构造下面文法的LL (1)分析表。D TLTint | realLid RR , id R |答：先计算FIRST和FOLLOW FI

14、RST(D) = FIRST(T) = i nt,real FIRST(L) = idFIRST(R) = , sFOLLOW(D) = FOLLOW(L) = $FOLLOW(T) = idFOLLOW(R) = $LL(1)分析表如下：intrealidJ$DD - TLD - TLTT - intT - realLL - idRRR - ,idRR - s9下面的文法产生的表达式是对整型和实型常数使用算符+形成的。当两个整数相加时，结果仍为整数，否则就是实数。E E+T|TT num .num |num(a) 给出一个语法制导定义以确定每个子表达式的类型。(b) 扩充(a)中的语法制导定

15、义把表达式翻译成前缀形式，并且决定类型。使用一元算符inttoreal把整型值转换成相等的实型值，以使得前缀形式中的+的两个操作对象是同类型的。答：(a):产生式语义规则E E1+TIF (E1.type=in teger) and (T.type=in teger) THENE.type:=in tegerELSEE.type:=realE TE.type:=T.typeT num.numT.type:=realT numT.type:=in teger(b)：产生式语义规则E E1+TIF (E1.type=in teger) and (T.type=in teger) THENBEGIN

16、E.type:=in tegerPrint( +,E1.val,T.val)ENDELSE BEGINE.type:=realIF E1.type=i nteger THENBegi nE1.type:=realE1.val:=i nttoreal(E1.val)EndIF T.type:=i nteger THENBegi nT.type:=realT.val:=in ttoreal(T.val)EndPrint( +,E1.val,T.val)ENDE TE.type:=T.typeE.val:=T.valT num.numT.type:=realT.val: = num.numexval

17、T numT.type:=in tegerT.val:= numexval10假设说明是由下列文法产生的：X id LL ,id L|:TT in teger |real(a) 建立一个翻译模式，把每一个标识符的类型加入到符号表中(b) 从(a)中的翻译模式构造一个预翻译程序。答：(a)：产生式翻译模式D idD.Type:=L.TypeLaddtype( id .entry, D.type)L ,idL.Type:=L1.TypeL1addtype( id .entry, L.type)L :TL.type:=T.typeT in tegerT.type:=i ntegerT realT.t

18、ype:=real(b)：Procedure D;beginIf lookahead=id the nBegi nMatch(id);D.type=L;addtype(id.e ntry,D.type) endelseerrorendFunction L: DataType;BeginIf lookahead= , thenBeginMatch( )；If lookahead=id the nbeginmatch(id);L.Type=L; addtype(id.e ntry,L.type); return(L.type)endElseerrorEndElse if lookahead= th

19、e nBeginMatch( )；L.Type=T; return(L.Type) endelseerrorEndFunction T: DataType;BeginIf lookahead=in teger the nBegi nMatch(i nteger);retur n(i nteger)endelse If lookahead=real the nBeg inMatch(real);return(real)endelseerrorend11为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号(即值大于零还是小于零)记录在属性E.sign中(属性值分别用POS或NE

20、G表示)。你可以假定所有的整数都不 为零，这样就不用担心零的符号。E E *E | +E | E | unsignec_integer答：_EEi *E2if Ei .sign= E2.sign then E.sign := POS else E.sign := NEG E+E1 E.sign := E1.sign EE1 if E1 .sign= POS then E.sign := NEG else E.sign := POSEun sig nec_in teger E.sig n := POS12为下面文法写一个语法制导的定义，用S的综合属性val给出下面文法中S产生的二进制数的值。例如

21、，输入101.101时，S. val:=5.625。(不得修改文法。SLRBL . R L B | B R | 0 | 1I L BB答：SL . RS.val:=L. val + R. valSLS.val:=L. valLL1 BL.val := L1. val 2 + B. valLBL.val:=B. valRB R1R.val:=(R1. val + B. val)/2RBR.val:=B. val/2B0B.val:=0B1B.val:=113试问下面的程序将有怎样的输出？分别假定：(a) 传值调用(call-by-value)；(b) 弓丨用调用(call-by-refere n

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

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

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

25、明在c中如何访 问变量X。program env ；procedure a ；var x:i nteger ； procedure b ;procedure c ;begin x:=2 ； b end; procedure c beg in c end; procedure bbegin b end； procedure a beg in a end. ma in答: 式参数i, j, f, e的地址间隔和它们的类型的大小不一致，试分析不一致的原因。注意，输出的数据是 八进制的。envcontrol linkaccess linkacontrol link wumwi-irtiipn-r-ma

26、ccess linkxbcontrol linkaccess linkcontrol linkaccess linkcontrol link access linkc.control link 心access link说明：c中沿着存取链向前走两步，到过程a的活动记录中就可15下面给出一个 C语言程序及其在 SPARC/SUN工作站上经某编译器编译后的运行结果。从运行结果看，函数func中4个局部变量i1, j1, f1, e1的地址间隔和它们类型的大小是一致的，而4个形以访问到变量func (i, j, f, e)short i, j; float f, e;short i1, j1; fl

27、oat 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, double = %d, %d, %d, %d, %d n, sizeof(short), sizeof(i nt), sizeof( Ion g), sizeof(float), sizeof(double);m

28、ai n()short i, j; float f, e;fun c(i, j, f, e);运行结果是：Address of i, j, f, e = 35777772536, 35777772542, 35777772544, 35777772554Address of i1, j1, f1, el = 35777772426, 35777772424, 35777772420, 35777772414Sizes of short, int, long, float, double = 2, 4, 4, 4, 8 请问为什么？答: c语言编译器是不做实在参数和形式参数的个数和类型是否一致的

29、检查的，由程序员自己保证它们的一致性。但是对于形式参数和实在参数是不同的整型（如一个是short型，另一个是long型），或者是不同的实型，编译器则试图保证目标代码运行时能得到正确的结果，条件是，当需要高级别类型数据向低级别类型数据转换时，不出现溢出。这样，C编译器作的约定是，当整型或实型数据作为实在参数时，分别将它们提升到long和double类型的数据传递到被调用函数。被调用函数根据形式参数所声明的类型，决定是否要将实在参数向低级别类型转换。在本例中，long类型数据占4个字节，而short类型数据只占2个字节。因此被调用函数把实在参数的低位字节的内容当成是自己所需的数据，见图 5.2注意

30、，对于SUN工乍站来说，低地址存放整型数g居的高位。对于实型来说。double类型是8个字节，而float类型4个字节。被调用函数把实在参数的前4个字节作为自己咼地址jmain函数中依次将参数提升后反序进栈，大小分别为，8, 8, 4, 4。在放n低函数中，按形式参数的类型,short，因为 double后面4个字节的内容都是为了增加精度用的，见图5.3。图5.2长整型和短整型Joublefloat图5.3双精度型和浮点型把这些存储单元的一部分看成是形式参数的存储单元, 它们的类型大小不一致了。见图5.4。从这个图不难理解为什么形式参数的地址间隔和在main函数中参数压栈时的观点在func函数

31、中存取形式参数时的观点i，4个字节栈的增 长方向f，8个字节e，8个字节j，4个字节-4个字节，起始地址图5.4参数在栈中的情况 2个字节，起始地址 2个字节，起始地址 j 4个字节，起始地址35777772536357777725423577777254435777772554注意，现在的编译器将需要进行类型转换的形式参数(类型是char、short、float等)另行分配在局部数据区,不会出现本题所碰到的现象。 而低位存放在高地址。如果是当控制进入被调用过程时，首先将调用过程压栈的需要进行类型转换的实在参数取出，把它们存入所分配的局部数 据区存储单元，并同时完成必要的数据类型的转换。在这种

32、情况下，X86机器，数据的另外，在SPARC工作站上，整型数据的高位存放在低地址， 高低位不是按这样的次序存放，那也不会出现本题所碰到的现象。int和long的大小一样)。下面是某个编译器的类型提升函数，供读者理解用(备注：Type promote(Type ty) switch(ty-op) case ENUM: return in ttype;case INT: if (ty-size size) return in ttype;break;case UNSIGNED:if (ty-size size) return in ttype;break;case FLOAT:if (ty-siz

33、e size)retur n doubletype; return ty;16试把下列C语言程序的可执行语句翻译为(a) 棵语法树，(b) 后缀式，(c) 三地址代码。mai n() int i;int a10;while (i=10)ai=0;从理论上可以说 值语句已经执行，i 10 =BM a i 0 = BRLwhile(i=10) ai=0;这显然和语义不符,的后缀式如上面表示 因此改为：但若这样表示，在执行while操作时，赋其中BM操作为当表达式为假时转向 ,BRL是一个一目运算，无条件转向。(c) 三地址代码序列为：100 if i = 10 got 102101 goto 10

34、6102 t1:=4*i103 t2:=a104 t2t1:=0105 goto 10010617 Pascal 语言中，语句：for v ：= initial to final do stmt和下列代码序列有相同含义begi nt1:=i nitial;t2:=fi nal;if t1=t2 then beginv:=t1;stmtwhile vt2 do beg inv : =succ (v)；stmtendendend(a) 试考虑下述Pascal程序program forloop(i nput, output);var i,initial,final: integer;beg inre

35、ad(i nitial, fin al);for i:= initial to final dowrite(i)end对于initial=MAXINT-5和final=MAXINT问此程序将做些什么？其中MAXINE目标机器允许的最大整数。(b) 试构造一个翻译pascal的for语句为三地址代码的语法制导定义。答：(a) 程序将显示如下六个整数：MAXINT -5 MAXINT -4 MAXINT -3 MAXINT -2 MAXINT -1 MAXINT(b) 为简单起见，for语句的三地址代码如下：t1 := in itial t2 := finalif t1 t2 goto S.n e

36、xt v := t1 stmt.code S.begi n:if v t2 goto S.n ext v := succ(v) stmt.code goto S.begi n语法制导定义如下：产生式 动作 St for E do S1 S.begi n := n ewlabel S.first := n ewtemp S.last := n ewtemp S.curr:= n ewtempS.code:=ge n(S.first“ := ” E.i nit) |ge n(S.last“ := ” E.fi nal) |ge n(if ” S.first“ firSt)ast |gen(S.be

37、gin“: ” ) |gen(if ” S.curr” S.Last goto ” S.next) |S1.code |gen(S.curr := succ(S.curr) |gEt v:=initial to final E.init := initial.place E.final := final.place18对于下面C语言文件s.cf1(i nt x)long x; x = 1;f2（i nt x）long x;x = 1;某编译器编译时报错如下：s.c: In function fl:s.c:3: warning: declaratio n of x shadows a param

38、eter请回答，对函数f2为什么没有类似的警告错误。答：对于函数f1，局部变量x声明的作用域是整个函数体，导致在函数体中不可能访问形式参数X。由于这是一个合法的C语言函数，因此编译器给出警告错误。对于函数f2,由于局部变量x的作用域只是函数体的一部分，不会出现上述问题，因而编译器不 报错。19考虑一个简单语言，其中所有的变量都是整型（不需要显式声明），并且仅包含赋值语句、读语 句和写语句。下面的产生式定义了该语言的语法（其中 lit表示整型常量；0P的产生式没有给出，因 为它和下面讨论的问题无关）。Program StmtListStmtListStmt StmtList | StmtStmt

39、id := Exp; | read （d ）; | write （ Exp ）;Expid | lit | Exp OP Exp我们把不影响write语句输出值的赋值（包括通过read语句来赋值）称为无用赋值，写一个语法 指导定义，它确定一个程序中出现过赋予无用值的变量集合（不需要知道无用赋值的位置）和没有置初值的变量集合（不影响 write语句输出值的未置初值变量不在考虑之中）。非终结符StmtList和Stmt用下面3个属性（你根据需要来定义其它文法符号的属性）：（1）uses_in：在本语句表或语句入口点的引用变量集合，它们的值影响在该程序点后的输出。（2）uses_out在本语句表或语

40、句出口点的引用变量集合，它们的值影响在该程序点后的输出。（3）useless本语句表或语句中出现的无用赋值变量集合。答：Exp的属性uses表示它引用的变量集合。Program的useless和no_initial分别表示程序的无用赋值变量集合和未置初值变量集合。Program StmtListStmtList.uses_out:=;Program.useless := StmtList.useless;Program. no_i nitial := StmtList.usesn;StmtList Stmt StmtList 1 StmtList 1.uses_out := StmtList.

41、uses_out;Stmt.uses_out := StmtList 1.uses_i n;StmtList.uses_in := Stmt.uses_inStmtList.useless := StmtList.useless Stmt.useless;StmtList Stmt Stmt.uses_out := StmlList.uses_out;StmlList.uses_in := Stmt.uses_i n;StmtList.useless := Stmt.uselessStmt id := Exp; Stmt.useless :=if id .lexeme Stmt.uses_ou

42、t then elseid .lexeme;Stmt.uses_in := if idexeme Stmt.uses_outthen (Stmt.uses_out - id .lexeme) Exp.uses else Stmt.uses_outStmtread (id );Stmt.useless:=if id .lexeme Stmt.uses_out thenelse idexemeStmt.uses_in := Stmt.uses_out -idexemeStmtwrite ( Exp );Stmt.useless :=, Stmt.uses_in := Stmt.uses_outEx

43、p.usesExpidExp.uses:= idexemeExplitExp.uses:=ExpExp1 OP Exp2Exp.uses:= Exp1.usesExp2.uses20为下列C程序生成目标代码。mai n()int i;int a10;while(i=10)ai=0;答：21试构造下面的程序的流图，并找出其中所有回边及循环read Px := 1c := P * Pif c 100 goto L1B := P * Px := x + 1B := B + xwrite xhaltL1: B:= 10x := x + 2B := B + xwrite Bif B 100 goto L

44、2haltL2: x := x + 1goto L1答：程序的流图如下B程序毓囹(2)强度削弱：B2中A和B都是I的归纳变量。优9.4(1)中，其中有三个基本块B1, B2, B3,有9.4 a(1)代码外提：由于循环中没有不变运算，故不做此项优化 化结果显示在图9.4(2)中。-：B ：二 10m :二 x + 2B :二 B 十 xwrite 8if B Bg循环i L = 3J B422试求出如下四元式程序中的循环并进行循环优化.I := 1 read J, K L: A := K * IB := J * IC := A * Bwrite CI := I + 1if I B2，相应的循环

45、是B2。read Px ：二 1C ：二 F * Fif c 100 goto LlII yrB := P * PXX + 1B ；= B + write x haltTread J, KL: AK*IEJ*IC ：*Bwri It: CIT+11 1 LOO 各utci LrhaltBT := 1 j-tad 1 KL: A :二巧D :-电C := A * B writc CI ；二 I + 1 巧：二巧+ KS2 ：- S2 + J if I 00 gotn I.halt9.4(2)经通度削弱后的槪圈(3)删除归纳变量：变换循环控制条件，删除归纳变量I后的流图显示在图9.4(3)中B图9

46、.4(3)删除归纲变量的程序流图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 := bgo

47、to 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 L1 （ 7） L5: h := 9（ 8）（2）（3）结点5、7和3构成一个循环，其中5是入口结点 24对下面的程序片段作出其程序流图并计算：（1）各基本块的到达_定值集INB；（2）各基本块中各变量引用点的ud链；（3）各基本块出口的活跃变量集 V_OUTB；（4）各基本块中变量定值点的du链。I := 1J := 0L1: J := J + Iread Iif I 100 goto L2write JhaltL2 : I := I * I答：本题程序的程序流图如图 9.6（1）所示。图g.6程咸医(1) 计算各基本块的到达-定值集INB。公式为： INB = U OUTPP PBOUTB = GENB U ( INB - K