A symbol table is used by computer systems as a way of centralizing information and reducing the size of programs. These tables work like the key to a secret code; a symbol or string is placed next to another, generally much larger, piece of information. When a program reads a symbol that is associated with the symbol table, the program references the table and takes the information rather than the symbol. This allows large pieces of information or commonly repeated structures to only have one entry, reducing the overall size of the program.
The concept behind a symbol table is very simple. A single table contains a wide range of information used by a program, each with its own entry and unique associated symbol. This information could be strings of code, debugging information, memory locations, literally anything that the program could use in order to function. Rather than include that information within the program, the code simply references the table using its unique symbol.
Machine-language instructions are a unit of execution in a computer system. Machine language instructions can be further subdivided into micro instructions within a computer processor and are themselves subdivisions of high-level language statements and expressions.
A compiler translates source code into machine-language instructions. In some cases, particularly in UNIX environments, development environments or compiler construction courses, compilers translate source code into human-readable assembly-language code. Sometimes entire systems are written in assembly language and sometimes just a subroutine. The C programming language has a construct that permits assembly code within a statement.
An assembler translates assembly-language code into machine-language instructions. An assembler operates on a source file and produces an object-code file. These represent two forms of the same program unit. Assembly instructions may refer to operands that are not defined in the same unit. These are called external references. Assembly programs may contain storage locations that are referred to from other program units. These are called external definitions.
A linker combines two or more object-code files to produce either another object file or an executable file. Theoretically, the only difference between an object file and an executable file is that the executable has no unresolved external references. In fact, there may be references in the executable file that are not resolved until load time.
Relocation occurs both when a linker combines object files and when a loader copies an executable file into memory in preparation for execution.
符号表对于一个编译器的重要性无论如何强调都不过分。在编译过程中，编译器使用符号表来记录源程序中各种名字的特性信息。所谓“名字”包括: 程序名、过程名、函数名、用户定义类型名、变量名、常量名、枚举值名、标号名等，所谓“特性信息”包括: 上述名字的种类、类型、维数、参数个数、数值及目标地址（存储单元地址）等。
符号表上的操作包括填表和查表两种。当分析到程序中的说明或定义语句时, 应将说明或定义的名字, 以及与之有关的特性信息填入符号表中，这便是填表操作。查表操作被使用得更为广泛，需要使用查表操作的情况有：填表前查表，检查在程序的同一作用域内名字是否重复定义；检查名字的种类是否与说明一致；对于那些类型要求更强的语言，要检查表达式中各变量的类型是否一致；生成目标指令时，要取得所需要的地址或者寄存器编号，等等。符号表的组织方式也有多种多样，你可以将程序中出现的所有符号组织成一张表，也可以将不同种类的符号组织成不同的表（例如，所有变量名组织成一张表，所有函数名组织成一张表，所有临时变量组织成一张表，所有结构体定义组织成一张表等等）；你可以针对每一个语句块、每一个结构体都新建一张表，也可以将所有语句块中出现的符号全部插入到同一张表；你的表可以仅支持插入不支持删除（此时如果要实现作用域的话需要将符号表组织成层次结构），也可以组织一张既可以插入又可以删除的、支持动态更新的表。不同的组织方式各有利弊，我希望你在看完了这篇文章并经过自己的仔细思考之后自行权衡利弊，并做出你自己的决定。
符号表里应该填些什么？这个问题的答案取决于不同的程序设计语言的特性，更取决于编译器的设计者本身。换句话说：只要你觉得方便，随便你往符号表里塞任何内容！毕竟符号表归根结底就是为了我们编译器的书写方便而设置的。单就本次实习来看，对于变量你至少要记录变量名和变量类型，对于函数你至少要记录返回类型、参数个数以及参数类型。符号表应该采用何种数据结构进行实现？这个问题同样没有一个统一的答案。不同的数据结构有不同的时间复杂度、空间复杂度以及编程复杂度，几种最常见的选择有：
符号表里所有的符号都用一条链表串起来,插入一个新的符号只需将这个符号放在链表的表头,时间效率为O(1)；在链表里查找一个符号需要对其进行遍历，时间效率为O(n)；删除一个符号只需要将这个符号从链表里摘下来，不过在摘之前由于我们必须要执行一次查找操作找到待删除的节点，因此时间效率也是O(n)。
链表的最大问题就在于它的查找和删除效率太低，一旦符号表中的符号数量增大之后，查表操作将变得十分耗时。不过，使用链表的好处也显而易见：它的结构简单、编程复杂度极低，可以被快速地、无错地实现。如果你事先能够确定表中的符号数目非常非常少（例如，在结构体的定义中或者在面向对象语言的一些短方法中），那么链表也是一个非常不错的选择。
相对于只能执行线性查找的链表而言，在平衡二叉树上进行的查找天生就是二分查找。在一个典型的平衡二叉树实现（例如AVL树、红黑树、伸展树等）上查找一个符号的时间效率为O(logn);插入一个符号相当于进行一次失败的查找找到待插入的位置，时间效率同样为O(logn)；删除一个符号可能需要做更多的维护操作，但其时间效率仍然维持在O(logn)级别。
平衡二叉树相对于其他数据结构而言具有很多优势，例如较高的搜索效率（在绝大多数应用中O(logn)的搜索效率已经完全可以被接受了）以及较好的空间效率（它所占用的空间随树中节点的增长而增长，不像散列表那样每一张表都需要大量的空间占用）。平衡二叉树的缺点是编程复杂太高，成功写完并调试出一个能用的红黑树所需要的时间不下于你完成本次实习所需的时间。不过如果你真的想要使用红黑树，其实并不需要自己动手写，从其他的地方（例如，Linux内核代码中）寻找一个别人写的红黑树一样是可行的。
散列表代表了一个数据结构可以达到的搜索效率的极致，一个好的散列表实现可以让插入、查找和删除的平均时间效率都达到O(1)。同时，与红黑树等操作复杂的数据结构不同，散列表在代码实现上竟是如此令人惊讶地简单：申请一个大数组、计算一个散列函数的值、然后根据这个值将该符号放到数组相应下标的位置即可。对于符号表来说，一个最简单的hash函数只需要把符号名中的所有字符相加，然后对符号表的大小取模。你可以自己去寻找一些更好的hash函数，这里我提供一个不错的选择，由P.J.Weinberger所提出：
|
需要注意的是，该方法对符号表的大小有要求——必须是2的某个乘幂。这个乘幂到底是多少，留给需要采用这种方法的你在理解这段代码的含义之后自己思考。
如果出现冲突，则可以通过在相应数组元素下面挂一个链表的方式（称为open hashing或者close addressing方法，推荐使用）或者再次计算散列函数的值从而为当前符号寻找另一个槽的方式（称为open addressing或者rehashing方法）来解决。如果你还知道一些更加fancy的技术，例如Multiplicative hash function以及Universal hash function，那将会使你的散列表的元素分布更加平均一些。
由于散列表无论在搜索效率还是在编程复杂度上的优异表现，它也成为了符号表的实现中最常被采用的数据结构。
目前为止我仍然没有找到对这个名字合适的翻译。虽然散列表的平均搜索效率很高，但在最坏情况下它会退化为O(n)的线性查找，而且几乎任何确定的散列函数都存在某种最坏的输入。另外，散列表所要申请的内存空间往往要比输入程序中出现的所有符号的数量还要多，未免有些浪费——如果我们为输入程序中出现每一个符号都分配一个单独的编号和单独的空间，岂不是既省空间又不会出现冲突吗？
Multiset discrimination所基于的就是这种想法。在词法分析部分，我们统计输入程序中出现的所有符号（包括变量名、函数名等等），然后把这些符号按照名字进行排序，最后开一张与符号总数一样大的散列表，某个符号的散列函数即为该符号在我们之前的排序里的序号。类似的想法在自然语言处理中也有应用。
联系客服
