编译原理

第六章 中间代码生成

2020-04-02 10:00 CST
2020-04-15 13:42 CST
CC BY-NC 4.0

中间代码

中间代码的表示:

  • 抽象语法树
  • 三地址代码

中间代码的好处:

  • 重定位:为新的机器创建编译器只需要做重中间代码到目标代码的翻译器(编译器的前端独立)
  • 高层次的优化:优化与源语言和目标机器都无关

中间代码的实现:静态类型检查和中间代码生成的过程都可以用语法制导的翻译(SDT)来描述和实现。

表达式的有向无环图

语法树中,公共子表达式每出现一次,就有一颗对应的子树。表达式的有向无环图(DAG)能够指出表达式中的公共子表达式,更简洁地表示表达式。

DAG构造

  • 可以用和构造抽象语法树一样的SDD来构造,
  • 不同的是每次创造新的节点/叶子时先检查是否已存在同样的节点,如果已经存在则直接返回已有的节点。

三地址代码

每条指令右侧最多有一个运算符,一般写成x = y op z

允许的运算分量:

  • 名字:源程序中的名字作为三地址代码的地址;
  • 常量:源程序中出现或生成的常量;
  • 编译器生成的临时变量。

指令集合

  • 运算/赋值指令:x = y op zx = op y
  • 复制指令:x = y
  • 无条件转移指令:goto L
  • 条件转移指令:if x goto Lif False x goto L
  • 条件转移指令:if x relop y goto L
  • 过程调用/返回:param ... call p, n,$n$为参数个数
  • 带下标的复制指令:x = y[i]x[i] = y,下标表示偏移量(字节)而不是元素个数
  • 地址/指针赋值指令:x = &yx = *y*x = y

表示方法

在实现时,可以使用四元式/三元式/间接三元式/静态单赋值来表示三地址指令。

四元式:op arg1 arg2 res,可以实现为记录(或结构)。

  • 单目运算符不使用arg2
  • param运算不使用arg2res
  • 条件转移/非条件转移将目标标号放在res字段。

三元式:op arg1 arg2,使用三元式的位置来引用三元式的运算结果。

  • 用语句的标号来表示语句的运行结果;
  • x[i] = y等指令需要拆分成两个三元式,先求x[i]的地址,再进行赋值。

间接三元式:

  • 包含了一个指向三元式的指针的列表,
  • 可以对这个列表进行操作,完成优化功能,操作时不需要修改三元式中的参数。

静态单赋值(SSA):所有赋值都是针对不同名称的变量。(所有可能的取值都有不同的名称)。

类型和声明

类型检查:利用一组规则来检查运算分量的类型和运算符的预期类型是否匹配

类型信息的用途:查错、确定名字所需要的内存空间、计算数组元素的地址、类型转换、选择正确的运算符

类型表达式

类型表达式:表示类型的结构

  • 可能是基本类型
  • 也可能通过类型构造算子作用于类型表达式而得到

类型构造算子:array(数组)、record(字段)、$\rightarrow$(函数)、笛卡尔积

类型等价

不同的语言有不同的类型等价的定义:

  • 结构等价:
    • 它们是相同的基本类型,或
    • 由相同的构造算子作用于结构等价的类型而得到,或
    • 一个类型是另一个类型表达式的名字
  • 名等价:
    • 类型名仅代表自身

局部变量的存储布局

  • 变量的类型可以确定变量需要的内存(类型的宽度)
  • 函数的局部变量总是分配在连续的区间
  • 变量的类型信息保存在符号表中

声明序列的SDT

在处理一个过程/函数时,局部变量应该放到单独的符号表中去。

这些变量的内存布局独立,从0地址开始每分配一个变量,偏移量增加对应的值(宽度)。

记录和类中的字段

约定:

  • 一个记录中各个字段的名字各不相同;
  • 字段名的偏移量是相对于该记录的数据区字段而言的。

记录类型使用一个专用的符号表,对各个字段的类型和相对地址进行编码。

增量式翻译方案

类似于语义分析的边扫描边生成。

  • gen不仅构造新的指令,还要将它添加到至今为止生成的指令序列之后。
  • 不需要code指令保存已有的代码,而是对gen的连续调用生成一个指令序列

数组访问

$base + i_1 \times w_1 + i_2 \times w_2 + \dots$(看ppt)

类型检查和转换

类型系统:

  • 给每一个组成部分赋予一个类型表达式
  • 通过一组逻辑规则来表达类型表达式必须满足的条件
  • 可发现错误、提高代码效率、确定临时变量的大小

类型检查分为动态和静态两种。

强类型的语言:如果编译器中的类型系统能够保证它接受的程序在运行时刻不会发生类型错误,则该语言的这种实现称为强类型的。

类型系统的分类:

  • 类型综合:根据子表达式的类型构造出表达式的类型。如$f:s \rightarrow t$,$x:s$,则$f(x):t$。
  • 类型推导:根据语言结构的使用方式来确定该结构的类型。如$f(x)$是一个表达式,则对于某些类型$\alpha$和$\beta$,满足$f:\alpha \rightarrow \beta$且$x:\alpha$。

运算符重载、类型转换(隐式/显式、拓宽/窄化)(看ppt)

控制流的翻译

布尔表达式可用于改变控制流/计算逻辑值。

短路代码:通过跳转指令实现控制流,逻辑运算符本身不出现。

三种控制流和布尔表达式语句的翻译(看ppt)