Symbol Table Management

Assignment 1
CPTR 415 Compiler Construction

  1. Overview

    2. A symbol table is used by a compiler to keep track of information associated with identifiers. In this assignment you will implement a symbol table table package in C++. In a later assignment you will incorporate this symbol table package in your Decaf compiler.

  2. Requirements

    3. Your symbol table is to be implemented using a hash table. You may implement the hash table any way you want. For this assignment and for the Decaf compiler, you do not need to worry about representing identifiers from different scopes in the same symbol table. We will instead use different symbol tables to represent different scopes. Consequently, all identifiers in a symbol table will be unique.

    The hash table should support the following operations: 

             class SymbolTable {
	 public:
	    SymbolTable(int num_entries);
	    int lookup(const char *id);
	    bool insert(const char *id, int value);
	 };

    1. Creation. The symbol table class constructor creates a new symbol table object with the indicated number of hash table entries.
    2. Look up. The lookup() method returns the value associated with the key id. All valid keys should be positive, so return -1 the entry is not found. In your Decaf compiler, each symbol table entry will probably not be an integer, so it should be easy to modify your "not in symbol table" return value. Using #define to define a symbolic constant may be helpful.
    3. Insertion. The insert() method inserts an entry with key id and value value into the symbol table. When you incorporate the symbol table routines into your compiler, you will change the type of the value field, but for now it suffices for it to be an integer. Duplicate keys should not be inserted. Return false if an attempt is made to insert a duplicate key; otherwise, return true. id.

  3. Testing

    4. Your program will be tested against a set of test data. To facilitate the running of the tests, you should prepare a simple interpreter that reads the following commands:

    1. new symbol_table_name number_of_entries

      The new command takes two arguments: a string which is the name of the symbol table to be created and an integer which is the number of hash table entries in the symbol table. The new command should not print anything on the screen. You may assume that all symbol table names are unique.

    2. lookup symbol_table_name key

      The lookup command takes two arguments: a string which is the name of the symbol table to be used and a string which is the identifier to be looked up. The lookup command should either print the value of the integer associated with the identifier or -1 if the identifier cannot be located in the symbol table.

    3. insert symbol_table_name key value

      The insert command takes three arguments: a string which is the name of the symbol table to be used, a string which is the name of the identifier to be inserted, and an integer associated with that identifier. It should insert the identifier and its associated value into the symbol table unless the identifier is already in the table. If the identifier is already in the table, the following error message should be printed: 

      	       *** Error *** Identifier xxxx is already in the symbol table

      xxxx should be replaced with the name of the identifier. The insert command should not print anything on the screen unless there is an error.

    4. quit

      The quit command exits the program.

    Your interpreter should not print any prompt messages. A sample input session might look like: 

    	    new a 11
	    insert a widget 11
	    insert a gadget 45
	    insert a widget 8
	    *** Error *** Identifier widget in already in the symbol table
	    new b 21
	    insert b rose 1422
	    insert b widget 10
	    insert a total 4
	    lookup b rose
	    1422
	    lookup a widget
	    11
	    lookup b gadget
	    -1
	    lookup b widget
	    10 
	    quit

    (The error message and lines containing single integer values are printed by the interpreter; the other lines are entered in.)

  4. Assignment Submission and Grading

    5. You should do all your developement within a single directory. When you are ready to submit the assignment, create a directory named symbol_table_submission in your home directory. Copy all the files from your development directory into this submission directory. Provide a make file, so I need only run make and then execute your program. Remove all the object files and executable and ensure that make properly builds your project.

    Each method and function should have a comment block at the beginning detailing what that function accomplishes. If the function is non-trivial (e.g., your hash function), the comment block should briefly describe the algorithm used to implement the function or method.

    The possible number of points for this assignment is 10. Points are awarded as follows:

    Program behaves correctly 6
    Program builds flawlessly 1
    Source code is readable and well commented 1
    Program speed is within 30% of reference program 1
    Program speed is within 10% of reference program 1