编译原理 6
第六章: 中间代码生成
- 中间代码表示
- 有向无环图DAG
- 三地址代码: x = y op z
- 类型检查: 类型, 类型检查, 表达式的翻译
- 中间代码生成: 控制流, 回填
- 编译器前端
- 与后端在中间代码分开
- 前端是机器无关的
- 词法语法->语义检查->中间代码生成
- 中间代码表示及其好处
- 形式: 抽象语法树, 三地址代码
- 重定位: 新的机器, 只需新的后端(中间代码到目标代码翻译器)
- 高层次的优化: 中间代码的优化与源代码和目标代码无关
- 中间代码的实现
- 静态类型检查和中间代码生成, 都可以用语法制导翻译实现
表达式的有向无环图
- 公共子表达式每出现一次, 就有一棵对应的子树
- 表达式的有向无环图, 能够指出表达式中的公共子表达式, 更简洁
- 寻找重复
- 值编码: op, l, r, 其中l, r为子节点编号
- 根据值编码去重, 新结点与某个已有结点, 值编码相同, 则重用
三地址代码
- 每条指令右侧最多有1个运算符
- 允许的运算分量
- 名字: 源程序的中的名字
- 常量: 源程序中出现或生成的常量
- 临时变量: 分析过程中生成的名字
- 指令集合
- 运算赋值: x = y op z; x = op y
- 复制指令: x = y
- 无条件转移指令: goto L
- 条件转移指令: if x goto L; if False x goto L
- 条件转移指令: if x relop y goto L
- 过程调用: param $x_1$, …, param $x_n$ call p,n
- 下标复制指令: x = y[i]; x[i] = y
- 地址, 指针赋值指令: x = \&y; x = y, x = y
- 表示方式
- 四元式: 3个地址, 一个运算符: op arg1 arg2 result
- 单目运算符不使用arg2
- param运算不使用arg2和result
- 条件转移/非条件转移, 目标标号在result
- 一些情况
- 引用: x = y[i]; =[] y i x
- 引用: x[i] = y; []= i y x
- 三元式: 没有result的四元式, 使用某行的结果, 直接用左侧标号(0起始)
- 一些情况
- 引用: x[i] = y; 先计算x[i]的地址, 之后才能赋值, 需要2行
类型和声明
- 类型检查: 利用一组规则, 检查运算分量的类型和运算符的预期类型是否匹配
- 类型信息的用途: 差错, 确定内存空间, 计算地址, 类型转换, 选择正确的运算符
类型表达式
- 表示类型的结构
- 基本类型
- boolean, char, integer, float, void
- 类型构造算子, 作用于类型表达式
- array(数字, 类型表达式)
- record(字段名 × 类型表达式)
- -> 函数类型的类型表达式
- 类型等价
- 相同的基本类型
- 由相同的构造算子, 作用于结构等价的类型而得到
- 一个类型是另一个类型表达式的名字
- 名等价: 类型名仅代表自身(仅有前两个条件)
- 类型的声明
- 应用文法和对应的语法制导定义, 可得类型表达式和内存布局
局部变量存储布局
- 类型确定需要的内存大小, 可变大小的只需考虑指针
- 局部变量总是分配在连续区间, 给出相对地址
- 变量类型信息存在符号表中
- 声明序列的SDT
- 局部变量放入单独的符号表
- 变量内存布局是独立的
- SDT处理方法
- offset记录当前可用的相对地址
- 每分配一个, offset增加其宽度
- top.put(id.lexeme, T.type, offset)
- offset看作继承属性
- 记录和类中的字段
- 约定
- 记录字段名各不相同
- 相对地址是相对于该记录的数据区字段而言的
- 记录类型使用专门的符号表
- 对其各个字段的类型和相对地址进行单独编码
- 记录类型record(t), t为符号表对象, 保存该记录类型各个字段的信息
表达式代码的SDD
- 表达式翻译成三地址代码的SDD
- code表示代码
- addr表示存放结果的地址
- new Temp()表示生成临时变量
- gen()生成指令
数组元素的寻址
- 数组连续存放, 0开始编号, 第i个元素的地址为
base + i * w
- k维数组的寻址:
A[i1][i2]...[ik], 则base+i1*w1+...+ik*wk, wi是一个当前层级元素的宽度, 相当于其后的维度取值范围, 连乘的积
- 数组的翻译方案
- 非终结符L: $L\to L[E]|\mathbf{id}[E]$ 三个综合属性
- L.array: 指向数组名字对应的符号表条目的指针, L.array.base是数组基地址
- L.addr: 指示一个临时变量, 计算数组引用的偏移量
- L.type: 是L生成的子数组的类型
- L.type.width给出其宽度
- L.type.elem给出其数组元素
- L的代码计算偏移量, 据此进一步计算加上base, 使用三地址指令
x=a[i]类型的检查和转换
- 类型系统
- 每个组成部分赋予类型表达式
- 一组规则来表达类型表达式必须满足的条件
- 可以: 发现错误, 提高代码效率, 确定临时变量的大小
- 类型检查可以分为动态和静态两种
- 强类型: 编译器中的类型系统能够保证其接受的程序在运行时刻不会发生类型错误
- 类型系统分类
- 类型综合: 子表达式的类型->表达式的类型
- 类型推导: 语言结构的使用方式, 确定该结构的类型(函数重载)
- 类型转换
- 隐式转换: 编译器自动
- 显式转换: 程序员用代码指定的转换
- 拓宽类型转换/窄化类型转换
- 函数max: 寻找两个类型在拓宽层次结构中的LCA最小公共祖先
- 函数widen: 生成必要的类型转换代码
控制流的翻译
- 通过跳转指令实现控制流, 逻辑运算符本身不出现
- 短路: 逻辑或, 靠前的为真就不计算后面的; 逻辑与, 靠前的为假就不计算后面的
- 自顶向下翻译控制流语句
- 继承属性
- B.true B为真时跳转目标
- B.false B为假时跳转目标
- S.next S 执行完毕的跳转目标
- 增量生成: gen(content)
布尔表达式
- 没有与或非, 而是通过跳转目标设定实现
- 或: Bi.true = B.true, Bi.false = (下一语句的开头)
- 与: Bi.false = B.false, Bi.true = (下一语句的开头)
- 非: 交换false 和 true
- 子语句
- B -> E1 rel E2: E1.code || E2.code || if ….. goto B.true || goto B.false
- B -> true: goto B.true
- B -> false: goto B.false
- 布尔值和跳转代码
- 布尔表达式也有可能是求值: 构建语法树, 根据表达式的不同角色来处理
- 对于来自if和while, 生成跳转的代码
- 对于赋值语句, 生成计算右值的代码
回填
- 布尔表达式和控制流语句生成: 某些跳转指令应该跳转到哪里
- 生成跳转需要S.next, 但S没有生成, 需要第二趟处理; 一趟处理完毕: 使用综合属性
- 基本思想
- 跳转语句的目标不确定时, 记录该跳转指令的标号, 但不生成跳转目标, 标号被记录到B的综合属性B.falselist/B.truelist中
- 当值已知时, 把falselist中的所有指令的目标都填上这个值
- 回填翻译
- 综合属性: 包含跳转指令的标号
- truelist: 取值true时执行的指令标号列表
- falselist: 取值false时执行的指令标号列表
- 辅助函数
- makelist(i): 创建一个包含指令标号i的列表
- merge(p1, p2): p1p2指向的标号列表合并并返回
- backpatch(p, i): 将i作为跳转目标, 插入p的所有指令中
- 产生式的改动: 添加$M\to\epsilon$, M.instr = nextinstr, 添加于待跳转目标的开头,添加跳转目标, 用于backpatch
- 控制流转移语句N
- 综合属性
- nextlist: 包含该语句执行完毕后, 紧接着执行的下一条指令的标号
- 产生式的改动: 添加$N\to\epsilon$在某S后
- 将会产生goto语句, 表示S执行后跳转到哪里
- N.nextlist = makelist(nextinstr), 直到交给顶层, 进行backpatch
扫一扫，分享到微信
{title}
