symtab.cpp

小型编译系统的源代码

#include "globals.h"
#include "symtab.h"

//the size of the hash table
const int SIZE = 17;
//the power of two used as multiplier in hash function
const int SHIFT = 4;

char * funcname = NULL;

/* 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
 */
struct LineList
{ 
        int lineno;
  struct LineList * next;
        LineList(){
                lineno = -1;
                next = NULL;
        }
};


/* 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
 */
struct BucketList
{ 
        char * name;
				LineList * lines;
				char * fname;
        entryType entrytype;
        int memloc;
        int size;
        paramType * param;
  //int memloc ; /* memory location for variable */
  struct BucketList * next;
        BucketList(){
                name = NULL;
								fname = NULL;
                lines = NULL;
                next = NULL;
                memloc = -1;
								param = NULL;
								size = 0;
        }
};

/* the hash table */
struct SymTab{
        BucketList * hashTable[SIZE];
        SymTab * child;
        SymTab * parent;
        SymTab * sibling;
        SymTab(){
                for (int i=0;i<SIZE;i++)
                        hashTable[i] = NULL;
                child = parent = sibling = NULL;
        }
};

SymTab * symtable = NULL;
SymTab * current = NULL;
SymTab * last    = NULL;

/* Procedure AllocateSym allocate space for a new SymTab 
 * and set the parent of the new table to the parameter parent
 */
SymTab * AllocateSym( SymTab * parent){
        SymTab * temps = new SymTab;
        temps->parent = parent;
        return temps;
}

/* Procedure st_insert inserts line numbers and
 * memory locations into the symbol table
 * loc = memory location is inserted only the
 * first time, otherwise ignored
 */
int st_insert( char * name, int lineno, ExpType type, ExpKind kind, int size)
{ 
        int h = hash(name);
        if (current==NULL)
                symtable = current = last = AllocateSym(NULL);
  BucketList * l =  current->hashTable[h];
  while ((l != NULL) && (strcmp(name,l->name) != 0))
    l = l->next;
  if (l == NULL) /* variable not yet in table */
  { 
                l = new BucketList;
    l->name = name;
		if (funcname == NULL){
			l->fname = new char [7];
			strcpy(l->fname, "Global");
		}
		else {
			l->fname = new char [strlen(funcname)-1];
			strcpy(l->fname, funcname);
		}
    l->lines = new LineList;
    l->lines->lineno = lineno;
    //l->memloc = loc;
    l->lines->next = NULL;
    l->next = current->hashTable[h];
    l->entrytype.type = type;
		switch (type){
			case Integer:
			case Float:
				l->size = 4;
				break;
			case Char:
				l->size = 1;
				break;
		}
    if (kind == IdK){
			l->entrytype.varK = Norm;
		}
    else if (kind == ArrayK){
			l->entrytype.varK = Array;
			l->size = l->size * size;
		}
    current->hashTable[h] = l; 
  }
  else /* found in table, so just add line number */
     return FAIL; 
  return SUCCESS;
} /* st_insert */

int st_insert( char * name, int lineno, ExpType type, TreeNode * params)
{
        int h = hash(name);
        if (current==NULL)
                symtable = current = last = AllocateSym(NULL);
  BucketList * l =  current->hashTable[h];
  while ((l != NULL) && (strcmp(name,l->name) != 0))
    l = l->next;
  if (l == NULL) /* variable not yet in table */
  { 
                l = new BucketList;
    l->name = name;
    l->lines = new LineList;
    l->lines->lineno = lineno;
    //l->memloc = loc;
    l->lines->next = NULL;
    l->next = current->hashTable[h];
    l->entrytype.type = type;
    l->entrytype.varK = Func;
		if (funcname == NULL){
			l->fname = new char [7];
			strcpy(l->fname, "Global");
		}
    paramType * head = l->param;
    for (TreeNode * tt = params; tt!=NULL; tt = tt->sibling){
      if (l->param==NULL){
        l->param = new paramType;
        l->param->next=NULL;
        head = l->param;
        l->param->type.type=tt->child[0]->attr.vartype;
			}
      else {
        l->param->next = new paramType;
				l->param=l->param->next;
        l->param->type.type=tt->child[0]->attr.vartype;
      }
			if (tt->child[1]->kind.exp == ArrayK)
        l->param->type.varK = Array;
      else l->param->type.varK = Norm;
    }  //for
    l->param = head;
		l->size = 0;
    current->hashTable[h] = l; 
        }
  else /* found in table, so just add line number */
     return FAIL; 
  return SUCCESS;
}

/* Function st_lookup returns the memory 
 * location of a variable or -1 if not found
 */
int st_lookup ( char * name , Result & result)
{ 
  int h = hash(name);
  SymTab * ts = current;
  for (;ts!=NULL;ts=ts->parent){
     BucketList * l = ts->hashTable[h];
     while ((l != NULL) && (strcmp(name,l->name) != 0))
            l = l->next;
     if (l!=NULL){
       result.etype = l->entrytype.type;
			 result.vark = l->entrytype.varK;
       if (l->entrytype.varK == Func)
         result.params = l->param;
			 result.memloc = l->memloc;
			 result.size = l->size;
       break;
     }
  }
	if (ts == symtable)result.local=false;
	else result.local=true;
	
  if (ts == NULL) return FAIL;
  else return SUCCESS;
}

int st_funclookup( char * name, ExpType type, TreeNode * params)
{
        if (symtable == NULL) return FAIL;
        int h = hash(name);
        BucketList * l = symtable->hashTable[h];
        while ((l != NULL) && (strcmp(name,l->name) != 0) )
                        l = l->next;
        if (l == NULL) return FAIL;
        else {//name found, compare the return type and parameters
                if (l->entrytype.type==type&&l->entrytype.varK==Func){
                        TreeNode * tp1;
                        paramType *tp2;
                        for (tp1=params,tp2=l->param;tp1!=NULL&&tp2!=NULL;tp1=tp1->sibling,tp2=tp2->next)
                                if (tp1->child[0]->attr.vartype!=tp2->type.type||tp1->child[1]->varK!=tp2->type.varK)
                                        break;
                        if (tp1==NULL&&tp2==NULL)return SUCCESS;
                        else return UNCONFORM;
                }
        }
				if (l->entrytype.type!=type)
					return INVALID;
        return FAIL;
}

int st_funclookup( char * name, Result & result)
{
	int h = hash(name);
  BucketList * l = symtable->hashTable[h];
  while ((l != NULL) && (strcmp(name,l->name) != 0))
     l = l->next;
  if (l!=NULL&&l->entrytype.varK==Func){
		result.params = l->param;
		result.etype = l->entrytype.type;
		result.vark = l->entrytype.varK;
		result.memloc = -1;
		result.local = false;
		result.size = 0;
	}
	else return FAIL;
	return SUCCESS;
}

/* Procedure st_setLoc  set a variable's memory location
 *
 */
int st_setLoc(char * name, int location)
{
	int h = hash(name);
  BucketList * l = current->hashTable[h];
  while ((l != NULL) && (strcmp(name,l->name) != 0))
     l = l->next;
  if (l!=NULL){
		l->memloc = location;
  }
  else return FAIL;
	return SUCCESS;
}

/* Function st_newBuck notes that the procedure enters
 * a new compoud statement
 */
void st_newBuck()
{
        if (symtable == NULL)
                symtable = current = last = AllocateSym(NULL);
        if (current == last){
        	if (current->child == NULL){
        		current->child = AllocateSym(current);
        		current = last = current->child;
        	}
        	else current = last = current->child;	
        }
        else if (last->parent == current){
        	if (last->sibling == NULL)
        		last->sibling = AllocateSym(current);
        	current = last = last->sibling;	
        }
        else {
        //error! You have met a bug of the procedure	
        }
}

/* Function st_delBuck notes that the procedure leaves
 * a compoud statement
 */
void st_delBuck()
{
        if (current->parent!= NULL){
        	if (current == last)
        		current = last->parent;
        	else if (last->parent= current){
        		current = current->parent;
        		last = last->parent;
        	}
        	else {
        	//error! You have met a bug of the procedure	
        	}
        }
}

void st_reset()
{
	current = last = symtable;
}

//Enterss a Function definition part
void st_inFunc(char * name){
	if (funcname!=NULL)delete funcname;
	funcname = new char[strlen(name)+1];
	strcpy(funcname,name);
}

//Leaves a Function definition part
void st_outFunc(){
	delete funcname;
	funcname = NULL;
}

void printSymTab(FILE * listing, SymTab * symbol)
{
	int i;
	if (symbol == NULL)return;
	for (i=0;i<SIZE;++i)
  { if (symbol->hashTable[i] != NULL)
    { BucketList *l = symbol->hashTable[i];
      while (l != NULL)
      { LineList *t = l->lines;
        fprintf(listing,"%-17s",l->name);
				//if (symbol == symtable)fprintf(listing,"Global  ");
				//else fprintf(listing,"Local   ");
				fprintf(listing,"%-14s",l->fname);
				if (l->entrytype.varK==Func){
					switch(l->entrytype.type){
					case Integer:
						fprintf(listing,"Func returns int   ");
						break;
					case Char:
						fprintf(listing,"Func returns char  ");
						break;
					case Void:
						fprintf(listing,"Func return void   ");
						break;
					}
				}
				else if (l->entrytype.varK==Array){
					switch(l->entrytype.type){
					case Integer:
						fprintf(listing,"Array of int       ");
						break;
					case Char:
						fprintf(listing,"Array of char      ");
						break;
					case Void:
						fprintf(listing,"Array of void      ");
						break;
					}
				}
				else {
					switch(l->entrytype.type){
					case Integer:
						fprintf(listing,"     int           ");
						break;
					case Char:
						fprintf(listing,"     char          ");
						break;
					case Void:
						fprintf(listing,"     void          ");
						break;
					}
				}
				fprintf(listing,"%-4d   ",l->size);
				fprintf(listing,"%-6d      ",l->memloc);
				fprintf(listing,"\n");
        l = l->next;
      }
    }
  }
	printSymTab(listing,symbol->child);
	printSymTab(listing,symbol->sibling);
}
void printSymTab(FILE * listing){
	fprintf(listing,"Variable Name        Area           Type          size    Location   \n");
	fprintf(listing,"-------------    ------------  --------------     ----   ----------  \n");
  printSymTab(listing,symtable);
}