The symbol table accumulates information about all the identifiers in a source text. For most languages, the number of "enter into symbol table" operations is much smaller than the number of "lookup this identifier" operations. Choose your data structure accordingly. (A linked list is not a good choice, since looking up items requires much pointer traversal.)
Following are the minimal public interface functions to the symbol table. In several cases, the functions return a pointer to an Item structure containing a type and union value. This is a convenient way to return both an error code (in the type field) and an error message (in the str field of the union) at the same time. The parser can check the error code and print the error message if needed. See the sample code for semantic actions to see how some of these functions are used.
See the sample code for semantic actions to see how some of these functions are used.
Like the lexical analyser and the semantic expression value stack, the symbol table is a private data structure accessed only through function calls; the internal structure of the table must be kept hidden. It might be a table; it might be a list; it might be a binary tree. By hiding the structure, the programmer is free to change it without having to completely rewrite the compiler or interpreter.
Where a symbol table interface function returns a pointer to a symbol table element, treat that pointer the same way that you would treat the FILE* pointer returned by fopen(). That is, you can pass the returned pointer to other symbol table functions, but you must not directly access the fields in the structure from code that is not part of the symbol table. In particular, the Parser must not be looking "inside" the returned pointers to see fields in the symbol table. Write symbol table interface routines, taking the pointer, that return the values you need.
(A similar situation exists with the FILE* structure used by <stdio.h>. Though you can directly index this structure to find the integer unit number associated with an open file, the standard insists that you call the fileno() function instead. This hides the internal structure of the I/O library and makes the code more portable.)
The symbol table manages all its own memory. If it needs to keep a string, it allocates storage and copies the string. Nothing except the symbol table functions must free memory returned by the symbol table functions. In particular, don't directly allocate or free any symbol table memory in the parser. Call symbol table functions to do the necessary work.
Ian D. Allen CST 8152 Home Page