2007-2008-2期中选考b卷编译答案.doc

第 6 页 共 6 页中国民航学院20052006 学年第1学期编译原理期中选考（B卷）标准答案(评分标准：每小题10分，共100分)1证明：E = T = iF = iE* = iEiT* = iTiT* = iFiT* E = T = F = E* = EiT* = TiT* = iFiT*评分标准：正确推导出二义性者得满分，否则不得分。2解：（1）消除左递归：S - a | | (T)T - STT - , ST | （2）计算FIRST和FOLLOW ：FIRST(S) = a, , ( )FIRST(T) = a, , ( FIRST(T) = , , FOLLOW(S) = #, , , ) FOLLOW(T) = ) FOLLOW(T) = （3）验证是LL(1)文法。首先，该文法已经消除了左递归；其次，S和T的产生式的FIRST集两两不相交；最后，FIRST(T)FOLLOW(T)为空，所以该文法是LL（1）文法。评分标准：消除左递归3分，计算FIRST和FOLLOW 4分，验证LL（1）文法3分。FIRST和FOLLOW不要求全部计算，但T的FIRST和FOLLOW必须全部计算。若计算错误，错一个扣1分，扣完为止。验证LL（1）文法时第一条不含左递归不明确表示也不扣分。3解答1）对于规则S Pa | Pb | c，我们有FIRDT(Pa) FIRDT(Pb)=c，ff所以该文法不是LL(1)文法。2）将文法拓广为：(1) S S(2) S Pa (3) S Pb (4) S c (5) P Pd(6) P Se(7) P f画出该文法识别活前缀的DFA，其中只有一个状态存在移进规约冲突。S S.P S.eFOLLOW(S)=#可以使用SLR方法解决冲突，所以该文法是SLR(1)文法。评分标准：LL（1）文法判断正确得4分，SLR（1）文法判断正确得5分。4.解答规约及翻译过程如下：步骤符号栈输入串使用规则输出结果0#aaadbc#1#aaadbc#2#Aaadbc#Aa33#Aaadbc#4#AAadbc#Aa35#AAadbc#6#AAAdbc#Aa37#AAAdbc#8#AAAdbc#9#AAAdbc#10#AAAdbC#CC611#AAAdB#BbC412#AAAB#BdB513#AAS#SAB214#AS #SAS115#S#SAS1输出结果为：333645211。评分标准：未给出输出结果或者输出结果错误者最高得分不能超过5分；归约过程酌情给分。5解答三地址代码：四元式序列T1 := i * 20100(*, i, 20, T1)T2 := T1 + j101(+, T1, _, T2)T3 := B 84102(-, B, 84, T3)T4 := 4 * T2103(*, 4, T2, T4)T5 := T3T4104(:=, T3T4, _, T5)T6 := i + j105(+, i, j, T6)T7 := C 4106(-, C, 4, T7)T8 := 4*T6107(*, 4, T6, T8)T9 := T7T8108(:=, T7T8, _, T9)A := T5 + T9109(+, T5, T9, A)评分标准：每行1分，给出四元式即得满分。6解答100(j=, A, 1, 102)101(j, _, _, 105)102(+, C, 1, T1)103(:=, T1, _, C)104(j, _, _, 107)105(+, A, 2, T2)106(:=, T2, _, A)107评分标准：100、101和104各占2分，其余每个1分，107不占分。7解答：100(j, A, C, 102)101(j, _, _, 115)102(j, B, D, 104)103(j, _, _, 115)104(j=, A, 1, 106)105(j, _, _, 109)106(+, C, 1, T1)107(:=, T1, _, C)108(j, _, _, 100)109(j=, A, D, 111)110(j, _, _, 114)111(+, A, 2, T2)112(:=, T2, _, A)113(j, _, _, 109)114(j, _, _, 100)115评分标准：外层循环和内层循环各占4分，选择结构占2分。8解答:(2) 假设只有L在基本块后面还要被引用，优化后的结果G = B * CH = G * GL = H * G9解答：L:A:=K*IB:=J*IC:=A*Bwrite CI:=I+1if I100 goto LI:=1Read J,KhaltL:A:=A+KB:=B+JC:=A*Bwrite CI:=I+1if I100 goto LI:=1Read J,K-A:=K*I B:=J*Ihalt强度削弱循环中I是基本归纳变量，A、B是与I同族的归纳变量，且有如下线性关系：A:=K*I，B:=J*I所以，条件I100可用A100*K或者B100*J来替代。控制语句改写为：T1:=100*K，If AT1 goto L 或者T2:=100*J，If BT2 goto L，此时，可以删除基本归纳变量I，另外还可以执行代码外提，将T1:=100*K外提到循环体外。I:=1Read J,KA:=K*I B:=J*IT1:=100*KL:A:=A+KB:=B+JC:=A*Bwrite C if AT1 goto Lhalt 评分标准：强度削弱占4分，代码外提占4分，删除归纳变量占2分。10试根据下述程序的活动树生长过程中的栈式分配的动态调用过程 主程序aaaA(a1,a2)B(a1,a2) C(a1.a2)B(a1,a2) D(a1.a2)解： 活动树的位置 栈中的活动记录A(a1,a2) A的活动记录SPA(a1,a2) A的活动记录 B的活动记录B(a1,a2) SPA(a1,a2) A的活动记录 C的