符号表是一个编译器工作的核心部分，从收集到整理再到通过它生成最终文件。

对于一个符号，记载了不同的内容，如函数符号可能记录了变量的类型，名字，作用域等。系统中主要有这几个符号：

Symbol Functions;       // 函数符号
Symbol Globals;         // 全局变量和静态变量符号
Symbol Strings;         // 字符串符号
Symbol FloatConstants;  // 浮点型变量符号

 UCC 的符号定义如下：

#define SYMBOL_COMMON     \
    int kind;             \
    char *name;           \
    char *aname;          \
    Type ty;              \
    int level;            \
    int sclass;           \
    int ref;              \
    int defined   : 1;    \
    int addressed : 1;    \
    int needwb    : 1;    \
    int unused    : 29;   \
    union value val;      \
    struct symbol *reg;   \
    struct symbol *link;  \
    struct symbol *next;

typedef struct symbol
{
        SYMBOL_COMMON
} *Symbol;

其中属性 ty( Type ) 记录的是类型信息，如类型的种类，大小，对齐方式等。在 UCC 自带的文档中有描述。

一个对符号表影响较大的属性是 level( int ) ，意指嵌套层次。因为 C 语言来说是分块的（在 { 和 } 之间）， 这个块就是一个作用域，一个作用域里不能出现两个同名的符号，当在一个作用域里查找一个符号时，回从当前作用域一直向上层的作用域中进行查找，直到查找到；否则，报错找不到符号。

 符号是通过符号表管理的，符号表有下面几个：

// tags in global scope, tag means struct/union, enumeration name
static struct table GlobalTags;
// normal identifiers in global scope
static struct table GlobalIDs;
// all the constants
static struct table Constants;
// tags in current scope
static Table Tags;
// normal identifiers in current scope
static Table Identifiers;

 符号表主要是一个符号的链表：

typedef struct table
{
	Symbol *buckets;
	int level;
	struct table *outer;
} *Table;

 属性 level 指的是嵌套层次，而 outer 指向的是上一层的符号表。以这种层次关系划分符号表， 可以很快的找到符号。

 另外，符号表的内容 buckets 是通过哈希表实现的，这样提高了效率。

对哈希表的管理可以参考这篇文章(pdf)：OCCL 编译器中符号表的研究和实现 ( 郭晓艳、朱望规 )

编译器对符号表的操作无非这么几种：

1. 向符号表中添加新符号 (Add 类函数 )

值得注意的是 UCC 为了避免不必要的空间开销，对符号表的初始化采用最迟分配和初始化方案处理的，你会看到符号表的空间初始化是在添加符号时完成的：

/**
 * 添加符号 sym 到符号表 tbl 中
 */
static Symbol AddSymbol(Table tbl, Symbol sym)
{
	unsigned int h = (unsigned long)sym->name & SYM_HASH_MASK;

	/// 为避免空间开销，仅当有新符号时才为符号表申请空间
	if (tbl->buckets == NULL)
	{
		int size = sizeof(Symbol) * (SYM_HASH_MASK + 1);

		tbl->buckets = HeapAllocate(CurrentHeap, size);
		memset(tbl->buckets, 0, size);
	}

	sym->link = tbl->buckets[h];
	sym->level = tbl->level;
	tbl->buckets[h] = sym;

	return sym;
}

2. 查询符号表中某个符号 (LookUp 类函数)

查找符号是从最近的作用域一直向上搜索，直至找到：

/**
 * 在本作用域和外层作用域中查找名为 name 的符号
 */
static Symbol LookupSymbol(Table tbl, char *name)
{
	Symbol p;
	unsigned h = (unsigned long)name & SYM_HASH_MASK;

	do
	{
		if (tbl->buckets != NULL)
		{
			for (p = tbl->buckets[h]; p; p = p->link)
			{
				if (p->name == name)
					return p;
			}
		}
	} while ((tbl = tbl->outer) != NULL);

	return NULL;
}

• 相关文章