《编译原理习题及答案》由会员分享，可在线阅读，更多相关《编译原理习题及答案（7页珍藏版）》请在金锄头文库上搜索。
1、编译原理模拟试卷及答案（二） 学生姓名：_ 学号：_学生系别：_ 专业：_ 年级_班级_ 课程名称：编译原理 课程性质：专业必修一、 文法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个)短语：二、构造
2、下列正则表达式的确定性的有限状态自动机。 （12%）aba(a|b)*a答： 三、证明下面文法是SLR(1)文法，并构造其SLR分析表。 （15%） + | | * | a | b答：分析表如下所示：状 态 T项 目 集输入符号下一状态0*1+12 2 3* 3a a4b b51*Accept*+62*/+#2*7* 7a a4b b53* /+/a/b#4* *84*a #65*b #76*+9 9 3* 3a a4b b57* /+/a/b#3* *88* #59*+/+#1* 7* 7a a4b b5四、写出下列表达式的三地址形式的中间表示。 （16%）（1） 5+6 (a + b);（
3、2） A( B (C D);（3） for j:=1 to 10 do aj + j:=0;（4） if x y then x:=10 else x:= x + y;答： 100:t1:=a+b101:t2:=6*t1102:t3:=5+t2 100:if A goto 102101:goto T102:if B goto 104103:goto F 104:if C goto T105:goto 106106:if D goto T107:goto F 100:j:=1101:if j10 goto NEXT102:i:=j+j103:ai:=0104:goto 101 100:if xy
4、goto 102101:goto 104102:x:=10103:goto 105104:x:=x+y105:五、条件语句可形式定义为：(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 为的值。试用句法制导翻译的方法写出符合上述要求的条件语句的翻译方案。答：条件语句的属性翻译文法为：ifCheckBool(.type);TLT:=NewTL;G
5、EN(LABEL,TLT);Backpatch(.true,TLT);.false:=.false; then 1 .TL:=NewTL;GEN(BR, .TL);TLF:=NewTL;GEN(LABEL,TLF);Backpatch(.false,TLF); else 2GEN(LABEL,.TL);六、对如下程序框架,若采用以过程为单位、二级存储区的存储分配方法.试写出当程序流到达L时,整个运行栈的内容. （15）procedure main procedure q(x,y : int)begin Z:real; array Bx.y of real; begin D,E: real; a
6、rray C1.600 of int;end;begin array A1.x of real;begin E,F : int; L:end;end;end;/q begin r,s : int; array T10.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*
7、T6；a)试给出基本块p的DAG。b)根据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为临时变量。
