编译原理实践：符号表组织方法

由于常量、变量等处理对象的作用和作用域可以有多种，所以符号表也有多种组织方式。其中，最简单的组织方式是让各栏所占的长度都是固定的（也称为直接方式）。这种方式易于组织、填写和查找，每一栏的内容可直接填写在有关的区段里。例如，有些语言规定标识符的长度不超过8个字符，假定每个机器字可容纳4个字符，则可以用两个机器字作为主栏，从而将名字直接填写在主栏中。若标识符长度不到8个字符，则用空白符补足。

然而，许多语言对标识符的长度几乎不加限制，比如，对于最长可允许100个字符的名字而言，如果每项都用25个字作主栏，则势必会大量浪费存储空间。因此，最好用一个字符串数组来单独存放标识符，并在符号表的主栏放一个指示器和一个整数，或在主栏仅放一个指示器，而在标识符前放一个整数。指示器用来指出标识符在字符数组中的起始位置，整数则用来表示此标识符的长度。这是一种间接安排名字栏的方式，符号表的结构如图7-2所示。

图7-2　符号表的间接组织方式

同样，若各种名字所需的信息空间长短不一，则可将那些特殊属性保存在符号表外，而将共同属性直接登记在符号表中，并附设一个指示器，指向存放特殊属性的地方。例如，就数组标识符来说，需要保存维数等信息，如果将它们与其他名字全部集中在一张符号表中，则处理起来很不方便。通常的做法如图7-3所示，首先，开辟一个专门的信息表区（称为数组信息表或内情向量表），将数组的有关信息全部填入此表中；然后，在符号表的地址栏中设置一个指针，指向该内情向量表。因此，当填写或查询数组有关信息时，可以很方便地通过符号表来访问此内情向量表。除数组之外，对于过程名字以及其他一些含信息较多的名字均可类似处理。

图7-3　符号表与内情向量表的连接

假设一个符号表可以容纳N项，每项需要K个字，则该符号表的存储可用下述两种不同的方式予以表示：(www.xing528.com)

（1）把每一项置于连续的K个存储单元中，从而给出一张K*N个字的表。

（2）把整个符号表分成M个子表T1、T2、…、TM，每个子表含N项。假定子表Ti的每一项所需的字数为Ki，则有K=K1+K2+…+KM，于是将T1[i]、T2[i]、…、TM[i]并置在一起就构成了符号表中的第i项。

在编译过程中，每一遍所用的符号表可能略有差别。一般说来，主栏和某些基本属性栏大多保持不变，但另外一些信息栏可能在不同的阶段具有不同的内容。为了合理地使用存储空间，尤其是重复利用那些已经过时的信息栏所占用的空间，方式（2）为我们提供了良好的思路，它有助于在不同阶段对靠后的子表进行重新安排。例如，把主栏和信息栏分成两个子表，令主栏占两个字，信息栏占四个字，那么，该符号表的存储方式如图7-4所示。

图7-4　以两个子表的形式存储符号表

另外，符号表的实现往往采用记录数组或变体记录数组的方式，并且，应按照名字的不同种类分别建立多张符号表，如常数表、变量名表、过程名表等，这样做要比使用一张统一的符号表方便得多。