In this assignment we will construct a symbol table that can store type and scope information of

a symbol found in the source program. If the source program consists of a single scope then we

can use a hash table to store information of different symbols. Hashing is done using the symbol

as key. Figure I illustrates such a symbol table. Now consider the following C code:

Suppose that we are currently dealing with line no $6.$ In that case, global variables $a,b$ and $c,$

function parameter $x,$ function func's local variable $t$ and the variable a declared within the if

block, are visible. Moreover the variable a declared within the if block hides the global variable

a$.$ How can we store symbols in a symbol$-$table which can help us to handle scope easily?

One way is to maintain a separate hash table for each scope. We call each hash table a

Scope$-$Table. In our Symbol$-$Table, we will maintain a list of seope$-$tables. You can also think of

the list of seope$-$tables as a stack of seope$-$tables. Whenever we enter a new block, we create a

new seope$-$table and insert it at the top of the list Whenever we find a new symbol within that

block of the source code, we insert it in the newly created scope$-$table i$.$e$.$ the scope$-$table at the

top of the stack. When we need to get the information of a symbol, at first we will search at the

topmost scope$-$table

If we could not find it there, we would search in its parent scope$-$table and so on$.$ When a block

ends we simply pop the topmost scope table. Suppose we give a unique number to each block,

to global scope, $2$ to the function func, $3$ to the if block and $4$ to the main function. Figure $2$

illustrates the state of the symbol table when we are in line no$.6$ of the given code.

$3\mathrm{.}1$ Symbol Table Generation

We have already used a symbol info class to build our syntax analyzer

Now, You have to implement two more classes.

scope table: This class implements a hash table. You may need an array $($array of

peinters of symbol$\_$info type$)$ and a hash function. The hash function will determine the

corresponding bucket no$.$ the sumbol info object will go into. The hash function woul

be any suitable hash function to your choice. The hash function will take the name of the

symbol as input Don't forget to keep the hashvalue in the range of the bucketsize.

You will also need a pointer of scope table type object named parent scope as a

member variable so that you can maintain a list of scope tables in the symbol table.

Also give each table a unique id$.$

You also need to add the following functionalities to your Scope Table:

D Insert: Insert into symbol table if already not inserted in this scope table. Return type

of this function should be boolean indicating whether insertion is successful or not.

Loek up: Search the hash table for a particular symbol. Return a symbol info pointet.

D Delete: Delete an entry from the scope table. Return true in case of successful deletion

and false otherwise.

Print: Print the scope table in the logfile

You should also write a constructor that takes an integer $n$ as a parameter and allocates

$n$ buckets for the hash table. You should also write a destructor to deallocate memory

The function signatures are already given in the scope$\_$table.h file. Complete them.

symbol table: This class implements a list of scope tables. The class should have

peinter of scope$\_$table type which indicates the current scopetable. This class shoul

contain the following functionalities

D Enter Scope: Create a new scope table and make it current one. Also make the

previous current table as its parent scope table

D Exit Scope: Remove the current scope$\_$table.

Insert. Insert a symbol in current scope table. Retum true for successful insertion and

false otherwise. This should call the Insert function of the current scope$\_$table.

a Remove: Remove a symbol from current scope$\_$table. Return true for successful

removal and false otherwise. This should call the remove function of the curren

scope$\_$table.

D Look up: Look up a symbol in the symbol$\_$table. At first search in the current

scope$\_$table then search in its parent scope table and so on$.$ Return a pointer to the

symbol$\_$info object representing the searched symbol.

Srint Current scope$\_$table: Print the current scope$\_$table to logfile

a Print All scope$\_$table: Print all the scope$\_$table$($s$)$ currently in the symbol table.

$3\mathrm{.}2$ Syntax Analysis with Symbol Insertions

We have already done syntax analysis in the $2$nd assignment. Now, you have to modify the

action parts for the grammar rules, where necessary. Insert all the identifiers in the symbol table

when they are declared in the input file. For example, if you find int $a,b,c$; then insert $a,b$ and

$c$