3

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

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

我正在阅读的这本书提供了一种使用索引跳转编译它的简单方法，但书中描述的简单方案仅适用于连续的、升序的 case 值范围。

现在，我在第一遍使用符号标签，在第二遍中，我将把标签解析为实际的跳转目标，因为有了标签可以大大简化对堆栈指令的初始编译。我现在的想法是使用以下方案将书中的内容以任何顺序概括为任何 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 语句的其他方法是什么？我的做法比连续范围的 case 值的索引跳转表要紧凑得多，但是当有很大的差距时效果很好。

4

1 回答 1

3

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

于 2014-03-04T12:07:26.963 回答