《编译原理》汇总

编译原理模拟试卷及答案

学生姓名：_____________ 学号：___________________

学生系别：_____________ 专业：______________ 年级___________班级_____________ 课程名称：编译原理 课程性质：专业必修

一、文法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个) 短语：

1

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

aba(a|b)*a 答：

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

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

? + | ? | ?* | a | b

答：分析表如下所示：

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

2

→·b b 5 7 * →· ⊥/+/a/b #3 * →·* * 8 8 * →*· #5 * →+· ⊥/+ #1 * →· 7 9 →·* 7 →·a a 4 →·b b 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 值为中真和假的尚待回填的出口的链首指针条件语句的语义可描述为：

3

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;

4

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％）

5