This assignment will give you more experience with C, particularly structs, pointers, and dynamic memory allocation. The resulting symbol table package is also something that we will use in the compiler project, with some minor additions and changes.
The package you are to implement is specified by the header file symtab.h,
which you should download and use for your project. Briefly, the header file
contains definitions for the symbol table data structure and individual entries
in it, and functions to initialize new symbol tables, add and find entries
in them, and delete the dynamic data associated with a symbol table when it
is no longer needed.
A symbol table should be implemented as an unbalanced binary search tree where
the string (symbol) values are used as the search keys in the tree. Two structures
are defined in symtab.h: symtab for the
symbol table, and symbol for a single node in the tree. For this
assignment, symtabs
just contain a pointer to the root of the tree (or NULL if there
are no entries in the table). Each symbol contains a pointer to
the string that is the key (and entry) for that node, and pointers to its children
in
the BST or NULL if a subtree is empty. Later in the compiler project
we will add some information to these structs, but this should suffice for
now.
When a new symbol is added to the table, a new symbol node should
be allocated for it, as well as a new array of characters to hold the symbol
(string). The
character array should only be as large as needed. The other operations defined
in the header that need to be implemented include searching for a string in
the table, initializing a new table (needed since C does not have constructors
like those
in C++ or
Java), and a delete operation to free all of the storage dynamically allocated
to a symbol table tree.
Use good programming style. The usual things apply: use meaningful names, comment appropriately, etc. Also be sure that if you declare any local functions in the symbol table implementation that they are hidden to client code outside the implementation. And be sure to watch for memory leaks - once a symbol table has been deleted, all dynamic memory allocated for that table by the symbol table operations should be properly recycled.
Test your symbol table package by creating suitable test programs and data.
Aside: A similar data structure is implemented as an example in Kernighan and Ritche's The C Programming Language. You will get the most out of this assignment if you try it first by yourself and treat that example as "the hint in the back of the book" if you do refer to it.
Turn in a copy of your C source files using this online turnin form.
Hand in the following: