编译原理(习题课)(三)

1编译原理朱雪峰博士计算机科学与技术系Tel:89733787(O)Email:xuefeng.zhu@cup.edu.cn2第三十（P218第6题）6.按7.4.2节的办法，写出布尔式Aor(Bandnot(CorD))的四元式序列。34第三十题（P218第6题）1(jnz,A,_,0)2(j,_,_,3)3(jnz,B,_,5)4(j,_,_,0)5(jnz,C,_,0)6(j,_,_,7)7(jnz,D,_,0)8(j,_,_,0)1(jnz,A,_,0)2(j,_,_,3)3(jnz,B,_,5)4(j,_,_,0)5(jnz,C,_,4)6(j,_,_,7)7(jnz,D,_,5)8(j,_,_,1)5第三十一题（P218第7题）7.用7.5.1节的办法，把下面的语句翻译成四元式序列：whileA<CandB<DdoifA=1thenC:=C+1elsewhileA≤DdoA:=A+267第三十一题（P218第7题）四元式序列：1(j<,A,C,0→3)2(j,_,_,0→16)3(j<,B,D,0→5)4(j,_,_,0→16)5(j=,A,1,0→7)6(j,_,_,0→10)7(+,C,1,T1)8(:=,T1,_,C)四元式序列：9(j,_,_,_→1)10(j≤,A,D,0→12)11(j,_,_,0→1)12(+,A,2,T2)13(:=,T2,_,A)14(j,_,_,10)15(j,_,_,1)168第三十二题（P219第12题）12.略（选作，不讲）9第三十三题（P270第9题）9.对于下面的程序，若参数传递的办法分别为(1)传名；(2)传地址；(3)得结果；(4)传值。试问，程序执行时所输出的A分别是什么？procedureP(X,Y,Z);beginY:=Y+1;Z:=Z+X;endP;beginA:=2;B:=3;P(A+B,A,A);printAend10第三十三题（P270第9题）（1）传名A:=2B:=3A:=A+1(A变为3）A:=A+(A+B)(A变为9）因此输出的A值为911第三十三题（P270第9题）（2）传地址因此输出的A值为812第三十三题（P270第9题）（3）得结果因此输出的A值为753XYZ7A+B存放位置A的存放位置A的存放位置13第三十三题（P270第9题）（4）传值由于传值并不改变实参的值，因此输出的A值为214第三十四题（P306第1题）1.试把以下程序划分为基本块并作出其程序流图readCA:=0B:=1L1:A:=A+BIfB≥CgotoL2B:=B+1gotoL1L2:writeAhalt15第三十四题（P306第1题）（1）首先，求出四元式程序中各个基本块的入口语句readCA:=0B:=1L1:A:=A+BIfB≥CgotoL2B:=B+1gotoL1L2:writeAhalt„程序的第一个语句；„能由条件转移语句或无条件转移语句转移到的语句；„紧跟在条件转移语句后面的语句。16第三十四题（P306第1题）（2）对以上求出的每一入口语句，构造其所属的基本块。readCA:=0B:=1L1:A:=A+BIfB≥CgotoL2B:=B+1gotoL1L2:writeAhalt„由该入口语句到另一入口语句（不包括该入口语句）、或到一转移语句（包括该转移语句）、或到一停语句（包括该停语句）之间的语句序列组成的。B1B2B3B417第三十四题（P306第1题）（3）对于划分出来的基本块，我们按照流图画法得到的程序流图如下：„每个流图以基本块为结点。如果一个结点的基本块的入口语句是程序的第一条语句，则称此结点为首结点。如果在某个执行顺序中，基本块B2紧接在基本块B1之后执行，则从B1到B2有一条有向边。18第三十五题（P306第2题）2.试把以下程序划分为基本块并作出其程序流图readA,BF:=1C:=A*AD:=B*BifC<DgotoL1E:=A*AF:=F+1E:=E+FwriteEhltL1:E:=B*BF:=F+2E:=E+FwriteEifE>100gotoL2haltL2:F:=F-1gotoL119第三十五题（P306第2题）（1）求入口语句readA,BreadA,BF:=1F:=1C:=A*AC:=A*AD:=B*BD:=B*BifC<DgotoLifC<DgotoL11E:=A*AF:=F+1E:=E+FwriteEhltL1:E:=B*BF:=F+2E:=E+FwriteEifE>100gotoL2haltL2:F:=F-1gotoL120第三十五题（P306第2题）（2）划分基本块readA,BreadA,BF:=1F:=1C:=A*AC:=A*AD:=B*BD:=B*BifC<DgotoLifC<DgotoL11E:=A*AF:=F+1E:=E+FwriteEhltL1:E:=B*BF:=F+2E:=E+FwriteEifE>100gotoL2haltL2:F:=F-1gotoL1B1B2B3B4B521第三十五题（P306第2题）（3）画数据流图如下：B1B2B3B4B522第三十六题（P306第3题）3.试对以下基本块B1和B2分别应用DAG对它们进行优化，并就以下两种情况分别写出优化后的四元式序列（1）假设只有G、L、M在基本块后面还要被引用；（2）假设只有L在基本块后面还要被引用。B1:A:=B*CD:=B/CE:=A+DF:=2*EG:=B*CH:=G*GF:=H*GL:=FM:=LB2:B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+1K:=B*5L:=K+JM:=L23第三十六题（P306第3题）B1:A:=B*CD:=B/CE:=A+DF:=2*EG:=B*CH:=G*GF:=H*GL:=FM:=L24第三十六题（P306第3题）B2:B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+1K:=B*5L:=K+JM:=L25第三十六题（P306第3题）（1）假设只有G、L、M在基本块后面还要被引用，基本块B1和B2优化后的四元式序列分别如下：B1:G:=B*CH:=G*GL:=H*GM:=LB2:D:=A+CE:=A*CF:=D+EG:=3*FL:=15+FM:=L26第三十六题（P306第3题）（2）假设只有L在基本块后面还要被引用，基本块B1和B2优化后的四元式序列分别如下：B1:G:=B*CH:=G*GL:=H*GB2:D:=A+CE:=A*CF:=D+EL:=15+F27第三十七题（P307第4题）4.对以下四元式程序，对其中的循环进行循环优化。I:=1readJ,KL:A:=K*IB:=J*IC:=A*BwriteCI:=I+1ifI<100gotoLhalt28第三十七题（P307第4题）4.对以下四元式程序，对其中的循环进行循环优化。解：先进行基本块划分，再画程序流图。由于要进行循环优化，于是可考虑代码外提、强度削弱和删除归纳变量等优化。先将程序划分为基本块B1、B2和B3，其程序流图如图1所示，从流图中可知要优化的循环是指基本块B2。对循环B2中的代码分别实行代码外提、强度削弱和删除归纳变量优化如下：（1）代码外提：由于循环中没有不变运算，故此项29第三十七题（P307第4题）4.对以下四元式程序，对其中的循环进行循环优化。（2）强度削弱：由于循环中有A:=K*I和B:=J*I，其中K、J在循环中值不发生改变，I每次增加1。因此对A、B的赋值运算可进行强度削弱，即可将表达式中的乘法运算（*）改为加法运算（+)。强度削弱后的程序流图如图2。（3）删除基本归纳变量：循环中I是基本归纳变量，A、B是与I同族的归纳变量，且有如下线性关系：A:=K*IB:=J*I于是，条件I<100完全可用A<100*K或B<100*J替代。30第三十七题（P307第4题）4.对以下四元式程序，对其中的循环进行循环优化。（3）这样基本块B2中的控制条件和控制语句便可改写为：T1:=100*KifA<T1gotoL’或改写为：T2:=100*JifB<T2gotoL’于是程序流图就变为如图3所示的情况。31第三十七题（P307第4题）4.对以下四元式程序，对其中的循环进行循环优化。（3）控制条件经过以上改变后，就可以删除基本块B2中的语句I:=I+1。又语句T1:=100*K是循环中的不变运算，可从基本块B2中外提到基本块B1中，于是程序流图最后变为如图4所示的形式。32第三十七题（P307第4题）33第三十七题（P307第4题）I:=1readJ,KA:=K*IB:=J*IT1:=100*KL’:C:=A*BwriteCA:=A+KB:=B+JifA<T1gotoL’haltB1B2B3434第三十八题（P307第5题）5.以下程序是某程序的最内循环，试对它进行循环优化A:=0I:=1L1:B:=J+1C:=B+IA:=C+AifI=100gotoL2I:=I+1gotoL1L2:35第三十八题（P307第5题）5.以下程序是某程序的最内循环，试对它进行循环优化解：程序流图如图1所示。流图中有一条回边B3→B2，且B2DOMB3，所以有一个循环{B2,B3}，B2是循环入口结点，也是出口结点。现在对循环{B2,B3}进行优化。①代码外提：对于B2中的赋值四元式B:=J+1，由于循环中没有对J的定值操作，所有对J的定值都在循环外，所以它是循环的不变运算，可以进行代码外提，提到循环外进行计算。36第三十八题（P307第5题）5.以下程序是某程序的最内循环，试对它进行循环优化②删除归纳变量：循环中I是基本归纳变量，C是与I同族的归纳变量，且两者有如下的线性关系：C:=B+I。于是，条件I=100完全可以用C=B+100替代，相应的I:=I+1可用C:=C+1替代。再将新出现的不变运算提到循环外。优化后的程序流图如图2所示。37第三十八题（P307第5题）A:=0I=1L1:B:=J+1C:=B+IA:=C+AifI=100gotoL2L2:B1B2B31I:=I+1gotoL1B4A:=0I=1B:=J+1C:=B+IR:=B+100L1':A:=C+AifC=RgotoL2L2:B1B2B32C:=C+1gotoL1'B438第三十九题（P327第1题）1.对以下中间代码序列G:T1:=B-CT2:=A*T1T3:=D+1T4:=E-FT5:=T3*T4W:=T2/T5假设可用寄存器为R0和R1，W是基本块出口的活跃变量，用简单代码生成算法生成其目标代码，同时列出代码生成过程中的寄存器描述和地址描述。39第三十九题（P327第1题）AVALUE{T3}={R0}AVALUE{T2}={R1}RVALUE{R0}={T3}RVALUE{R1}={T2}LDR0,DADDR0,1T3:=D+1AVALUE{T1}={R0}AVALUE{T2}={R1}RVALUE{R0}={T1}RVALUE{R1}={T2}LDR1,AMULR1,R0T2:=A*T1AVALUE{T1}={R0}T1在R0中RVALUE{R0}={T1}R0含有T1LDR0,BSUBR0,CT1:=B-CAVALUERVALUE目标代码四元式40第三十九题（P327第1题）AVALUE{T2}={T2}AVALUE{T3}={R0}AVALUE{T4}={R1}RVALUE{R0}={T3}RVALUE{R1}={T4}STR1,T2LDR1,ESUBR1,FT4:=E-FAVALUE{T2}={T2}AVALUE{T5}={R0}AVALUE{T4}={R1}RVALUE{R0}={T5}RVALUE{R1}={T4}MULR0,R1T5:=T3*T4AVALUE{T2}={T2}AVALUE{T5}={R0}AVALUE{W}={R1}RVALUE{R0}={T5}RVALUE{R1}={W}LDR1,T2DIVR1,R0W:=T2/T5STR1,W