Submit all your programs (include .h files) and test cases in a ZIP file (* I ba

Question

Submit all your programs (include .h files) and test cases in a ZIP file

(* I basically need to complete functions symtbl_hash, symtbl_lookup, and symtbl_finalizeScope in symtbl.c *)

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:

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:

To run the Makefile, just type make.

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

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

//symtbl.c

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

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

//symtbl.h

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

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

//lab4main.c

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

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

//mem.c

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

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

//mem.h

Explanation / Answer

From the precise explanation of the question, the incompleted functions symbl_hash() and symtbl_lookup() into the file symtbl.c -can be implemented as -

int symtbl_hash(char *name)

{

int i;

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

name += symtbl_hash_table[i].sym_name; /* Calculates sum in each iteration */

return name % SYMTBL_HASH_TABLE_SIZE; /* returns modulo answer */

}

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; /* If not found, returns NULL value */

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.