资源描述
平时作业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 (k0）。则 SS10|S21，|S1|=2k (k0），|S2|=2k (k0）。且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(01*0)1|0)*2 给出接受下列在字母表0,1上的语言的DFA。(1)所有以00结束的符号串的集合。(2)所有具有3个0的符号串的集合。答：(1) DFAM=(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* DFAM=(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 )* ;请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。答：D T L ; T int | floatL L, id | id4 试分析下面给出的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分析表。EE+T|T TTF|F FF*|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)如下:I0 = EE, EE+T, ET, TTF, TF, FF*,Fa, Fb I1 = EE, EE+TI2 = ET, TTF, FF*, Fa, FbI3 = TF, FF* I4 = Fa I5 = Fb I6 = EE+T, TTF, TF, FF*, Fa, Fb I7 = TTF, FF* I8 = FF*I9 = EE+T, TTF, FF*, Fa, Fb求FOLLOW集：FOLLOW(E)=, FOLLOW(T)=, , a, bFOLLOW(F)=, , a, b, *构造的SLR分析表如下： 显然，此分析表无多重定义入口，所以此文法是SLR文法。6 为下面的文法构造LALR(1)分析表SE EE+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)如下: I0 = SS, $, SE, $, EE+T, $/+, ET, $/+,T(E), $/+, Ta, $/+ I1 = SS, $ I2 = SE, $, EE+T, $/+ I3 = ET, $/+I4 = T(E), $/+, EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+ I5 = Ta, $/+ I6 = EE+T, $/+, T(E), $/+, Ta, $/+I7 = T(E), $/+, EE+T, )/+ I8 = ET, )/+I9 = T(E), )/+, EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+I10 = Ta, )/+ I11 = EE+T, $/+ I12 = T(E), $/+I13 = EE+T, )/+, T(E), )/+, Ta, )/+ I14 = T(E), )/+, EE+T, )/+I15 = EE+T, )/+ I16 = T(E), )/+合并同心的LR(1)项目集，得到LALR的项目集和转移函数如下： I0 = SS, $, SE, $, EE+T, $/+, ET, $/+, T(E), $/+, Ta, $/+I1 = SS, $ I2 = SE, $, EE+T, $/+ I3,8 = ET, $/+/)I4,9 = T(E), $/+/), EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+I5,10 = Ta, $/+/) I6,13 = EE+T, $/+/), T(E), $/+/), Ta, $/+/)I7,14 = T(E), $/+/), EE+T, )/+ I11,15 = EE+T, $/+/) I12,16 = T(E) , $/+/)LALR分析表如下：7 （1）通过构造识别活前缀的DFA和构造分析表，来证明文法E E + id | id是SLR(1)文法。答：先给出接受该文法活前缀的DFA如下：E EE E + idE idI0E EE E+ idI1E idI2Eid+E E +idI3E E + idI4id再构造SLR分析表如下：状态 动作转移 id + $ E 0 s2 1 1 s3 acc 2 r2 r2 3 s4 4 r1 r1 表中没有多重定义的条目，因此该文法是SLR(1)的。（2）下面左右两个文法都和（1）的文法等价E E + M id | idE M E + id | idM eM e请指出其中有几个文法不是LR(1)文法，并给出它们不是LR(1)文法的理由。答：只有文法E M E + id | idM e不是LR(1)文法。因为对于句子id+id+id来说，分析器在面临第一个id时需要做的空归约次数和句子中+id的个数一样多，而此时句子中+id的个数是未知的。8根据自上而下的语法分析方法，构造下面文法的LL（1）分析表。D TLT int | realL id RR , id R | e答：先计算FIRST和FOLLOWFIRST(D) = FIRST(T) = int,realFIRST(L) = id FIRST(R) = ,FOLLOW(D) = FOLLOW(L) = $FOLLOW(T) = idFOLLOW(R) = $LL(1)分析表如下：intrealid,$DD - TLD - TLTT - intT - realLL - idRRR - ,idRR - 9 下面的文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时，结果仍为整数，否则就是实数。 EE+T|T Tnum.num|num （a）给出一个语法制导定义以确定每个子表达式的类型。 （b）扩充（a）中的语法制导定义把表达式翻译成前缀形式，并且决定类型。使用一元算符inttoreal把整型值转换成相等的实型值，以使得前缀形式中的+的两个操作对象是同类型的。答： (a):产生式语义规则EE1+TIF (E1.type=integer) and (T.type=integer) THEN E.type:=integerELSE E.type:=realETE.type:=T.typeTnum.numT.type:=realTnumT.type:=integer(b):产生式语义规则EE1+TIF (E1.type=integer) and (T.type=integer) THEN BEGIN E.type:=integer Print(+,E1.val,T.val) ENDELSE BEGIN E.type:=real IF E1.type=integer THEN Begin E1.type:=realE1.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)ENDETE.type:=T.typeE.val:=T.valTnum.numT.type:=realT.val:=num.num.lexvalTnumT.type:=integerT.val:=num.lexval10 假设说明是由下列文法产生的： Did L L,id L|:T Tinteger |real （a）建立一个翻译模式，把每一个标识符的类型加入到符号表中。 （b）从（a）中的翻译模式构造一个预翻译程序。 答： (a)：产生式翻译模式Did LD.Type:=L.Typeaddtype(id.entry, D.type)L,id L1L.Type:=L1.Typeaddtype(id.entry, L.type)L:TL.type:=T.typeTintegerT.type:=integerTrealT.type:=real(b)：Procedure D;beginIf lookahead=id then BeginMatch(id);D.type=L;addtype(id.entry,D.type) endelse errorendFunction L: DataType;BeginIf 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 EndElse if lookahead=: thenBeginMatch(:);L.Type=T;return(L.Type)endelse errorEndFunction T: DataType;BeginIf lookahead=integer thenBeginMatch(integer);return(integer)endelse If lookahead=real thenBeginMatch(real);return(real)endelse errorend11为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号（即值大于零还是小于零）记录在属性E.sign中（属性值分别用POS或NEG表示）。你可以假定所有的整数都不为零，这样就不用担心零的符号。E E *E | +E | -E | unsigned_integer答：E E1 *E2if 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 := POSE unsigned_integer E.sign := POS12为下面文法写一个语法制导的定义，用S的综合属性val给出下面文法中S产生的二进制数的值。例如，输入101.101时，S. val := 5.625。（不得修改文法。）S L . R | LL L B | BR B R | BB 0 | 1答：S L . RS. val := L. val + R. val S 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）引用调用（call-by-reference）； （c）复制恢复（copy-restore）； （d）传名调用（call-by-name）。 program main(input,output）； procedure p（x,y,z）； begin y：y1； z：zx； end； begin a：2； b：3； p(ab,a,a)； print a end.答：1)传地址：所谓传地址是指把实在参数的地址传递给相应的形式参数。在过程段中每个形式参数都有一对应的单元，称为形式单元。形式单元将用来存放相应的实在参数的地址。当调用一个过程时，调用段必须领先把实在参数的地址传递到一个为被调用段可以拿得到的地方。当程序控制转入被调用段之后，被调用段首先把实参地址捎进自己相应的形式单元中，过程体对形式参数的任何引用1或赋值都被处理成对形式单元的间接访问。当调用段工作完毕返回时，形式单元(它们都是指示器)所指的实在参数单元就持有所指望的值。 2)传结果：和“传地址”相似(但不等价)的另一种参数传递力法是所谓“传结果”。这种方法的实质是，每个形式参数对应有两个申元，第1个单元存放实参的地址，第2个单元存放实参的值。在过程体中对形参的任何引用或赋值都看成是对它的第2个单元的直接访问。但在过程工作完毕返回前必须把第2个单元的内容行放到第1个单元所指的那个实参单元之中。 3)传值：所谓传值，是一种简单的参数传递方法。调用段把实在参数的值计算出来并存放在一个被调用段可以拿得到的地方。被调用段开始丁作时，首先把这些值抄入形式中元中，然后就好像使用局部名一样使用这些形式单元。如果实在参数不为指示器，那末，在被调用段中无法改变实参的值。 4)传名：所谓传名，是一种特殊的形实参数结合方式。解释“传名”参数的意义：过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实在参数(文字替换)。它与采用“传地址”或“传值”的方式所产生的结果均不相同。 (a)2； (b)8； (c)7； (d)9。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答： envcontrol linkaccess linkacontrol linkaccess linkx bcontrol linkaccess link ccontrol linkaccess link bcontrol linkaccess link caccess linkcontrol 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, &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(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类型的数据传递到被调用函数。被调用函数根据形式参数所声明的类型，决定是否要将实在参数向低级别类型转换。低地址放高位高地址放低位shortlong图5.2 长整型和短整型在本例中，long类型数据占4个字节，而short类型数据只占2个字节。因此被调用函数把实在参数的低位字节的内容当成是自己所需的数据，见图5.2注意，对于SUN工作站来说，低地址存放整型数据的高位。floatdoublee图5.3 双精度型和浮点型对于实型来说。double类型是8个字节，而float类型4个字节。被调用函数把实在参数的前4个字节作为自己所需的数据，因为double后面4个字节的内容都是为了增加精度用的，见图5.3。e，8个字节在main函数中参数压栈时的观点在func函数中存取形式参数时的观点4个字节，起始地址357777725544个字节，起始地址357777725442个字节，起始地址357777725422个字节，起始地址35777772536f，8个字节j，4个字节i，4个字节栈的增长方向图5.4 参数在栈中的情况这样在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;case INT:if (ty-size size)return inttype;break;case UNSIGNED:if (ty-size size)return inttype;break;case FLOAT:if (ty-size size)return doubletype;return ty;16 试把下列C语言程序的可执行语句翻译为(a)一棵语法树， (b)后缀式， (c)三地址代码。main() int i; int a10; while (i=10) ai=0;while答：(a).一棵语法树赋值表达式布尔表达式表达式表达式数组元素表达式=下标表达式110a01(b) 后缀式为： i 10= a i 0 = while从理论上可以说while(i=10) ai=0; 的后缀式如上面表示。但若这样表示，在执行while操作时，赋值语句已经执行，这显然与语义不符，因此改为：i 10 =BM a i 0 = BRL其中BM操作为当表达式为假时转向，BRL是一个一目运算，无条件转向。(c) 三地址代码序列为：100 if i = 10 got 102101 goto 106102 t1:=4*i103 t2:=a104 t2t1:=0105 goto 10010617Pascal语言中，语句： for v：initial to final do stmt 与下列代码序列有相同含义begin t1:=initial;t2:=final; if t1=t2 then begin v:=t1; stmt while vt2 do begin v：=succ（v)； stmt end endend (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 语法制导定义如下： 产生式 动作 Sfor 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) Ev:=initial to final E.init := initial.place E.final := final.place18对于下面C语言文件s.c f1(int x)long 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考虑一个简单语言，其中所有的变量都是整型（不需要显式声明），并且仅包含赋值语句、读语句和写语句。下面的产生式定义了该语言的语法（其中lit表示整型常量；OP的产生式没有给出，因为它和下面讨论的问题无关）。ProgramStmtListStmtList Stmt StmtList | StmtStmtid := Exp; | read (id ); | write ( Exp ); Expid | lit | Exp OP Exp我们把不影响write语句输出值的赋值（包括通过read语句来赋值）称为无用赋值，写一个语法指导定义，它确定一个程序中出现过赋予无用值的变量集合（不需要知道无用赋值的位置）和没有置初值的变量集合（不影响write语句输出值的未置初值变量不在考虑之中）。非终结符StmtList和Stmt用下面3个属性（你根据需要来定义其它文法符号的属性）：（1）uses_in：在本语句表或语句入口点的引用变量集合，它们的值影响在该程序点后的输出。（2）uses_out：在本语句表或语句出口点的引用变量集合，它们的值影响在该程序点后的输出。（3）useless：本语句表或语句中出现的无用赋值变量集合。答：Exp的属性uses表示它引用的变量集合。Program的useless和no_initial分别表示程序的无用赋值变量集合和未置初值变量集合。Program StmtList StmtList.uses_out:=; Program.useless := StmtList.useless;Program.no_initial := StmtList.uses_in;StmtList Stmt StmtList1 StmtList1.uses_out := StmtList.uses_out;Stmt.uses_out := StmtList1.uses_in;StmtList.uses_in := Stmt.uses_inStmtList.useless := StmtList1.useless Stmt.useless;StmtList StmtStmt.uses_out := StmlList.uses_out;StmlList.uses_in := Stmt.uses_in;StmtList.useless := Stmt.uselessStmt id := Exp; Stmt.useless :=if id.lexemeStmt.uses_out then elseid.lexeme; Stmt.uses_in := if id.lexemeStmt.uses_out then (Stmt.uses_outid.lexeme)Exp.uses else Stmt.uses_outStmt read (id ); Stmt.useless:=if id.lexemeStmt.uses_out then elseid.lexeme;Stmt.uses_in := Stmt.uses_out id.lexemeStmt write ( Exp );Stmt.useless := , Stmt.uses_in := Stmt.uses_out Exp.usesExp idExp.uses:= id.lexemeExp litExp.uses:= Exp Exp1 OP Exp2Exp.uses:= Exp1.uses Exp2.uses20 为下列C程序生成目标代码。main()int i;int a10;while(i=10) ai=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 答：程序的流图如下22 试求出如下四元式程序中的循环并进行循环优化. I := 1 read J, K L: A := K * I B := J * I C := A * B write C I := I + 1 if I B2，相应的循环是B2。 （1）代码外提：由于循环中没有不变运算，故不做此项优化 （2）强度削弱：B2中A和B都是I的归纳变量。优化结果显示在图9.4(2)中。 （3）删除归纳变量：变换循环控制条件，删除归纳变量I后的流图显示在图9.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） （2）14237865b := 1b := 2if w = x goto L2（1）e := bgoto 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）（3） 结点5、7和3构成一个循环，其中5是入口结点。24 对下面的程序片段作出其程序流图并计算：（1）各基本块的到达_定值集INB；（2）各基本块中各变量引用点的ud链；（3）各基本块出口的活跃变量集V_OUTB；（4）各基本块中变量定值点的du链。 I := 1 J := 0 L1: J := J + I read I if I 100 goto L2 write J halt L2 : I := I * I答：本题程序的程序流图如图9.6(1)所示。 （1）计算各基本块的到达-定值集INB。公式为： INB = OUTP PPB OUTB = GENB ( INB - KILLB ) GENB和KILLB由程序流图直接求出，显示在表9.6(1)中。 表9.6(1) 基本块GENB位向量KILLB位向量B1 d1, d2 11000000 d3, d4, d6 00110100B2 d3, d4 00110000 d1, d2, d6 11000100B3 d6 00000100 d1, d4 10010000B4 00000000 00000000 求各基本块到达-定值的初值及各遍的执行结果显示在表9.6(2)中。表9.6(2)基本块初值第一遍后第二遍后第三遍后INBOUTBINBOUTBINBOUTBINBOUTBB10000000011000000000000001100000000000000110000000000000011000000B20000000000110000110001000011000011100100001100001110010000110000B30000000000000100001100000010010000110000001001000011000000100100B40000000000000000001100000011000000110000001100000011000000110000（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链在INB2= 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链是INB3中I的所有定值点，所以是 d4 。 B4中J的引用点d8前面没有对J的定值点，其ud链是INB4中J的所有定值点。已知INB4 = d3, d4 ，所以，J的引用点d8的ud链是 d3 。（3）各基本块出口的活跃变量集v-OUTB： 对程序中某变量a和某点P，如果存在一条从P开始的道路，其中引用了a在P点的值，则称a在点P是活跃的。计算公式如下： V_INB = USEB ( V_OUTB - DEFB ) V_OUTB = V_INS SSB其中，SB是B的所有后继块组成的集合。 DEFB和USEB可以从给定流图直接求出。从图9.6(1)的流图中求出的各基本块的DEFB和USEB显示在表9.6(3)中。表9.6(3) 基本块USEBDEFBB1 I, J B2 I, J B3 I B4 J 计算次序为B4, B3, B2, B1，各次迭代结果显示在表9.6(4)中。表9.6(4) 基本块第一次迭代后第二次迭代后第三次迭代后V_INBV_OUTBV_INBV_OUTBV_INBV_OUTBB1 I, J I, J I, J B2 I, J I, J I, J I, J I, J I, J B3 I I, J I, J I, J I, J B4 J J J （4）各基本块变量定值点的du链 一个变量a在某点P定值后该定值到达a的那些引用点成为该定值点的定值-引用链（简称du链）。使用下面的方程式进行计算： D_INB = D_USEB ( D_OUTB - D_DEF
展开阅读全文