《中间代码生成》PPT课件.ppt

中间代码生成在编译器中的作用,词法分析,语法分析,语义分析,中间代码优化,中间代码生成,目标代码生成,分析,合成,中间代码生成,中间代码生成是将源程序翻译成等价中间表示的过程中间代码生成不是编译程序的必经阶段生成中间代码的目的有二：增强语言的可移植性进行中间代码级别的优化中间代码生成方法：基于Token序列基于抽象语法树语法制导的翻译方法：属性文法和动作文法,生成中间代码后，修改编译器后端，可将编译器移植到不同的机器上,源程序,Token序列,词法分析器,语法分析器,语法分析树,语义分析器,中间代码生成器,中间代码,M1,Mn,中间代码级别的优化,程序(代码)优化分为源程序级别优化、中间代码级别优化、目标代码级别优化源程序级别优化取决于用户对算法的取舍编译程序可进行中间代码和目标代码上的优化中间代码级别优化：循环内下标变量地址的计算常表达式节省公共子表达式节省循环不变式外提,中间代码级别的优化,intAmn,t;for(inti=0;im;i+;)for(intj=0;jn;j+)t=Aij;Aij=Aji;Aji=t;,(subi,j,0,t5)(multi,t5,1,t6)(multi,t6,1,t7)(aadd,t4,t7,t8),(subi,i,0,t1)(multi,t1,n,t2)(multi,t2,1,t3)(aadd,A,t3,t4),第七章中间代码生成,7.1几种常见的中间代码表示7.2中间代码生成中的几个问题7.3表达式的中间代码生成7.4原子语句的中间代码生成7.5结构语句的中间代码生成7.6声明的中间代码生成,7.1常见的中间表示,后缀式，逆波兰式抽象语法树AST(abstractsyntaxtree)无环有向图DAG(directedacyclicgraph)三元式四元式,三地址中间代码,7.1常见的中间表示,后缀式(逆波兰式)通常用于表达式的中间表示中缀(运算符在操作数的中间)a*b前缀式(运算符在操作数的前面)*ab后缀式(运算符在操作数的后面)ab*如何由中缀式转为后缀式？,由抽象语法树生成后缀式,中缀式:a*d+b*c+e,+,*,+,a,d,*,e,b,c,抽象语法树,后根遍历生成后缀式:ad*bc*+e+,先根遍历生成前缀式:+*ad*bce,由Token序列生成后缀式（1）-不带括号表达式的后缀式生成,(1)初始化:S1和S2为空;/S1是运算符栈，S2是运算分量栈(2)读token:tk=ReadOne();(3)Switchtkof(i)#:if(S1为空)exit;elsewhile(S1不为空)/*产生剩余操作符的后缀表示*/op=pop(S1,1);(str1,str2)=pop(S2,2);push(S2,str2+str1+“op”);/str1是左操作数，str2是右操作数，(ii)运算分量:push(S2,tk);goto(2);(iii)运算符:if(S1为空|tk优先级大于Top(S1)push(S1,tk);goto(2);elsewhile(tk小于等于Top(S1),生成后缀式的例子,中缀式表达式:a*d+b*c+e#,运算符栈S1,运算分量栈S2,由Token序列生成后缀式（2）带括号表达式的后缀式生成,注意:任何运算符的优先级都大于(;(1)初始化:S1和S2为空;(2)读token:tk=ReadOne();(3)Switchtkof(i)#:if(S1为空)exit;elsewhile(S1不为空)/*产生剩余运算符的后缀表示*/op=pop(S1,1);(str1,str2)=pop(S2,2);push(S2,str2+str1+“op”);(ii)运算分量:push(tk,S2);goto(2);(:push(,S1);goto(2);(iii)运算符:if(S1为空|tk优先级大于Top(S1)push(tk,S1);goto(2);elsewhile(tk小于等于Top(S1),带括号表达式的后缀式例子,中缀式表达式:(a+(d+b)*c)+e#,Operatorstack运算符栈S1,Operandstack运算分量栈S2,后缀式:adb+c*+e+,7.1常见的中间表示,抽象语法树-AST无环有向图-DAG(共享的AST),a*c+a*c+e,AST,DAG,+,*,+,a,c,*,e,a,c,+,*,+,a,c,*,e,a,c,7.1常见的中间表示,三地址中间代码三地址:两个操作分量和一个结果的抽象地址;为方便起见,通常用变量名代替抽象地址;三元式No.(op,operand1,operand2)编号(操作符,操作分量1,操作分量2)其中操作分量可以是变量名(抽象地址)或者编号四元式(op,operand1,operand2,result)(操作符,操作分量1,操作分量2,结果)其中操作分量可以是变量名(抽象地址)或者临时变量(抽象地址),三地址代码的例子,a*d+b*c+e,(1)(*,a,d),三元式,(2)(*,b,c),(3)(+,(1),(2),(4)(+,(3),e),(*,a,d,t1),四元式,(*,b,c,t2),(+,t1,t2,t3),(+,t3,e,t4),常用四元式,表达式运算四元式(op,id1,id2,ti),op可以是：ADDI,ADDF,SUBI,SUBF,MULTI,MULTF,DIVI,DIVF,MOD,AND,OR,NOT,EQ,NE,GT,GE,LT,LE类型转换(FLOAT,id1,_,id2)-把整数id1转换成实数,并赋值给id2赋值(ASSIG,id1,n,id2)-把id1的值赋值给id2(长度为n)I/O操作(READI,_,_,id)-输入整数到id(READF,_,_,id)-输入实数到id(WRITE,_,_,id)-把id的值输出,常用四元式,地址加(AADD,id1,id2,id3)-id1对应的地址加上id2后得到的地址赋值给id3标号(LABEL,_,_,label)-定义label为标号,并且定位于当前位置跳转(JUMP,_,_,label)-无条件转向标号label(JUMP0,id,_,label)-如果id为假则转向标号label(JUMP1,id,_,label)-如果id为真则转向标号label,常用四元式,函数(ENTRY,label,size,level)-函数入口(ENDFUNC,-,-,-)-函数出口(CALL,f,true/false,Result)-调用函数f,返回值给Result(RETURN,-,-,-)(RETURN,-,-,t)传递参数(VARACT,id,offset,size)-传地址(VALACT,id,offset,size)-传值结构语句(THEN,t,_,_)-THEN分支标记(ELSE,_,_,_)-ELSE分支标记(ENDIF,_,_,_)-IF语句结束四元式(WHILE,_,_,_)-WHILE语句开始标记(DO,t,_,_)-循环体开始标记(ENDWHILE,_,_,_)-WHILE语句结束标记,操作分量的抽象地址,操作分量的种类数值类整数或者实数标号类标号和过程/函数入口地址类变量和临时变量层数，偏移，存取方式操作分量的FORM结构-内部数据结构数值类：数据值标号类:标号值或过