Symbol Tables
Definition
Symbol table is a data structure that associates names with information about the objects that are denoted by the names.
Must be well organized:
- For fast lookup of symbols
- To reflect the organization of the program (block structure)
쉽게 생각하면, Lexicon = dictionary = symbol table.
Operations : insert / search / search-insert
Method of Organization
- Think of key-value dictionary.
- Linear, unsorted: Symbols are stored in an array; new symbols are inserted at the end.
- Linear, sorted: Symbols are stored in an array that is sorted.
- Hash table: typical hash table :: do you remember collision and rehash?
- Indexed Buckets: hashed with buckets / alphabetized buckets
- Tree of symbol table
- Stack symbol table
Tree and stack formats both have concepts of scoping: inheritance.
Speed
- Linear, unsorted: Insert O(1) Search O(n)
- Linear, sorted: Insert: O(n) Search(log n) binary search
- Hash table: Insert: O(1) Search(1)
Advantages
- Binary tree symbol tables have log n search time, so build AVL trees.
- Hash tables are super fast, don’t have to sort!
Disadvantages
- AVL tree is bit complicated.
- Hash Table is more complex, and hard to find hashing function, also complexity of rehashing.
Comparison
Be Able to select a method for a particular application.
Search is More Frequent than Insertion
Symbol Tables for Block-Structured Languages
Tree, Stack structure
What Things Are Put in Symbol Tables?
Symbols: statement labels, variables, constants, subprogram names
- Symbolic constants
- Enumerated types
- Subrange types
- Scalar types
- Variables
- Arrays
- Records
- Functions and procedures
- Labels
- Objects
Examples of Symbols in a Compiler
|variable|description|
|:———:|:—————:|
|link|link to next symbol|
|name string|name of symbol|
Deletion of Symbols
When it is needed
Relation to Table Organization Methods
Methods of Strong Identifier Names
User of Indirection or Auxiliary Table Structures
Citation:
- Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools
- UT Austin CS375: Compilers by G.Novak.