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.