CSE411: Introduction to Compilers

Symbol Table

Jooyong Yi (UNIST)

Proof Tree

------------------------   ------------------------
 [x:int][y:int] ⊢ y:int     [x:int][y:int] ⊢ x:int
-------------------------------------------------------
                 [x:int][y:int] ⊢ (y = x;): unit
               ----------------------------------
                 [x:int] ⊢ (int y; y = x;): unit
               -----------------------------------
                   ⊢ (int x; int y; y = x;): unit

Symbol Table

------------------------   ------------------------
 [x:int][y:int] ⊢ y:int     [x:int][y:int] ⊢ x:int           # [x:int][y:int]: symbol table
-------------------------------------------------------
                 [x:int][y:int] ⊢ (y = x;): unit
               ----------------------------------
                 [x:int] ⊢ (int y; y = x;): unit
               -----------------------------------
                   ⊢ (int x; int y; y = x;): unit

Environment

• A mapping from identifiers to their associated information such as type.

• A symbol table is an implementation of environment used by a compiler.

Name Resolution

int x = 10;

void foo() {
  boolean x = true;

  {
    boolean b = x; // which x does this refer to?
  }
}

• The symbol table: "x" in "boolean b = x;" --> "boolean x = true;"
• Q: What if we do not have a symbol table?