编译原理习题课三.pdf

1 编译原理 朱雪峰朱雪峰博士博士 计算机科学与技术系计算机科学与技术系 Tel: 89733787(O) Email: xuefeng.zhu 2 第三十题（第三十题（ P218 第第6题）题） 6.按7.4.2节的办法，写出布尔式A or (B and not (C or D)的四元式序列。 3 4 第三十题（第三十题（ 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节的办法，把下面的语句翻译成四元式 序列： while AC and BD do if A=1 then C:=C+1 else while AD do A:=A+2 6 7 第三十一题（第三十一题（ P218 第第7题）题） 四元式序列： 1 (j, A, C, 03) 2 (j, _, _, 016) 3 (j, B, D,05) 4 (j, _, _, 016) 5 (j=, A, 1, 07) 6 (j, _, _, 010) 7 (+, C, 1, T1) 8 (:=, T1, _, C) 四元式序列： 9 (j, _, _, _ 1) 10 (j, A, D, 012) 11 (j, _, _, 01) 12 (+, A, 2, T2) 13 (:=, T2, _, A) 14 (j, _,_, 10) 15 (j, _, _, 1) 16 8 第三十二题（第三十二题（ P219 第第12题）题） 12. 略（选作，不讲） 9 第三十三题（第三十三题（ P270 第第9题）题） 9.对于下面的程序，若参数传递的办法分别为(1)传名；(2) 传地址；(3)得结果；(4)传值。试问，程序执行时所输出 的A分别是什么？ procedure P (X, Y, Z); begin Y:=Y+1; Z:=Z+X; end P; begin A:=2; B:=3; P(A+B,A,A); print A end 10 第三十三题（第三十三题（ P270 第第9题）题） （1）传名 A:=2 B:=3 A:=A+1(A变为3） A:=A+(A+B)(A变为9） 因此输出的A值为9 11 第三十三题（第三十三题（ P270 第第9题）题） （2）传地址 因此输出的A值为8 12 第三十三题（第三十三题（ P270 第第9题）题） （3）得结果 因此输出的A值为7 5 3 X Y Z 7 A+B存放位置 A的存放位置 A的存放位置 13 第三十三题（第三十三题（ P270 第第9题）题） （4）传值 由于传值并不改变实参的值，因此输出的A 值为2 14 第三十四题（第三十四题（ P306 第第1题）题） 1.试把以下程序划分为基本块并作出其程序流图 read C A:=0 B:=1 L1 : A:=A+B If BC goto L2 B:=B+1 goto L1 L2 : write A halt 15 第三十四题（第三十四题（ P306 第第1题）题） （1）首先，求出四元式程序中各个基本块的入口语句 read C A:=0 B:=1 L1 : A:=A+B If BC goto L2 B:=B+1 goto L1 L2 : write A halt ?程序的第一个语句；程序的第一个语句； ?能由条件转移语句或无条件转移语句 转移到的语句； 能由条件转移语句或无条件转移语句 转移到的语句； ?紧跟在条件转移语句后面的语句。紧跟在条件转移语句后面的语句。 16 第三十四题（第三十四题（ P306 第第1题）题） （2）对以上求出的每一入口语句，构造其所属的基本块。 read C A:=0 B:=1 L1 : A:=A+B If BC goto L2 B:=B+1 goto L1 L2 : write A halt ?由该入口语句到另一入口语 句（不包括该入口语句）、 或到一转移语句（包括该转 移语句）、或到一停语句 （包括该停语句）之间的语 句序列组成的。 由该入口语句到另一入口语 句（不包括该入口语句）、 或到一转移语句（包括该转 移语句）、或到一停语句 （包括该停语句）之间的语 句序列组成的。 B1 B2 B3 B4 17 第三十四题（第三十四题（ P306 第第1题）题） （3）对于划分出来的基本块，我们按 照流图画法得到的程序流图如下 ： ?每个流图以基本块为结点。如果一个 结点的基本块的入口语句是程序的第 一条语句，则称此结点为首结点。如 果在某个执行顺序中，基本块 每个流图以基本块为结点。如果一个 结点的基本块的入口语句是程序的第 一条语句，则称此结点为首结点。如 果在某个执行顺序中，基本块B2紧接 在基本块 紧接 在基本块B1之后执行，则从之后执行，则从B1到到B2有 一条有向边。 有 一条有向边。 18 第三十五题（第三十五题（ P306 第第2题）题） 2.试把以下程序划分为基本块并作出其程序流图 read A,B F:=1 C:=A*A D:=B*B if C100 goto L2 halt L2: F:=F-1 goto L1 19 第三十五题（第三十五题（ P306 第第2题）题） （1）求入口语句 read A,Bread A,B F:=1F:=1 C:=A*AC:=A*A D:=B*BD:=B*B if CD goto Lif C100 goto L2 halt L2: F:=F-1 goto L1 20 第三十五题（第三十五题（ P306 第第2题）题） （2）划分基本块 read A,Bread A,B F:=1F:=1 C:=A*AC:=A*A D:=B*BD:=B*B if CD goto Lif C100 goto L2 halt L2: F:=F-1 goto L1 B1 B2 B3 B4 B5 21 第三十五题（第三十五题（ P306 第第2题）题） （3）画数据流图如下： B1 B2B3 B4B5 22 第三十六题（第三十六题（ P306 第第3题）题） 3.试对以下基本块B1和 B2分别应用DAG对它 们进行优化，并就以 下两种情况分别写出 优化后的四元式序列 （1）假设只有G、L、 M在基本块后面还要被 引用；（2）假设只有 L在基本块后面还要被 引用。 B1: A:=B*C D:=B/C E:=A+D F:=2*E G:=B*C H:=G*G F:=H*G L:=F M:=L B2: B:=3 D:=A+C E:=A*C F:=D+E G:=B*F H:=A+C I:=A*C J:=H+1 K:=B*5 L:=K+J M:=L 23 第三十六题（第三十六题（ P306 第第3题）题） B1: A:=B*C D:=B/C E:=A+D F:=2*E G:=B*C H:=G*G F:=H*G L:=F M:=L 24 第三十六题（第三十六题（ P306 第第3题）题） B2: B:=3 D:=A+C E:=A*C F:=D+E G:=B*F H:=A+C I:=A*C J:=H+1 K:=B*5 L:=K+J M:=L 25 第三十六题（第三十六题（ P306 第第3题）题） （1）假设只有G、L、M在基本块 后面还要被引用 ，基本块B1 和B2优化后的四元式序列分 别如下： B1: G:=B*C H:=G*G L:=H*G M:=L B2: D:=A+C E:=A*C F:=D+E G:=3*F L:=15+F M:=L 26 第三十六题（第三十六题（ P306 第第3题）题） （2）假设只有L在基本块后面还 要被引用，基本块B1和B2优 化后的四元式序列分别如下 ： B1: G:=B*C H:=G*G L:=H*G B2: D:=A+C E:=A*C F:=D+E L:=15+F 27 第三十七题（第三十七题（ P307 第第4题）题） 4.对以下四元式程序，对其中的循环进行循环优化。 I:=1 read J,K L : A:=K*I B:=J*I C:=A*B write C I:=I+1 if I100 goto L halt 28 第三十七题（第三十七题（ 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*I B:=J*I 于是，条件I100完全可用A100*K或B100*J替代。 30 第三十七题（第三十七题（ P307 第第4题）题） 4.对以下四元式程序，对其中的循环进行循环优化。 （3）这样基本块B2中的控制条件和控制语句便可改写为 ： T1:=100*K if AT1 goto L 或改写为： T2:=100*J if BT2 goto L 于是程序流图就变为如图3所示的情况。 31 第三十七题（第三十七题（ P307 第第4题）题） 4.对以下四元式程序，对其中的循环进行循环优化。 （3）控制条件经过以上改变后，就可以删除基本块B2中 的语句I:=I+1。又语句T1:=100*K是循环中的不变运算 ，可从基本块B2中外提到基本块B1中，于是程序流图 最后变为如图4所示的形式。 32 第三十七题（第三十七题（ P307 第第4题）题） 33 第三十七题（第三十七题（ P307 第第4题）题） I:=1 read J, K A:=K*I B:=J*I T1:=100*K L: C:=A*B write C A:=A+ K B:=B+J if AT1 goto L halt B1 B2 B3 4 34 第三十八题（第三十八题（ P307 第第5题）题） 5.以下程序是某程序的最内循环，试对它进行循环优化 A:=0 I:=1 L1 : B:=J+1 C:=B+I A:=C+A if I=100 goto L2 I:=I+1 goto L1 L2 : 35 第三十八题（第三十八题（ P307 第第5题）题） 5.以下程序是某程序的最内循环，试对它进行循环优化 解：程序流图如图1所示。流图中有一条回边B3B2，且B2 DOM B3，所以有一个循环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:=0 I=1 L1 : B:=J+1 C:=B+I A:=C+A if I=100 goto L2 L2: B1 B2 B3 1 I:=I+1 goto L1 B4 A:=0 I=1 B:=J+1 C:=B+I R:=B+100 L1 : A:=C+A if C=R goto L2 L2: B1 B2 B3 2 C:=C+1 goto L1 B4 38 第三十九题（第三十九题（ P327 第第1题）题） 1.对以下中间代码序列G: T1:=B-C T2:=A*T1T3:=D+1 T4:=E-F T5:=T3*T4W:=T2/T5 假设可用寄存器为R0和R1，W是基本块出口的 活跃变量，用简单代码生成算法生