symtab.c

SIP软件开发记录 由于通信网的封闭性

/* symtab.c
 * Symbol table implementation for the TINY conpiler
 * (allows only one symbol table)
 * Symbol tables is implemented as a chianed
 * hash table
 *
 * Compiler Construction: Principles and Practice
 * Kenneth C. Louden
 * 编译原理及实践
 * (美) Kenneth C. Louden 著
 * 冯博琴 冯岚 等译
 * 机械工业出版社 IBSN 7-111-07703-2
 * 源代码：zwf编辑并修订
 * Code Modify: Larry Li 2001.11
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "symtab.h"

/* SIZE is the size of the hash table */
#define SIZE 211

/* SHIFT is the power of two used as multiplier
 * in hash function
 */
#define SHIFT 4

/* the hash function */
static int hash(char *key)
{
	int temp = 0;
	int i;

	for (i = 0; key[i] != '\0'; i++)
		temp = ((temp << SHIFT) + (unsigned) key[i]) % SIZE;
	/* use unsigned support Chinese */
	return temp;
}

/* the list of line numbers of the source
 * code in which a variable is referenced
 */
typedef struct LineListRec {
	int lineno;
	struct LineListRec *next;
} *LineList;

/* The record in the bucket lists for
 * each variable, include name,
 * assigned memory location, and
 * the list of line numbers in which
 * it appears in the source code
 */
typedef struct BucketListRec {
	char *name;
	LineList lines;
	int memloc;					/* memory location for variable */
	struct BucketListRec *next;
} *BucketList;

/* the hash table */
static BucketList hashTable[SIZE];

/* Procedure st_insert inserts line numbers and
 * memory locations into the symbol table
 * loc = memory llocation is inserted only the
 * first time, otherwise ignored
 */
void st_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) {			/* variable not yet in table */
		l = (BucketList) malloc(sizeof(struct BucketListRec));
		//???if(l==NULL)
		l->name = name;
		l->lines = (LineList) malloc(sizeof(struct LineListRec));
		//???if(l->lines==NULL)
		l->lines->lineno = lineno;
		l->memloc = loc;
		l->lines->next = NULL;
		l->next = hashTable[h];
		hashTable[h] = l;
	} else {					/* found in table, so just add line number */
		LineList t = l->lines;

		while (t->next != NULL)
			t = t->next;
		t->next = (LineList) malloc(sizeof(struct LineListRec));
		//???if(t->next==NULL)
		t->next->lineno = lineno;
		t->next->next = NULL;
	}
}

/* Function st_lookup returns the memory
 * loaction of a variable or -1 if not found
 */
int st_lookup(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;
}

/* Procedure printSymTab prints a formatted
 * listing of the symbol table contents
 * to the listing file
 */
void printSymTab(FILE * listing)
{
	int i;

#ifdef CHINESE
	fprintf(listing, "变量名称      位置     行号\n");
#else
	fprintf(listing, "Variable Name Location Line Numbers\n");
#endif
	fprintf(listing, "------------- -------- ------------\n");
	for (i = 0; i < SIZE; i++) {
		if (hashTable[i] != NULL) {
			BucketList l = hashTable[i];

			while (l != NULL) {
				LineList t = l->lines;

				fprintf(listing, "%-13s ", l->name);
				fprintf(listing, "%-8d ", l->memloc);
				while (t != NULL) {
					fprintf(listing, "%4d ", t->lineno);
					t = t->next;
				}
				fprintf(listing, "\n");
				l = l->next;
			}
		}
	}
}