Symbol Table Assignment

Symbol Table Routines (Part 1 of 7)

Date Assigned: 2/2/07
Date Due: 2/16/07
Points: 50 pts

The following symbol table specifications presume the use of pcc07defines.h which is a header file containing a number of user-defined types that will be used throughout our compiler project. You must include this file with all subsequent compiler code. DO NOT MODIFY THIS FILE AT ANY TIME. If a new version of this file is needed, I will make the modifications and tell you where you can get the file.

In CS300 we discussed the concept of hash tables to include hash functions and collision handling techniques. While this discussion was not exhaustive, it was inclusive enough to allow you to code up an efficient solution to the following problem.

Problem: You are to implement the Symbol Table (ST) module and the Error Handler (ER) module for your compiler. Below are specifications of the routines to be written.

1) Write ST routines to:

Search for a given name in the ST - accepts an identifier and returns a pointer to the ST entry if found or NULL
Add a new name to the ST - accepts as parameters all entry fields and adds the symbol to ST
Delete all entries on the current level - accepts no parameters and deletes all ST entries on the current level
Print the contents of the ST sorted alphabetically increasing

2) Each entry is to consist minmally of the following fields:

the identifier (<= 32 characters including the NULL character)
the integer level at which the id was declared which is of type SymbolTableLevel
the type which is of type SymbolTableType
an integer miscellaneous field (address field) with the following uses:
- for variables, the stack address where it is stored
- for reserved words, the particular reserved word which is of type ReservedWord
- for function names, their first quad
an integer field for array dimensions and procedure param count

3) The organization of your ST must:

use a hash table data structure with chaining as the collision handling technique
use a hash method that is efficient yet effective
be able to handle as many symbols as there is memory

4) Testing your routines

To test your routines, write a driver as follows:
1. Add all reserved words to the table (main, int, if, else, return, for, input, output)
2. Loop through a command file where the commands are of the form: 'c string' where c is a command code and string is optional on some commands
  - A = accepts as parameters all entry fields and adds the symbol to ST. Level will be a globally defined integer
  - L = increment the global level counter (initialized by your driver to 0)
  - D = accepts no arguments and removes all entries at the current level and then decrement level
  - S = accepts an identifier and searches for the identifier in the table. If the entry is found, output all fields for that entry, else output Symbol Not Found
  - P = print entire ST

5) Results

I will want to see the results from executing the following commands:

     P
     S firstid
     A firstid
     A secondid
     P
     L
     A thirdid
     P
     D
     P
     S thirdid
     S firstid
     S main
     D
     P

Note1: For this assignment and all subsequent assignments, you must use the make facility and version control to manage your programs. To compile and create your executable pcc (pacific c compler), I will simply type: (1) tar xfz user.tar.gz, (2) cd user, (3) make and (4) pcc testfile.c . The user in this case is simply your last name. If your program compiles successfully, then the executable pcc will be made. Not using make will be the same as turning in a program that does not compile in which case you will automatically lose 70% of the assignment points. Further, I will only test your program in the following way: pcc testfile.c This will run your program and accept the input file testfile.c and print out the results asked for above.

Note2: Turn in the following source code in this order:

makefile
symbol table header file
symbol table source file
error handler header file
error handler source file
driver
test results for the above example

Note3: The column headings for your symbol table output is to be (not including the numeric row):

123456789012345678901234567890123456789012345678901234567890123456789012345678

       
                            S Y M B O L   T A B L E
                      Identifier   Level   Type   Address   Other
------------------------------------------------------------------------------

Note4: Every time a print command is executed, print the above three lines followed by the symbol information right justified in the above columns exactly as shown above. Print each symbol on a line by itself with no blank lines between any two symbols in a single symbol table printout.

Note5: For this assignment, set undefined fields to -1.

Note6: Your project is to be set up similar to the makeex2.tar.gz example.

Note7: You will notice that I want you to print out source code for the error handler. While I will not test any error conditions in this first part, you should create the error module and the functions to handle identifying errors. The error handler is to identify the line number and first error encountered. You can simulate the line number by incrementing a counter each time a new command is read.

Note8: I will tell you next week exactly how I want your tarred up file to be submitted.

Douglas J. Ryan / ryandj@pacificu.edu