表达式翻译相关技术解析

# 表达式翻译相关技术解析 ## 1. 条件语句处理 在程序执行中，条件语句的处理至关重要。当节点 `c.prn(1)` 推导出 `if - then - else` 语句时，设 `n1;...;nx` 为执行的 `if` 部分或 `else` 部分的扁平化序列，新程序剩余部分为 `c′.prn = n1;...;nx;tail(c.prn)`。对于 `y < x`，节点 `nx` 是节点 `nx−1` 的直接后继，`nx` 的父节点 `Fa(nx)` 是推导出执行的 `if - then - else` 语句的节点 `c.prn(1)`。通过归纳假设可得 `c.prn(2) = succ(c.prn(1)) = succ(Fa(nx))`，对于尾部的其他节点，结论可直接由归纳假设得出。 当节点 `c.prn(1)` 推导出 `if - then` 语句时，设 `n1;...;nx` 为 `if` 部分的扁平化序列。若执行该部分，处理方式与 `if - then - else` 语句类似；若不执行，则 `c′.prn = tail(c.prn)`，结论同样可由归纳假设直接得出。 为了后续参考，我们将引理 90 纳入具有幽灵组件的格式良好的 C0 程序应满足的不变式中。若引理 90 对 `c` 成立，则称不变式 `inv - prn - clr(c)` 得到满足。 ## 2. Sethi - Ullman 算法 ### 2.1 表达式节点与代码生成 表达式 `e` 具有推导树 `T`，其根节点 `n` 位于表达式节点集合 `en` 中。通过对推导树 `T` 的结构进行归纳，我们定义了表达式 `e` 的语义，代码生成也将基于这些树进行归纳定义。 一般来说，若表达式节点 `n` 有两个表达式子节点 `n′` 和 `n′′`，生成的代码将按以下步骤执行： 1. 计算从节点 `n′` 和 `n′′` 推导得到的表达式 `e′` 和 `e′′` 作为中间结果。 2. 计算从节点 `n` 推导得到的表达式 `e`，并丢弃中间结果（即存储中间结果的寄存器可被覆盖）。 若节点 `n` 只有一个表达式子节点 `n′`，处理方式类似。没有表达式子节点的表达式节点将生成变量名或常量。 ### 2.2 寄存器使用与表达式求值顺序 我们使用 32 个通用寄存器进行表达式求值。其中，寄存器 `gpr(05)` 固定为零，寄存器 `gpr(285)` 到 `gpr(315)` 分别用于基指针、栈指针、堆指针和链接地址。对于包含乘法和除法的表达式，还需要寄存器 `gpr(205)` 到 `gpr(275)` 来执行软件乘法和除法算法。因此，寄存器 `gpr(15)` 到 `gpr(195)` 可用于表达式求值。在翻译赋值语句时，其中一个寄存器将暂时不可用，最终只剩下 18 个寄存器用于表达式求值。幸运的是，只要按正确顺序计算子表达式，这些寄存器足以计算推导树中最多有 `2^18 = 262144` 个表达式节点的所有表达式。这种顺序在 [SU70] 中被确定，具体规则为：对于兄弟节点 `n` 及其子树 `T`，先计算表达式节点数量较多的子树，在计算较小子树时仅保留该计算结果。 ### 2.3 石子游戏模型 为了分析寄存器消耗，我们使用石子游戏对表达式求值进行建模。该游戏在根树 `T` 上进行，每个节点 `n` 最多有两个子节点。游戏规则如下： 1. 可以随时从自由石子列表中取一个石子放在树的叶子节点上，此操作将该石子从自由列表中移除。 2. 若节点 `n` 的唯一子节点有石子 `i`，则可将该石子从子节点滑到节点 `n` 上。 3. 若节点 `n` 的子节点分别有石子 `i` 和 `j`，则可将其中一个石子滑到节点 `n` 上，并将另一个石子从图中移除并放回自由列表。 我们定义树的大小 `|T|` 为树中节点的数量，即 `|T| = #T.V`。定义 `P(n)` 为在大小为 `n`（即最多有 `n` 个节点）的任何树上成功玩游戏所需的最少石子数，并通过对 `n` 进行归纳证明了引理 91：`P(n) ≤ max{1,⌈logn⌉}`。 ### 2.4 实现步骤 若要为表达式 `e` 的求值生成代码，可按以下三个阶段进行： 1. **计算子树大小**：对于节点 `n ∈ T.A`，用 `size(n) = #{u | n◦u ∈ en}` 表示其后代中表达式节点的数量。为了确定上述策略的移动，需要知道每个表达式节点 `n ∈ en` 的 `size(n)`。具体做法是，将类型为 `DTE`（表示推导树元素）的记录增加整数组件 `.size` 和 `.pebble`，在第一阶段遍历树 `T′`，并将子树的大小（仅计算表达式节点）记录在 `.size` 组件中。 2. **递归遍历树并维护自由列表**：在为表达式 `e` 生成代码之前，创建一个“初始自由列表”，作为包含所有可用于表达式求值的寄存器编号的链表。然后从根节点 `r` 开始递归遍历树 `T`。在树 `T′` 中，对于任何有子节点 `n′` 和 `n′′` 的节点 `n`，先遍历 `.size` 组件较大的子树；若大小相等，则先遍历左子树。根据石子游戏的移动要求维护自由列表，并为每个推导树元素的 `.pebble` 组件记录放置在该 `DTE` 所建模节点上的石子编号。 3. **生成代码**：同样通过递归树遍历生成代码，先遍历较大的子树；若大小相等，则先遍历左子树。对于表达式节点 `n` 执行的操作，从节点子节点的石子所指示的寄存器中获取操作数，并将结果存储在节点上的石子所指示的寄存器中。生成的代码将按生成顺序执行，从而按照 Sethi - Ullman 策略高效使用寄存器。 需要注意的是，阶段 2 和 3 可以合并为一个阶段。以下是一个简单的 mermaid 流程图，展示了整个过程： ```mermaid graph TD A[开始] --> B[计算子树大小] B --> C[递归遍历树并维护自由列表] C --> D[生成代码] D --> E[结束] ``` ## 3. R 标签 在表达式求值过程中，我们同时定义了表达式类型 `etype(e, f)`、左值 `lv(e, c)` 和右值 `va(e, c)`。为了向代码生成算法指示是为左值还是右值生成代码，我们为推导树的表达式节点 `i ∈ en` 附加一个二进制标签 `R : en → B`。若 `R(i) = 0`，则为节点 `i` 的左值生成代码；若 `R(i) = 1`，则为右值生成代码。标签 `R` 通过对推导树的表达式节点进行递归情况拆分来定义，具体如下： ### 3.1 表达式节点为语句节点子节点的情况 | 语句类型 | 语句形式 | 节点设置 | R 标签设置 | | ---- | ---- | ---- | ---- | | 赋值语句 | `e = e′` | 节点 `n` 有子节点 `i, i′ ∈ en`，`bw(i) = e`，`bw(i′) = e′` | `R(i) = 0`，`R(i′) = 1` | | while 循环 | `while e { body }` | 节点 `n` 有子节点 `i ∈ en`，`bw(i) = e` | `R(i) = 1` | | 条件语句 | `if e { if - part }` 或 `if e { if - part } else { else - part }` | 节点 `n` 有子节点 `i ∈ en`，`bw(i) = e` | `R(i) = 1` | | new 语句 | `e = new t ∗` | 节点 `n` 有子节点 `i ∈ en`，`bw(i) = e` | `R(i) = 0` | | 函数调用 | `e0 = g(e1,...,ep)` 或 `e0 = g()` | 节点 `n` 有子节点 `i0 ∈ en`，`bw(i0) = e0`；若有参数，参数 `ej` 由节点 `ij ∈ en` 推导 | `R(i0) = 0`；对于参数 `ej`，`R(ij) = 1` | | 返回语句 | `return e` | 节点 `n` 有子节点 `i ∈ en`，`bw(i) = e` | `R(i) = 1` | ### 3.2 表达式节点不是语句节点子节点的情况 | 表达式类型 | 表达式形式 | 节点设置 | R 标签设置 | | ---- | ---- | ---- | ---- | | 二元运算符 | `e◦e′` | 节点 `n` 有子节点 `i, i′ ∈ en`，`bw(i) = e`，`bw(i′) = e′` | `R(i) = R(i′) = 1` | | 一元运算符 | `◦e` | 节点 `n` 有子节点 `i ∈ en`，`bw(i) = e` | `R(i) = 1` | | 常量 | `c` | 节点 `n` 有子节点 `i ∈ en`，`bw(i) = c` | `R(i) = 1` | | 括号项 | `(e)` | 节点 `n` 有子节点 `i ∈ en`，`bw(i) = e` | `R(i) = 1` | | 结构体元素 | `e.x` | 节点 `n` 有子节点 `i ∈ en`，`bw(i) = e` | `R(i) = 0` | | 数组元素 | `e[e′]` | 节点 `n` 有子节点 `i, i′ ∈ en`，`bw(i) = e`，`bw(i′) = e′` | `R(i) = 0`，`R(i′) = 1` | | 指针解引用 | `e∗` | 节点 `n` 有子节点 `i ∈ en`，`bw(i) = e` | `R(i) = 1` | | 取地址 | `e&` | 节点 `n` 有子节点 `i ∈ en`，`bw(i) = e` | `R(i) = 0`，`R(n) = 1` | | 单子节点情况 | 节点 `n` 只有一个子节点 `i` 且 `i ∈ en` | | `R(i) = R(n)` | 为了计算表达式节点 `n` 的 `R(n)` 值，可在类型为 `DTE` 的推导树元素中添加组件 `.R` 来存储 `R` 标签的值。这些标签的计算可以与 `.size` 组件的计算一起进行。 ## 4. 可组合的 MIPS 程序 设 `d` 和 `d′` 为 MIPS 配置，`p ∈ (B32)∗` 为 MIPS ISA 程序，`q ∈ B30 ◦ {00}` 为对齐的字节地址。假设程序 `p` 从地址 `q` 开始存储在配置 `d` 的内存中，即 `d.m4·|p|(q) = p`，且程序 `p` 存储在代码区域 `[q : q + 32 (4·|p| - 1)32] ⊆ [a : b]` 中。若存在一个 MIPS 计算 `(d0,...,dK)` 满足以下条件，则称执行以这种方式存储的程序 `p` 结束于配置 `d′`，并记为 `d →∗ p,q d′`： 1. 计算从配置 `d` 开始，结束于配置 `d′`，即 `d0 = d ∧ dK = d′`。 2. 程序计数器最初位于程序 `p` 的起始位置，最终位于程序 `p`