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

中间代码生成在编译器中的作用 词法分析 语法分析 语义分析 中间代码优化 中间代码生成 目标代码生成 分析 合成 中间代码生成 中间代码生成是将源程序翻译成等价中间表示的过程中间代码生成不是编译程序的必经阶段生成中间代码的目的有二 增强语言的可移植性进行中间代码级别的优化中间代码生成方法 基于Token序列基于抽象语法树语法制导的翻译方法 属性文法和动作文法 生成中间代码后 修改编译器后端 可将编译器移植到不同的机器上 源程序 Token序列 词法分析器 语法分析器 语法分析树 语义分析器 中间代码生成器 中间代码 M1 Mn 中间代码级别的优化 程序 代码 优化分为源程序级别优化 中间代码级别优化 目标代码级别优化源程序级别优化取决于用户对算法的取舍编译程序可进行中间代码和目标代码上的优化中间代码级别优化 循环内下标变量地址的计算常表达式节省公共子表达式节省循环不变式外提 中间代码级别的优化 intA m n t for inti 0 i m i for intj 0 j n j t A i j A i j A j i A j i 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 else while 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 else while 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结构 内部数据结构数值类 数据值标号类 标号值或过程 函数的入口地址变量 level offset mode 临时变量的层数为 1 偏移为编号 mode dir或indir 为便于阅读 课件和书中用对应的变量名 函数名或者标号 值等代替相应的FORM结构 作业 请写出下列表达式的后缀式表示 a b d d a c e d a b c d a b c