这些元素，每个都用一种数据结构存储。这种数据结构，我们把它叫做“符号”，对应的英文术语是“Symbol”。
细心一点的读者朋友会发现：并不是每行只有一个元素，有的行有多个元素。写在同一行的元素属于同一个类别。
在C语言中，有哪几种类别的语言元素呢？先给出下面几种类别。这些类别和上面的那几行元素一一对应。请看。
除了上述六种类别，还有这些类别。
符号的数据结构
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。
存储dt。
存储dt的成员num2。
现在可以说说什么是符号了。符号，用来存储变量或常量的数据结构。
仿照上面的例子，比较容易知道怎么存储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能存储公共表达式吗？
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的符号。如下。
t0:a+b用ValueDef记录，记作def0。
t1:a+b用ValueDef记录，记作def1。
怎么记录t0呢？用VariableSymbol。请看下面。
比较一下a和t0的符号，至少有3个差异：
哈希表
开放散列法
如果a+b已经出现过一次，再次遇到a+b时，将不再计算a+b。那么，怎么才能知道a+b有没有出现过呢？方法是，把a+b存储起来。
存储一个表达式，用哈希表很合适。我们使用的这个哈希表使用“开放散列法”创建。具体方法如下：
这个哈希表在哪里？我把它放在函数的符号中。来看一看存储函数的结构。
存储函数的符号
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 编译器剖析》