编译器构造/中间表示
不同编译器之间内部表示的形式差异很大。如果后端由前端作为子程序调用，那么中间表示可能就是某种形式的带注释的解析树，可能还包含补充表。如果后端作为一个单独的程序运行，那么中间表示很可能就是某种低级的伪汇编语言或寄存器传输语言（它可以只是数字，但如果它是人可读的，调试会更容易）。
在本章中，我们将讨论中间代码的基于堆栈的表示。它有许多优点，其中一些是
- 基于堆栈的语言的解释器往往更紧凑和直接。
- 语言的语法往往很简单。
但是，这种表示也有以下缺点，使其不适合于操作和改进代码
- 更改指令顺序并非易事。
- 对基于堆栈的代码的研究很少。
基于堆栈的代码在控制流中经常会出现问题。
将三地址代码等表示转换为基于堆栈的代码通常是微不足道的，因此这种情况留作练习。反过来，这是一个具有挑战性的问题。
将基于堆栈的代码转换算法背后的主要任务是识别操作之间的依赖关系。而条件跳转和无条件跳转使得确定这些依赖关系变得困难。因此，没有它们（条件跳转和无条件跳转）的代码可以以直接的方式转换为三地址代码，如下所示
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; }
- 编写一段基于堆栈的代码，以便根据执行路径，堆栈的深度在该段代码之后可能会有所不同。
- 草拟将三地址代码转换为基于堆栈的代码的算法，假设没有跳转。提示：将堆栈中的每个位置视为一个对应的临时变量。
- 编写一段基于堆栈的代码，使得在每个位置的堆栈高度无法在编译时确定。
- 进一步阅读
- Raja Vallee-Rai The Jimple Framework. 1998. [1]
- expr.c 来自 GCC。
- CFG.java 来自 Soot 框架。
- 解释器的堆栈缓存 由 M. Anton Ertl 撰写
