《编译原理与技术》练习题 26
repeat S until E;
《编译原理与技术》练习题 27
练习 10
10.1 一个编译程序的代码生成工作需要考虑哪些因素？ 10.2 利用语法制导的翻译技术把下列程序段翻译成目标代码： (1) x := (a+b)*c ? a (2) a > b and c＝d or e < f
10.2 请把以下程序划分为基本块并作出其程序流图。
read C A := 0 B:= 1
L1: A := A + B
if B ?C gogo L2 B := B + 1 goto L1
L2: write A
10.3请把以下程序划分为基本块并作出其程序流图。
i := m j := n a := u1
L1: i := i + 1
j := j – 1 if i > j goto L2 a := u2
L2: i := u3
goto L1
10.4 对下列中间代码序列
《编译原理与技术》练习题 28
(1) T1 := B – C
T2 := A?T1 T3 := D + 1 T4 := E – F T5 := T3?T4 W := T2/T5
W是基本块出口的活跃变量
(2) T1 := A + B
T2 := T1– C T3 := T2 ?T1 T4 := T1 + T3 T5 := T3 – E E := T4?T5
F是基本块出口的活跃变量
假设可用寄存器为R0和R1，用简单代码生成算法生成目标代码，同时列出代码生成过程中的寄存器
描述和地址描述。对于（2）小题，如果只有一个寄存器R0可用，结果如何？
10.5 对于下列基本块, 假设只有寄存器R1和R2可用，开始的时候没有值在寄存器中，A和B的值
在内存中，L是基本块出口的活跃变量，而且假设目标代码的算术运算不满足交换率。请用简单代码生成算法生成其目标代码，同时列出代码生成过程中的寄存器描述和地址描述。 T1 := A－B T2 := A / T1 T3 := 3?T1 L := T3＋T2
10.6 分别把下列C语句首先转换成三地址代码，然后产生目标代码，假定三个可用的寄存器R0，
R1和R2。
（1）X = A [i] +1 （2）A[i] = B[C[i]] （3）A[i] = A[i] + A[j]
（4）if (i > j ) A = j + 1; else A = i + 1;
《编译原理与技术》练习题 29
练习 11
11.1 何谓代码优化？代码优化需要什么样的基础？ 11.2 编译过程中可以进行的优化是如何分类的？ 11.3 常用的代码优化技术有哪些？
11.4 使用基本的代码优化技术对下面的代码进行优化：
x = 1; ... y = 0; ...
if (y ) x := 0; ... if (x) y = 1; ...
11.5 对以下基本块B1和B2：
B1: 1. A := B?C
2. D := B/C 3. E := A+D 4. F := 2?E 5. G := B?C 6. H := G?G 7. F := H?G 8. L := F 9. M := L
B2: 1. B := 3
2. D := A+C 3. E := A?C 4. F := D+E 5. G :=B?F 6. H := A+C 7. I := A?C 8. J := H+I 9. K := B?5 10. L := K+J 11. M := L
分别构造出DAG，然后应用DAG就以下两种情况分别写出优化后的三地址中间代码： （1）假设变量G、L和M在基本块之后还要被引用；
《编译原理与技术》练习题 30
（2）假设只有变量L在基本块之后还要被引用。 11.6 下面的C语言程序
p = 0;
for ( i = 0; i<= 20; i ++ ) { p = p + a[i] ?b[i] };
经过编译得到的中间代码如下
(1) p := 0 (2) i := 1 (3) t1 := 4?i (4) t2 := addr(a) ? 4 (5) t3 := t2[t1] (6) t4 := 4?i (7) t5 := addr(b) ? 4 (8) t6 := t5[t4] (9) t7 := t3?t6 (10) p := p + t7 (11) i := i + 1 (12) if i ? 20 goto (3)
（1）把上述三地址程序划分为基本块并做出流图。 （2）将每个基本块的公共子表达式删除。
（3）找出流图中的循环，将循环不变量计算移出循环。 （4）找出每个循环中的归纳变量，并在可能之处删除它们。
11.7 请用窥孔优化技术对下列指令进行优化，其中R1和R2不一定是同一寄存器。
MOV R1, L MOV L, R1
11.8 窥孔优化经常使用模式变量描述，用一条规则表示一类优化，例如
MUL #2, %R ? ADD %R, %R
表示任何寄存器乘以2都可以用寄存器自身的加法代替（这里，用%R匹配任意的寄存器）。请考虑
如何在窥孔优化器中实现这种模式匹配。
11.9 请利用代码优化的思想（代码外提和强度消弱），优化下列C语言程序，写出优化后的C程序。
main ()