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
SymTab *symtab_new ()
void symtab_free (SymTab *stab)
int symtab_enter (SymTab *stab)
int symtab_exit (SymTab *stab)
int symtab_put (SymTab *stab, char *sym, AttributeSet *attributes)
sym. Returns true (1) if it succeeds and false (0) otherwise.
int symtab_update (SymTab *stab, char *sym, char *attname, Attribute attval)
AttributeSet *symtab_get (SymTab *stab, char *sym)
NULLif the symbol is not in the table.
int symtab_is_in_scope (SymTab *stab, char *sym)
int symtab_is_declared (SymTab *stab, char *sym)
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
symtab.cfiles you create for this assignment.
attribute.cfrom a previous assignment.
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