Symbol Table Design

Date assigned: 1/11/00
Date Due: 1/14/00
Points: 25

This assignment involves designing in a high level notation the entire symbol table module. Further, this assignment is to be typed and include the following:

1) A data structures section (placed first in your design) to include all data structures used in implementing the symbol table module. Show the specific data structures in C and provide suitable explanation to the understanding and uses of/for these data structures. Also, each field of all structures and each variable is to be documented. Remember, the choices for data structures determines much of how your functions will be written. Major changes to data structures later on is a real pain!!

2) High level design of every function that will be used in the symbol table module. This must be a high level design and NOT CODE. Below is an example of the level of design that I'm looking for.

3) Every function must contain information on the parameters passed in/out along with the high level pseudo-code algorithm of the function. Also, include with each function a description of the purpose of the function.

The majority of your grade will be based on completeness and correctness. That is, are all routines making up the symbol table module present and correct.

For purposes of the design, assume that entries into the symbol table are of the form of the Sample Hand Assembly. Later changes should be minor and easy to implement if the design is good.

The symbol table needs to be able to:
1) Insert a symbol
2) Update a symbol
3) Search for a symbol
4) Print the symbol table sorted by name (alphabetically increasing)

You will most surely have other support routines for this module. Implement your symbol table using a hash table, the mid square hash function, and chaining for collision handling. Efficiency and speed are a very important part of this design. How you decide to do the sorting is up to you.

Grading will be in four areas:
1) Level of design: 6
2) Modularity: 5
3) Completeness/Correctness: 11
4) Presentation: 3

As an example, assume we are designing the stack module. We know that the operations on a stack include: FStkcreate, FStkisfull, FStkadd, FStkisempty, WStkdelete. So I will pick a possible data structure for the stack and then design the function FStkisfull.

My choice for a data structure is a structure that contains both the stack (an array of integers) and a top of stack pointer (also an integer). With this data structure I can just pass the structure in and out of the various functions that use it.

typedef struct
{
  int rgwStk[Maxstack];  // a stack of integers of size Maxstack
  int iuTop;             // integer top pointer 
} Stack;

/***********************************************************************************
bool FStkisfull(stack)  // IN: the stack of elements and top pointer

Purpose: This function returns TRUE if the stack is full; else FALSE is returned

/***********************************************************************************

  if(number of elements in stack == maximum number of elements)
    return TRUE
  else 
    return FALSE

One more function without the documentation to give you an idea of the level of algorithmic specification:

int WStkdelete(stack)
  if(FStkisempty(stack))
    return a value indicating no deletion occurred
  else
    remove and return the top stack element

To test your symbol table module, several datafiles consisting of lines of the form below will be run through your driver:

symbol value mode defbyset defbyentry

Each field is separated by exactly one space and rules for each field are as follows:

1) symbol - string up to 31 characters in length
2) value - signed integer value
3) mode - mode (absolute, relocatable, undefined external) of the symbol which is either: a, r, u
4) defbyset - a bool that is either True or False (1 or 0 in the file respectively)
5) defbyentry - a bool that is either True or False (1 or 0 in the file respectively)

A sample line would look like:

offset 40 a 1 0

Bring your typed up design to class on Friday morning by 9:00am. Anything after 9:05am will be considered late.