《编译原理》第八章习题答案下载.pdf 22页

'《编译原理》课后习题答案第八章第8章语法制导翻译和中间代码生成第1题给出下面表达式的逆波兰表示(后缀式)：(1)a*(-b+c)(2)if(x+y)*z=0thens∶∶=(a+b)*celses=a*b*c答案：给出下面表达式的逆波兰表示(后缀式)：(1)ab-c+*(2)xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else运算）如果写成这样：xy+z*0=sab+c*:=sabc**:=￥，则是错误的，因为写表达式和赋值语句的中间代码序列，或是写它们的代码生成过程，必须注意按照算符优先序进行，这实际上是按照LR分析过程进行的。例如：写出赋值语句a:=a+b*c*(d+e)的四元式中间代码,当前四元式序号为100。不能写成：100(+,d,e,t1)101(*,b,c,t2)102(*,t2,t1,t3)103(+,a,t3,t4)104(:=,t4,-,a)应该写成：100(*,b,c,t1)101(+,d,e,t2)102(*,t1,t2,t3)103(+,a,t3,t4)104(:=,t4,-,a)第2题请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式、四元式序列、树形、逆波兰，当前序号为100。答案：三元式：100(+,a,b)101(+,c,d)102(*,(1),(2))盛威网（www.snwei.com）专业的计算机学习网站1 《编译原理》课后习题答案第八章103(-,(3),/)104(+,a,b)105(+,(5),c)106(-(4),(6))间接三元式：间接三元式序列间接码表100(+，a,b)(100)101(+，c,d)(101)102(*，(1),(2))(102)103(-，(3),/)(103)104(+，(1),c)(100)(104)105(-，(4),(1))(105)或者：间接三元式：100(+，a,b)101(+，c,d)102(*，(1),(2))103(-，(3),/)104(+，(1),c)105(-，(4),(1))间接码表：100101102103100104105四元式：100(+,a,b,t1)101(+,c,d,t2)102(*,t1,t2,t3)103(-,t3,/,t4)104(+,a,b,t5)105(+,t5,c,t6)106(-,t4,t6,t7)树形：盛威网（www.snwei.com）专业的计算机学习网站2 《编译原理》课后习题答案第八章逆波兰：ab+cd+*-ab+c+-［典型例题］：写出ifAandBandC>DthenifAD的四元式*/(2)(j,_,_,13)(3)(jnz,B,_,5)(4)(j,_,_,13)(5)(j>,C,D,7)(6)(j,_,_,13)(7)(j<,A,B,9)/*AD)thenX:=Y+Z翻译成四元式答案：假定翻译的四元式序列从（100）开始：（100）ifAidE.code:=id.lexeme;问题4：有文法：S→(L)|aL→L,S|S给此文法配上语义动作子程序(或者说为此文法写一个语法制导定义)，它输出配对括号的个数。如对于句子(a,(a,a))，输出是2。（中国科学院计算所1994）答案：加入新开始符号S"和产生式S"→S，设num为综合属性，代表值属性，则语法制导定义如下：产生式语义规则S"→Sprint(S.num)S→(L)S.num:=L.num+1S→aS.num:=0L→L1,SL.num:=L1.num+S.numL→SL.num:=S.num盛威网（www.snwei.com）专业的计算机学习网站13 《编译原理》课后习题答案第八章问题5：文法G的产生式如下：S→(L)|aL→L,S|S①试写出一个语法制导定义，它输出配对括号个数；②写一个翻译方案，打印每个a的嵌套深度。如((a),a),打印2,1。（中国科学院软件所1999）答案：①为S,L引入综合属性num，代表配对括号个数；语法制导定义产生式语义动作S"→Sprint(S.num)S→(L)S.num:=L.num+1S→aS.num:=0L→L1,SL.num:=L1.num+S.numL→SL.num:=S.num②引入继承属性f,代表嵌套深度S"→{S.f:=0}SS→"("{L.f:=S.f+1;}L")"S→a{print(S.f);}L→{L1.f:=L.f;}L1,{S.f:=L.f}SL→{S.f:＝L．f;}S盛威网（www.snwei.com）专业的计算机学习网站14 《编译原理》课后习题答案第八章问题6：对下面的文法，只利用综合属性获得类型信息。DÆL,id|LLÆTidTÆint|real答案：语法制导定义产生式语义规则DÆL,idD.type:=L.typeaddtype(id.entry,L.type)DÆLD.type:=L.typeLÆTidL.type:=T.typeaddtype(id.entry,T.type)TÆintT.type:=integerTÆrealT.type:=real盛威网（www.snwei.com）专业的计算机学习网站15 《编译原理》课后习题答案第八章问题7：下面文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时,结果为整数，否则为实数。EÆTRRÆ+TR|εTÆnum.num|numa)给出语法制导定义确定每个子表达式的类型。b)把表达式翻译成前缀形式，并且决定类型。试用一元运算符inttoreal把整型值转换为相等的实型值，以使得前缀表达式中两个运算对象是同类型的。答案：a)设type是综合属性，代表各非终结符的“类型”属性设in是继承属性，翻译方案产生式语义规则EÆT{R.i:=T.type}R{E.Type:=R.s}RÆ+T{IF(R.i=integer)and(T.type=integer)THENR1.i:=integerELSER1.i:=real}R1{R.s:=R1.s}RÆε{R.s:=R.i}TÆnum.numT.type:=realTÆnumT.type:=integerb)设属性s和i用于传递属性type，属性t和j用于传递属性val。盛威网（www.snwei.com）专业的计算机学习网站16 《编译原理》课后习题答案第八章翻译方案产生式语义规则EÆT{R.i:=T.type}{R.j:=T.val}R{E.Type:=R.s}{E.val:=R.t}RÆ+T{IF(R.i=integer)and(T.type=integer)THENBEGINR1.i:=integerPrint(‘+’,R.j,T.val)R1.j:=R.j+T.valENDELSEBEGINR1.i:=realIFR.i=integerTHENBeginR.i:=realR.j:=inttoreal(R.j)EndIFT.type=integerTHENBeginT.type:=realT.val:=inttoreal(T.val)EndPrint(‘+’,R..j,T.val)R1.j:=R.j+T.valEND}R1{R.s:=R1.s}{R.t:=R1.t}RÆε{R.s:=R.i}{R.t:=R.j}TÆnum.num{T.type:=real}{T.val:=num.num.lexval}TÆnum{T.type:=integer}{T.val:=num.lexval}盛威网（www.snwei.com）专业的计算机学习网站17 《编译原理》课后习题答案第八章问题8：翻译算术表达式a*-(b+c)为a)一棵语法树b)后缀式*c)三地址代码auminus答案：+a)语法树：b)后缀式:bcabc+uminus*c)三地址代码:t1:=b+ct2:=-t1t3:=a*t2问题9：翻译算术表达式–(a+b)*(c+d)+(a+b+c)为a)四元式b)三元式c)间接三元式答案：先写出三地址代码为：t1:=a+bt2:=-t1t3:=c+dt4:=t2*t3t5:=a+bt6:=t5+ct7:=t4+t6a)：对应的四元式为：oparg1arg2result(0)+abt1(1)uminust1t2(2)+cdt3(3)*t2t3t4(4)+abt5(5)+t5ct6(6)+t4t6t7盛威网（www.snwei.com）专业的计算机学习网站18 《编译原理》课后习题答案第八章b)：对应的三元式为：oparg1arg2(0)+ab(1)Uminus(0)(2)+cd(3)*(1)(2)(4)+ab(5)+(4)c(6)+(3)(5)c)：对应的间接三元式为：statementoparg1arg2(0)1515+ab(1)1616uminus15(2)1717+cd(3)1818*1617(4)1519+15c(5)1920+1819(6)20问题10：将下列赋值语句译成三地址代码。A[i,j]:=B[i,j]+C[A[k,l]]+D[i+j]答案：t11:=i*20t12:=t11+jt13:=A-84;t14:=4*t12t15:=t13[t14]//A[i,j]t21:=i*20t22:=t21+jt23:=B-84;t24:=4*t22t25:=t23[t24]//B[i,j]t31:=k*20t32:=t31+l盛威网（www.snwei.com）专业的计算机学习网站19 《编译原理》课后习题答案第八章t33:=A-84t34:=4*t32t35:=t33[t34]//A[k,l]t36:=4*t35t37:=C-4t38:=t37[t36]//C[A[k,l]]t41:=i+jt42:=4*t41t43:=D-4t44:=t43[t42]//D[i+j]t1:=t25+t38t2:=t1+t44t23[t24]:=t2问题11：写出for语句的翻译方案答案：产生式动作SÆforEdoS1S.begin:=newlabelS.first:=newtempS.last:=newtempS.curr:=newtempS.code:=gen(S.first“:=”E.init)||gen(S.last“:=”E.final)||gen(“if”S.first“>”S.last“goto”S.next)||gen(S.curr“:=”S.first)||gen(S.begin“:”)||gen(“if”S.curr“>”S.Last“goto”S.next)||S1.code||gen(S.curr:=succ(S.curr))||gen(“goto”S.begin)EÆv:=initialtofinalE.init:=initial.placeE.final:=final.place盛威网（www.snwei.com）专业的计算机学习网站20 《编译原理》课后习题答案第八章问题12：写出说明语句中的名字和类型及相对地址的翻译模式，以允许在形如DÆid:T的说明中可用一串名字表来代替单个名字。答案：产生式动作PÆ{offset:=0}DDÆD;DDÆidL{enter(id.name,L.type,offset)offset:=offset+L.width}LÆid,L1{L.type:=L1.typeL.width:=L1.widthenter(id.name,L1.type,offset)offset:=offset+L1.width}LÆ:T{L.type:=T.typeL.width:=T.width}TÆinteger{T.type:=integerT.width:=4}TÆreal{T.type:=realT.width:=8}TÆarray[num]ofT1{T.type:=array(num.val,T1.TypeT.width:=num.val*T1.Width)TÆ^T1{T.type:=pointer(T1.type)T.width:=4}盛威网（www.snwei.com）专业的计算机学习网站21 《编译原理》课后习题答案第八章问题13：（浙江大学1997年）在一个移入－归约的分析中采用以下的语法制导的翻译模式，在按一产生式归约时，立即执行括号中的动作。A→aB{print“0”;}A→c{print“1”;}B→Ab{print“2”}当分析器的输入为aacbb时，打印的字符串是什么？答案：分析器的分析过程如下图所示：由于分析器采用移入－归约的方式进行分析，符号串aacbb的分析过程将如图中所标的归约顺序进行，而在按一产生式归约时，立即执行括号中的动作，所以分析器打印的字符为12020。盛威网（www.snwei.com）专业的计算机学习网站22'