编译原理与技术练习题汇总

《编译原理与技术》练习题 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 ()

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4