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

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

第5页共5页中国民航学院2005－2006学年第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->ST’T’->,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和FOLLOW4分，验证LL（1）文法3分。FIRST和FOLLOW不要求全部计算，但T’的FIRST和FOLLOW必须全部计算。若计算错误，错一个扣1分，扣完为止。验证LL（1）文法时第一条不含左递归不明确表示也不扣分。3．解答1）对于规则S®Pa|Pb|c，我们有FIRDT(Pa)ÇFIRDT(Pb)={c，f}¹f所以该文法不是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，其中只有一个状态存在移进规约冲突。5n第5页共5页S’®S.P®S.eFOLLOW(S’)={#}可以使用SLR方法解决冲突，所以该文法是SLR(1)文法。评分标准：LL（1）文法判断正确得4分，SLR（1）文法判断正确得5分。4.解答规约及翻译过程如下：步骤符号栈输入串使用规则输出结果0#aaadbc#1#aaadbc#2#Aaadbc#A®a33#Aaadbc#4#AAadbc#A®a35#AAadbc#6#AAAdbc#A®a37#AAAdbc#8#AAAdbc#9#AAAdbc#10#AAAdbC#C®C611#AAAdB#B®bC412#AAAB#B®dB513#AAS#S®AB214#AS#S®AS115#S#S®AS1输出结果为：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:=T3[T4]104(:=,T3[T4],_,T5)T6:=i+j105(+,i,j,T6)T7:=C–4106(-,C,4,T7)T8:=4*T6107(*,4,T6,T8)T9:=T7[T8]108(:=,T7[T8],_,T9)A:=T5+T9109(+,T5,T9,A)5n第5页共5页评分标准：每行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在基本块后面还要被引用，优化后的结果5n第5页共5页G=B*CH=G*GL=H*G9．解答：L:A:=K*IB:=J*IC:=A*BwriteCI:=I+1ifI<100gotoLI:=1ReadJ,KhaltL’:A:=A+KB:=B+JC:=A*BwriteCI:=I+1ifI<100gotoL’I:=1ReadJ,K-------------------A:=K*IB:=J*Ihalt强度削弱循环中I是基本归纳变量，A、B是与I同族的归纳变量，且有如下线性关系：A:=K*I，B:=J*I所以，条件I<100可用A<100*K或者B<100*J来替代。控制语句改写为：T1:=100*K，IfA

查看更多