编译原理模拟试卷及答案（二） 学生姓名：_____________ 学号：___________________学生系别：_____________ 专业：______________ 年级___________班级_____________ 课程名称：编译原理 课程性质：专业必修一、 文法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推导树如下：b)所有短语：(2个)、*、 + * 简单短语：(2个)短语：二、构造下列正则表达式的确定性的有限状态自动机。
（12%）aba(a|b)*a答： 三、证明下面文法是SLR(1)文法，并构造其SLR分析表 （15%）® + | ® | ®* | a | b答：分析表如下所示：状 态 T项 目 集输入符号下一状态0*→·⊥1→·+1→·2→· 2→· 3→·* 3→·a a4→·b b51*→·⊥⊥Accept*→·++62*→·⊥/+#2*→·7→·* 7→·a a4→·b b53*→· ⊥/+/a/b#4*→·* *84*→a· #65*→b· #76*→+·9→· 9→· 3→·* 3→·a a4→·b b57*→· ⊥/+/a/b#3*→·* *88*→*· #59*→+·⊥/+#1*→· 7→·* 7→·a a4→·b b5四、写出下列表达式的三地址形式的中间表示。
（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所示：七、设基本块p由如下语句构成：（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)试给出基本块p的DAGb)根据DAG重写基本块c)若p所在的程序中只有A和B在p后将要被引用，试写出优化后的基本块答：1）基本块 p 的DAG如图7.1所示图7.1 基本块 p 的DAG2）因为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将在 p 后被引用，所以最后优化的代码为：S1:=R+r ;S2:=R-r ;A:=6.28*S1;B:=A*S2;其中，S1、S2为临时变量。