编译器构造/基于堆栈的表示
在本章中，我们将讨论中间代码的基于堆栈的表示。它有很多优点，其中一些是
- 基于堆栈的语言的解释器往往更紧凑，更直接。
- 语言的语法往往很简单。
但这种表示也有一些缺点，这使得它不适合用于操作和改进代码
- 改变指令顺序并不容易。
- 基于堆栈的代码的研究很少。
基于堆栈的代码在控制流中经常出现复杂情况。
将三地址代码等表示形式转换为基于堆栈的代码通常很简单，因此这种情况留作练习。这是问题的反面，是一个具有挑战性的问题。
将基于堆栈的代码转换算法背后的主要任务是识别操作之间的依赖关系。而条件和无条件跳转使得很难弄清楚这些依赖关系。因此，没有它们（条件和无条件跳转）的代码可以以直接的方式转换为三地址代码，如下所示
push 2 push 3 push 4 add mul
我们可以看到每个堆栈位置都有一个对应的临时变量。换句话说，存储和加载分别仅由 push 和 pop 完成，并且一次可以访问的临时变量仅限于顶部，而不是通常情况下变量可以自由指定的情况。
s0 = 2 s1 = 3 s2 = 4 s1 = s1 + s2 s0 = s0 * s1
当一个变量被类型化时，采用SSA 形式可能会很有益。这省去了分析每个变量在某一时刻持有什么类型的需要，正如下面所示，这可能相当棘手。这种调整可以在转换后进行，也可以在转换代码的同时进行。
现在，假设执行可能不会从上到下进行。在这种情况下，我们基本上必须在翻译代码之前分析控制流。更具体地说，我们计算每个指令对堆栈深度的贡献。例如，
... goto A // unconditionally jump to label A ... A: // a label add // push the sum of two values popped from the stack. ...
正如我们所看到的，在标签 A 处，堆栈的状态取决于指令“goto A”之前的操作。
一种保守的方法是在转换之前对字节码进行注释。基本思想是，当我们解释代码时，我们既知道我们在哪里，也知道堆栈有多高。因此，通过假装我们正在评估代码，我们可以计算每个位置的堆栈高度。为此的算法类似于（在实际编写中，必须安排代码以使其终止）。
procedure eval(start, depth)
{
for i from start to code.length
{
depth_at[i] = depth
case code[i]
{
'push': depth = depth + 1
'pop': depth = depth - 1
'goto': i = code[i].target
'if_so_goto': eval(code[i].target, depth)
...
}
}
}
eval(0, 0) // start the calculation
在实践中，对上述解决方案进行编码可能很繁琐，尤其是在语言中的指令数量很大时。Java 字节码就是一个著名的例子。因此，以下提供了一个激进的替代方案，即不是以通常的顺序方式转换基于堆栈的代码，而是以基本块（即没有跳转的块）为单位进行转换。为了说明这一点，请考虑以下内容
0 (A): push 10 1 (A): push 13 2 (A): less_than // pop < pop 3 (A): if_not_goto 6 4 (B): push '10 < 13' 5 (B): goto 7 6 (C): push 'it is not 10 < 13; your computer is broken!' 7 (C): print
在上面，我们可以识别出三个基本块：第一个 (A) 从 0 到 3，第二个 (B) 从 4 到 5，第三个 (C) 从 6 到 7。我们首先编译 A，然后我们知道 B 或 C 开始时的堆栈高度。每个块编译完成后，我们按它们在源代码中出现的顺序输出块。
敏锐的读者会注意到，在本节中，我们一直假设堆栈的深度在每个指令位置都是固定的，因此可以在编译时确定。如果该假设不成立，那么我们必须在运行时拥有某种堆栈。
- 为以下每个高级表达式编写基于堆栈的代码
- 10 * (20 + 30);
- if a < b then -a else -b;
- case a % 3 { 0: x; 1: y; 2: z; }
- 编写一段基于堆栈的代码，以便堆栈的深度在执行路径完成后可能会有所不同。
- 概述将三地址代码转换为基于堆栈的代码的算法，假设没有跳转。提示：将堆栈中的每个位置视为具有一个对应的临时变量。
- 编写一段基于堆栈的代码，使得堆栈在每个位置的高度无法在编译时确定。
- 进一步阅读