在我们写的代码中，有若干个变量，若干个函数；变量还会重名，还有值。编译器却总能找到我们指定的变量或函数，从不找错人。在我看来，这是一个很神奇的功能。剖析一番，会发现”符号表“的身影。

符号表，存储变量的值、函数。变量作用域依赖它，找到正确的变量也依赖它。

一起来看看符号表吧。

老规矩，先从一段代码开始。

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;}

从上面的代码中抽取下列元素：

这些元素，每个都用一种数据结构存储。这种数据结构，我们把它叫做“符号”，对应的英文术语是“Symbol”。

细心一点的读者朋友会发现：并不是每行只有一个元素，有的行有多个元素。写在同一行的元素属于同一个类别。

在C语言中，有哪几种类别的语言元素呢？先给出下面几种类别。这些类别和上面的那几行元素一一对应。请看。

除了上述六种类别，还有这些类别。

#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。

马上来用VariableSymbol存储int a。

存储dt。

存储dt的成员num2。

现在可以说说什么是符号了。符号，用来存储变量或常量的数据结构。

仿照上面的例子，比较容易知道怎么存储Color、INT32等语言元素，我就不一一示范了。

在上面，我介绍了符号的数据结构，但那并不是符号的最终版本。

是的，我要补充新内容了，公共表达式。

还是先看代码吧。

这段代码对应的中间代码如下。

c和d的值都是a+b。生成一个临时变量t0，存储a+b的值。把t0赋值给c、d。在这个过程中，只计算了一次a+b。a+b就是“公共表达式”。

引入“公共表达式”，能减少最终生成的机器指令，提高程序的执行效率。

我们设计的VariableSymbol能存储公共表达式吗？

我在想什么？

在想，用什么理由引出valueUse最合适。

想不到！

dt[4]的值为什么不是t0而是t1？因为a被修改了，t0不能再作为公共表达式。

一旦公共表达式中的变量被修改，这个变量参与过的所有公共表达式都将失效，不再被当作公共表达式使用。我们设计的符号管理机制必须实现这个功能。

#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个差异：

临时变量的符号的uses有意义吗？

换个问法：需要记录临时变量参与过的表达式吗？我也不知道。

如果a+b已经出现过一次，再次遇到a+b时，将不再计算a+b。那么，怎么才能知道a+b有没有出现过呢？方法是，把a+b存储起来。

存储一个表达式，用哈希表很合适。我们使用的这个哈希表使用“开放散列法”创建。具体方法如下：

这个哈希表在哪里？我把它放在函数的符号中。来看一看存储函数的结构。

公共表达式经过哈希函数处理之后，存储到FunctionSymbol的成员valNumTable中。

这意味着，我们只处理函数中的公共表达式。对函数外面的公共表达式，不处理。

一起看一看怎么把t0:a+b存储到哈希表中。伪代码如下。

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。

上面的代码中有两个a，但这两个a的作用域不同。

全局变量a存储在哈希表A中，test的局部变量a存储在哈希表B中。

A和B一起构成哈希链表。

bucketLinker的数据结构如下。

typedef struct bucketLinker{  Symbol sym;   // 指向下一个bucketLinker。   struct bucketLinker *link;}*BucketLinker;

Symbol有两个成员link和next，都能指向下一个Symbol。为什么还新建一个BucketLinker用来创建链表呢？因为Symbol的两个成员link和next都有其他用途，暂且不关注。

再看哈希表的数据结构。

level存储”作用域“。在前面的例子中，存储全局变量a的哈希表的level的值是0，存储test的局部变量a的哈希表的level的值是1。

本节的小标题是一个函数名，这个函数的功能是：把一个存储了变量或函数的Symbol存储到哈希表中。请看伪代码。

再看一小段代码。

这不就是从AddSymbol中抽出来的吗？有必要再看一次。

因为这两行代码运用了”开放散列法“，而我很久以前觉得”开放散列法“是比较有技术含量东西。

在我的工作中，未曾需要自己动手实现”开放散列法“。用到哈希时，调用一个哈希函数而已。

关于符号表，就讲完了。本文囊括了主要知识点。

第一次看符号表，我觉得有点复杂。惭愧惭愧。

做个简单的总结吧。

在编程语言例如C语言中，存在变量、函数。要为一个变量建模，就要设计出合适的结构存储变量的数据类型和变量名、变量值。

用类型系统存储数据类型。

用符号表存储变量的变量名、变量值、变量的初始值等。

符号表需具备下列功能：

对了，想了解类型系统，请阅读《C语言的类型系统》。

《C 编译器剖析》