Project, Phase 3: Symbol Table

• Assigned: Friday, 28 October 2011
• Due: Monday, 7 November 2011

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

• The symtab.h and symtab.c files you create for this assignment.
• An updated version of attribute.h and attribute.c from a previous assignment.
• A set of unit tests for the symbol table. Your unit tests should verify that there are no memory leaks in your code.
• A Makefile that ties everything together.