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

编译原理期末模拟试卷及答案 课程名称编译原理课程性质专业必修 一、文法G[lt;Egt;]的产生式为12 lt;Egt; lt;Egt; lt;Tgt; I lt;Tgt; lt;Tgt; lt;Tgt; * lt;Egt; I lt;Fgt; lt;Fgt; 11 lt;Egt; a 给出II * I的最左推导、最右推导及相应的推导树； b 列出句型lt;Fgt; lt;Tgt; * lt;Fgt;的所有短语、简单短语和句柄。 答a最左推导 lt;Egt; lt;Tgt; lt;Tgt; *lt;Egt; lt;Fgt; *lt;Egt; lt ;Egt; *lt;Egt; lt;Egt;lt;Tgt;*lt;Egt; lt;Tgt;lt;Tgt;*lt;Egt; lt;Fgt;lt;Tgt;*lt;Egt; Ilt;Tgt;*lt;Egt; Ilt;Fgt;*lt;Egt; 1 I *lt；Egt; II*lt;Tgt; II*lt;Fgt; II*I 最右推导 lt;Egt; lt;Tgt; lt;Tgt; *lt;Egt; lt;Tgt; *lt;Tgt; lt;Tgt; *lt;Fgt; lt;Tgt;*I lt;Fgt;*I lt;Egt;*I lt;Egt;lt;Tgt;*I lt;Egt;lt;Fgt;*I lt;Egt;I*I lt;Tgt;I*I lt;Fgt;I*I II*I 推导树如下 lt;Egt; I * I I 1 b）所有短语lt;Fgt;（2 个）、lt;Tgt;*lt;Fgt;、lt;Fgt; lt;Tgt; * lt;Fgt;简 单短语lt;Fgt;（2 个）短语lt;Fgt; 二、构造下列正则表达式的确定性的有限状态自动机。（12） aba（alb）*a 答 三、证明下面文法是SLR⑴文法，并构造其SLR分析表。15 lt;Egt; lt;Egt; lt;Tgt; I lt;Tgt; lt;Tgt; lt;Tgt; lt;Fgt; I lt;Fgt; lt;Fgt; lt;Fgt;* I a I b 答分析表如下所示 四、写出下列表达式的三地址形式的中间表示。 1 56a b; 2 A B CD; 3 for jl to 10 do a[j j]0; 4 if x gt; y then x10 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 tlab t26*tl t35t2 if A goto 102 goto T if B goto 104 goto F if C goto T goto 106 if D goto T goto F jl if jgt;10 goto NEXT ijj a[i]0 goto 101 if xgt;y goto 102 goto 104 x10 goto 105 xxy 4 五、条件语句可形式定义为20 lt;Sgt; IF lt;Egt; THEN lt;Sgt;l ELSE lt;Sgt;2 其中lt;Egt;带有属性 1. lt;Egt;.type 值为boolean” 表示lt;Egt;是布尔类型 2. lt;Egt;.true和lt;Egt;.false值为lt;Egt;中真和假的尚待回填的出口的链首指 针 条件语句的语义可描述为 te;L1; lt;Sgt;l; L2; LI lt;Sgt;2; L2 其中e为lt;Egt;的值。 试用句法制导翻译的方法写出符合上述要求的条件语句的翻译方案。 答条件语句的属性翻译文法为 lt;ifl gt; iflt;Egt; CheckB oollt;Egt;. type; TLTNewTL; GENLABEL,TLT; B ackpatchlt;Egt;. true,TLT; lt;iflgt;.falselt;Egt;.false; lt;if2gt; lt;iflgt; then lt;Sgt;l lt;if2gt;.TLNewTL; GENBR, lt;if2gt;.TL; 5 TLFNewTL; GENLABEL,TLF; Backpatchlt;Egt;.false,TLF; } lt;Sgt; lt;if2gt; else lt;Sgt;2 GENLABEL,lt;if2gt;.TL; } 六、对如下程序框架，若采用以过程为单位、二级存储区的存储分配方法. 试写出当程序流到达L时,整个运行栈的15 procedure main procedure qx,y int begin Zreal; array B[x..y] of real; begin D, E real; array C[1..6OO] of int; end; begin array A[l..x] of real; begin E, F int; L end; 6 end; end;//q begin r,s int; array T[10..400] of real; call q 1,200; end;//main 要求用图的形式详细列出调用记录中各个项的分布情况。 答调用记录中各项的分布情况如图 6.29所示 栈 增 长 方 向 7 七、设基本块 由如下语句构成（10） T0 3.14; Tl2*T0; T2Rr; AT1*T2； BA; T32*T0; T4Rr; T5T3*T4; T6R-r； BT5*T6； a）试给出基本块 的DAGo b）根据DAG重写基本块。 c）若 所在的程序中只有A和B在 后将