编译原理期末模拟试卷及答案

一、文法G[]的产生式为： （12%）

 + |  * |  I | ()

a)给出（I+I）* I的最左推导、最右推导及相应的推导树； b)列出句型 + * 的所有短语、简单短语和句柄。

答：a)最左推导：

**()*(+)*(+)*

(+)*(I+)*(I+)*(I+I)*(I+I)*(I+I)*(I+I)*I 最右推导：

****I*I()*I

(+)*I(+)*I(+I)*I(+I)*I(+I)*I(I+I)*I 推导树如下：

( I ) + * I I

b)所有短语：(2个)、*、 + * 简单短语：(2个) 短语：

二、构造下列正则表达式的确定性的有限状态自动机。 （12%）

aba(a|b)*a

答：

1 a 2 b 3 a b a 4 b 5 a

三、证明下面文法是SLR(1)文法，并构造其SLR分析表。 （15%）

 + |  | * | a | b

答：分析表如下所示：

状 态 T * 0 1 * * * * 2 3 4 5 * * * * * 6 7 * 项 目 集 →·⊥ →·+ →· →· →· →·* →·a →·b →·⊥ →·+ →· →· →·* →·a →·b →· →·* →a· →b· →+· →· →· →·* →·a →·b →· 输入符号 a b ⊥ + ⊥/+ a b ⊥/+/a/b * a b ⊥/+/a/b 下一状态 1 1 2 2 3 3 4 5 Accept 6 #2 7 7 4 5 #4 8 #6 #7 9 9 3 3 4 5 #3 * 8 * * * 9

→·* →*· →+· →· →·* →·a →·b * ⊥/+ a b 8 #5 #1 7 7 4 5

四、写出下列表达式的三地址形式的中间表示。 （16%）

（1） 5+6  (a + b);

（2） A( B  (C  D));

（3） for j:=1 to 10 do a[j + j]:=0;

（4） if x > y then x:=10 else x:= x + y;

答：⑴ 100: t1:=a+b 101: t2:=6*t1 102: t3:=5+t2

⑵ 100: if A goto 102 101: goto T

102: if B goto 104 103: goto F 104: if C goto T 105: goto 106 106: if D goto T 107: goto F ⑶ 100: j:=1

101: if j>10 goto NEXT 102: i:=j+j 103: a[i]:=0 104: goto 101

⑷ 100: if x>y goto 102 101: goto 104 102: x:=10 103: goto 105 104: x:=x+y 105:

五、条件语句可形式定义为： (20%)

 IF THEN 1 ELSE 2 其中带有属性

1．.type 值为“boolean” 表示是布尔类型

2．.true 和.false 值为中真和假的尚待回填的出口的链首指针

条件语句的语义可描述为： t:=e;

if not t then goto L1; 1; goto L2; L1: 2; L2:

其中 e 为的值。

试用句法制导翻译的方法写出符合上述要求的条件语句的翻译方案。

答：条件语句的属性翻译文法为： if {

CheckBool(.type); TLT:=NewTL;

GEN(LABEL,TLT);

Backpatch(.true,TLT); .false:=.false; }

 then 1 {

.TL:=NewTL; GEN(BR, .TL); TLF:=NewTL;

GEN(LABEL,TLF);

Backpatch(.false,TLF); }

 else 2 {

GEN(LABEL,.TL); }

六、对如下程序框架,若采用以过程为单位、二级存储区的存储分配方法.

试写出当程序流到达L时,整个运行栈的内容. （15％） procedure main procedure q(x,y : int) begin Z:real; array B[x..y] of real;

begin D,E: real; array C[1..600] of int; end; begin array A[1..x] of real; begin E,F : int; L: end; end; end;//q begin r,s : int; array T[10..400] of real; call q(1,200); end;//main

要求用图的形式详细列出调用记录中各个项的分布情况。

答：调用记录中各项的分布情况如图6.29所示：

数组A 数组B E,F 分程序4的stp4 数组A1的信息向量 分程序3的stp3 Z,数组B的信息向量 分程序1的stp1 q过程的stp 形实参数通讯区x,y,1,200 调用点的机器状态 Old SP 区头地址表 SP 数组T 数组T的信息向量 r,s 分程序的stp main过程的stp 形实参数通讯区 调用点的机器状态 Old SP 区头地址表 栈增长方向

七、设基本块由如下语句构成：（10％）

T0: =3.14; T1:=2*T0; T2:=R+r; A:=Tl*T2； B:=A; T3:=2*T0; T4:=R+r; T5:=T3*T4; T6:=R-r； B:=T5*T6；

a)试给出基本块的DAG。 b)根据DAG重写基本块。

c)若所在的程序中只有A和B在后将要被引用，试写出优化后的基本块。

答：1）基本块  的DAG如图7.1所示。

8,* A,T5 B 6,* 7,- T6 5,+ T2,T4 1 3.14 T0 2 6.28 T1,T3 4 3 r R 图7.1 基本块  的DAG

2）因为DAG重写基本块必须满足的约束条件是：DAG中各节点计算时，其子节点已经完成计算。

所以重写序列为1、3、4、5、7、2、6、8。 即可重写为： T0:=3.14; T2:=R+r; T4:=T2; T6:=R-r; T1:=6.28; T3:=T1;

A:=6.28*T2; T5:=A; B:=A*T6;

3）因为只有A、B将在  后被引用， 所以最后优化的代码为： S1:=R+r ; S2:=R-r ; A:=6.28*S1; B:=A*S2;

其中，S1、S2为临时变量。 答案完