Description

CSE 310: Compiler Sessional
Assignment 1 Implementation of Symbol Table

1 Introduction

Figure 1: Symbol Table using hashing.
2 Symbol Table
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 1 illustrates such a symbol table. Now consider the following C code.

1. int a,b,c;
2. int func(int x){
3. int t=0;
4. if(x==1){
5. int a=0;
6. t=1;
7. }
8. return t;
9. }
10.int main(){
11. int x=2;
12. func(x);
13. return 0;
14.}

To successfully compile this program, we need to store the scope information. Suppose that we are currently dealing with line no. 5. 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 we can store symbols in 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 maintain a list of scope tables. You can also think the list of scope tables as a stack of scope tables. Whenever we enter in a new block, we create a new scope table and insert it in the top of the list. Whenever we found a new symbol within that block of the source code, we insert it in the newest 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 the next 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, 1 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 symbol table when we are in line no 6 of the given code.
3 Tasks
You have to implement following three classes.

Figure 2: Symbol Table with scope handling.
– 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.
– Look up: Search the hash table for particular symbol. Return a SymbolInfo pointer.
– Delete: Delete an entry from the symbol table. Return true in case of successful deletion and false otherwise.
– Print: Print the scope table in the console.
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.
• SymbolTable: This class implements a list of scope tables. The class should have a pointer of ScopeTable type which indicates the current scope table. This class should contain the following functionalities:
– Enter Scope: Create a new ScopeTable and make it current one. Also make the previous current table as its parentScopdeTable.
– Exit Scope: Remove the current ScopeTable.
– Insert: Insert a symbol in current ScopeTable. Return true or false.
– Remove: Remove a symbol from current ScopeTable. Return true or false.
– Lookup: LookupasymbolintheScopeTable. AtfirstsearchinthecurrentScopeTable, if not found then search in its parent ScopeTable. Return a pointer of SymbolInfo type.
– Print Current ScopeTable: Print the current ScopeTable.
– Print All ScopeTable: Print all the ScopeTables currently in the SymbolTable.
4 Input
The first line of the input is a number indicating number of buckets in each hash table. Each of the following line will start with a code letter indicating the operation you want to perform. The letters will be among ‘I’, ‘L’, ‘D’, ‘P’, ‘S’ and ‘E’ . ‘I’ stands for insert which is followed by two space separated strings where the first one is symbol name and the second one is symbol type. As you already know, the symbol name will be the key of the record to be stored in the symboltable. ‘L’ means lookup which is followed by a string containing the symbol to be looked up in the table. ‘D’ stands for delete which is also followed by a string to be deleted. ‘P’ stands for print the symbol table which will be followed by another code letter which is either ‘A’ or ‘C’. If ’A’ is followed by ‘P’ then you will need to print all the scope tables otherwise you will print only the current scope table. Finally, ‘S’ is for entering into a new scope and ‘E’ is for exiting the current scope. You should also check the sample input file.
5 Output
Check the sample output file.
6 Important Notes
Please try to follow the instructions listed below while implementing your assignment:
• Implement using C++ programming language
• Avoid hard coding
• Use dynamic memory allocation
• Try to get accustomed to a Linux platform
7 Rules
• You have to submit all your source codes via Moodle. All the file name will be in following format
<your 7 digit student id>_<additional name>
For example, the submitted file name would look like 1605001_symboltable.cpp if it is submitted by a student having 1605001 as student id. Put all your source files in a folder (evenifyouputallyourcodesinonlyonefile)namedafteryour7digitstudentidandcreate a zipped archive of the folder. Then submit the zipped file in Moodle. Any compression format other than .zip will not be accepted.
• There will be an online assignment based on the offline during evaluation.