1.        实验目的

了解符号表的作用、组织和数据结构，设计和实现一个符号表。

2.        实验要求

a)                  合理有效地设计符号表可存储程序语言中的各种标识符（变量、常量、数组、结构、指针、函数和过程）及其属性和作用域信息

b)                  列出关键算法的具体实现的思路

3.        实验原理及内容

（1）符号表的作用

符号表用于登录名字（标识符）、相应对象的种类（常量、变量、数组、结构、文件、标号、指针、函数与过程等）、属性（整型、实型、字符型、布尔型与枚举型等）和作用域信息。

由于在编译的各个阶段都要对符号表进行频繁操作（查表和填表），在整个编译时间中占了较大比例，因此如何有效合理地组织符号表并选择好的填表和查表方式，对于提高编译器的工作效率有很大影响。

       （2）符号表的组织

源程序中的每个标识符在符号表中都有1个条目，一般由两部分组成：名字栏和信息栏。

如果一个语言对标识符的最大长度有限制，可设计名字栏的域大小为最大长度来容纳整个标识符；若该语言对标识符最大长度无限制或最大长度较大（如：32），为节省存储空间，可另用一个字符数组存储标识符，在名字栏域中存储其起始地址和长度（字符个数）。

源程序中的标识符种类繁多，不同种类的标识符所需要存储的信息不同。如：变量需存储其类型、存储地址等，数组应存储其数组维数m、数组元素类型T、各维元素个数 di、起始地址base等，指针应存储其指向对象类型的位置，函数应存储其参数及类型、返回值类型等……

源程序中的说明将标识符与具有某种类型属性的数据对象相关联。同一个标识符在不同程序位置被说明时代表不同的数据对象。当出现对一个标识符的引用时，需根据作用域规则查符号表获取正确的符号表条目。C语言采用静态作用域规则，按最近嵌套原则确定作用域。

       （3）符号表的数据结构

由于线性表的访问复杂度为O（n），效率较低，符号表常采用效率更高的哈希技术进行实现： 当出现标识符id的定义时，计算哈希函数H(id)，获取其在哈希表的存储位置，如该位置为空，则直接存储，否则应用冲突消解方法来获取其存储位置；当出现对标识符id的引用时，计算哈希函数H(id)，获取其在哈希表的存储位置。

4.        程序代码

C++

Microsoft Visual Studio 6.0

#include

#include

#include

using namespace std;

//标志符数据类型的枚举，整型、实型、字符型、布尔型与枚举型等

enum{Int, Float, Char, Bool};

#define SIZE 211

#define SHIFT 4

static int hash ( string key )

{ int temp = 0;

  int i = 0;

  while (key[i] != '\0')

  { temp = ((temp spec=2*3;

    Array * next;

} * ArrayList;

typedef class Param

{

public:

int type; //参数类型

string name; //参数名

Param *next;

} * ParamList;

//函数

typedef class Function

{

public:

string name; //函数名

int type; //返回值类型

    ParamList pl; //参数列表

    long scope; //标识符作用域信息

long memloc; //函数入口的地址

    Function * next; //异名链表指针

} * FunctionList;

static BucketList ListHash[SIZE];

static ArrayList ArrayHash[SIZE];

static FunctionList FunctionHash[SIZE];

//量的哈希表插入 

void List_insert(string name, int type, long scope, long loc, int flag)

{ 

int h = hash(name);

List *l;

l = new List;

l->name = name;

l->type = type;

l->scope = scope;

l->memloc = loc;

l->flag = flag;

l->next = ListHash[h];

ListHash[h] = l;

}

//量的哈希表修改 

void List_delete(string name)

{

int h = hash(name);

ListHash[h] = NULL;

}

//量的哈希表查找

long List_find(string name)

{

int h = hash(name);

List *l;

l = ListHash[h];

return l->memloc;

}

//数组的哈希表插入 

void Array_insert(string name, int type, long scope, long loc, int weishu, string spec)

{

int h = hash(name);

Array *l;

l = new Array;

l->name = name;

l->type = type;

l->scope = scope;

l->memloc = loc;

l->weishu = weishu;

l->spec = spec;

l->next = ArrayHash[h];

ArrayHash[h] = l;

}

//数组的哈希表修改 

void Array_delete(string name)

{

int h = hash(name);

ArrayHash[h] = NULL;

}

//数组的哈希表查找

long Array_find(string name)

{

int h = hash(name);

Array *l;

l = ArrayHash[h];

return l->memloc;

}

//函数的哈希表插入

void Function_insert(string name, int type, ParamList pl, long scope, long loc)

{

int h = hash(name);

Function *l;

l = new Function;

l->name = name;

l->type = type;

l->pl = pl;

l->scope = scope;

l->memloc = loc;

l->next = FunctionHash[h];

FunctionHash[h] = l;

}

//函数的哈希表插入

void Function_delete(string name)

{

int h = hash(name);

FunctionHash[h] = NULL;

}

//函数的哈希表查找

long Function_find(string name)

{

int h = hash(name);

Function *l;

l = FunctionHash[h];

return l->memloc;

}

//量的打印

void printList()

{

int i;

cout