编译原理期末模拟试卷及答案
编译原理期末模拟试卷及答案 课程名称:编译原理课程性质:专业必修 一、文法G[E]的产生式为:(12%) E E + T I T T T * E I F F 11 (E) a) 给出(I+I) * I的最左推导、最右推导及相应的推导树; b) 列出句型F + T * F的所有短语、简单短语和句柄。 答:a)最左推导: E T T *E F *E (E) *E (E+T)*E (T+T)*E (F+T)*E (I+T)*E (I+F)*E (1+ I) * (I+I)*T (I+I)*F (I+I)*I 最右推导: E T T *E T *T T *F T*I F*I (E)*I (E+T)*I (E+F)*I (E+I)*I (T+I)*I (F+I)*I (I+I)*I 推导树如下: (E I ) + * I I 1 b)所有短语:F(2 个)、T*F、F + T * F简 单短语:F(2 个)短语:F 二、构造下列正则表达式的确定性的有限状态自动机。(12%) aba(alb)*a 答: 三、证明下面文法是SLR⑴文法,并构造其SLR分析表。(15%) E E + T I T T T F I F F F* I a I b 答:分析表如下所示: 四、写出下列表达式的三地址形式的中间表示。 (1) 5+6(a + b); (2) A (B (CD)); (3) for j:=l to 10 do a[j + j]:=0; (4) if x y then x:=10 else x:= x + y; (16%) 答:⑴100: 101: 102: ⑵ 100: 101: 102: 103: 104: 105: 106: 107: ⑶ 100: 101: 102: 103: 104: ⑷ 100: 101: 102: 103: 104: 105: tl:=a+b t2:=6*tl t3:=5+t2 if A goto 102 goto T if B goto 104 goto F if C goto T goto 106 if D goto T goto F j:=l if j10 goto NEXT i:=j+j a[i]:=0 goto 101 if xy goto 102 goto 104 x:=10 goto 105 x:=x+y 4 五、条件语句可形式定义为:(20%) S IF E THEN Sl ELSE S2 其中E带有属性 1. E.type 值为“boolean” 表示E是布尔类型 2. E.true和E.false值为E中真和假的尚待回填的出口的链首指 针 条件语句的语义可描述为: t:=e;L1; Sl; L2; LI: S2; L2: 其中e为E的值。 试用句法制导翻译的方法写出符合上述要求的条件语句的翻译方案。 答:条件语句的属性翻译文法为: ifl ifE ( CheckB ool(E. type); TLT:=NewTL; GEN(LABEL,TLT); B ackpatch(E. true,TLT); ifl.false:=E.false; ) if2 ifl then Sl ( if2.TL:=NewTL; GEN(BR, if2.TL); 5 TLF:=NewTL; GEN(LABEL,TLF); Backpatch(E.false,TLF); } S if2 else S2 ( GEN(LABEL,if2.TL); } 六、对如下程序框架,若采用以过程为单位、二级存储区的存储分配方法. 试写出当程序流到达L时,整个运行栈的(15% ) procedure main procedure q(x,y : int) begin Z:real; array B[xy] of real; begin D, E: real; array C[16OO] of int; end; begin array A[lx] of real; begin E, F : int; L: end; 6 end; end;//q begin r,s : int; array T[10400] of real; call q( 1,200); end;//main 要求用图的形式详细列出调用记录中各个项的分布情况。 答:调用记录中各项的分布情况如图 6.29所示: 栈 增 长 方 向 7 七、设基本块 由如下语句构成:(10%) T0: =3.14; Tl:=2*T0; T2:=R+r; A:=T1*T2; B:=A; T3:=2*T0; T4:=R+r; T5:=T3*T4; T6:=R-r; B:=T5*T6; a)试给出基本块 的DAGo b)根据DAG重写基本块。 c)若 所在的程序中只有A和B在 后将