编译原理平时作业答案

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

2、k0),IS2k2k(k0)。且S是0,1上的串，含有奇数个。和奇数个1。S2是0,1上的串，含有偶数个。和偶数个1。考虑有一个自动机M接受S,那么自动机M如下：和L(M)等价的正规表达式，即S为：(00111)1(01110)(00111(01110)类似的考虑有一个自动机M?接受S2,那么自动机M?如下:和L(M0等价的正规表达式，即S2为：(00111)1(01110)(00111X01110)-因此，s为：(00lll)l(01ll0)(00lllX01ll0)0l(00111)1(01110)(00111X01110)4(6)不包含子串011的由。和1组成的符号串的全体。答：1对1*

3、0(0110)*(11)(7)由。和1组成的符号串，把它看成二进制数，能被3整除的符号串的全体。答：假设W的自动机如下：对应的正规表达式：(1(01*0)110)*2给出接受下列在字母表0,1上的语言的DFA。(1)所有以00结束的符号串的集合。DFAM=(0,1,q,q2,q0,q2,)其中定义如下：(q0,0)=q1(q0,1)=q0(q/0)=q2(q/1)=q0(q，0)=q(q，1)=q状将转换图JLJL所有具有3个。的符号串的集合。正则表达式：1*01*01*01*DFAM=(0,1,q0，qfq2，q3,q0，q3,)其中定义如下：TOC o 1-5 h z(q0,0)=q1(q

4、。，1)=q0(q/0)=q2(q/1)=q1q,0)=q3(q2，1)=q2(q3，1)=q33下面是用正规式表示的变量声明：(intIfloat)id(,id)*;请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。答：DTTL;Ttint|floatLtL,id|id4试分析下面给出的if-then-else语句的文法，它的提出原本是为了矫正dangling-else(悬而未决的else)文法的二义性：stmtifexprthenstmt|matched-stmtmatched-stmtifexprthenmatched-stmtelsestmt|other试说明此文

5、法仍然是二义性的。答：考虑句子ifethenifethenotherelseifethenotherelseother它具有如下所示的两种分析树stmtexprtheneifstmtifmatched-stmtexprthenmatched-stmteotherifeslestmtmatched-stmtexprthenmatched-stmteothereslestmtmatched-stmtotherstmtmatched-stmtifexprthenmatched-stmteifeslestmteslestmtmatched-stmtexprthenestmtotherexprthenm

6、atchedstmteotherifmatched-stmtother则上面给出的if-then-else文法仍是二义性的。5证明下面文法是SLR(l)文法，并构造其SLR分析表。FFFF答：该文法的拓广文法G为TOC o 1-5 h z(0),(1)()()F()F(5)FFOF()F其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下：Io=FFFFFF11=1=FFFFFI=FFFI=F15=FFFF18二I=FFF18二FFI=FFFFF求FOLLOW集：FOLLOW(E);+,$FOLLOW(T);+,$,a,bFOLLOW(F);+,$,a,b,*构造的SLR分析表如下

7、：状态actiongoto+*ab$ETF0S4S5123136acc2出S4S5r273r4SBr4r4r44份r6rGr6r66r77r7r7r76S4S5937田S8r3r3r38r5r5r5r5r5Sr1S4S5r17显然，此分析表无多重定义入口，所以此文法是SLR文法。6为下面的文法构造LALR(1)分析表+()答：其拓广文法G：TOC o 1-5 h z(0)(1)+(3)()(5)构造其1区(1)项目集规范族和goto函数(识别活前缀的DFA)如下:Io,+,/+,，/+,(),/+,/+I1，)I2,+,/+I3,/+I4(),/+,+,)/+,)/+,(),)/+,)/+I5

8、,/+I6+,/+,(),/+,/+I7(),/+,+,)/+I8，)/+I9(),)/+,+,)/+,)/+,(),)/+,，)/+I1o，)/+I11+,/+I12(),/+I13I15+,)/+,+(),)/+,)/+,)/+I16(),)/+I14(),)/+,+,)/+合并同心的LR项目集，得到LALR的项目集和转移函数如下:%=L=%=L=【4,9=15,10=17,14=112,16=13,8=匕=13,8=,16,13=LALR分析表如下:STATEactionflotoA+)$ET0S5.10S4.9123.81acc2S6.13r13,3r3r3r34,9S5,10S4,9

9、7,143.S5,10r5r5r56,13S5.10S4.911,157,14S6J3S12.1611,15r2r2r212,16r4r4r47(1)通过构造识别活前缀的DFA和构造分析表，来证明文法EfE+idIid是SLR文法。答：先给出接受该文法活前缀的DFA如下：再构造SLR分析表如下：状态动作转移id+$E0s211s3acc2r2r23s44r1r1表中没有多重定义的条目，因此该文法是SLR(1)的。(2)下面左右两个文法都和(1)的文法等价EfE+MidIidEfME+idIidMf8Mf8请指出其中有几个文法不是LR(1)文法，并给出它们不是LR(1)文法的理由。答：只有文法E

10、tME+idIidMt8不是LR(1)文法。因为对于句子id+id+id来说，分析器在面临第一个id时需要做的空归约次数和句子中+id的个数一样多，而此时句子中+id的个数是未知的。8根据自上而下的语法分析方法，构造下面文法的LL(1)分析表。DtTLTtint|realLtidRRt,idR|8答：先计算FIRST和FOLLOWFIRST(D)=FIRST(T)=int,realFIRST(L)=idFIRST(R)=,FOLLOW(D)=FOLLOW(L)=$FOLLOW(T)=idFOLLOW(R)=$LL(1)分析表如下：intrealid,$DD-TLD-TLTT-intT-real

11、LL-idRRR-,idRR-e9下面的文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时，结果仍为整数，否则就是实数。EE+TITTnum.numlnum(a)给出一个语法制导定义以确定每个子表达式的类型。(b)扩充(a)中的语法制导定义把表达式翻译成前缀形式，并且决定类型。使用一元算符inttoreal把整型值转换成相等的实型值，以使得前缀形式中的+的两个操作对象是同类型的。答：(a):产生式语义规则EfE1+TIF(E1.type=integer)and(T.type=integer)THENE.type:=integerELSEE.type:=realEfTE.typ

12、e:=T.typeTfnum.numT.type:=realTfnumT.type:=integer(b):产生式语义规则EfE1+TIF(E1.type=integer)and(T.type=integer)THENBEGINE.type:=integerPrint(+,E1.val,T.val)ENDELSEBEGINE.type:=realIFE1.type=integerTHENBeginE1.type:=realE1.val:=inttoreal(E1.val)EndIFT.type:=integerTHENBeginT.type:=realT.val:=inttoreal(T.va

13、l)EndPrint(+,E1.val,T.val)ENDEfTE.type:=T.typeE.val:=T.valTfnum.numT.type:=realT.val:=num.num.lexvalTfnumT.type:=integerT.val:=num.lexval10假设说明是由下列文法产生的：DidLL,idLI:TTintegerIreal(a)建立一个翻译模式，把每一个标识符的类型加入到符号表中。(b)从(a)中的翻译模式构造一个预翻译程序。答：(a)：产生式翻译模式DfidLD.Type:=L.Typeaddtype(id.entry,D.type)Lf,idL1L.Type

14、:=L1.Typeaddtype(id.entry,L.type)LTL.type:=T.typeTfintegerT.type:=integerTfrealT.type:=real(b)：ProcedureD;beginIflookahead=idthenBeginMatch(id);D.type=L;addtype(id.entry,D.type)endelseerrorendFunctionL:DataType;BeginIflookahead=,thenBeginMatch(,);Iflookahead=idthenbeginmatch(id);L.Type=L;addtype(id.

15、entry,L.type);return(L.type)endElseerrorEndElseiflookahead=:thenBeginMatch(:);L.Type=T;return(L.Type)endelseerrorEndFunctionT:DataType;BeginIflookahead=integerthenBeginMatch(integer);return(integer)endelseIflookahead=realthenBeginMatch(real);return(real)endelseerrorend11为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子

16、表达式E的符号（即值大于零还是小于零）记录在属性E.sign中（属性值分别用POS或NEG表示）。你可以假定所有的整数都不为零，这样就不用担心零的符号。EfE*EI+EI一EIunsigned_integer答：EfE1*E2ifE1.sign=E2.signthenE.sign:=POSelseE.sign:=NEGEf+E1E.sign:=E1.signEf一E1ifE1.sign=POSthenE.sign:=NEGelseE.sign:=POSEfunsigned_integerE.sign:=POS12为下面文法写一个语法制导的定义，用S的综合属性val给出下面文法中S产生的二进制数

17、的值。例如，输入101.101时，S.val:=5.625。（不得修改文法。）SfL.RILLfLBIBRfBRIBBf0I1答：SfL.RS.val:=L.val+R.valSTLS.val:=L.valLTL1BL.val:=L1.valx2+B.valLTBL.val:=B.valRTBR1R.val:=(R1.val+B.val)/2RTBR.val:=B.val/2BT0B.val:=0BT1B.val:=113试问下面的程序将有怎样的输出？分别假定：(a)传值调用(call-by-value)；(b)引用调用(call-by-reference)；(c)复制恢复(copy-rest

18、ore);(d)传名调用(call-by-name)。programmain(input,output)；procedurep(x,y,z)；beginy：=y+1；z：=z+x；end；begina：=2；b：=3；p(ab,a,a)；printaend.答：1)传地址：所谓传地址是指把实在参数的地址传递给相应的形式参数。在过程段中每个形式参数都有一对应的单元，称为形式单元。形式单元将用来存放相应的实在参数的地址。当调用一个过程时，调用段必须领先把实在参数的地址传递到一个为被调用段可以拿得到的地方。当程序控制转入被调用段之后，被调用段首先把实参地址捎进自己相应的形式单元中，过程体对形式参数的

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

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

21、reb；procedurec；beginX:=2；bend；procedurecbegincend；procedurebbeginbend；procedureabeginaend.main答：enva-controllink、cbccontrollink“accesslinkenva-controllink、cbccontrollink“accesslinkaccesslinkcontrollinkaccesslinkcontrollink-accesslinkcontrollink-一accesslinknxcontrollinkaccesslink说明：c中沿着存取链向前走两步，到过程a的

22、活动记录中就可以访问到变量X。15下面给出一个C语言程序及其在SPARC/SUN工作站上经某编译器编译后的运行结果。从运行结果看，函数func中4个局部变量i1,j1,f1,el的地址间隔和它们类型的大小是一致的，而4个形式参数i,j,f,e的地址间隔和它们的类型的大小不一致，试分析不一致的原因。注意，输出的数据是八进制的。func(i,j,f,e)shorti,j;floatf,e;shorti1,j1;floatf1,e1;printf(Addressofi,j,f,e=%o,%o,%o,%on,&i,&j,&f,&e);printf(Addressofi1,j1,f1,e1=%o,%o,

23、%o,%on,&i1,&j1,&f1,&e1);printf(Sizesofshort,int,long,float,double=%d,%d,%d,%d,%dn,sizeof(short),sizeof(int),sizeof(long),sizeof(float),sizeof(double);main()shorti,j;floatf,e;func(i,j,f,e);运行结果是：Addressofi,j,f,e=35777772536,35777772542,35777772544,35777772554Addressofi1,j1,f1,e1=35777772426,357777724

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

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

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

27、。如栈的增长方向栈的增长方向在main函数中参数压栈时的观点i，4个字节j，4个字节f，8个字节”e，8个字节”在func函数中存取形式参数时的观点22个字节，起始地址3577777253622个字节，起始地址357777725424个字节，起始地址357777725444个字节，起始地址35777772554图5.4参数在栈中的情况果是X86机器，数据的高低位不是按这样的次序存放，那也不会出现本题所碰到的现象。下面是某个编译器的类型提升函数，供读者理解用(备注：int和long的大小一样)。Typepromote(Typety)switch(ty-op)caseENUM:returnintt

28、ype;caseINT:if(ty-sizesize)returninttype;break;caseUNSIGNED:if(ty-sizesize)returninttype;break;caseFLOAT:if(ty-sizesize)returndoubletype;returnty;16试把下列C语言程序的可执行语句翻译为(a)一棵语法树，(b)后缀式，三地址代码。main()inti;inta10;while(i=10)ai=0;后缀式为：i10=ai0=while从理论上可以说while(i=10)ai=0;的后缀式如上面表示。但若这样表示，在执行while操作时，赋值语句已经执行

29、，这显然与语义不符，因此改为：i10=BMai0=BRL其中BM操作为当表达式为假时转向下一个语句开始地址,，BRL是一个一目运算，无条件转向。三地址代码序列为：100ifi=10got102101goto106102t1:=4*i103t2:=a104t2t1:=0105goto10010617Pascal语言中，语句：forv：=initialtofinaldostmt与下列代码序列有相同含义begint1:=initial;t2:=final;ift1=t2thenbeginv:=t1;stmtwhilevt2dobeginv：=succ(v)；stmtendendend(a)试考虑下述

30、Pascal程序programforloop(input,output);vari,initial,final:integer;beginread(initial,final);fori:=initialtofinaldowrite(i)end对于initial二MAXINT-5和final二MAXINT,问此程序将做些什么？其中MAXINT为目标机器允许的最大整数。(b)试构造一个翻译pascal的for语句为三地址代码的语法制导定义。答：(a)程序将显示如下六个整数：MAXINT-5MAXINT-4MAXINT-3MAXINT-2MAXINT-1MAXINT(b)为简单起见，for语句的三

31、地址代码如下：t1:=initialt2:=finalift1t2gotoS.nextv:=t1stmt.codeS.begin:ifvt2gotoS.nextv:=succ(v)stmt.codegotoS.begin语法制导定义如下：产生式动作SforEdoS1S.begin:=newlabelS.first:=newtempS.last:=newtempS.curr:=newtempS.code:=gen(S.first“:=”E.init)|gen(S.last“:=”E.final)|gen(“if”S.first“”S.last“goto”S.next)|gen(S.curr“:=

32、”S.first)|gen(S.begin“:”)|gen(“if”S.curr“”S.Last“goto”S.next)IlSl.codellgen(S.curr:=succ(S.curr)llgen(gotoS.begin)Ev:=initialtofinalE.init:=initial.placeE.final:=final.place18对于下面C语言文件s.cf1(intx)longx;x=1;f2(intx)longx;x=1;某编译器编译时报错如下：s.c:Infunctionf1:s.c:3:warning:declarationofxshadowsaparameter请回答

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

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

35、（3）useless：本语句表或语句中出现的无用赋值变量集合。答：Exp的属性uses表示它引用的变量集合。Program的useless和no_initial分别表示程序的无用赋值变量集合和未置初值变量集合。ProgramfStmtListStmtList.uses_out:=0;Program.useless:=StmtList.useless;Program.no_initial:=StmtList.uses_in;StmtListfStmtStmtList1StmtList1.uses_out:=StmtList.uses_out;Stmt.uses_out:=StmtList1.us

36、es_in;StmtList.uses_in:=Stmt.uses_inStmtList.useless:=StmtList1.uselessuStmt.useless;StmtListfStmtStmt.uses_out:=StmlList.uses_out;StmlList.uses_in:=Stmt.uses_in;StmtList.useless:=Stmt.uselessStmtfid:=Exp;Stmt.useless:=ifid.lexemegStmt.uses_outthen0elseid.lexeme;Stmt.uses_in:=ifid.lexemegStmt.uses_o

37、utthen(Stmt.uses_outid.lexeme)uExp.useselseStmt.uses_outStmtfread(id);Stmt.useless:=ifid.lexemegStmt.uses_outthen0elseid.lexeme;Stmt.uses_in:=Stmt.uses_outid.lexemeStmtfwrite(Exp);Stmt.useless:=0,Stmt.uses_in:=Stmt.uses_outuExp.usesExpfidExp.uses:=id.lexemeExp今litExp.uses:=0ExpfExp1OPExp2Exp.uses:=E

38、xp1.usesuExp2.uses20为下列C程序生成目标代码。main()inti;inta10;while(i=10)ai=0;21试构造下面的程序的流图，并找出其中所有回边及循环。readPx:=1c:=P*Pifc100gotoL1B:=P*Px:=x+1B:=B+xwritexhaltL1:B:=10 x:=x+2B:=B+xwriteBifB100gotoL2haltL2:x:=x+1gotoL1答：程序的流图如下22试求出如下四元式程序中的循环并进行循环优化.I:=1readJ,KA:=K*IB:=J*IC:=A*BwriteCI:=I+1ifIB2，相应的循环是B2。图9r程

39、序流图(1)代码外提：由于循环中没有不变运算，故不做此项优化(2)强度削弱：B2中A和B都是I的归纳变量。优化结果显示在图9.4(2)中。(3)删除归纳变量：变换循环控制条件，删除归纳变量I后的流图显示在图9.4(3)中B，23考虑下面的三地址语句序列:b:=1b:=2ifw=xgotoL2e:=bgotoL2L1:gotoL3L2:c:=3b:=4c:=6L3:ify=zgotoL4gotoL5L4:g:=g+1h:=8gotoL1L5:h:=9(1)在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序号。画出该代码的控制流图，每个基本块就用（1）的序号表示。若有循环的话，列出构成每

40、个循环的结点。答：（1）b:=1b:=2ifw=xgotoL2e:=b（1）TOC o 1-5 h zgotoL2(2)gotoL3(3)L2:c:=3b:=4c:=6(4)L3:ify=zgotoL4(5)gotoL5(6)L4:g:=g+1h:=8gotoL1(7)L5:h:=9(8)(2)(3)结点5、7和3构成一个循环，其中5是入口结点。24对下面的程序片段作出其程序流图并计算：(1)各基本块的到达一定值集INB；(2)各基本块中各变量引用点的ud链；(3)各基本块出口的活跃变量集V_OUTB；(4)各基本块中变量定值点的du链。:=1J:=0:J:=J+IreadIifI100got

41、oL2writeJhaltL2:I:=I*I答：本题程序的程序流图如图9.6(1)所示。图比1)程序特图(1)计算各基本块的到达-定值集INB。公式为:INB=UOUTPPePBOUTB=GENBU(INB-KILLB)GENB和KILLB由程序流图直接求出，显示在表9.6(1)中。表9.6基本块GENB位向量KILLB位向量B1d1,d211000000d3,d3,d600110100B2d3001100004,d2,d611000100B3d600000100d1,d310010000B30000000000000000求各基本块到达-定值的初值及各遍的执行结果显示在表9.6(2)中。表9

42、.6(2)基本块初值第一遍后第二遍后第三遍后INBOUTBINBOUTBINBOUTBINBOUTBB10000000011000000000000001100000000000000110000000000000011000000B20000000000110000110001000011000011100100001100001110010000110000B30000000000000100001100000010010000110000001001000011000000100100B300000000000000000011000000110000001100000011000000

43、11000000110000(2)求各基本块中各变量引用点的ud链：假设在程序中某点u引用了变量a,则把能到达u的a的所有定值点，称为a在引用点u的引用-定值链(简称ud链)。可以利用到达-定值信息来计算各个变量在任何引用点的ud链。由图9.6的程序流图可知，I的引用点是d3、d5和d6，J的引用点是d3和d8。TOC o 1-5 h zB2中I和J的引用点d前面没有对I和J的定值点，其ud链在INB=d,d,d,d中，所以I在引用点d；的ud链是d1,d6；J在引用点d3的ud链是dd3。36在B2中I的引用点d5前面有I的定值点d4,且在d4定值后到达d5,所以I在引用点d5的ud链是d。B中I的引用点d前面没有I的定值点，其ud链是INB中I的所有定值点，所以是d。B3中J的引用点d6前面没有对J的定值点，其ud链是IN3B中J的所有定值点。已知IN4B=d3,d3,所以，J的引用点d8的ud链是d3。44(3)各基本块出口的活跃变量集V-O