编译原理中间代码生成.

第八章中间代码生成学习内容三地址码表示方法声明语句的翻译赋值语句的翻译：数组寻址布尔表达式的翻译case语句的翻译backpatching技术的实现过程调用的翻译8.1中间语言8.1.1图表示a:=b*-c+b*-c语法树方式表示后缀表示——语法树的线性表示方式abcuminus*bcuminus*+assign语法制导定义构造语法树PRODUCTIONSemanticRuleSid:=E{S.nptr=mknode(‘assign’,mkleaf(id,id.entry),E.nptr)}EE1+E2{E.nptr=mknode(‘+’,E1.nptr,E2.nptr)}EE1*E2{E.nptr=mknode(‘*’,E1.nptr,E2.nptr)}E-E1{E.nptr=mknode(‘uminus’,E1.nptr)}E(E1){E.nptr=E1.nptr}Eid{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：输出一条三地址码指令赋值语句的翻译PRODUCTIONSemanticRuleSid:=E{S.code=E.code||gen(id.place‘:=’E.place)}EE1+E2{E.place=newtemp;E.code=E1.code||E2.code||||gen(E.place‘:=’E1.place‘+’E2.place)}EE1*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}Eid{E.place=id.entry;E.code=‘’}控制流语句的翻译while语句：SwhileEdoS1翻译为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]:=yx:=y[i]间接三元组实现方式8.2声明语句的翻译8.2.1过程内部的声明PRODUCTIONSemanticRulePMD{}M{offset:=0}Did:T{addtype(id.entry,T.type,offset)offset:=offset+T.width}Tchar{T.type=char;T.width=4;}Tinteger{T.type=integer;T.width=4;}Tarray[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作用域的处理处理作用域的翻译模式PMD{addwidth(top(tblptr),top(offset));pop(tblptr);pop(offset)}M{t:=mktable(null);push(t,tblptr);push(0,offset)}DD1;D2Dprocid;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);}Did: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计算E1t1计算E2t2t=t1+t2计算E2的临时变量的生存期都包含在t1内重用算法——计数器c，初始为0临时名字作为运算对象使用c--生成新的临时名字——$c，c++例8.1x=a*b+c*d–e*f$0,$1为运算对象，c减2，变为0结果又保存在$08.3.3数组元素寻址一维数组typeA[low..high];计算A[i]的地址A的起始地址——base数组元素大小——wA[i]与A起始位置的“距离”——(i–low)*w最终结果：base+(i–low)*wi*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)*n2A[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]|idL→Elist]|idElist→Elist,E|EElist→Elist,E|id[E(…((i1n2+i2)n3+i3)…)nm+im的计算e1=i1，em=em-1*nm+imElist.ndim：数组维数Elist.place：下标表达式计算结果，emlimit(array,j)：第j维的大小，nmL.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==