北方工业大学编译原理第7章习题

第七章语义分析和中间代码产生作业：7.1，7.3，7.4，7.5，7.6，7.7，7.8，7.9第七章语义分析和中间代码产生7.1给出下面表达式的逆波兰表示（后缀式）：解：a*(-b+c)notAornot(CornotD)a+b*(c+d/e)(AandB)or(notCorD)-a+b*(-c+d)(AorB)and(CornotDandE)if(x+y)*zthen(a+b)↑celsea↑b↑c表达式后缀式a*(-b+c)ab-c+*a+b*(c+d/e)abcde/+*+-a+b*(-c+d)a-bc-d+*+notAornot(CornotD)AnotCDnotornotor(AandB)or(notCorD)ABandCnotDoror(AorB)and(CornotDandE)ABorCDnotEandorandif(x+y)*zthen(a+b)↑celsea↑b↑c后缀式为xy+z*p1Jezab+c↑p2Jumpp1:abc↑↑p2：7.3请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。三元式：(1)+ab(2)-(1)-(3)+cd(4)*(2)(3)(5)+ab(6)+(5)c(7)-(4)(6)四元式：(1)+abT1(2)-T1-T2(3)+cdT3(4)*T2T3T4(5)+abT5(6)+T5cT6(7)-T4T6T7间接三元式：(1)+ab(2)-(1)-(3)+cd(4)*(2)(3)(5)+(1)c(6)-(4)(5)7.4写出下面赋值句A:=B*(-C+D)的自下而上语法制导翻译过程。给出所产生的三地址代码。输入栈PLACE四元式A:=B*(-C+D):=B*(-C+D)iAB*(-C+D)i:=A_*(-C+D）i:=iA_B*(-C+D）i:=EA_B（-C+D）i:=E*A_B_-C+D）i:=E*(A_B__C+D）i:=E*(-A_B___+D）i:=E*(-iA_B___C+D）i:=E*(-EA_B___C+D）i:=E*(EA_B__T1(-,C,-,T1)D）i:=E*(E+A_B__T1_）i:=E*(E+iA_B__T1_D）i:=E*(E+EA_B__T1_D)i:=E*(EA_B__T2(+,T1,D,T2)i:=E*(E)A_B__T2_i:=E*EA_B_T2i:=EA_T3(*,B,T2,T3)S(:=,T3,_,,A)7.5写出下面赋值句的中间代码A[I,J]:=B[A[I+1,J+1]]+B[I+J]设A，B数组每维下界为1，每维的上界：high1、high2，每维的长度：n1=high1-low1+1，n2=high2-low2+1，数组每个元素宽度为w，则设A数组C1=((1*n2)+1)*w,B数组C2=1w=wT10:=B-C2T11:=W*T9T12:=T10[T11]/*B[A[I+1,J+1]]T12*/T13:=I+JT14:=W*T13T15:=T10[T14]T16:=T12+T15T2[T3]=T16T1:=I*n2T1:=T1+JT2:=A-C1T3:=W*T1/*T2[T3]即为A[I,J]*/T4:=I+1T5:=T4*n2T6:=J+1T6:=T5+T6T7:=A-C1T8:=W*T6T9:=T7[T8]/*A[I+1,J+1]T9*/7.6按照作为条件控制的布尔式翻译写出布尔式Aor(Bandnot(CorD))的四元式序列。(3)E→notE1{E.truelist:=E1.falselist;E.falselist:=E1.truelist}(4)E→(E1){E.truelist:=E1.truelist;E.falselist:=E1.falselist}解：四元式序列为：100（jnz,A,_,0）/*为真*/101(j,_,_,102)102(jnz,B,_,104)103(j,_,_,0)/*为假*/104(jnz,C,_,103)/*为假*/105(j,_,_,106)106(jnz,D,_,104)/*假链链首*/107(j,_,_,100)/*真链链首*/其中：真链为{107,100}，链首E.truelist=107，假链为{106,104,103}，链首E.falselist=1067.6按照作为条件控制的布尔式翻译写出布尔式Aor(Bandnot(CorD))的四元式序列。(5)E→id1relopid2{E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(‘j’relop‘,’id1.place‘,’id2.place‘,’‘0’);emit(‘j,-,-,0’)}(6)E→id{E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(‘jnz’‘,’id.place‘,’‘-’‘,’‘0’)；emit(‘j,-,-,0’)}解：四元式序列为：100（jnz,A,_,0）/*为真*/101(j,_,_,102)102(jnz,B,_,104)103(j,_,_,0)/*为假*/104(jnz,C,_,103)/*为假*/105(j,_,_,106)106(jnz,D,_,104)/*假链链首*/107(j,_,_,100)/*真链链首*/其中：真链为{107,100}，链首E.truelist=107，假链为{106,104,103}，链首E.falselist=1067.6按照作为条件控制的布尔式翻译写出布尔式Aor(Bandnot(CorD))的四元式序列。解：四元式序列为：100（jnz,A,_,0）/*为真*/101(j,_,_,102)102(jnz,B,_,104)103(j,_,_,0)/*为假*/104(jnz,C,_,103)/*为假*/105(j,_,_,106)106(jnz,D,_,104)/*假链链首*/107(j,_,_,100)/*真链链首*/其中：真链为{107,100}，链首E.truelist=107，假链为{106,104,103}，链首E.falselist=106(1)E→E1orME2{backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist}(2)E→E1andME2{backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist)}E1.codeToE.trueToE1.falseE2.codeToE.trueToE.falseE1.codeToE.falseToE1.trueE2.codeToE.trueToE.false7.7把下面的语句翻译成四元式序列：whileACandBDdoifA=1thenC:=C+1elsewhileA=DdoA:=A+2;7.7把下面的语句翻译成四元式序列：whileACandBDdoifA=1thenC:=C+1elsewhileA=DdoA:=A+2;7.7把下面的语句翻译成四元式序列：whileACandBDdoifA=1thenC:=C+1elsewhileA=DdoA:=A+2;7.8请给出ifAandBandCDthenifABthenF:=1elseF:=0elseG:=G+1;的四元式序列，翻译过程中，采用then与else的最近匹配原则。解：100(jnz,A,_,102)/*AandBandCD*/101(j,_,_,112)102(jnz,B,_,104)103(j,_,_,112)104(j,C,D,106)105(j,_,_,112)106(j,A,B,108)/*AB*/107(j,_,_,110)108(:=,1,_,F)/*F:=1*/109(j,_,_，0)110(:=,0,_,F)/*F:=0*/111(j,_,_,109)112(+,G,1,T1)113(:=,T1,_,G)7.9对下面的文法，只利用综合属性获得类型信息。请给出该文法各个产生式的语义子程序。D→L,id|LL→TidT→int|real解：D→L,id{D.type:=L.typeaddtype(id.type,L.type)}D→L{D.type:=L.type}L→Tid{L.type:=T.typeaddtype(id.type,T.type)}T→int{T.type:=integer}T→real{T.type:=real}