I need to build the function symtbl_finalizeScope, which will be at the bottom of file symtbl.c Thanks

Complete the implementation of the symbol table. A template of the symbol table program is given in symtbl.c. You can find symtbl.h in the project resources page.

You need to make use of a memory management module, which we will discuss in class. The codes can be found clicking the following links: mem.h and mem.c.

From page 87 of the textbook by Aho, Lam, Sethi and Ullman on Optimization of Symbol Tables for Blocks:

"Some compilers maintain a single hash table of accessible entries; that is, of entries that are not hidden by a declaration in a nested block. Such a hash table supports essentially constant-time lookups, at the expense of inserting and deleting entries on block entry and exit. Upon exit from a block B, the compiler must undo any changes to the hash table due to declarations in block B. It can do so by using an auxiliary stack to keep track of changes to the hash table while block B is processed."

In this lab, we implement the symbol table using hashing and an auxiliary stack.

The symbol table is a hash table (array) of linked list of symbol table entries. Symbol table entry names may vary significantly in lengths. The names are held in one memory pool str_pool. On the other hand, the symbol table entries are to be allocated from another memory pool symtbl_entry_pool.

The hash function used is a simple one. It is explained in the documentation for the function symtbl_hashin symtbl.c.

Detailed Instructions:

To implement symtbl_install, you need to call mem_get_free to a get a piece of memory for aSYMENTRY. Let p be a pointer to the structure SYMENTRY. That is, p is the type SYMTBL. Asmem_get_free is returning a pointer to char, we need to apply a type conversion before we can assign it to p. The type conversion is given in the following:

p = (SYMTBL) mem_get_free( ..... )

For each variable in the symbol table, we need to enter its scope level. It is possible to declare different variables of the same name but at different scope levels. However, we cannot have the same variable name declared within the same block (that is, same scope level). That is, the parser program needs to determine if a variable has been declared more than once.

A block has its limited life span. When a block ends, we need to go to the symbol table to delete all variables declared within the block. It will be convenient if all the variables defined within the same block have been linked together so that they can be easily accessed for deletion. That is, we need to augment the data structure for the symbol table to add one more link to the symbol table entry structure. In addition, the head pointer for such links, called head_scope_link is maintained as a global variable insymtbl.c. Actually, we are not going to physically delete the symbol table entries since there may be some abstract syntax tree nodes pointing to the symbol entries. We only need to remove the entries from being accessible through the hash table. We need to prepare a function symtbl_finalizeScope() for performing the conceptual deletions when a block ends.

To look up a symbol from the symbol table, we need to take into account of the scope rule to look for the symbol defined in the nearest/closest block. Click here for the explanations from pages 756-759 of "Engineering a Compiler" by Cooper and Torczon.

When inserting an entry of name sym to the hash table, we first need to determine the bucket index which is calculated as symtbl_hash(sym). For the list of entries linked from symtbl_hash_table[index], the entries are ordered in decreasing order of scope levels. If the entry is a constant (that is, a number as C-- language has only number constants), we consider the scope of a constant to be 0. In the case of an entry for a constant, we need to append the entry to the end of the list. On the other hand, for any other entries that are not constants, we just insert them to the front of the list.

We suggest the following conventions to follow: Number constants are considered to be of scope level 0 no matter in which blocks they are defined. Using the program 1 below as an example, The program name fact is considered to be of scope level 1. The parameter v of float type and variable i of integer type are of scope level 2. Another variable i of float type is of scope level 3, etc.

Example programs:

 // program 1 int fact(float v){ int i; { float i; i = 2; } return i; } 

 // program 2 int fact(float v){ int i; float i; { i = 2; } return i; } 

 // program 3 int fact(float v){ {int i; i = 2; } {float i; i = 3; } } 

 // program 4 int fact(float v){ {int i; i = 2; } {float i; i = 3; } return i; } 

Note that programs 1 and 3 are legitimate, whereas programs 2 and 4 have compilation error.

A main program for testing the correctness of your implementation is provided in lab4main.c.

Here are the commands you need to use:

gcc -c mem.c gcc -c symtbl.c gcc -o lab4 lab4main.c symtbl.o mem.o lab4

You may want to make use of a Makefile to compile the programs. The content of the Makefile is as follows:

 lab4: lab4main.c symtbl.o mem.o gcc -o lab4 lab4main.c symtbl.o mem.o symtbl.o: symtbl.c symtbl.h gcc -c symtbl.c mem.o: mem.c mem.h gcc -c mem.c 

To run the Makefile, just type make.

You should modify lab4main.c to try out some other test cases.

******************************************

//symtbl.c

/** ** Symbol table manager **/ #include  #include  #include "symtbl.h" #include "mem.h" #define SYMTBL_SIZE 1024 #define STR_TABLE_SIZE 1024 #define SYMTBL_HASH_TABLE_SIZE 32 char *symtbl_type_name[] = { "ID", "NUM", "FUNC", "PARA", "TEMP" }; char *data_type_name[] = { "INT", "FLOAT", "VOID" }; MEM_POOL symtbl_entry_pool; /* pool of symbol table entries */ SYMTBL symtbl_hash_table[SYMTBL_HASH_TABLE_SIZE]; /* hash table */ MEM_POOL str_pool; int temp_num; /* number of temp variables, also used to name temps */ int num_entries; /* total number of entries used in the symtbl_entry_pool */ SYMTBL head_scope_link; /* initialize each symbol hash table entry to NULL. allocate memory to 'symtbl_entry_pool' and 'str_pool' using 'mem_alloc_pool'. specifically, 'str_pool' should hold 'STR_TABLE_SIZE' bytes and 'symtbl_entry_pool' should hold 'SYMTBL_SIZE' number of 'SYMENTRY's. 'temp_num' and 'head_scope_link' are initialized to null. */ void symtbl_init() {int i; for (i = 0; i < SYMTBL_HASH_TABLE_SIZE; i++) symtbl_hash_table[i] = 0; symtbl_entry_pool = mem_alloc_pool(SYMTBL_SIZE*sizeof(SYMENTRY)); str_pool = mem_alloc_pool(STR_TABLE_SIZE); temp_num = 0; head_scope_link = 0; } /* use the following simple hash function: add up the ascii value of each character in 'name' return `sum' modulo SYMTBL_HASH_TABLE_SIZE */ int symtbl_hash(char *name) { 

int i;

for (i = 0; i < SYMTBL_HASH_TABLE_SIZE; i++) name = name + symtbl_hash_table[i]->sym_name; return name % SYMTBL_HASH_TABLE_SIZE;

 } /* return a pointer to a symbol table entry that has the name field being 'sym' hint: use 'strcmp' to compare between two strings. return NULL if there is no symbol table entry with the name being 'sym'. */ SYMTBL symtbl_lookup(char *sym) { 

int i;

for (i = 0; i < SYMTBL_HASH_TABLE_SIZE; i++)

if(strcmp(symtbl_hash_table[i]->sym_name, sym) == 0) return symtbl_hash_table[i]; return NULL;

} /* install a new symbol table entry with the name and type being 'sym' and 'stype' where the symbol types are defined as integers in symtbl.h assume that 'symtbl_lookup' has already been consulted and it is determined that there is not a symbol table entry with the name 'sym' in scope level 'scope' need to call 'mem_get_free' to allocate memory from the pool 'symtbl_entry_pool' to hold a new SYMENTRY need to call 'mem_get_free' to allocate memory from the pool 'str_pool'.' to hold a copy of the string 'sym' we use 'strcpy' to copy string 'sym' into the str_pool. update the linked list appropriately. scope for int or float const is 0; scope is non-negative the symbol table entry for a int or float const needs to be appended to the end of the corresponding list in the symtbl_hash_table. increase the value of the variable 'num_entries' by 1 update the scope_link for entries that are of scope > 0 update the head_scope_link as well. return the entry created */ SYMTBL symtbl_install(char *sym, int stype, int dtype, int scope) { SYMTBL entry, p; char *name; int index; entry = (SYMTBL) mem_get_free(symtbl_entry_pool, sizeof(SYMENTRY)); name = mem_get_free(str_pool, strlen(sym)+1); num_entries += 1; strcpy(name, sym); entry->sym_name = name; entry->sym_type = stype; entry->data_type= dtype; entry->scope = scope; index = symtbl_hash(sym); if (scope == 0) { entry->next = 0; if (!symtbl_hash_table[index]) { symtbl_hash_table[index] = entry; } else { // append to the end of the list as scope is 0 for (p=symtbl_hash_table[index];p->next;p=p->next) /* do nothing */ ; p->next = entry; } } else { entry->next = symtbl_hash_table[index]; symtbl_hash_table[index] = entry; entry->scope_link = head_scope_link; head_scope_link = entry; } return(entry); } SYMTBL symtbl_new_temp(int dtype) { char s[10]; temp_num++; sprintf(s, "TEMP%d", temp_num); return(symtbl_install(s,SYMBOL_TEMP,dtype,-1)); } /* print out the contents of a symbol table entry */ void symtbl_dump_entry(SYMTBL entry) { printf(" Name %s Scope %d Symbol Type %s Data Type %s ", entry->sym_name, entry->scope, symtbl_type_name[entry->sym_type], data_type_name[entry->data_type]); } /* print out the contents of all current entries found in the symbol table. algorithm: search through each bucket of the hash table by following the pointers in the lists to print out all the entries. */ void symtbl_dump_current() { SYMTBL entry; int i; printf(" SYMBOL TABLE DUMP CURRENT: "); for (i = 0; i < SYMTBL_HASH_TABLE_SIZE; i++) for (entry = symtbl_hash_table[i]; entry; entry = entry->next) { printf("Hash index %d: ", i); symtbl_dump_entry(entry); } } /* print out the contents of all entries (including the obsolete ones) found in the symbol table. algorithm: sequentially search through all the entries found in the symtbl_entry_pool. */ void symtbl_dump_all() { int i; SYMTBL entry; printf(" SYMBOL TABLE DUMP ALL: "); for (i=0, entry=(SYMTBL)symtbl_entry_pool->pool; i 
/******************************************************
 
******************************************************/
 
 void symtbl_finalizeScope() { /* TO BE COMPLETED */ } 
 
/******************************************************
 
******************************************************/
 
 
 
 
 
******************************************************
 
*******************************************************
 
//symtbl.h
 
/** ** Interface to the symbol table manager **/ typedef struct SYMTBL_ENTRY { struct SYMTBL_ENTRY *next; /* link entries with the same hash values */ struct SYMTBL_ENTRY *scope_link; /* link entries according to scope level; exception: entries with scope level 0 are not linked */ char *sym_name; int sym_type; int data_type; int scope; /* scope level number that the symbol is in */ } SYMENTRY; typedef SYMENTRY *SYMTBL; /* symbol types */ #define SYMBOL_ID 0 #define SYMBOL_NUM 1 #define SYMBOL_FUNC 2 #define SYMBOL_PARA 3 #define SYMBOL_TEMP 4 /* data types */ #define TYPE_INT 0 #define TYPE_FLOAT 1 #define TYPE_VOID 2 void symtbl_init(); /* initialize symbol table */ SYMTBL symtbl_install(char *sym, int stype, int dtype, int scope); /* find or create entry */ SYMTBL symtbl_lookup(char *sym); /* lookup a symbolic name */ SYMTBL symtbl_new_temp(int dtype); /* create a new temp var */ void symtbl_dump_current(); /* print out all current symbol table entries */ void symtbl_dump_all(); /* print out all symbol table entries (including entries that are not current) */ void symtbl_finalizeScope(); /* set variables in current scope level inactive */ 
 
*********************************************
 
********************************************
 
//lab4main.c
 
#include  #include  #include "symtbl.h" #include "mem.h" main(){ SYMTBL entry; mem_init(); symtbl_init(); symtbl_install("fact", SYMBOL_ID, TYPE_INT, 1); symtbl_install("v", SYMBOL_ID, TYPE_FLOAT, 2); symtbl_install("i", SYMBOL_ID, TYPE_INT, 2); symtbl_install("ii", SYMBOL_ID, TYPE_INT, 2); symtbl_install("i", SYMBOL_ID, TYPE_FLOAT, 3); symtbl_install("r", SYMBOL_ID, TYPE_FLOAT, 3); symtbl_install("2", SYMBOL_NUM, TYPE_INT, 0); entry = symtbl_lookup("i"); if (entry) printf("variable i is found and has scope %d and data type %s ", entry->scope, entry->data_type == 0 ? "integer" : "float" ); else printf("variable i is not found "); symtbl_dump_current(); printf("============================ "); symtbl_dump_all(); printf(" "); printf("============================ "); symtbl_finalizeScope(); entry = symtbl_lookup("i"); if (entry) printf("variable i is found and has scope %d and data type %s ", entry->scope, entry->data_type == 0 ? "integer" : "float" ); else printf("variable i is not found "); symtbl_dump_current(); printf("============================ "); symtbl_dump_all(); printf("============================ "); symtbl_finalizeScope(); symtbl_dump_current(); printf("============================ "); symtbl_dump_all(); } /*********** Outputs are: ************* variable i is found and has scope 3 and data type float SYMBOL TABLE DUMP CURRENT: Hash index 9: Name i Scope 3 Symbol Type ID Data Type FLOAT Hash index 9: Name i Scope 2 Symbol Type ID Data Type INT Hash index 18: Name r Scope 3 Symbol Type ID Data Type FLOAT Hash index 18: Name ii Scope 2 Symbol Type ID Data Type INT Hash index 18: Name 2 Scope 0 Symbol Type NUM Data Type INT Hash index 22: Name v Scope 2 Symbol Type ID Data Type FLOAT Hash index 30: Name fact Scope 1 Symbol Type ID Data Type INT ============================ SYMBOL TABLE DUMP ALL: Name fact Scope 1 Symbol Type ID Data Type INT Name v Scope 2 Symbol Type ID Data Type FLOAT Name i Scope 2 Symbol Type ID Data Type INT Name ii Scope 2 Symbol Type ID Data Type INT Name i Scope 3 Symbol Type ID Data Type FLOAT Name r Scope 3 Symbol Type ID Data Type FLOAT Name 2 Scope 0 Symbol Type NUM Data Type INT ============================ variable i is found and has scope 2 and data type integer SYMBOL TABLE DUMP CURRENT: Hash index 9: Name i Scope 2 Symbol Type ID Data Type INT Hash index 18: Name ii Scope 2 Symbol Type ID Data Type INT Hash index 18: Name 2 Scope 0 Symbol Type NUM Data Type INT Hash index 22: Name v Scope 2 Symbol Type ID Data Type FLOAT Hash index 30: Name fact Scope 1 Symbol Type ID Data Type INT ============================ SYMBOL TABLE DUMP ALL: Name fact Scope 1 Symbol Type ID Data Type INT Name v Scope 2 Symbol Type ID Data Type FLOAT Name i Scope 2 Symbol Type ID Data Type INT Name ii Scope 2 Symbol Type ID Data Type INT Name i Scope 3 Symbol Type ID Data Type FLOAT Name r Scope 3 Symbol Type ID Data Type FLOAT Name 2 Scope 0 Symbol Type NUM Data Type INT ============================ SYMBOL TABLE DUMP CURRENT: Hash index 18: Name 2 Scope 0 Symbol Type NUM Data Type INT Hash index 30: Name fact Scope 1 Symbol Type ID Data Type INT ============================ SYMBOL TABLE DUMP ALL: Name fact Scope 1 Symbol Type ID Data Type INT Name v Scope 2 Symbol Type ID Data Type FLOAT Name i Scope 2 Symbol Type ID Data Type INT Name ii Scope 2 Symbol Type ID Data Type INT Name i Scope 3 Symbol Type ID Data Type FLOAT Name r Scope 3 Symbol Type ID Data Type FLOAT Name 2 Scope 0 Symbol Type NUM Data Type INT */
 
******************************************************
 
*****************************************************
 
//mem.c
 
/** mem.c ** ** The Memory Management module **/ #include  #include  #include "mem.h" #define ERROR_MSG(msg) { fprintf(stderr, "%s ", msg); exit(-1); } #define MAX_POOL 10 MEM_POOL_NODE mem_pools[MAX_POOL]; MEM_POOL next_free_pool; void mem_init() { int i; for (i = 0; i < MAX_POOL-1; i++) { mem_pools[i].link = &mem_pools[i+1]; mem_pools[i].pool = NULL; } mem_pools[MAX_POOL-1].link = NULL; mem_pools[MAX_POOL-1].pool = NULL; next_free_pool = mem_pools; } MEM_POOL mem_alloc_pool(int size) { MEM_POOL mpool = next_free_pool; if (mpool == NULL) ERROR_MSG("Running out of memory pools"); if (size <= 0) ERROR_MSG("mem_alloc_pool: requested size <= 0"); mpool->pool = malloc(size); mpool->size = size; mpool->next_free = mpool->pool; next_free_pool = mpool->link; mpool->link = NULL; return(mpool); } void mem_reset_pool(MEM_POOL mpool) { if ((mpool == NULL) || (mpool->pool == NULL)) ERROR_MSG("Invalid memory pool"); mpool->next_free = mpool->pool; } void mem_free_pool(MEM_POOL mpool) { if ((mpool == NULL) || (mpool->pool == NULL)) ERROR_MSG("Invalid memory pool"); free(mpool->pool); mpool->pool = NULL; mpool->size = 0; mpool->next_free = NULL; mpool->link = next_free_pool; next_free_pool = mpool; } char *mem_get_free(MEM_POOL mpool, int size) { char *ptr; if ((mpool == NULL) || (mpool->pool == NULL)) ERROR_MSG("Invalid memory pool"); ptr = mpool->next_free; if (ptr + size > mpool->pool + mpool->size) ERROR_MSG("Memory pool overflows"); mpool->next_free = ptr + size; return(ptr); } 
 
**************************************************
 
*************************************************
 
//mem.h
 
/** mem.h ** ** Interface to the memory management module **/ typedef struct MEM_POOL_NODE_STRUCT { struct MEM_POOL_NODE_STRUCT *link; char *next_free; int size; char *pool; } MEM_POOL_NODE; typedef MEM_POOL_NODE *MEM_POOL; /* Init memory management module */ void mem_init(); /* Allocate a new memory pool: MEM_POOL mem_alloc_pool(int size_in_bytes) */ MEM_POOL mem_alloc_pool(int size_in_bytes); /* Reset memory pool: void mem_reset_pool(MEM_POOL pool) This does not deallocate/free the memory pool. It only reset the memory pool so that all the memory in the pool can be re-used. */ void mem_reset_pool(MEM_POOL pool); /* Deallocate memory pool: void mem_free_pool(MEM_POOL pool) */ void mem_free_pool(MEM_POOL pool); /* Get free memory space from a memory pool: char *mem_get_free(MEM_POOL pool, int size) */ char *mem_get_free(MEM_POOL pool, int size);