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

中间间代码码生成在编译编译 器中的作 用 词法分析 语法分析 语义 分析 中间代码优 化 中间代码生成 目标代码生成 分析合成 中间间代码码生成 中间间代码码生成是将源程序翻译译成等价中间间表示的过过程 中间间代码码生成 不是编译编译 程序的必经经阶阶段 生成中间间代码码的目的有二： 增强语语言的可移植性 进进行中间间代码级别码级别 的优优化 中间间代码码生成方法： 基于Token序列 基于抽象语语法树树 语语法制导导的翻译译方法：属性文法和动动作文法 生成中间间代码码后，修改编译编译 器后端，可将编将编 译译器移植到不同的机器上 源程序Token 序列 词法分析器 语法分析器 语法 分析 树 语义分析器 中间代码生成器 中间代码 M1 Mn 中间代码级别 的优化 程序(代码码)优优化分为为源程序级别优级别优 化、中间间代码级别码级别 优优化、目标标代码级别优码级别优 化 源程序级别优级别优 化取决于用户对户对 算法的取舍 编译编译 程序可进进行中间间代码码和目标标代码码上的优优化 中间间代码级别优码级别优 化： 循环环内下标变标变 量地址的计计算 常表达式节节省 公共子表达式节节省 循环环不变变式外提 中间代码级别 的优化 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)(subi,j,0,t5) (multi,t5,1,t6)(multi,t5,1,t6) (multi,t6,1,t7)(multi,t6,1,t7) (aadd,t4,t7,t8)(aadd,t4,t7,t8) (subi,i,0,t1)(subi,i,0,t1) (multi,t1,n,t2)(multi,t1,n,t2) (multi,t2,1,t3)(multi,t2,1,t3) (aadd,A,t3,t4)(aadd,A,t3,t4) 第七章 中间间代码码生成 l 7.1 几种常见见的中间间代码码表示 l 7.2 中间间代码码生成中的几个问题问题 l 7.3 表达式的中间间代码码生成 l 7.4 原子语语句的中间间代码码生成 l 7.5 结结构语语句的中间间代码码生成 l 7.6 声明的中间间代码码生成 7.1 常见见的中间间表示 l 后缀缀式，逆波兰兰式 l 抽象语语法树树 AST(abstract syntax tree) l 无环环有向图图 DAG(directed acyclic graph) l 三元式 l 四元式 三地址中间代码 7.1 常见见的中间间表示 后缀缀式(逆波兰兰式) 通常用于表达式的中间间表示 中缀缀 (运算符在操作数的中间间) a*b 前缀缀式(运算符在操作数的前面) *ab 后缀缀式(运算符在操作数的后面) ab* 如何由中缀缀式转为转为 后缀缀式？ 由抽象语语法树树生成后缀缀式 中缀式: a*d + b*c + e + * + ad * e bc 抽象语法树 后根遍历生成后缀式: 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 (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) (str1, str2)=pop(S2,2); push(S2, str2+str1 + “op”); push(S1,tk); goto (2); 生成后缀缀式的例子 中缀缀式表达式 : a * d + b * c + e # 运算符栈 S1 运算分量栈 S2 由Token序列生成后缀式（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 (S1为为空 | tk优优先级级大于Top(S1) push (tk, S1);goto(2); else while(tk小于等于Top(S1) (str1, str2)=pop(S2,2); push(S2, str2+str1 + “op”); goto(2); (iv) ): while (Top(S1) ( ) op = pop(S1,1); (str1, str2)=pop(S2,2); push(S2, str2+str1 + “op”); pop(S1,1); goto (2); 带括号表达式的后缀式例子 中缀缀式表达式: (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 ASTDAG + * + ac * e ac + * + ac * e ac 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的值输值输 出 常用四元式 l地址加 (AADD, id1, id2, id3) - id1对应的地址加上id2后得到的地 址赋值给 id3 l标号 (LABEL, _, _, label)- 定义label为标号 ,并且定位于当 前位置 l跳转 (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结结构 - 内部数据结结构 数值类值类