内容提要
在我们写的代码中，有若干个变量，若干个函数；变量还会重名，还有值。编译器却总能找到我们指定的变量或函数，从不找错人。在我看来，这是一个很神奇的功能。剖析一番，会发现”符号表“的身影。
符号表，存储变量的值、函数。变量作用域依赖它，找到正确的变量也依赖它。
一起来看看符号表吧。
符号
老规矩，先从一段代码开始。
struct Data{ int num1; int num2; }dt; Enum Color{RED, GREEN, BLUE}; int a,b,c,d; typedef int INT32; int main(int argc, char *argv[]){ char *hi = "hello,world"; Begin: c = a + b; d = a + b; a = 3; dt.m2 = a + b; return 0; }
从上面的代码中抽取下列元素：
Data、ColorRED, GREEN, BLUEa,b,c,dINT32"hello,world"Begin
这些元素，每个都用一种数据结构存储。这种数据结构，我们把它叫做“符号”，对应的英文术语是“Symbol”。
细心一点的读者朋友会发现：并不是每行只有一个元素，有的行有多个元素。写在同一行的元素属于同一个类别。
在C语言中，有哪几种类别的语言元素呢？先给出下面几种类别。这些类别和上面的那几行元素一一对应。请看。
SK_TagSK_EnumConstantSK_VariableSK_TypedefNameSK_StringSK_Lable。
除了上述六种类别，还有这些类别。
SK_Register。例如eax。SK_IRegister。例如(eax)。SK_Tmp。临时变量。SK_Offset。后面再将这个类别。 SK_Function。存储函数。
符号的数据结构
Enum SymbolKind {SK_Tag, SK_EnumConstant, SK_Variable, SK_TypedefName, SK_String, SK_Lable, SK_Register, SK_IRegister, SK_Tmp, SK_Offset}; #define SYMBOL_COMMON \ // kind的取值是SymbolKind中的枚举值。 int kind; \ // 变量的数据类型。 Type ty; \ // 变量名，例如int a中的a。 char *name; \ // 这个变量的别名，以后会用到。 char *aname; \ // 当kind是SK_Offset时，这个值才有意义。 int offset; typedef struct symbol{ SYMBOL_COMMON }*Symbol;
一般不直接使用Symbol存储变量，而是使用它的“子结构”，VariableSymbol。
typedef struct VariableSymbol{ SYMBOL_COMMON }*VariableSymbol;
马上来用VariableSymbol存储int a。
| 成员 | 成员值 |
|---|---|
| kind | SK_Variable |
| ty | int |
| name | a |
| aname | |
| offset | 0 |
存储dt。
| 成员 | 成员值 |
|---|---|
| kind | SK_Tag |
| ty | struct Dt。派生类型。 |
| name | dt |
| aname | |
| offset | 0 |
存储dt的成员num2。
| 成员 | 成员值 |
|---|---|
| kind | SK_Offset |
| ty | int |
| name | num |
| aname | |
| offset | 4。后面解释。 |
现在可以说说什么是符号了。符号，用来存储变量或常量的数据结构。
仿照上面的例子，比较容易知道怎么存储Color、INT32等语言元素，我就不一一示范了。
公共表达式
什么是公共表达式
在上面，我介绍了符号的数据结构，但那并不是符号的最终版本。
是的，我要补充新内容了，公共表达式。
还是先看代码吧。
// 从前面的例子中抽取出来的。 c = a + b; d = a + b; a = 3; dt.m2 = a + b;
这段代码对应的中间代码如下。
t0: a+b c: t0 d: t0 a: 3 t1: a+b dt[4]: t1
c和d的值都是a+b。生成一个临时变量t0，存储a+b的值。把t0赋值给c、d。在这个过程中，只计算了一次a+b。a+b就是“公共表达式”。
引入“公共表达式”，能减少最终生成的机器指令，提高程序的执行效率。
怎么存储公共表达式
我们设计的VariableSymbol能存储公共表达式吗？
我在想什么？
在想，用什么理由引出valueUse最合适。
想不到！
dt[4]的值为什么不是t0而是t1？因为a被修改了，t0不能再作为公共表达式。
一旦公共表达式中的变量被修改，这个变量参与过的所有公共表达式都将失效，不再被当作公共表达式使用。我们设计的符号管理机制必须实现这个功能。
typedef struct valueDef{ Symbol dst; int op; Symbol src1; Symbol src2; struct valueDef *link; }ValueDef; typedef struct valueUse{ ValueDef def; struct valueUse *use; }ValueUse; #define SYMBOL_COMMON \ // kind的取值是SymbolKind中的枚举值。 int kind; \ // 变量的数据类型。 Type ty; \ // 变量名，例如int a中的a。 char *name; \ // 这个变量的别名，以后会用到。 char *aname; \ // 当kind是SK_Offset时，这个值才有意义。 int offset; // ValueDef def; // ValueUse uses;
我在SYMBOL_COMMON中新增了两个成员def和uses。
每个变量参与了哪些表达式，用uses记录。uses是一个ValueDef的单链表。
存储公共表达式实例
完善一下存储a的符号。如下。
| 成员 | 成员值 |
|---|---|
| kind | SK_Variable |
| ty | int |
| name | a |
| aname | |
| offset | 0 |
| uses | def0 |
t0:a+b用ValueDef记录，记作def0。
| dst | t0 |
|---|---|
| op | + |
| src1 | 存储a的VariableSymbol |
| src2 | 存储b的VariableSymbol |
| link |
t1:a+b用ValueDef记录，记作def1。
| dst | T1 |
|---|---|
| op | + |
| src1 | 存储a的VariableSymbol |
| src2 | 存储b的VariableSymbol |
怎么记录t0呢？用VariableSymbol。请看下面。
| 成员 | 成员值 |
|---|---|
| kind | SK_Tmp |
| ty | int |
| name | t0 |
| aname | |
| offset | 0 |
| def | def0 |
比较一下a和t0的符号，至少有3个差异：
t0的kind是SK_Tmp，因为t0是一个临时变量。name不同。def不同。我认为，只有临时变量的符号的def才有意义。
临时变量的符号的uses有意义吗？
换个问法：需要记录临时变量参与过的表达式吗？我也不知道。
哈希表
开放散列法
如果a+b已经出现过一次，再次遇到a+b时，将不再计算a+b。那么，怎么才能知道a+b有没有出现过呢？方法是，把a+b存储起来。
存储一个表达式，用哈希表很合适。我们使用的这个哈希表使用“开放散列法”创建。具体方法如下：
哈希key = (src1 + src2 + op) / 16; key相同、但实际上不同的表达式组成一个单链表。 这个单链表中的结点的数据类型是 ValueDef。ValueDef的成员link用来创建单链表。
这个哈希表在哪里？我把它放在函数的符号中。来看一看存储函数的结构。
存储函数的符号
typedef struct functionSymbol{ SYMBOL_COMMON // 存储函数的参数。 Symbol params; // 存储函数的局部变量。 Symbol locals; // 存储公共表达式的哈希表。 ValueDef valNumTable[16]; }FunctionSymbol;
公共表达式经过哈希函数处理之后，存储到FunctionSymbol的成员valNumTable中。
这意味着，我们只处理函数中的公共表达式。对函数外面的公共表达式，不处理。
使用哈希表的实例
一起看一看怎么把t0:a+b存储到哈希表中。伪代码如下。
int key = ((int)src1 + (int)src2 + op) / 16; ValueDef head = valNumTable[key]; ValueDef current = head; ValueDef target = NULL; while(current != NULL){ if(current->src1 == src1 && current->src2 == src2 && current->op == op){ target == current; break; } current = current->link; } if(target == NULL){ ValueDef tmp; tmp->op = op; tmp->src1 = src1; tmp->src2 = src2; tmp->dst = t0; // 存储到哈希表中。 tmp->link = valNumTable[key]; valNumTable[key] = tmp; }
上面的伪代码正确展示了用”开放散列法“创建哈希表，忽略了很多关于”公共表达式“的逻辑。
在哈希表中找到公共表达式后，如果这个表达式中的src1或src2已经被修改过，这个公共表达式就是无效的。
另一个哈希表
用上一个哈希表，我们解决了存储a+b的问题。现在，我们面临新的问题：
a存储在Symbol，大量的Symbol存储在哪里?
依然存储在哈希表中。这些哈希表还会构成一个单链表。
为什么要创建哈希表链表
在C语言中，存在”作用域“这个概念，英文术语是scope。
int a; int test(){ int a = 5; return 0; }
上面的代码中有两个a，但这两个a的作用域不同。
全局变量a存储在哈希表A中，test的局部变量a存储在哈希表B中。
A和B一起构成哈希链表。
哈希链表的数据结构
bucketLinker
bucketLinker的数据结构如下。
// 哈希表的大小。 #define BUCKET_SIZE 128 // 计算哈希key的掩码。 #define BUCKET_HASH_MASK 127 typedef struct bucketLinker{ Symbol sym; // 指向下一个bucketLinker。 struct bucketLinker *link; }*BucketLinker;
Symbol有两个成员link和next，都能指向下一个Symbol。为什么还新建一个BucketLinker用来创建链表呢？因为Symbol的两个成员link和next都有其他用途，暂且不关注。
哈希表
再看哈希表的数据结构。
typedef struct table{ // BucketLinker就存储在table中，实质是变量Symbol或函数Symbol存储在table中。 Symbol buckets[BUCKET_SIZE]; // 哈希表的层次。 int level; struct table *outer; }*Table;
level存储”作用域“。在前面的例子中，存储全局变量a的哈希表的level的值是0，存储test的局部变量a的哈希表的level的值是1。
AddSymbol
本节的小标题是一个函数名，这个函数的功能是：把一个存储了变量或函数的Symbol存储到哈希表中。请看伪代码。
AddSymbol(Symbol sym, Symbol *table){ int key = (int)sym / BUCKET_HASH_MASK; // 创建一个BucketLinker BucketLinker linker; linker->sym = sym; // 如果table中没有存储BucketLinker链表，把新linker作为链表的第一个结点 // 存储到table中。 if(table[key] == NULL){ table[key] = linker; }else{ // 如果table中存储了BucketLinker链表，把新linker添加到链表的头结点， // 然后把新链表也就是链表的头结点存储到table中。 // 把sym存储到哈希表中。 linker->link = table[key]; table[key] = linker; } }
再看一小段代码。
linker->link = table[key]; table[key] = linker;
这不就是从AddSymbol中抽出来的吗？有必要再看一次。
因为这两行代码运用了”开放散列法“，而我很久以前觉得”开放散列法“是比较有技术含量东西。
在我的工作中，未曾需要自己动手实现”开放散列法“。用到哈希时，调用一个哈希函数而已。
总结
关于符号表，就讲完了。本文囊括了主要知识点。
第一次看符号表，我觉得有点复杂。惭愧惭愧。
做个简单的总结吧。
在编程语言例如C语言中，存在变量、函数。要为一个变量建模，就要设计出合适的结构存储变量的数据类型和变量名、变量值。
用类型系统存储数据类型。
用符号表存储变量的变量名、变量值、变量的初始值等。
符号表需具备下列功能：
存储变量的变量名、变量值、变量的初始值等；存储函数的函数名、参数值、函数体等。 上面这句话不全对。对错依赖编译器设计者的具体设计。 读者朋友理解为：存储变量值或函数体等。
作用域。 查找变量、函数等。
对了，想了解类型系统，请阅读《C语言的类型系统》。
参考资料
《C 编译器剖析》