symtab.c

1.小型编译器 2。支持整数

/****************************************************/
/* File: symtab.c                                   */
/* Symbol table implementation for the TINY compiler*/
/* (allows only one symbol table)                   */
/* Symbol table is implemented as a chained         */
/* hash table                                       */
/* Compiler Construction: Principles and Practice   */
/* Kenneth C. Louden                                */
/****************************************************/

#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 = 0;
  	while (key[i] != '\0')
  	{ 
  		temp = ((temp << SHIFT) + key[i]) % SIZE;
    	++i;
  	}
  	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, including 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 location 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));
   	 	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 /* 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));
    	t->next->lineno = lineno;
    	t->next->next = NULL;
  	}
} /* st_insert */

/* Function st_lookup returns the memory 
 * location 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;
  	fprintf(listing,"Variable Name  Location   Line Numbers\n");
  	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,"%-14s ",l->name);
        		fprintf(listing,"%-8d  ",l->memloc);
        		while (t != NULL)
        		{ 
        			fprintf(listing,"%4d ",t->lineno);
          			t = t->next;
        		}	
        		fprintf(listing,"\n");
        		l = l->next;
      		}
    	}
  	}
} /* printSymTab */