分类： C/C++
2009-09-21 09:26:32
很早就想写一篇关于符号表的学习小结，可是迟迟不能下笔。其一是因为符号表在编译器的设计中占有举足轻重的地位【我们在学习编译原理的时候更多的是注重principles，而没有关心一个编译器的实现，所以符号表讲解的也比较少】，编译阶段的每“遍”都会和符号表打交道，本人只做过一个Mini C的编译器的前端部分，感觉功底不够；其二是因为我想在原来C语言的基础上，增加C++语言符号表的一些知识，对于C++的符号表至今为止我还没有在Internet上找到相关的专门描述，有一本书《C++编程艺术》【英文《The Art of C++》，
如果文中有任何错误的地方，拜托你一定要指点我，谢谢了！
符号表存储的内容有哪些？从编译器来看，符号表与编译的各个阶段都有交互，符号表的内容也会在编译器的不同阶段包含不同的内容【一般来讲，在词法分析，语法分析阶段编译器都是填充符号表，在语义分析阶段更多得操作是从符号表中查询数据，当然还有删除符号表的内容】。一般来讲，符号表有内存地址和函数/变量的对应关系，编译时节点的各种属性（类型，作用域，分配空间大小，（函数）的参数类型）等。对符号表的具体使用方法每个编译器都不同。
目标文件中的符号表用来输出函数/变量符号信息，供连接时给其他模块引用。这种符号表中主要包含函数/变量的名称和地址对应关系，其中的地址一般是位置无关码。
【在此在推荐一本好书《Linker & Loader》，目前在网上还能找到中科大的一位博士翻译的中文版本，这本书比较详细的介绍了连接器和加载器的工作原理】
我们可以想象在编译器中符号表的管理使用可以分为三步：收集符号属性、根据BNF范式进行语法的合法性检查、在生成目标代码阶段使用。
一、 收集符号属性
编译程序扫描说明部分收集有关标识符的属性，并在符号表中建立符号的相应属性信息。例如，编译程序分析到下述两个说明语句
int iVar;;
double fArray[2];
则在符号表中收集到关于符号iVar的属性是一个整型变量，关于符号fArray的属性是具有2个double元素的一维数组。这只是一个简单说明，我们想看一下符号表具体的数据结构。但目前我还没有找到一个非常完整的描述。那么先来看一下Java的Class文件中找到一些类似存储符号表信息的方法。
借鉴Java的Class文件结构
下面的ClassFile结构Class文件的C语言描述【以下内容可参考《Java虚拟机规范》第四章或者网上文章《解读Java Class文件格式》】：
struct ClassFile
{
u4 magic; // 识别Class文件格式，具体值为0xCAFEBABE，
u2 minor_version; // Class文件格式副版本号，
u2 major_version; // Class文件格式主版本号，
u2 constant_pool_count; // 常数表项个数，
cp_info **constant_pool; // 常数表，又称变长符号表，
u2 access_flags; // Class的声明中使用的修饰符掩码，
u2 this_class; // 常数表索引，索引内保存类名或接口名，
u2 super_class; // 常数表索引，索引内保存父类名，
u2 interfaces_count; // 超接口个数，
u2 *interfaces; // 常数表索引，各超接口名称，
u2 fields_count; // 类的域个数，
field_info **fields; // 域数据，包括属性名称索引，域修饰符掩码等，
u2 methods_count; // 方法个数，
method_info **methods; // 方法数据，包括方法名称索引，方法修饰符掩码等，
u2 attributes_count; // 类附加属性个数，
attribute_info **attributes; // 类附加属性数据，包括源文件名等。
};
其中u2为unsigned short，u4为unsigned long：
cp_info **constant_pool是常量表的指针数组，指针数组个数为constant_pool_count，结构体cp_info如下：
struct cp_info
{
u1 tag; //常数表数据类型
u1 *info; //常数表数据
};
常数表数据类型Tag定义如下：
#define CONSTANT_Class 7
#define CONSTANT_Fieldref 9
#define CONSTANT_Methodref 10
#define CONSTANT_InterfaceMethodref 11
#define CONSTANT_String 8
#define CONSTANT_Integer 3
#define CONSTANT_Float 4
#define CONSTANT_Long 5
#define CONSTANT_Double 6
#define CONSTANT_NameAndType 12
#define CONSTANT_Utf8 1
每种类型对应一个结构体保存该类型数据，例如CONSTANT_Class 的info指针指向的数据类型应为CONSTANT_Class_info
struct CONSTANT_Class_info
{
u1 tag;
u2 name_index;
};
CONSTANT_Utf8的info指针指向的数据类型应为CONSTANT_Utf8_info
struct CONSTANT_Utf8_info
{
u1 tag;
u2 length;
u1 *bytes;
};
Tag和info的详细说明参考《Java虚拟机规范》第四章4.4节。
access_flags为类修饰符掩码，域与方法都有各自的修饰符掩码。
#define ACC_PUBLIC 0x0001
#define ACC_PRIVATE 0x0002
#define ACC_PROTECTED 0x0004
#define ACC_STATIC 0x0008
#define ACC_FINAL 0x0010
#define ACC_SYNCHRONIZED 0x0020
#define ACC_SUPER 0x0020
#define ACC_VOLATILE 0x0040
#define ACC_TRANSIENT 0x0080
#define ACC_NATIVE 0x0100
#define ACC_INTERFACE 0x0200
#define ACC_ABSTRACT 0x0400
#define ACC_STRICT 0x0800
field_info **fields是类域数据的指针数组，指针数组个数为fields_count，结构体field_info定义如下：
struct field_info
{
u2 access_flags; //域修饰符掩码
u2 name_index; //域名在常数表内的索引
u2 descriptor_index; //域的描述符，其值是常数表内的索引
u2 attributes_count; //域的属性个数
attribute_info **attributes; //域的属性数据，即域的值
};
例如一个域定义如下：
private final static byte UNSET=127;
则该域的修饰符掩码值为：ACC_PRIVATE | ACC_STATIC | ACC_FINAL=0x001A。常数表内name_index索引内保存数据为UNSET，常数表内descriptor_index索引内保存的数据为B（B表示byte, 其他类型参考《Java虚拟机规范》第四章4.3.2节）。attributes_count的值为1，其中attributes是指针数组。指针数组个数为attributes_count，在此为1，attribute_info结构体如下：
struct attribute_info
{
u2 attribute_name_index; //常数表内索引
u4 attribute_length; //属性长度
u1 *info; //根据属性类型不同而值不同
};
attribute_info可以转换(cast)为多种类型ConstantValue_attribute，Exceptions_attribute，LineNumberTable_attribute，LocalVariableTable_attribute，Code_attribute等。
因为域的属性只有一种：ConstantValue_attribute，因此此结构体转换为
struct ConstantValue_attribute
{
u2 attribute_name_index; //常数表内索引
u4 attribute_length; //属性长度值，永远为2
u2 constantvalue_index; //常数表内索引，保存域的值
//在此例中，常数表内保存的值为127
};
method_info **methods是方法数据的指针数组，指针数组个数为methods_count，结构体method_info定义如下：
struct method_info
{
u2 access_flags; //方法修饰符掩码
u2 name_index; //方法名在常数表内的索引
u2 descriptor_index; //方法描述符，其值是常数表内的索引
u2 attributes_count; //方法的属性个数
attribute_info **attributes; //方法的属性数据，
//保存方法实现的Bytecode和异常处理
};
例如一个方法定义如下：
public static boolean canAccessSystemClipboard()
{
...
}
则access_flags的值为 ACC_PUBLIC | ACC_STATIC =0x0009，常数表内name_index索引内保存数据为canAccessSystemClipboard，常数表内descriptor_index索引内保存数据为()Z；(括号表示方法参数，Z表示返回值为布尔型，详细说明参照《Java虚拟机规范》第四章4.3.2节)。attribute_info **attributes是方法的属性指针数组，个数为attributes_count，数组内保存的是常数表索引，info为Code_attribute或Exceptions_attribute。
ClassFile结构体中的attribute_info **attributes是附加属性数组指针，个数为attributes_count。
struct SourceFile_attribute
{
u2 attribute_name_index; //常数表内索引
u4 attribute_length; //属性长度值，永远为2
u2 sourcefile_index; //常数表内索引，info保存源文件名
};
C++的符号表的特别之处
因为Java的Class文件是一个中间文件，在Class文件中保存的信息是很多的，而且和C++编译器也是不完全相同，那么上面的结构中那些是我们在C++编译器生成的符号表中也必须有的？我想上面的field_info、method_info、namespace和const等在C++的符号表也是需要的，但是这些内容也不完全相同。
那我们先看以下几个常见的问题，加深C++编译器的理解
« 符号表如何存储静态变量（包括全局变量和局部变量）和类非静态成员变量有哪些区别？
对于静态变量，C++编译器的处理方法和Java解释器处理的方法有类似的地方。那就是访问控制符public/private/protected和static一样都会写入符号表；对于非静态成员变量符号表存储的什么内容？有没有这些访问控制符？类的非静态成员在类中的表示是通过偏移量来访问，只有和对象邦定以后才能找到其真实的地址，那么在编译后的目标文件中没有为成员分配地址，访问控制符也就没有写入到目标文件。【注1:为什么访问控制符是在编译期间处理，而不放在运行期间处理？如果要放在运行期间处理必须完成新的连接器和加载器来保证，另外重要的是运行效率的问题】【注2:参考CSDN上一篇文章，一个类的成员变量修改了访问控制符，在另外一个文件被引用，是否必须编译修改的文件才能连接成功？《今天面试碰到的一个以前没有想过的问题（顺便给一点分出去）》】。
« 符号表如何处理const、volatile变量？
C++编译器把Const对象放在了符号表之中，C语言一般是放在只读数据区。【为什么C++编译器这么做？我想一个原因就是减少一些存储操作次数】。对于volatile变量我们应该怎么考虑？声明的voliate告诉编译器不能优化它呀，我们只能在符号表中增加标识位来告诉编译器自己不优化volatile变量。
« 符号表怎么处理虚函数、虚继承、多继承的情况？
其实对于这些处理在Lippman的《Inside the C++ Object Model》中有详细的介绍。也许你知道那些应该放在符号表中，那些是不能的。例如对于局部静态对象static class obj;的定义那些不需要放在符号表中？【注：局部静态变量只要求在函数执行时初始化一次】，为了保证Obj满足要求，需要附加标志变量，这个附加变量能放在符号表中吗？不能，原因很简单，它需要在运行时控制对象的构造和析构。
一个多继承，有虚函数的例子：
struct __mptr
{
int delta; //多继承下第二个对象要调整的偏移量
int index; //是否为虚函数的标志
union {
ptrtofunc faddr;
int v_offset;
};
};
这个数据应该放在哪里？程序的目标代码中还是符号表中？显然这个数据应该放在符号表之中。当然对于C++编译器的不通现实，数据结构可能是不同的，但是我们知道了那些数据应该放在符号表之中啦。
C++ 编译器中对于异常是如何完成的？看看《深入探索C++对象模型》，然后再从汇编上分析，在符号表上的处理并没有很大的技巧。但是对于模板的处理，符号表就 要起很大的作用啦。目前大多数C++编译器为了减少模板带来的代码扩张基本上都会增加一次编译，准确的获取要实例化的模板对象，可惜的对此内容知之甚少， 不敢乱讲。
也许你觉得我扯了大半天，也没有告诉你一个符号表的准确结构。真的很抱歉，我也没有设计过C++编译器，当然没有办法给出一个完整的结构，我主要是想探索一下怎么设计一个C++编译器使用的符号表。【对于符号表的管理目前常用的是Hash table，可以参考相关文档设计Hash表以及解决冲突的办法】
二、 根据BNF范式进行语法的合法性检查
根据文法，可以识别代码。在此处的语法检查主要指的符号表的检查，是编译器出错处理的一部分。例如我们重复定义变量，其根本原因就是变量信息进入符号表时发现已经存在了数据项【当然这个数据项不是上面所说的Hash冲突】。
是否有符号表的语义检查？从我看来是没有的，语义是什么？语义指的是代码实际代表的意义，符号表仅仅是符号，没有实际的语义。
三、 在生成目标代码阶段使用
我想看过编译原理的都经常看到这样的函数lookup(id)，指的是在符号表中查找id对象。在生成目标代码的时候就是要根据程序的语义，不断地查找符号表，然后生成目标代码。
每个符号变量在目标代码生成时需要确定其在存储分配的位置（主要是相对位置）。语言程序中的符号变量由它被定义的存储类别（如在C、FORTRAN语言中）或被定义的位置（如分程序结构的位置）来确定。首先要确定其被分配的区域。例如，在C++中常见的段（sections）有.bss，.data，.text，.rdata，.init，.fini等【可参考《Linker & Loader》或者自己通过反汇编查看，如通过GCC的Objdump －D ExeFile或者Visual Studio中的dumpbin就可以看到可执行文件中所有的段】。其次是根据变量出现的次序，（一般来说）决定该变量在某个区中所处的具体位置，这通常使用在该区域中相对区头的相对位置确定。而有关区域的标志及相对位置都是作为该变量的语义信息被收集在该变量的符号表属性中。
四、 后记
如果在以后有时间有机会的话能够阅读的GCC/G++的源代码（不知道未来的N多年中真的是否有这样的机会），我一定重写这篇文章。但是现在，如果你发现我的错误，一定通知我。如果你也有一些涉及到编译器的问题（C and/or C++ Compiler），我也非常乐意和你一起探讨。
在此恳请指点文中的错误。
为了使大家能够看到我所参考的文章，我把他们都重新的放在一起，不仅仅是一个连接。希望没有侵犯原作者的版权吆。
参考的文章：
【1】 符号表，http://www.cppblog.com/pengkuny/archive/2006/12/18/16581.html
【2】 Mini Java编译器，http://blog.csdn.net/sandy_xu/category/106115.aspx
【3】 今天面试碰到的一个以前没有想过的问题（顺便给一点分出去），
【4】 Const的思考，
【5】 解读Java Class文件格式，http://blog.csdn.net/tyrone1979/archive/2006/07/23/964560.aspx
推荐读物：
【1】 编译原理。个人手头有好几本，每本都有他的特点。
【2】 Linker & Loader，网上可以找到中英文版本。
【3】 深入探索C++对象模型，网上中英文版本都可以找到。
