编译原理复习资料

编译原理复习资料

1、某操作系统下合法的文件名为：device:name.extension，其中第一部分（device:）和第三部分（.extension）可缺省，若device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的DFA。用标记d表示任意字母。

d d

d d : . d . 1 2 3 4 5 6

.

图1 接受文件名的DFA

2、用两个不同最左推导来说明下面的文法是二义的。 S ? A S | b A ? S A | a 答：句型aSAS的两个不同最左推导如下：

d start

S ? AS ? aS ? aAS ? aSAS S ? AS ? SAS ? ASAS ? aSAS 3、证明下面的文法

S ? S A | A A ? a

不是LL(1)文法，但是SLR(1)文法，并画出SLR(1)分析表。

答：该文法的第一个产生式表现出直接左递归，因此该文法不是LL(1)。

接受该文法的活前缀的DFA见下面右边；Follow(S?) = {$}，Follow(S) = {$, a}，Follow(A) = {$, a}；SLR(1)分析表见下面左边。该表无冲突，所以该文法是SLR(1)的。

动作 状态 0 1 2 3 4 a $ s3 s3 acc r2 r2 r3 r3 r1 r1 转移 S A 1 2 4 1

S? ? · S SA S ? ·S ? · A A ? · a I0 A S ? A · I2 S S? ? S · S ? S · A A ? · a I1 a A ? a · I3 A S ? SA · I4

a 4、用SLR(1)文法能定义的语言集合、用LR(1)文法能定义的语言集合和用LALR(1)文法能定义的语言集合之间有什么关系？

答：用SLR(1)文法能定义的语言集合 ? 用LALR(1)文法能定义的语言集合， 用LALR(1)文法能定义的语言集合 ? 用LR(1)文法能定义的语言集合。 5、下面是int i, j, k这样的类型声明的两种不同语法：

D ? T L D ? T L T ? int | real T ? int | real L ? L , id | id L ? id , L | id 如果用LL(1)分析方法，应该选择哪个文法？如果用某种LR分析方法，选择哪个文法更好？简要说明理由。

答：对于LL(1)分析方法，两个文法都不合适，左边的文法是左递归的，右边文法有公共左因子。修改右边文法来适应LL(1)分析的要求，相对来说比较容易一些，因为只要提公共左因子。

对于LR的各种分析方法，两个文法都适用，但是采用左边的文法更好一些。用左边的文法时，分析器一边扫描一边归约，占用分析栈的空间较少。而用右边的文法时，分析器要把所有的标识符都移进栈后才进行归约，因此使用较多的分析栈空间。（结合语法制导的翻译，采用左边的文法还有好处：便于确定T的类型属性在栈中的位置。）

6、在C语言中，3++和( id + id )++这样的表达式被编译时，编译器都会报告如下的错误： invalid lvalue in increment

说明左值不能为数值或表达式。现有如下简化的C语言表达式文法： E ? E + E | ( E ) | E ++ | id | num

请写一个语法制导定义或翻译方案，检查++的运算对象是否合法。

答：给非终结符E一个综合属性v，其值可取lvalue或rvalue，分别表示E是左值标识符和右值表达式，那么语法制导定义如下（无输出则表示无错）： E? ? E E ? E1 + E2 E.v := rvalue E ? ( E1 ) E.v := E1.v E ? E1 ++ if E1.v = rvalue then printf(“invalid lvalue in increment”);

E.v := rvalue E ? id E ? num 7、 E ? E+T | T

E.v := lvalue E.v := rvalue

T ? num.num | num

给出一个语法制导定义以确定每个子表达式的类型int/real。

2

答：E ? E1+T { if ( E1.type=real or T.type=real )

then E.type=real else E.type=integer } E ? T { E.type = T.type;} T ? num.num {T.type = real;}

T ? num {T.type = integer;} 8、把下列C语言程序的可执行语句翻译为：

main()

{int i; int a[10]; while (i<=10) a[i] = 0; } (a) 三地址代码 (b) 后缀式

答：(a) L0: if i<=10 goto L1 goto L2 L1: a[i]:=0

goto L0 L2:

(b) 后缀式：i 10 <= a[i] 0 assign while

9、 试构造下面的程序的流图，并找出其中所有回边及循环。 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

3

答: 程序的流图如下

10、 对本题中所示的流图，求出其各结点n的控制结点集D(n)、回边及循环（n0为首结点）。 答：各结点n的控制结点集D(n)如下： D(n0) = {n0} D(n1) = {n0, n1} D(n2) = {n0, n1, n2} D(n3) = {n0, n1, n2, n3} D(n4) = {n0, n1, n2, n4} D(n5) = {n0, n1, n2, n5} D(n6) = {n0, n1, n2, n5, n6} D(n7) = {n0, n1, n2, n5, n6, n7} 回边和循环：

因为 D(n5) = {n0, n1, n2, n5} ，且 n5 -> n2，所以 n5 -> n2为一条回边。根据它求出的循环 L1 = {n2, n5, n3, n4}。

因为D(n6) = {n0, n1, n2, n5, n6} ，且 n6 -> n1，所以n6 -> n1为一条回边。根据这条回边，求出的循环 L2 = {n6, n1, n5, n3, n4, n2}。 11、 考虑下面求矩阵A、B成绩的程序片段：

BEGIN

FOR i := 1 TO n DO

FOR j := 1 TO n DO FOR k = 1 TO n DO

c[i, j] := c[i, j] + A[i, k} * B[k, j] END

（1） 假定对数组A、B、C采用静态存储分配，每个字占用4个字节，存储器以字节为单

位编址。给出该程序的三地址代码序列。 （2）构造该程序相应的流图。

4

（3）删除流图中各基本块内的公共子表达式

（4）指出流图中所有回边及其相应循环，并且进行循环优化。

答：（1）设数组元素按行存放，A、B、C数组都是 n*n 的二维数组，各维的下界均为0，每个元素占一个字（4个字节），则数组元素（如A[i, j]）的地址计算公式为： D(A[i, j]) = addr(A) + ((i - 0) * n + (j - 0)) * 4 = addr(A) + 4 * ( i * n + j )

该程序的三地址代码序列被划分成基本块后如下：

（2）程序流图如下：

5

（3）仅基本块B7中有公共子表达式，删除公共子表达式后基本块B7变换成：

（4）根据（2）的程序流图，每个结点的控制结点集如下： D(B1) = { B1 }

6

D(B2) = { B1, B2 } D(B3) = { B1, B2, B3 } D(B4) = { B1, B2, B3, B4 } D(B5) = { B1, B2, B3, B4, B5 } D(B6) = { B1, B2, B3, B4, B5, B6 } D(B7) = { B1, B2, B3, B4, B5, B6, B7 } D(B8) = { B1, B2, B3, B4, B5, B6, B8 } D(B9) = { B1, B2, B3, B4, B9 } 根据回边 B7 -> B6，循环L1为： L1 = { B7, B6 }

根据回边 B8 -> B4，循环L2为： L2 = { B8, B6, B7, B5, B4 }

根据回边 B9 -> B2, 循环L3为：

L3 = { B9, B4, B5, B6, B7, B8, B3, B2 } 经循环优化后三地址代码序列变为:

7

8

12、 试求出如下四元式程序中的循环并进行循环优化. I := 1 read J, K L: A := K * I B := J * I C := A * B write C I := I + 1

if I < 100 goto L halt

答：把本题的三地址代码划分成基本块并画出其程序流图显示在图9.4(1)中，其中有三个基本块B1，B2，B3，有一条回边B2 -> B2，相应的循环是{B2}。

（1）代码外提：由于循环中没有不变运算，故不做此项优化 （2）强度削弱：B2中A和B都是I的归纳变量。优化结果显示在图9.4(2)中。

（3）删除归纳变量：变换循环控制条件，删除归纳变量I后的流图显示在图9.4(3)中

9

13、下面是应用筛法求2到N之间素数的程序： begin

read N;

for i := 2 to N do

A[i] := true; /*置初值*/

for i := 2 to N**0.5 do /*运算符**代表幂乘*/ if A[i] then /*i是一个素数*/ for j := 2 * i to N by i do

A[j] := false /*j可被i除尽*/ end

（1）试写出其四元式中间代码，假设对数组A用静态分配存储单元，且下届为0；（2）作出流图并求出其中的循环； （3）进行代码外提；

（4）进行强度削弱和删除归纳变量；

答：采用字节地址，两个字节作为一个机器字。 （1）程序的四元式中间代码如下：

B1: read N /* 置初值 */ i := 2

B2: if i > N goto B4 /* 第一个for语句 */ B3: T1 := i

T2 := addr(A) /* 数组A的基地址 */ T1 := 2 * T1 T2[T1] := true i := i + 1 goto B2 B4: i := 2

T3 := N ** 0.5

T3 := [T3] + 1 /* [T3]是对T3的值取整 */

10

B5: if i > T3 goto B12 B6: T4 := i

T5 := addr(A) T4:= 2 * T4

if T5[T4] goto B8 B7: goto B11 B8: j := 2 * i

B9: if j > N goto B11 /* 第三个for语句 */ B10: T6 := j

T7 := addr(A) T6 := 2 * T6 T7[T6] = false j := j + i goto B9 B11: i := i + 1 goto B5 B12:

（2）根据四元式的中间代码，可划分成基本块B1，B2，B3，B4，B5，B6，B7，B8，B9，B10，B11。其程序流图如下：

11

考察上面的程序流图：

D(B3) = { B1, B2, B3 } 又有 B3 -> B2，因此 B3 -> B2 是一条回边。根据它找到的循环 L1 = { B2, B3 }。

D(B10) = { B1, B2, B4, B5, B6, B9, B10 }，又有 B10 -> B9，所以 B10 -> B9 是一条回边。根据这条回边找到循环 L2 = { B9, B10 }。

D(B11) = { B1, B2, B4, B5, B6, B9, B11 }，又有 B11 -> B5，因此 B11 -> B5 是一条回边。根据这条回边找到循环 L3 = { B11, B9, B10, B8, B7, B6, B5 } （3）进行代码外提

12

把在循环中不随循环变化的操作提到循环外的前置结点中，且在基本块中作复写传播和删除无用赋值。结果程序流图如下：

（4）进行强度削弱和删除归纳变量后，其程序流图如下：

13

14

14、对下面的程序片段作出其程序流图并计算： （1）各基本块的到达_定值集IN[B]； （2）各基本块中各变量引用点的ud链； （3）各基本块出口的活跃变量集V_OUT[B]； （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）计算各基本块的到达-定值集IN[B]。公式为： IN[B] = ∪ OUT[P]

P∈P[B]

OUT[B] = GEN[B] ∪ ( IN[B] - KILL[B] )

GEN[B]和KILL[B]由程序流图直接求出，显示在表9.6(1)中。 表9.6(1) 基本块 GEN[B] 位向量 KILL[B] 位向量 B1 { d1, d2 } 11000000 { d3, d4, d6 } 00110100 B2 { d3, d4 } 00110000 { d1, d2, d6 } 11000100 B3 { d6 } 00000100 { d1, d4 } 10010000 B4 { } 00000000 { } 00000000 求各基本块到达-定值的初值及各遍的执行结果显示在表9.6(2)中。 表9.6(2) 基初值 第一遍后 第二遍后 第三遍后 本块IN[B] OUT[B] IN[B] OUT[B] IN[B] OUT[B] IN[B] OUT[B] B1 00000000 11000000 00000000 11000000 00000000 11000000 00000000 11000000

15

B2 00000000 00110000 11000100 00110000 11100100 00110000 11100100 00110000 B3 00000000 00000100 00110000 00100100 00110000 00100100 00110000 00100100 B4 00000000 00000000 00110000 00110000 00110000 00110000 00110000 00110000 （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链在IN[B2]={ 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链是IN[B3]中I的所有定值点，所以是{ d4 }。

B4中J的引用点d8前面没有对J的定值点，其ud链是IN[B4]中J的所有定值点。已知IN[B4] = { d3, d4 }，所以，J的引用点d8的ud链是{ d3 }。 （3）各基本块出口的活跃变量集v-OUT[B]：

对程序中某变量a和某点P，如果存在一条从P开始的道路，其中引用了a在P点的值，则称a在点P是活跃的。计算公式如下：

V_IN[B] = USE[B] ∪ ( V_OUT[B] - DEF[B] ) V_OUT[B] = ∪ V_IN[S]

S∈S[B]

其中，S[B]是B的所有后继块组成的集合。

DEF[B]和USE[B]可以从给定流图直接求出。从图9.6(1)的流图中求出的各基本块的DEF[B]和USE[B]显示在表9.6(3)中。 表9.6(3) 基本块 USE[B] DEF[B] B1 Φ { I, J } B2 { I, J } Φ B3 { I } Φ B4 { J } Φ 计算次序为B4, B3, B2, B1，各次迭代结果显示在表9.6(4)中。 表9.6(4) 第一次迭代后 第二次迭代后 第三次迭代后 基本块 V_IN[B] V_OUT[B] V_IN[B] V_OUT[B] V_IN[B] V_OUT[B] B1 Φ { 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_IN[B] = D_USE[B] ∪ ( D_OUT[B] - D_DEF[B] ) D_OUT[B] = ∪ D_IN[S]

S∈S[B]

其中S[B]是B的后继基本块集。D_USE[B]和D_DEF[B]根据程序流图可直接求出。本题根据图9.6(1)的程序流图求出的D_USE[B]和D_DEF[B]显示在表9.6(5)中。 表9.6(6) 基本块 D_DEF[B] D_USE[B]

16

{ (d3, I), (d5, I), (d6, I), (d3, J), (d8, { } J) } B2 { (d6, I), (d8, J) } { (d3, I), (d3, J) } B3 { (d3, I), (d5, I) } { (d6, I) } B4 { } { (d8, J) } 变量I和J的D_IN[B]和D_OUT[B]的计算结果分别显示在表9.6(6)和表9.6(7)中。 表9.6(6) 第一次迭代后 第二次迭代后 第三次迭代后 基本块 D_IN[B] D_OUT[B] D_IN[B] D_OUT[B] D_IN[B] D_OUT[B] B1 00000000 00100000 00000000 00100000 00000000 00100000 B2 00100000 00000100 00100000 00000100 00100000 00000100 B3 00000100 00000000 00000100 00100000 00000100 00100000 B4 00000000 00000000 00000000 00000000 00000000 00000000 根据表9.6(6)，D_OUT[B1] = 00100000，故I在B1中定值点d1的du链是{ d3 }。D_OUT[B2] = 00000100，故I在B2中定值点d4的du链是{ d5, d6 }。D_OUT[B3] = 00100000，故I在B3中定值点d6的du链是{ d3 }。 表9.6(7) 第一次迭代后 第二次迭代后 第三次迭代后 基本块 D_IN[B] D_OUT[B] D_IN[B] D_OUT[B] D_IN[B] D_OUT[B] B1 00000000 00100000 00000000 00100000 00000000 00100000 B2 00100000 00000001 00100000 00100001 00100000 00100001 B3 00000000 00000000 00100000 00100000 00100000 00100000 B4 00000001 00000000 00000001 00000000 00000001 00000000 根据表9.6(7)，D_OUT[B1] = 00100000，J在B1中定值点d2的du链是{ d3 }。D_OUT[B2] = 00100001，故J在B2中定值点d3的du链是{ d3, d8 }。 15、 对下面的程序片段作出其程序流图并计算： （1）各基本块的到达_定值集IN[B]； （2）各基本块中各变量引用点的ud链； （3）各基本块出口的活跃变量集V_OUT[B]； （4）各基本块中变量定值点的du链。 N := 0 L1: I := 2

L2: if I < N goto L4 write N L3: N := N+1 goto L1 L4: J := N/I

if J = 0 goto L3 I := I=1 goto L2

答：对本题程序划分基本块并构造其程序流图，结果显示在图9.7(1)中，流图中以深度为主次序为：B1, B2, B3, B5, B7, B4, B6。 B1 17

（１）各基本块的到达－定值集IN[B]：

从图9.7(1)的程序流图直接求GEN[B]和KILL[B]，显示在表9.7(1)中。到达－定值集的计算结果显示在表9.7(2)中。 表9.7(1) 基本块 GEN[B] 位向量 KILL[B] 位向量 B1 { d1 } 1000000000 { d5 } 0000100000 B2 { d2 } 0100000000 { d9 } 0000000010 B3 { } 0000000000 { } 0000000000 B5 { d7 } 0000001000 { } 0000000000 B7 { d9 } 0000000010 { d2 } 0100000000 B4 { } 0000000000 { } 0000000000 B6 { d5 } 0000100000 { d1 } 1000000000 表9.7(2) 基本块 B1 B2 B3 B5 B7 B4 B6 初值 第一次迭代 第二次迭代 第三次迭代 IN[B] OUT[B] IN[B] OUT[B] IN[B] OUT[B] IN[B] OUT[B] 0000000000 1000000000 0000000000 1000000000 0000000000 1000000000 0000000000 1000000000 0000000000 0100000000 1000100000 1100100000 1100101010 1100101000 1100101010 1101101000 0000000000 0000000000 1100100010 1100100010 1100101010 1100101010 1100101010 1100101010 0000000000 0000001000 1100101010 1100101010 1100101010 1100101010 1100101010 1100101010 0000000000 0000000010 1000101010 1000101010 1100101010 1000101010 1100101010 1000101010 0000000000 0000000000 1100100010 1100100010 1100101010 1100101010 1100101010 1100101010 0000000000 0000100000 1100101010 0100101010 1100101010 0100101010 1100101010 0100101010 （2）各基本块中各变量的ud链： I在B3中引用点d3的ud链是{ d2, d9 }； I在B5中引用点d7的ud链是{ d2, d9 }； I在B7中引用点d9的ud链是{ d2, d9 }； N在B3中引用点d3的ud链是{ d1, d5 }； N在B5中引用点d7的ud链是{ d1, d5 }； N在B4中引用点d4的ud链是{ d1, d5 }； N在B8中引用点d5的ud链是{ d1, d5 }； N在B5中引用点d8的ud链是{ d7 }；

（3）各基本块出口的活跃变量集V_OUT[B]： 使用下面的联立方程：

V_IN[B] = USE[B] ∪ ( V_OUT[B] - DEF[B] )

18

V_OUT[B] = ∪ V_IN[S] S∈S[B]

根据图9.7(1)的程序流图，求出USE[B]和DEF[B]显示在表9.7(3)中。已知各基本块的深度为主次序的逆序为B6, B4, B7, B5, B3, B2, B1。各次迭代结果显示在表9.7(4)中。 表9.7(3) 基本块 DEF[B] USE[B] B1 { N } Φ B2 { I } Φ B3 Φ { I, N } B5 { J } { I, N } B7 Φ { I } B4 Φ { N } B6 Φ { N } 表9.7(4) 第一次迭代 第二次迭代 第三次迭代 基本块 V_IN[B] V_OUT[B] V_IN[B] V_OUT[B] V_IN[B] V_OUT[B] B1 { } { N } { } { N } { } { N } B2 { N } { I, N } { N } { I, N } { N } { I, N } B3 { I, N } { I, N } { I, N } { I, N } { I, N } { I, N } B5 { I, N } { I, N } { I, N } { I, N } { I, N } { I, N } B7 { I } { } { I, N } { I, N } { I, N } { I, N } B4 { N } { N } { N } { N } { N } { N } B6 { N } { } { N } { N } { N } { N } （4）各基本块中变量定值点的du链。 计算采用下面的联立方程：

D_IN[B] = D_USE[B] ∪ ( D_OUT[B] - D_DEF[B] ) D_OUT[B] = ∪ D_IN[S] S∈S[B]

其中D_USE[B]和D_DEF[B]可以从图9.7(1)的程序流图直接求出，显示在表9.7(5)中。D_IN[B]和D_OUT[B]的计算结果显示在表9.7(6)中。

注：下表中用{ I:{d3, d1, d9}}表示{(d3, I), (d7, I), (d9, I)}。 表9.7(5) 基本块 D_DEF[B] D_USE[B] B1 { N: { d3, d4, d5, d7 } { } B2 { I: { d3, d7, d9 } } { } B3 { } { I: { d3 }, N: { d3 } } B5 { } { I: { d7 }, N: { d7 } } B7 { I: { d3, d7 } } { I: { d9 } } B4 { } { N: { d4 } } B6 { N: { d3, d4, d7 } } { N: { d5 } } 表9.7(6) 基第一次迭代 第二次迭代 第三次迭代 本D_IN[B] D_OUT[B] D_IN[B] D_OUT[B] D_IN[B] D_OUT[B] 块 B{N:{d3,d4,d5,d7}{N:{d3,d4,d5,d7}{N:{d3,d4,d5,d7}{ } { } { } } } } 1 B{N:{d3,d4,d5,d7}{I:{d3,d7,d9}, {N:{d3,d4,d5,d7}{I:{d3,d7,d9}, {N:{d3,d4,d5,d7}{I:{d3,d7,d9}, } N:{d3,d4,d5,d7}} } N:{d3,d4,d5,d7}} } N:{d3,d4,d5,d7}} 2 19

B{I:{d3,d7,d9}, {I:{d4,d7}, N:{d3,d4,d5,d7}} N:{d4,d5,d7}} 3 B{I:{d7,d9}, N:{d5, d7}} 5 B{I:{d9}} 7 B{N:{d4,d5}} 4 B{N:{d5}} 6 {I:{d9}, N:{d5,}} {I:{d3,d7,d9}, {I:{d7,d9}, {I:{d3,d7,d9}, {I:{d7,d9}, N:{d3,d4,d5,d7}} N:{d3,d4,d5,d7}} N:{d3,d4,d5,d7}} N:{d3,d4,d5,d7}} {I:{d7,d9}, {I:{d9}, {I:{d7,d9}, {I:{d9}, N:{d3,d4,d5,d7}} N:{d3,d4,d5,d7}} N:{d3,d4,d5,d7}} N:{d3,d4,d5,d7}} {I:{d9}, {I:{d3,d7,d9}, {I:{d9}, {I:{d3,d7,d9}, N:{d3,d4,d5,d7}} N:{d3,d4,d5,d7}} N:{d3,d4,d5,d7}} N:{d3,d4,d5,d7}} {N:{d4,d5}} {N:{d5}} {N:{d5}} {N:{d4,d5}} {N:{d5}} {N:{d3,d4,d5,d7}} { } {N:{d5}} { } {N:{d3,d4,d5 d7}} {N:{d5}} 根据表9.7(6)： B1中N的定值点d1的du链是{d3, d4, d5, d7}； B2中I的定值点d2的du链是{d3, d7, d9}； B5中J的定值点d7的du链是{d8}；

B7中I的定值点d9的du链是{d3, d7, d9}； B6中N的定值点d5的du链是{d3, d4, d5, d7}。 16、 填空题 在对编译程序产生的中间代码进行优化时，就实施优化的范围来说，分 A 优化和 B 优化。循环优化属于 B 优化，它对于提高目标代码的运行速度是非常有效的。循环优化主要采用的三项优化措施是 C 、 D 、 E 。 答:A：局部 B：全局 C：代码外提 D：削减运算强度 E：删除归纳变量

20

本文来源：https://www.bwwdw.com/article/3ydf.html