Question

反编译器用符号表存储在程序中使用的变量的有关信息。在二进制程序中变量是用变量的地址来标识；变量没有与之关联的名称。全局变量是有实际内存地址的变量；通过它们的段和偏移量来存取。相对于框架指针，位于负偏移上的变量是与这个栈框架对应的子程序的局部变量，位于正偏移上的变量是该子程序的实际参数。由于编译器为了效率的缘故使用寄存器变量，因此起初先把所有寄存器看作变量；再对寄存器做进一步分析以确定它们是否果真代表寄存器变量 (见第 5 章第 5.2.9 节)。在代码生成期间赋予变量唯一的名称，见第 7 章说明。

符号表必须能够有效地提供一个项目的有关信息，并且管理数目可变化的变量；因此，符号表可在必要时动态生长。符号表的性能测量是通过存取一个项目和插入一个新的数据项到表中。

3.4.1 数据结构

符号表用多种数据结构表现。有些实现是以编写更多的代码为代价来获得更高的效能。为了通过例子说明各种数据结构之间的差别，我们假设要把下列数据项放进符号表：

cs:01F8	; 全局变量
bp + 4	; 参数
bp – 6	; 局部变量
ax	; 寄存器 ax
bp – 2	; 局部变量

无顺序列表

无顺序列表是一个数据项链表或者是一个数据项数组。数据项被储存在一个基于先入的列表 (即，放在下一个可用位置)。数组实现受数组尺寸的限制；链表实现则没有这些限制。这个符号表是一个有 n 个数据项的列表，它的存取时间复杂度是 O(n)。图 3-9 是我们例子的列表。

图 3-9: 无顺序列表表示法

有顺序列表

有顺序列表比较容易存取，因为确定一个数据项是否已经在列表中不需要检查该列表的全部数据项。有顺序列表可以使用二分法搜索，其存取时间复杂度是 O(log n)。但是，插入一个数据项花费代价较大，因为列表需要保持有顺序。

因为在一个二进制程序中有不同类型的变量，而这些数据项是根据其类型以不同的方式来识别，同一种类型数据项的排序是可以的，但是四个不同类型就必须独立存取。图 3-10 是我们例子的有顺序列表表示法：首先用一个记录指定所使用数据项的数据类型，然后每一个数据类型关联一个有顺序的列表。

图 3-10: 有顺序列表表示法

散列表

散列表是在一个表的固定数目位置和可能很大数目的变量之间的映射。这个映射是通过一个散列函数 (为所有可能的变量定义这个函数) 完成的，能够快速地计算，为所有变量提供一致的概率，而且把相似的变量映射到表中不同的随机位置。

在打开的散列中，散列表表现为一个固定大小的数组而且每个数组位置(bucket) 附接着一个链表。链表保存那些经过散列产生相同 bucket 的不同变量。图 3-11 是我们例子的散列表；对于有顺序列表，首先用一个记录指定变量的类型，然后每个不同的变量类型关联一个散列表。

图 3-11: 散列表表示法

适用于反编译的符号表表示法

为了适合反编译目的，将上述方法配合使用。根据不同类型的变量定义符号表：全局的、局部的、参数和寄存器。其中每一种类型均以不同方式实现。对于全局变量，因为它们的地址范围大，所以用散列表实现最合适。对于局部变量和参数，由于这些变量是相对框架指针的偏移量，而且总是以顺序方式分配的 (即，在栈框架中没有“间隙”)，所以它们的实现是一个关于偏移量的顺序列表；不需要把寄存器 bp 存入，因为它总是相同的。最后，因为寄存器数目是固定的，所以寄存器的实现是一个以寄存器编号作为索引的数组；数组位置有一个关联的数据项，表示在符号表中所定义的寄存器。这个表示法见图 3-12 所示。

图 3-12: 符号表表示法

有关讨论符号表的文献非常多，有关从编译器角度讨论符号表的资料可参考[ASU86a, FJ88a, Gou88]。