第八章中间代码生成学习内容三地址码表示方法声明语句的翻译赋值语句的翻译:数组寻址布尔表达式的翻译case语句的翻译backpatching技术的实现过程调用的翻译8.1中间语言8.1.1图表示a:=b*-c+b*-c语法树方式表示后缀表示——语法树的线性表示方式abcuminus*bcuminus*+assign语法制导定义构造语法树PRODUCTIONSemanticRuleSid:=E{S.nptr=mknode(‘assign’,mkleaf(id,id.entry),E.nptr)}EE1+E2{E.nptr=mknode(‘+’,E1.nptr,E2.nptr)}EE1*E2{E.nptr=mknode(‘*’,E1.nptr,E2.nptr)}E-E1{E.nptr=mknode(‘uminus’,E1.nptr)}E(E1){E.nptr=E1.nptr}Eid{E.nptr=mkleaf(id,id.entry)}语法树的计算机内部表示8.1.2三地址码Three-AddressCode一般形式:x:=yopz语法树、dag的线性化表示t1:=-ct1:=-ct2:=b*t1t2:=b*t1t3:=-ct5:=t2+t2t4:=b*t3a:=t5t5:=t2+t4a:=t58.1.3三地址码语句类型1.二元运算:x:=yopz2.一元运算:x:=opy3.复制语句:x:=y4.无条件转移:gotoL5.条件转移:ifxrelopygotoL6.函数调用:paramx1paramx2…paramxncallp,n7.数组:x:=y[i],x[i]:=y8.指针:x:=&y,x:=*y语法制导翻译生成三地址码赋值语句:id:=E利用属性E.place:保存E的值的名字E.code:计算E的三地址代码newtemp:生成临时变量名gen:输出一条三地址码指令赋值语句的翻译PRODUCTIONSemanticRuleSid:=E{S.code=E.code||gen(id.place‘:=’E.place)}EE1+E2{E.place=newtemp;E.code=E1.code||E2.code||||gen(E.place‘:=’E1.place‘+’E2.place)}EE1*E2{E.place=newtemp;E.code=E1.code||E2.code||||gen(E.place‘:=’E1.place‘*’E2.place)}E-E1{E.place=newtemp;E.code=E1.code||||gen(E.place‘:=’‘uminus’E1.place)}E(E1){E.place=E1.place;E.code=E1.code}Eid{E.place=id.entry;E.code=‘’}控制流语句的翻译while语句:SwhileEdoS1翻译为S.begin:E.codeifE.place=0gotoS.afterS1.codegotoS.beginS.after:语法制导定义:S.begin=newlabel;S.after=newlabel;S.code=gen(S.begin‘:’)||E.code||gen(‘if’E.place‘=’‘0’‘goto’S.after)||S1.code||gen(‘goto’S.begin)||gen(S.after‘:’)8.1.5三地址码的实现四元组,三元组三元运算的实现——拆分x[i]:=yx:=y[i]间接三元组实现方式8.2声明语句的翻译8.2.1过程内部的声明PRODUCTIONSemanticRulePMD{}M{offset:=0}Did:T{addtype(id.entry,T.type,offset)offset:=offset+T.width}Tchar{T.type=char;T.width=4;}Tinteger{T.type=integer;T.width=4;}Tarray[num]ofT1{T.type=array(num.val,T1.type)T.width=num.val*T1.width}T^T1{T.type=pointer(T1.type);T1.width=4}8.2.2作用域的处理处理作用域的翻译模式PMD{addwidth(top(tblptr),top(offset));pop(tblptr);pop(offset)}M{t:=mktable(null);push(t,tblptr);push(0,offset)}DD1;D2Dprocid;ND;S{t:=top(tblpr);addwidth(t,top(offset));pop(tblptr);pop(offset);enterproc(top(tblptr),id.name,t)}N{t:=mktable(top(tblptr));push(t,tblptr);push(0,offset);}Did:T{enter(top(tblptr),id.name,T.type,top(offset));top(offset):=top(offset)+T.width符号表栈内存占用量栈8.2.3记录类型的处理创建独立的符号表T→recordLDend{T.type=record(top(tblptr));T.width=top(offset);pop(tblptr);pop(offset);}L→{t=mktable(null);push(t,tblptr);push(0,offset);}8.3赋值语句8.3.1符号表中的名字S→id:=E{p=lookup(id.name);if(p!=null)emit(p‘:=’E.place);elseerror;}E→E1+E2{E.place=newtemp;emit(E.place‘:=’E1.place‘+’E2.place;}E→E1*E2{E.place=newtemp;emit(E.place‘:=’E1.place‘*’E2.place;}E→-E1{E.place=newtemp;emit(E.place‘:=’‘uminus’E1.place;}E→(E1){E.place=E1.place}E→id{p=lookup(id.name);if(p!=null)E.place=p;elseerror;}在符号表中查找标识符8.3.2临时名字的重用newtemp每次产生不同名字,浪费空间E→E1+E2计算E1t1计算E2t2t=t1+t2计算E2的临时变量的生存期都包含在t1内重用算法——计数器c,初始为0临时名字作为运算对象使用c--生成新的临时名字——$c,c++例8.1x=a*b+c*d–e*f$0,$1为运算对象,c减2,变为0结果又保存在$08.3.3数组元素寻址一维数组typeA[low..high];计算A[i]的地址A的起始地址——base数组元素大小——wA[i]与A起始位置的“距离”——(i–low)*w最终结果:base+(i–low)*wi*w+(base–low*w)(base–low*w)为常量,可在编译时计算A[i]base(i–low)*w数组元素寻址(续)二维数组:typeA[low1..high1,low2..high2]计算A[i1,i2]地址数组的数组,两次利用一维数组计算方法行:n2=high2–low2+1个元素的一维数组元素二维数组:n1=high1-low1+1个“行”的一维数组i1行的位置(i1-low1)*n2A[i1,i2]距行开始位置的距离:i2–low2最终结果base+((i1-low1)*n2+i2-low2)*w((i1*n2)+i2)*w+(base–((low1*n2)+low2)*w)(base–((low1*n2)+low2)*w)为常量A[low1,low2]…A[low1,high2]…A[i1,low2]…A[i1,i2]…basen2*w数组元素寻址(续)扩展到多维情况typeA[low1..high1,…,lowk..highk]计算A[i1,i2,…,ik]的地址最终结果((…((i1n2+i2)n3+i3)…)nk+ik)*w+base–((…((low1n2+low2)n3+low3)…)nk+lowk)*w实现方法L→id[Elist]|idL→Elist]|idElist→Elist,E|EElist→Elist,E|id[E(…((i1n2+i2)n3+i3)…)nm+im的计算e1=i1,em=em-1*nm+imElist.ndim:数组维数Elist.place:下标表达式计算结果,emlimit(array,j):第j维的大小,nmL.place:基地址(地址计算常量部分)L.offset:偏移,普通变量为null8.3.4数组元素寻址的翻译模式文法(1)S→L:=E(2)E→E+E(3)E→(E)(4)E→L(5)L→Elist](6)L→id(7)Elist→Elist,E(8)Elist→id[E数组元素寻址的翻译模式(续)(1)S→L:=E{if(L.offset==null)emit(L.place‘:=’E.place);elseemit(L.place‘[’L.offset‘]’‘:=’E.place);}(2)E→E1+E2{E.place=newtemp;emit(E.place‘:=’E1.place‘+’E2.place);}(3)E→(E1){E.place=E1.place;}普通变量?数组?数组元素寻址的翻译模式(续)(5)L→id{L.place=id.place;L.offset=null;}(6)Elist→Elist1,E{t=newtemp;m=Elist1.ndim+1;emit(t‘:=’Elist1.place‘*’limit(Elist1.array,m));emit(t‘:=’t‘+’E.place);Elist.array=Elist1.array;Elist.place=t;Elist.ndim=m;}(5)Elist→id[E{Elist.array=id.place;Elist.place=E.place;Elist.ndim=1;}em-1em数组元素寻址的翻译模式(续)(4)E→L{if(L.offset==null)E.place=L.place;else{E.place=newtemp;emit(E.place‘:=’L.place‘[’L.offset‘]’);}}(5)L→Elist]{L.place=newtemp;L.offset=newtemp;emit(L.place‘:=’c(Elist.array));emit(L.offset‘:=’Elist.place‘*’width(Elist.array));}地址计算常量部分例8.210×20的数组,low1=low2=1,n1=10,n2=20,w=4翻译x:=A[y,z]生成的三地址码:t1:=y*20t1:=t1+zt2:=ct3:=4*t1t4:=t2[t3]x:=t48.3.5类型转换E→E1+E2的语义动作E.place=newtemp;if(E1.type==integer&&E2.type==integer){emit(E.place‘:=’E1.place‘int+’E2.place;E.type=integer;}elseif(E1.type==real&&E2.type==real){emit(E.place‘:=’E1.place‘real+’E2.place;E.type=real;}elseif(E1.type==