Skip to content

6 中间代码生成

约 1868 个字 20 行代码 预计阅读时间 6 分钟

1 基本翻译方法

1.1 声明语句

收集类型信息，并为 identifier 分配地址

1.1.1 类型表达式 Type Expression

用于表达“类型的结构”

包含以下几种：

  • 基本类型：integer, real, char, boolean, type_error, void
  • 类型名（为类型表达式命名）
  • 数组构造符（type constructor） + 类型表达式 产生的新类型表达式，如：
    • 使用数组构造符 array 产生的 array(int lenth, Type)
      • 一维数组 int[3] = array(3, int)
      • 二维数组 int[2][3] = array(2, array(3, int))
    • 使用指针构造符 pointer 产生的 pointer(Type)（表达的是指针类型）
    • 使用笛卡尔积构造符 × 产生的 Exp1 × Exp2
    • 使用函数构造符 → 产生的 Exp1 × Exp2 × Exp3 × ExpN → R
    • 使用记录构造符 record 产生的 record((Exp1 × Type1) × (ExpN × TypeN))

以下面的 C 程序为例：

struct stype {
    char[8] name;
    int score;
};
stype[50] table;
stype *p;
  • stype 绑定的类型表达式为： 
    record((name × array(8, char)) × (score × int))
  • table 绑定的类型表达式为： 
    array(50, stype)
  • p 绑定的类型表达式为： 
    pointer(stype)

1.1.2 局部变量的存储分配

  • 对于声明语句，语义分析的主要任务就是收集 identifier 的类型等属性信息，并为每一个标识符分配一个 相对地址
  • 我们可以从类型表达式中计算得出类型在运行时刻所需的存储单元数量，称之为「类型的宽度 width」。在运行时刻，我们可以以此为依据进行地址分配

identifier 的 类型 & 相对地址信息 均保存在 符号表 的对应记录中

  • 为此我们需要添加一些属性和方法
    • 全局变量
      • offset：当前可用地址的偏移量
      • t：当前定义变量的类型
      • w：当前定义变量的基本长度
    • 节点属性
      • type：当前节点的数据类型
      • width：当前节点数据所占的总长

    • 函数 enter(id, type, offset)

      用于向符号表中插入关于变量 id 的记录：类型为 type，起始地址为 offset

1.2 简单赋值语句

  • 对于赋值语句，语义分析的主要任务就是生成对表达式求值的 三地址码 （ id = val ）
  • 为此我们需要添加一些属性和方法
    • 节点属性
      • code：三地址码
      • addr：当前 token 值的存放地址
    • 函数
      • lookup(name) 查询符号表中关于 name 的记录
      • gen(code) 用于产生三地址指令 code
      • newtemp() 产生一个新的临时变量，返回其地址
  • 增量翻译 Incremenatl Translation
    • 在原始的方法中，我们不断 concat 表达式的 code 属性 => 极大的存储开销

    • 通过直接在已经生成的三地址指令后进行追加的方式，就可以把 code concat 的操作去除了

      此时的 gen() 函数不仅需要构造出新的三地址指令，还要负责将其追加到已生成的指令序列之后

      下面以 x = (a+b)*c 为例展示三地址码的产生过程：

t1 = a + b;
t2 = t1 * c;
x = t2;

1.3 数组引用

对于数组引用语句（ a[idx]），我们需要进行数组元素的寻址（确定特定数组元素的存放地址），随后进行三地址码的翻译。

  • 对于「一维数组」的情况，我们假设每个数组元素的宽度为 \(w\)，则 a[i].addr = baseAddr + i * w
  • 对于「二维数组」的情况，我们假设行宽为 \(w_1\) ，单个数组元素的宽度为 \(w_2\) ，则 a[i1][i2].addr = baseAddr + i1 * w1 + i2 * w2
  • 我们不难将其推广至「K 维数组」的情况，a[i1][i2]...[ik] = baseAddr + i1*w1 + i2*w2 + ... + ik*wk，其中 \(w_i = \prod_{j=i+1}^{k} w_j * w_{unit}\)

这次我们只用为节点添加两个属性：

  • type： 当前节点数组元素的类型（包了几层了，每层多少个）
  • offset：截至目前的总偏移量，用于累加 ik * wk
  • array：数组名在符号表中的入口地址

1.4 Switch 语句

  • 我们认为 Switch 的代码是由 条件代码 \(E\) & 各分支情况代码 \(S_i\) 构成的，然后
    • 在每个屁股后面插入 条件跳转指令（效率比较低）
    • 把所有条件测试语句都塞到 test 标签下，并在 \(E\) 后面插入 goto test

1.5 过程调用语句

  • 典型的过程调用语句形如 call id (eList) ，其中 id 为函数名
  • 为方便起见，我们使用队列 q 存放所有参数（参数表达式计算结果）的 addr

2 控制流语句 SDT

  • 程序设计语言的流程一般分为 顺序、分支、循环 三种

  • 以分支语句 \(S \rightarrow if \ B\ then \ S_1 \ else S_2\) 为例：

    • 我们认为它的代码部分由三部分构成：布尔表达式 \(B\)，两个分支结构体 \(S_1, S_2\)

      其中布尔表达式 \(B\) 被翻译成由 跳转指令 构成的跳转代码（选择下一个执行点）

    • 为此，我们需要添加以下属性和方法

      • 属性
        • S.next：保存了 \(S\) 代码的后继指令序号（不算分支体，\(S_1,S_2\) 的 next 属性指向同一标号）
        • B.true：保存当 B == true 时控制流专项指令的标号
        • B.false：保存当 B == false 时控制流专项指令的标号
      • 方法
        • newLabel()：生成用于存放标号的临时变量，返回地址
        • label(token.next)：将吓一跳三地址指令的标号赋给传入的参数（这里只是为了向 \(S,S_1,S_2\) 传递共同后继指令的标号）
    • 而对于 while-do 循环，我们还需要保存结构体起始指令的地址 S.begin

任何 SDT 都可以通过自左向右的深度优先遍历实现

3 布尔表达式 SDT

布尔表达式的基本文法如下：

\[ \begin{align} B \rightarrow &B \ or \ B \ |\ B\ and \ B \ |\ not \ B\\\\ &|\ (B) \ |\ E \ relop \ E \\\\ &|\ true \ |\ false \end{align} \]
  • 其中 \(relop\) 是 关系运算符，包含 < <= > >= == !=，\(E \ relop \ E\) 构成的 关系表达式 也是布尔表达式
  • 几个基本操作的优先级为：not > and > or
  • 在 跳转代码 中，逻辑运算符 && || ! 被翻译成 跳转指令，运算符本身并不会出现在代码中。
  • 我们以 if( x<100 || x>200 && x!=y) x=0; 为例，生成的三地址代码如下： 
        if x<100 goto L2;
    goto L3;
L3: if x>200 goto L4;
    goto L1;
L4: if x!=y goto L2;
    goto L1;
L2: x=0;
L1: next();

4 回填 Backpatching

  • 在为 布尔表达式/控制流语句 生成中间代码时，关键的问题是：确定跳转指令的目标标号（下一条指令应该跳到哪里

  • 由于在 生成跳转指令 时，目标标号尚且不能确定

    • 在上面的例子中，我们将目标标号作为 继承属性 进行传递，但这样需要将标号与具体的地址绑定
    • 在 回填 这一方法中，我们将由 跳转指令 组成的列表 以 综合属性 的形式进行传递
      • 在「生成」跳转指令时，我们并不指定目标标号，而是将其放入由跳转指令组成的列表中
      • 同一个列表中的所有跳转指令都具有「相同的目标标号」
      • 直到能够确认标号时，再「统一」对列表中的跳转指令进行填充
  • 在「回填」方法中，我们需要为非终结符 \(B\) 添加以下的 综合属性 和 函数
    • 综合属性
      • B.trueList：指向列表，其中所有跳转指令需要获取 B == true 时的目标标号
      • B.falseList：（略）
    • 函数
      • makeList(i)：创造仅包含 i 的列表（ i 为 跳转指令 标号），返回列表指针
      • merge(p1, p2)：合并 p1 & p2 指向的列表，返回结果指针
      • backpatch(p, i)：将列表 p 中的所有目标标号置为 i