systab.h

<compiler construction principles and practice>书中定义的tiny语言编译器。

#define SIZE 211

#define SHIFT 4


typedef struct LineListRec
{ 
	int lineno;
    struct LineListRec * next;
} * LineList;

typedef struct BucketListRec
{
	char * name;
    LineList lines;
    int memloc ; 
    struct BucketListRec * next;
} * BucketList;


static BucketList hashTable[SIZE];

class SymTab
{
private:
	int Hash(char *key);

public:

	void Insert(char * name, int lineno, int loc );
	int Find ( char * name );
	void PrintSymTab();
};




void SymTab ::Insert(char *name, int lineno, int loc)
{
	int h = Hash(name);
    BucketList l =  hashTable[h];
    while ((l != NULL) && (strcmp(name,l->name) != 0))
		l = l->next;
	if (l == NULL) 
    {
		l = (BucketList) malloc(sizeof(struct BucketListRec));
	    l->name = name;
		l->lines = (LineList) malloc(sizeof(struct LineListRec));
		l->lines->lineno = lineno;
		l->memloc = loc;
		l->lines->next = NULL;
		l->next = hashTable[h];
		hashTable[h] = l;
	}
    else
	{
		LineList t = l->lines;
	    while (t->next != NULL) t = t->next;
			t->next = (LineList) malloc(sizeof(struct LineListRec));
		t->next->lineno = lineno;
		t->next->next = NULL;
	}
}

void SymTab::PrintSymTab()
{
	int i;
	cout<<"Variable Name  Location   Line Numbers\n";
	cout<<"-------------  --------   ------------\n";

	for (i=0;i<SIZE;++i)
	{ 
		if (hashTable[i] != NULL)
		{
			BucketList l = hashTable[i];
	        while (l != NULL)
			{
				LineList t = l->lines;
				cout <<left<<setw(15)<< l->name;
				cout << setw(11)<<l->memloc;
			    while (t != NULL)
			    { 
					cout <<setw(3)<<t->lineno;
					t = t->next;
				}
				cout << endl;
				l = l->next;
			}
		}
	}
} 


int SymTab ::Find(char *name)
{ 
	int h = Hash(name);
	BucketList l = hashTable[h];
	while ((l != NULL) && (strcmp(name,l->name) != 0))
		l = l->next;
	if (l == NULL) return -1;
	else return l->memloc;
}




int SymTab ::Hash(char *key)
{ int temp = 0;
  int i = 0;
  while (key[i] != '\0')
  { temp = ((temp << SHIFT) + key[i]) % SIZE;
    ++i;
  }
  return temp;
}