CS362 2011F Compilers

Project, Phase 3: Symbol Table

As our book suggests, most compilers use a symbol table to keep track of our knowledge about the symbols we have seen in the program. For example, we might associate a type with an identifier for type checking. Similarly, we might associate a memory location with a named variable or parameter for code generation.

For a statically scoped language, like Pascal, the symbol table must also keep track of scope - the same identifier can have a different meaning at different points in the program.

For this assignment, you should implement a symbol table for your parser.

You should define a type, SymTab, and implement the following functions.

SymTab *symtab_new ()
Allocate space for and initialize a new symbol table.
void symtab_free (SymTab *stab)
Free the space allocated to a symbol table.
int symtab_enter (SymTab *stab)
Enter a new scope. Returns true (1) if it succeeds and false (0) if it fails.
int symtab_exit (SymTab *stab)
Exit the scope most recently entered.
int symtab_put (SymTab *stab, char *sym, AttributeSet *attributes)
Add a symbol and its attributes to the table. Makes a copy of sym. Returns true (1) if it succeeds and false (0) otherwise.
int symtab_update (SymTab *stab, char *sym, char *attname, Attribute attval)
Update the value of one attribute of a symbol. That attribute must already be associated with the symbol. Returns true (1) if it succeeds and false (0) otherwise.
AttributeSet *symtab_get (SymTab *stab, char *sym)
Get the attributes associated with symbol, using normal scoping rules. Returns NULL if the symbol is not in the table.
int symtab_is_in_scope (SymTab *stab, char *sym)
Determine if the symbol has been declared in the current scope.
int symtab_is_declared (SymTab *stab, char *sym)
Determine if the symbol has been declared at some point - in the current scope, in an enclosing scope, at the top level, etc.

Note that there are many ways to implement a symbol table. Two obvious ones are (a) a stack of (symbol,attribute set) pairs with special elements to represent the start of a new scope; (b) a stack of hash tables with each scope represented by a separate hash table. The former is easier to implement, while the latter is likely to be faster.

As you know, there are a variety of ways to implement stacks. You can link nodes together, or you can use a dynamic array. I will admit a slight preference for dynamic arras.

Submitting Your Work

Please submit a tarball of your work on P'Web. Your tarball should include everything necessary to explore your code, including

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Sun Nov 20 22:32:12 2011.
The source to the document was last modified on Wed Nov 2 13:22:16 2011.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2011F/Handouts/phase-3.html.

Samuel A. Rebelsky, rebelsky@grinnell.edu