Chapter 22 of 33

Symbol Table

When you read a long novel, you meet a character on page 12 and see their name again on page 300. To make sense of page 300 you need to remember who that person is: their role, their family, what they did. Many readers keep a little list of characters for exactly this reason.

A compiler has the same problem. A variable is declared on line 5 and used on line 500. When the compiler reaches line 500, it must know that the name is a variable, that its type is double, that it lives at offset 16 in the current function's frame, and that it belongs to this function and not to another one with the same name. All of that is kept in one central data structure.

A symbol table is a data structure used by the compiler to store information about every name (identifier) in the source program, such as its kind, type, scope and storage location. Every phase of the compiler can insert into it or look things up in it.

In this chapter we will see what goes into a symbol table, which phases use it and how, the operations it must support, the data structures that can implement it (and why hash tables win), and how nested scopes are handled. The scope examples were run with GCC, and the hash calculations and the scoped-table demo were run in Python.


What Is Stored in a Symbol Table

Each name gets an entry, a record with fields describing it. Which fields exist depends on what kind of name it is:

Field

Meaning

Example

Name (lexeme)

The identifier's spelling

count

Kind

Variable, constant, function, parameter, type name, label, ...

variable

Type

A type expression (see Semantic Analysis & Type Checking)

array(10, integer)

Scope / nesting level

Where the name is visible

level 1 (inside main)

Storage information

Offset in the activation record, or a static address; size (width)

offset 16, width 40

For functions

Number and types of parameters, return type, how parameters are passed

(char × integer) → integer

For arrays

Number of dimensions and their bounds

2 dimensions: 0..9, 0..19

For records

A pointer to a separate table of fields

fields x, y with their offsets

Other

Line of declaration, whether it was used, whether it is initialised

declared at line 7

Keywords such as if and while are often put into the symbol table too, before compilation starts, marked as reserved. Then the lexer can scan every word as an identifier and simply look it up: if the entry says "keyword", it returns the keyword token instead (see Input Buffering & Recognition of Tokens).

Storing the Names Themselves

Identifiers have different lengths. There are two ways to store them in the entries:

  • Fixed-length field: reserve, say, 32 characters in every entry. Simple, but wastes space for short names and limits the length of names.

  • Separate string table: store all names one after another in a big character array, and keep in each entry only a pointer (index) to the start of the name and its length. No waste, no length limit. This is what real compilers do.

String table:  c o u n t \0 i \0 t o t a l \0 ...
               0           6    8

Entries:   name → 0   kind: variable   type: int     ...
           name → 6   kind: variable   type: int     ...
           name → 8   kind: variable   type: double  ...

Who Uses the Symbol Table

The symbol table is not a phase; it sits beside all the phases, and each phase reads or writes the parts it cares about.

   source
     │
 ┌───▼──────────────┐
 │ Lexical analysis │──── enters identifiers (name) ──────────┐
 ├──────────────────┤                                          │
 │ Syntax analysis  │──── adds kind, structure ──────────┐     │
 ├──────────────────┤                                    │     │
 │ Semantic analysis│◄─── looks up types; adds types ──┐ │     │
 ├──────────────────┤                                  │ │     │
 │ Intermediate code│◄─── needs types, offsets ───┐    ▼ ▼     ▼
 ├──────────────────┤                             │  ┌──────────────┐
 │ Optimization     │◄─── needs scope, aliasing ──┼──│ SYMBOL TABLE │
 ├──────────────────┤                             │  └──────────────┘
 │ Code generation  │◄─── needs addresses, sizes ─┘
 └──────────────────┘

Phase

What it does with the symbol table

Lexical analysis

May create an entry for each new identifier and return a pointer to it as the token's attribute; looks up reserved words

Syntax analysis

Knows which names appear in declarations; in many compilers, the parser's actions create the entries

Semantic analysis

Records types and scopes; checks declare-before-use, duplicate declarations and type compatibility by lookups

Intermediate code generation

Uses types (to choose integer or float operations) and offsets (to generate addresses); enters compiler-generated temporaries

Code optimization

Uses information such as which variables are global, which may be aliased

Code generation

Uses storage addresses and sizes to produce real load/store instructions

A common exam question asks exactly when the symbol table is "created" or "used". The safe answer: it is built mainly during the analysis phases (lexical, syntax and semantic analysis) and used by all phases, including synthesis.


Operations

A symbol table needs only a few operations, but they are called extremely often: every occurrence of every name causes a lookup.

Operation

Purpose

Called when

insert(name, attributes)

Add a new entry

A declaration is processed

lookup(name)

Find the entry visible at this point, or report "not declared"

Every use of a name; also before insert, to detect redeclaration

enterScope()

Start a new, nested scope

Entering a block, function or class

exitScope()

Leave the current scope, hiding its names

Leaving a block, function or class

setAttribute / getAttribute

Update or read fields of an entry

Later phases add offsets, flags, etc.


Data Structures for a Symbol Table

Suppose a program has n distinct names, and the compiler performs e lookups in total (one per use). Usually e is much larger than n.

Linear List

Keep entries in an array or linked list, in order of insertion. Insert appends at the end (after a lookup to check for duplicates), and lookup scans from one end. If you scan from the most recent entry backwards, the newest declaration of a name is found first, which conveniently handles nested scopes.

Each lookup costs O(n) in the worst case, so the total work is O(n × (n + e)). Easy to write, but far too slow for programs with thousands of names.

Search Tree

Keep entries in a binary search tree ordered by name. Insert and lookup take O(log n) on average, but a plain BST degenerates into a list (O(n)) if names arrive in sorted order, which is common (a1, a2, a3, ...). A balanced tree (AVL, red-black) guarantees O(log n).

Hash Table

Use a hash function h(name) to compute a bucket number, and keep a short list (chain) of entries in each bucket. With a good hash function and enough buckets, each chain is short, so insert and lookup take O(1) on average. This is the structure almost every production compiler uses.

Let us hash a few names with a toy hash function: the sum of the ASCII codes of the characters, modulo 7 buckets.

Name

Sum of ASCII codes

Bucket (sum mod 7)

count

99+111+117+110+116 = 553

0

total

116+111+116+97+108 = 548

2

i

105

0

sum

115+117+109 = 341

5

x

120

1

temp

116+101+109+112 = 438

4

j

106

1

bucket 0 : count → i
bucket 1 : x → j
bucket 2 : total
bucket 3 : (empty)
bucket 4 : temp
bucket 5 : sum
bucket 6 : (empty)

count and i collide in bucket 0, as do x and j in bucket 1. With chaining, colliding entries simply share a linked list. To look up i, compute h("i") = 0 and compare only against the two names in bucket 0, instead of all seven names.

The sum-of-codes function is fine for a hand example but poor in practice: anagrams like ab and ba always collide. Real compilers use functions that mix the characters with multiplication, such as h = h × 31 + c for each character c, and a table size that grows as more names are added.

Comparison

Structure

Insert

Lookup

Pros

Cons

Linear list (unsorted)

O(1) to append (O(n) with duplicate check)

O(n)

Simplest; easy scope handling

Slow for large programs

Sorted array

O(n) (shifting)

O(log n) (binary search)

Fast lookup

Slow insert

Binary search tree

O(log n) average, O(n) worst

O(log n) average, O(n) worst

Names kept in sorted order

Can degenerate; balancing adds complexity

Hash table

O(1) average

O(1) average (O(n) worst)

Fastest in practice

Needs a good hash function; names not ordered


Handling Scopes

The same name can mean different things in different parts of a program:

#include <stdio.h>

int x = 10;                         /* global x */

void show(void) { printf("show: x = %d\n", x); }

void change(void) {
    int x = 20;                     /* local to change */
    show();
}

int main(void) {
    int x = 1;                      /* local to main */
    {
        int x = 2;                  /* inner block */
        printf("inner: x = %d\n", x);
    }
    printf("main:  x = %d\n", x);
    change();
    show();
    return 0;
}

Output (GCC):

inner: x = 2
main:  x = 1
show: x = 10
show: x = 10

C uses lexical (static) scoping with the most closely nested rule:

A use of a name refers to the declaration in the innermost enclosing scope (in the program text) that declares that name.

So inside the inner block, x is the one declared there (2). After the block ends, that declaration is gone and main's own x (1) is visible again. Inside show, the only x in the text around it is the global one (10), so show prints 10 even when called from change, where a local x = 20 exists. GCC even warns unused variable 'x' for that local, because nothing inside change ever reads it.

Under dynamic scoping (used by early Lisp dialects, and by variables declared with local in Perl and in Bash functions), a name refers to the most recent active declaration at run time. Then show() called from change() would print 20, and called directly from main() would print 1 (main's own x is the most recent active one). Static scoping is decided by the compiler from the text, which is why it fits naturally with a symbol table.

Approach 1: One Table per Scope, Chained

Create a new table for each scope, with a pointer to the table of the enclosing scope. lookup searches the current table and then follows the chain outward; insert always goes into the current table. On entering a block, create a table whose parent is the current one; on exit, go back to the parent.

class Scope:
    def __init__(self, parent=None, name="global"):
        self.table = {}          # name -> attributes (a hash table)
        self.parent = parent     # enclosing scope
        self.name = name
        self.level = 0 if parent is None else parent.level + 1

    def insert(self, name, **attrs):
        if name in self.table:                  # same scope: error
            raise NameError(f"redeclaration of '{name}' in scope {self.name}")
        self.table[name] = dict(attrs, level=self.level)

    def lookup(self, name):
        s = self
        while s is not None:                    # innermost scope first
            if name in s.table:
                return s.name, s.table[name]
            s = s.parent
        return None                             # undeclared

g = Scope()
g.insert("x", type="int")
g.insert("f", type="int -> void")
main = Scope(g, "main")
main.insert("x", type="float")
main.insert("y", type="int")
block = Scope(main, "main.block1")
block.insert("x", type="char")

for name in ["x", "y", "f", "z"]:
    print(f"lookup {name!r} from block1 ->", block.lookup(name))
print("lookup 'x' from main   ->", main.lookup("x"))
try:
    main.insert("y", type="double")
except NameError as e:
    print("error:", e)
lookup 'x' from block1 -> ('main.block1', {'type': 'char', 'level': 2})
lookup 'y' from block1 -> ('main', {'type': 'int', 'level': 1})
lookup 'f' from block1 -> ('global', {'type': 'int -> void', 'level': 0})
lookup 'z' from block1 -> None
lookup 'x' from main   -> ('main', {'type': 'float', 'level': 1})
error: redeclaration of 'y' in scope main

Notice the two different checks. A redeclaration is an error only if the name already exists in the same scope (so main may declare its own x even though there is a global x, but not a second y). A use searches all enclosing scopes, innermost first; returning None means "undeclared identifier".

          ┌───────────────┐
          │ global        │   x : int,  f : int → void
          └───────▲───────┘
                  │ parent
          ┌───────┴───────┐
          │ main          │   x : float,  y : int
          └───────▲───────┘
                  │ parent
          ┌───────┴───────┐
          │ main.block1   │   x : char          ← current scope
          └───────────────┘

A nice property: when a function's scope is finished, its table does not have to be destroyed. The compiler can keep it attached to the function's entry, which later phases (and debuggers) use. Records and classes also get their own tables in the same way, so p.x is looked up in the table of p's struct type.

Approach 2: One Hash Table with Scope Levels

Keep a single hash table. Each entry carries its nesting level, and new entries are put at the front of their bucket's chain, so the innermost declaration of a name is always found first. In addition, keep a stack of lists: each list links together the entries declared in one scope. On exitScope(), walk the top list and remove those entries from the hash table, then pop it.

Point

Table per scope (chained)

Single table with levels

Lookup cost

One hash lookup per enclosing scope (deep nesting costs more)

One hash lookup

Leaving a scope

O(1): just switch to the parent

Remove every entry of that scope

Keeping old scopes for later phases

Easy, tables survive

Entries are removed (must be copied out if needed)

Typical use

Most modern compilers; classes and records

Single-pass compilers, older designs


Solved Problems

Problem 1: Which Declaration?

1  int a = 5, b = 7;
2  void p(void) {
3      int a = 9;
4      {
5          int b = a + 1;
6          print(a, b);
7      }
8      print(a, b);
9  }

With static scoping, what does each print output when p is called?

Solution. Line 6 is inside the block of lines 4 to 7. b is declared there (line 5); a is not, so we go out one level to p, where a = 9. Line 5 computes b = 9 + 1 = 10. So line 6 prints 9 10. At line 8 the block has ended: a is p's (9) and b is now the global (7). It prints 9 7.

Problem 2: Static vs Dynamic Scoping

Using the C program from the Handling Scopes section, what would the four lines of output be under dynamic scoping?

Solution. The first two lines do not involve calls, so they stay inner: x = 2 and main: x = 1. When main calls change, which declares x = 20 and calls show, the most recent active x is change's: show prints 20. When main calls show directly, the most recent active x is main's (the inner block has ended): show prints 1. Under static scoping both calls print 10.

Problem 3: Hash Lookups

Using the 7-bucket table above, how many name comparisons are needed to look up j, and to find out that k is undeclared? Assume new entries were appended to the end of each chain.

Solution. h("j") = 106 mod 7 = 1. Bucket 1 holds x then j, so 2 comparisons. h("k") = 107 mod 7 = 2. Bucket 2 holds only total, so 1 comparison fails and k is reported as undeclared. A linear list of 7 names would need 7 comparisons for k.


Common Mistakes

  • Saying the symbol table is used only by the lexer or only by the parser. It is built mostly in the analysis phases and used by every phase.

  • Treating any repeated name as a redeclaration error. Redeclaration is an error only within the same scope; inner scopes may shadow outer names.

  • Looking up only the current scope. A use must search enclosing scopes outward until the name is found.

  • Confusing static and dynamic scoping in output questions. Static: follow the program text. Dynamic: follow the chain of active calls.

  • Claiming hash tables are O(1) in the worst case. They are O(1) on average; a bad hash function can put everything in one bucket.


Interview and Exam Questions

Q1. What is a symbol table and why does a compiler need one?

A data structure holding information about each identifier: kind, type, scope, storage location and more. Phases far apart in the program text and in the compiler pipeline need the same facts about a name, and the symbol table keeps them in one place with fast lookup.

Q2. Which data structure is most commonly used for a symbol table, and why?

A hash table with chaining, because insert and lookup take O(1) time on average, and the compiler performs a lookup for every occurrence of every name.

Q3. How are nested scopes handled?

Either by a separate table for each scope linked to its enclosing scope's table (lookup searches outward), or by a single hash table where new entries go to the front of chains and a stack records each scope's entries so they can be removed when the scope ends.

Q4. When is a duplicate declaration an error?

When the same name is declared twice in the same scope. Declaring it again in a nested scope is legal and hides the outer declaration.

Q5. Why store identifier names in a separate string table?

Identifiers vary in length; a separate character array with pointers from the entries wastes no space and imposes no length limit, unlike fixed-length name fields.

Q6. In which phase are entries for compiler-generated temporaries like t1, t2 added?

During intermediate code generation, when the temporaries are created (they may later get storage like any local variable).

Q7. What is the time complexity of n insertions and e lookups with an unsorted linear list?

Each operation may scan the whole list, so the total is O(n × (n + e)). With a hash table it is O(n + e) on average.


Summary

  • The symbol table stores, for every name: kind, type, scope level, storage (offset, size) and extra details for functions, arrays and records. Names are best kept in a separate string table.

  • It is built mostly during analysis and used by all phases.

  • Core operations: insert, lookup, enterScope, exitScope.

  • Implementations: linear list O(n) lookup, search tree O(log n) average, hash table O(1) average, which is the usual choice.

  • Static scoping uses the most closely nested rule; implement it with chained per-scope tables or one table with scope levels. Redeclaration is checked in the current scope only; lookups search outward.

We now know how the compiler understands names and types. The next step is to translate the checked program into a simpler, machine-independent form: Intermediate Code & Three-Address Code.