资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第六章 中间代码生成,赵建华,南京大学计算机系,本章内容,中间代码表示,抽象语法树,三地址代码：,x=y op z,静态类型检查,类型检查（,type checking,）,语法分析之后的抽象语法,(syntax),检查，比如,break,的位置，,goto,的目标,.,中间代码生成,编译器前端的逻辑结构,三地址代码（,1,）,每条指令右侧最多有一个运算符,一般情况可以写成,x,=,y op z,允许的运算分量：,名字：源程序中的名字作为三地址代码的地址,常量：源程序中出现或生成的常量,编译器生成的临时变量,三地址代码（,2,）,指令集合（,1,）,运算,/,赋值指令：,x=y op zx,=,op y,复制指令：,x=y,无条件转移指令：,goto L,条件转移指令：,if x goto Lif False x goto L,条件转移指令：,if x relop y goto L,三地址代码（,3,）,指令集合（,2,）,过程调用,/,返回：,param x1/,设置参数,param x2,param xn,call p,n/,调用子过程,p,，,n,为参数个数,带下标的复制指令：,x=yi,xi=y,注意：,i,表示离开数组位置第,i,个字节，而不是数组的第,i,个元素,地址,/,指针赋值指令：,x=&yx=*y*x=y,例子,语句,do i=i+1;while(aiv),；,三地址指令的四元式表示方法,在实现时，可以使用四元式,/,三元式,/,间接三元式来表示三地址指令,四元式：可以实现为纪录（或结构）,格式（字段）：,oparg1arg2result,op:,运算符的内部编码,arg1,arg2,result,是地址,x=y+z+y z x,单目运算符不使用,arg2,param,运算不使用,arg2,和,result,条件转移,/,非条件转移将目标标号放在,result,字段,四元式的例子,赋值语句：,a=b*-c+b*-c,三元式表示,三元式（,triple,）,oparg1arg2,使用三元式的位置来引用三元式的运算结果,xi=y,需要拆分为两个三元式,求,xi,的地址，然后再赋值,x=y op z,需要拆分为（这里？是编号）,(?)opyz,=x?,问题：在优化时经常需要移动,/,删除,/,添加三元式，导致三元式的移动。,三元式的例子,a=b*-c+b*-c,间接三元式,包含了一个指向三元式的指针的列表,我们可以对这个列表进行操作，完成优化功能；操作时不需要修改三元式中的参数。,静态单赋值（,SSA,）,SSA,中的所有赋值都是针对不同名的变量,对于同一个变量在不同路径中定值的情况，可以使用,函数来合并不同的定值,if(flag)x=-1;else x=1;y=x*a,if(flag)x,1,=-1;else x,2,=1;,x,3,=,(x,1,x,2,),；,y=x,3,*a,类型和声明,类型检查,(Type Checking),利用一组规则来检查运算分量的类型和运算符的预期类型是否匹配。,类型信息的用途,查错、确定名字需要的内存空间、计算数组元素的地址、类型转换、选择正确的运算符,本节的内容,确定名字的类型，,变量的存储空间布局（相对地址）,类型表达式,类型表达式（,type,expression,）：表示类型的结构,基本类型,类名,类型构造算子作用于类型,array,数字，类型表达式,record,字段,/,类型对的列表,（可以用符号表表示）,函数类型构造算子,：参数类型,结果类型,笛卡尔积：,s X t,可以包含取值为类型表达式的变量,类型表达式的例子,类型例子,元素个数为,3X4,的二维数组,数组的元素的记录类型,该记录类型中包含两个字段,:,x,和,y,其类型分别是,float,和,integer,类型表达式,array3,array4,record(x,float),(y,float),类型等价,不同的语言有不同的类型等价的定义,结构等价,或者它们是相同的基本类型,或者是相同的构造算子作用于结构等价的类型而得到的。,或者一个类型是另一个类型表达式的名字,名等价,类型名仅仅代表其自身,声明,文法,D,T id;D|,T B C|record D,C int|float,C,|num C,含义：,D,生成一系列声明；,T,生成不同的类型；,B,生成基本类型,int/float,；,C,表示分量，生成,num,序列；,注意,record,中包含了各个字段的声明。字段声明和变量声明的文法一致。,局部变量的存储布局,变量的类型可以确定变量需要的内存,即类型的宽度,可变大小的数据结构只需要考虑指针,函数的局部变量总是分配在连续的区间；,因此给每个变量分配一个相对于这个区间开始处的相对地址,变量的类型信息保存在符号表中；,计算,T,的类型和宽度的,SDT,综合属性：,type,width,全局变量,t,和,w,用于将类型和宽度信息从,B,传递到,C,相当于,C,的继承属性，因为总是通过拷贝来传递，所以在,SDT,中只赋值一次。,也可以把,t,和,w,替换为,C.t,和,C.w,SDT,运行的例子,输入：,int23,作用域和符号表,在具有语句块概念的编程语言中，标识符,x,在最内层的,x,声明的作用域中。,每个作用域对应于一个符号表；多个符号表形成树状结构。,在语义分析时，通过栈来存放当前符号表及其祖先。,声明序列的,SDT,（,1,）,在处理一个过程,/,函数时，局部变量应该放到单独的符号表中去；,这些变量的内存布局独立,相对地址从,0,开始；,假设变量的放置和声明的顺序相同；,SDT,的处理方法,变量,offset,记录当前可用的相对地址；,每“分配”一个变量，,offset,的值增加相应的值,top.put(id.lexeme,T.type,offset),在当前符号表,(,位于栈顶,),中创建符号表条目，记录标识符的类型，偏移量,声明序列的,SDT,（,2,）,我们可以把,offset,看作,D,的继承属性,D.offset,表示,D,中第一个变量的相对地址,P,D.offset=0 D,D T id;D,1,.offset=D.offset+T.width;D,1,记录字段的处理,T,record D,为每个记录创建单独的符号表,首先创建一个新的符号表，压到栈顶；,然后处理对应于字段声明的,D,，字段都被加入到新符号表中；,最后根据栈顶的符号表构造出,record,类型表达式；符号表出栈,表达式代码的,SDD,将表达式翻译成三地址指令序列,表达式的,SDD,属性,code,表示代码,addr,表示存放表达式结果的地址（临时变量）,new Temp(),可以生成一个临时变量,gen(),生成一个指令,增量式翻译方案,主属性,code,满足增量式翻译的条件。,注意：,top.get(),从栈顶符号表开始，逐个向下寻找,id,的信息,。,这里的,gen,发出相应的代码,数组元素的寻址,假设数组元素被存放在连续的存储空间中。,元素从,0,到,n-1,编号，第,i,个元素的地址为,base+i*w,K,维数组的寻址：假设数组按行存放，即首先存放,A0i,2,i,k,，然后存放,A1i,2,i,k,，,Ai,1,i,2,i,k,的地址,base+i,1,*w,1,+i,2,*w,2,+i,k,*w,k,或者,base+(i,1,*n,2,+i,2,)*n,3,+i,3,)*n,k,+i,k,)*w,其中：,base,、,w,、,i,、,n,的值可以从符号表中找到。,新的文法产生式,数组元素,L,：,L,LE|idE,以数组元素为左部的赋值：,SL=E;,数组元素作为表达式中的因子：,E,L,L,的代码计算偏移量，将结果存放于,L.addr,所指的临时变量中,综合属性,array,记录了相应数组的信息：元素类型，基地址，,数组元素作为因子,L,的代码只计算了偏移量；,数组元素的存放地址应该根据偏移量进一步计算，即,L,的数组基址加上偏移量,使用三地址指令,x=ai,数组元素作为赋值左部,使用三地址指令,ai=x,例子,表达式：,c+aij,类型检查和转换,类型系统：,给每一个组成部分赋予一个类型表达式,通过一组逻辑规则来表示这些类型表达式必须满足的条件,可发现错误、提高代码效率、确定临时变量的大小、,类型系统的分类,类型综合,根据子表达式的类型构造出表达式的类型,if,f,的类型为,s,t,且,x,的类型为,s,then,f(x),的类型为,t,类型推导,根据语言结构的使用方式来确定该结构的类型：,if,f(x),是一个表达式,then,对于某些类型,；,f,的类型为,且,x,的类型为,类型转换,假设在表达式,x,*,i,中，,x,为浮点数、,i,为整数，则结果应该是浮点数,x,和,i,使用不同的二进制表示方式,浮点*和整数*使用不同的指令,t1=(float)i,t2=x fmul t1,类型转换比较简单时的,SDD,：,E,E1+E2,if(E1.type=integer and E2.type=integer)E.type=integer;,else if,(E1.type=float and E2.type=integer)E.type=float;,这个规则没有考虑生成类型转换代码,类型的,widening,和,narrowing,Java,的类型转换规则,编译器自动完成的转换为隐式转换，程序员用代码指定的转换为显式转换。,处理类型转换的,SDT,函数,Max,求的是两个参数在拓宽层次结构中的最小公共祖先,Widen,函数已经生成了必要的类型转换代码,函数,/,运算符的重载,通过查看参数来解决函数重载问题,E,f(E,1,),if,f.typeset=s,i,t,i,|1=i=k and E,1,.type=s,k,then,E.type=t,k,控制流的翻译,布尔表达式可以用于改变控制流,/,计算逻辑值。,文法,B,BB|B&B|!B|(B)|E,rel,E|,true,|false,语义,B,1,B,2,中,B,1,为真时，不计算,B,2,，整个表达式为真。因此，当,B,1,为真时应该跳过,B,2,的代码。,B,1,&B,2,中,B,1,为假时，不计算,B,2,，整个表达式为假,短路代码,通过跳转指令实现控制流的处理,逻辑运算符本身不在代码中出现；,短路代码的例子,语句：,if(x200,代码,if x 200goto L1,ifFalse x!=ygoto L1,L2:x=0,L1:,接下来的代码,注：,当,x200,时，,x100,必然为假,同理：计算,x!=y,时，,x200,为真,控制流语句的翻译,文法：,B,表示布尔表达式，,S,代表语句,S,if,(B)S,1,S,if,(B)S,1,else,S,2,S,while,(B)S,1,代码的布局见右图,继承属性,B.true,：,B,为真的跳转目标,B.false,：,B,为假的跳转目标,S.next,：,S,执行完毕时的跳转目标,语法制导的定义（,1,）,语法制导的定义（,2,）,增量式生成代码：,S,while,(,begin=newlabel();B.true=newlabel;B.false=S.next;,gen(begin:),B ),gen(B.true:);,S1.next=begin;,S1,gen(goto begin);,布尔表达式的控制流翻译,生成的代码执行时跳转到两个标号之一。,表达式的值为真时，跳转到,B.true,表达式的值为假时，跳转到,B.false,B.true,和,B.false,是两个继承属性，根据,B,所在的上下文指向不同的位置,如果,B,是,if,语句的条件表达式，分别指向,then,分支和,else,分支；如果没有,else,分支，则指向,if,语句的下一条指令,如果,B,是,while
展开阅读全文