为简单 VM 编译 switch 语句

Question

因此，出于学习目的，我正在将 C 的一个子集编译成一个简单的堆栈 VM，并且我想知道如何最好地编译 switch 语句，例如

switch (e) {
  case 0: { ... }
  case 1: { ... }
  ...
  case k: { ... }
}

我正在阅读的这本书提供了一种使用索引跳转对其进行编译的简单方法，但书中描述的简单方案仅适用于连续的、递增的案例值范围。

现在我在第一遍中使用符号标签，在第二遍中我将把标签解析为实际的跳转目标，因为使用标签可以大大简化堆栈指令的初始编译。我现在的想法是使用以下方案将书中的内容概括为以任何顺序排列的任何 case 值序列。调用 case 值 c1, c2, ..., cn 和相应的标签 j1, j2, ..., jn 然后生成以下假定值的指令序列e 位于栈顶:

dup, loadc c1, eq, jumpnz j1,
dup, loadc c2, eq, jumpnz j2,
...
dup, loadc cn, eq, jumpnz jn,
pop, jump :default
j1: ...
j2: ...
...
jn: ...
default: ...

希望表示法清楚，但如果不是:dup = 栈顶的重复值，loadc c = 压入常量 c栈顶，eq = 比较栈顶的两个值并根据比较压入 0 或 1，jumpnz j = 跳转到标签 j 如果栈顶值不为 0，label: = 将在第二次编译过程中解析为实际地址的内容。

所以我的问题是还有哪些其他方式可以编译 switch 语句？对于连续的案例值范围，我的做法比索引跳转表要紧凑得多，但在存在较大差距时效果很好。

Answer 1

首先对所有案例进行排序。然后识别所有(大到值得)连续或接近连续的序列，并将它们视为一个由跳转表处理的单个单元。然后，使用平衡的分支二叉树来最小化平均跳转次数，而不是您的比较和跳转的线性序列。为此，您可以递归地与案例或案例 block 的中位数进行比较。