第七章 中间代码生成(1).ppt

1、中间代码生成在编译器中的作用,词法分析,语法分析,语义分析,中间代码优化,中间代码生成,目标代码生成,分析,合成,中间代码生成,中间代码生成是将源程序翻译成等价中间表示的过程 中间代码生成 不是编译程序的必经阶段 生成中间代码的目的有二： 增强语言的可移植性 进行中间代码级别的优化 中间代码生成方法： 基于Token序列 基于抽象语法树 语法制导的翻译方法：属性文法和动作文法,生成中间代码后，修改编译器后端，可将编译器移植到不同的机器上,源程序,Token 序列,词法分析器,语法分析器,语法分析树,语义分析器,中间代码生成器,中间代码,M1,Mn,中间代码级别的优化,程序(代码)优化分为源程序

2、级别优化、中间代码级别优化、目标代码级别优化 源程序级别优化取决于用户对算法的取舍 编译程序可进行中间代码和目标代码上的优化 中间代码级别优化： 循环内下标变量地址的计算 常表达式节省 公共子表达式节省 循环不变式外提,中间代码级别的优化,int Amn,t; for(int i= 0; im; i+;) for(int j=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) (mul

3、ti,t2,1,t3) (aadd,A,t3,t4),第七章 中间代码生成,7.1 几种常见的中间代码表示 7.2 中间代码生成中的几个问题 7.3 表达式的中间代码生成 7.4 原子语句的中间代码生成 7.5 结构语句的中间代码生成 7.6 声明的中间代码生成,7.1 常见的中间表示,后缀式，逆波兰式 抽象语法树 AST(abstract syntax tree) 无环有向图 DAG(directed acyclic graph) 三元式 四元式,三地址中间代码,7.1 常见的中间表示,后缀式(逆波兰式) 通常用于表达式的中间表示 中缀 (运算符在操作数的中间) a*b 前缀式(运算符在操作

4、数的前面) *ab 后缀式(运算符在操作数的后面) ab* 如何由中缀式转为后缀式？,由抽象语法树生成后缀式,中缀式: a*d + b*c + e,+,*,+,a,d,*,e,b,c,抽象语法树,后根遍历生成后缀式: a d * b c * + e +,先根遍历生成前缀式: + + * a d * b c e,由Token序列生成后缀式（1）-不带括号表达式的后缀式生成,(1) 初始化: S1和S2为空; /S1是运算符栈，S2是运算分量栈 (2) 读token: tk=ReadOne(); (3) Switch tk of (i) #: if (S1为空) exit; else while

5、(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); else while(tk小于等于Top(S1) ,生成后缀式的例子,中缀式表达式 : a * d + b * c + e #,运算符栈 S1,运算分量栈 S2,由Token序列生成后缀

6、式（2）带括号表达式的后缀式生成,注意: 任何运算符的优先级都大于 (; (1)初始化: S1和S2为空; (2) 读token: tk=ReadOne(); (3) Switch tk of (i) #: if (S1为空) exit; else while (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

7、(S1为空 | tk优先级大于Top(S1) push (tk, S1);goto(2); else while(tk小于等于Top(S1) ,带括号表达式的后缀式例子,中缀式表达式: (a + (d + b) * c ) + e #,Operator stack 运算符栈 S1,Operand stack 运算分量栈 S2,后缀式: a d b + 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 常见的中间表示,三地址中

8、间代码 三地址:两个操作分量和一个结果的抽象地址; 为方便起见, 通常用变量名代替抽象地址; 三元式 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

9、), 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 操作 (

10、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为真则转向标

11、号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结构 - 内部数据结构 数值类：数据值 标号类: 标号