Semanticsimplementation

The Symbol Table

Name to declaration to type to scope. `x` is a local variable of type `int` in the block starting at line 12; `foo` is a function of type `(int) -> bool` at file scope. It is a hash map with a scope discipline, and every name-related question a compiler or an editor answers is a query against it.

The question

Where does a compiler keep what it knows about every name, and how does it find the right one?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

A mapping from a name, in a scope, to everything known about the entity that name denotes: what kind of thing it is, where it was declared, its type, its mutability, its storage class, and — later — where it lives at runtime. The AST says the identifier x appears here; the symbol table says which x, and that is the question the tree cannot answer because the answer is not in the subtree.

What this phase may assume or do

A symbol table lookup is meaningful only under a fixed scope discipline: the set of scopes visible at a program point must be determined before any lookup at that point, and a lookup must consult them in a defined order. A compiler may assume that inserting a declaration into a scope makes it visible to exactly the region the language specifies — no earlier, unless the language hoists; no later, unless the language allows forward reference. Where those two assumptions differ from the language, every resolution is wrong in the same direction, which makes the bug systematic rather than sporadic.

Key points

An entry maps a name to everything known about the entity: kind, declaration site, type, and later its storage and linkage.
The structure is a hash map with interned names; the compiler-specific part is the scope discipline layered over it.
Lookup finds the innermost scope containing the name, which *is* the definition of shadowing.
Declaring checks only the current scope, which is why an inner block may reuse a name and the same block may not.
A stack of maps is right for a single-pass batch compiler; scopes addressed by id are required for editors, debuggers and incremental builds.
Many languages have several namespaces, and modelling one namespace where the language has several produces spurious redeclaration errors.

What an entry actually holds

targetThe storage column depends entirely on the target and its ABI. −8(%rbp) is x86-64 System V with a frame pointer; the same local is at a different offset with -fomit-frame-pointer, at an sp-relative offset on AArch64, and frequently in no memory location at all after register allocation. Nothing about the first four columns depends on a target; nothing about the fifth is portable.

The word "table" undersells it. An entry is not a type; it is everything the rest of the compiler will need to know about that entity, accumulated over several phases. Name resolution creates the entry and records the kind and the declaration site. Type checking fills in the type. Later phases add storage — stack slot, register, global address, capture index — and the backend adds the mangled symbol that the linker will see.

Because entries accumulate, they are usually a distinct data structure from the map: the map holds names, and points at declaration records that other phases keep filling in. That indirection is what lets a later phase annotate a declaration without touching the scope structure that found it.

Two entries, and which phase filled in each columntypical

Name	Kind	Type	Scope	Added later
`x`target	local variable	`int`	block at 12:3–18:1	stack slot −8(%rbp), or a register after allocation
`foo`	function	`(int) -> bool`	file / module scope	linkage, mangled symbol name, address after linking
`n`target	parameter	`int`	function body of `foo`	argument register or incoming stack offset per the ABI
`Point`	type	`struct { x: int, y: int }`	module scope	layout, size, alignment, field offsets
`MAX`	constant	`int`	module scope	the value itself, once const evaluation runs

It is a hash map, and the scope discipline is the interesting part

The core structure is the hash table from the data-structures domain: names are looked up far more often than they are inserted, and the lookup must be O(1) because it happens once per identifier in the program. Compilers usually intern names first — mapping each distinct string to a small integer once, at lexing time — so the map is keyed by integer, comparison is a machine word compare, and the string hashing happens exactly once per unique name in the file rather than once per occurrence.

The genuinely compiler-specific part is that lookup is not "find the key". It is "find the key in the innermost scope that has it", which means the structure has to model nesting. There are two mainstream designs and they are not equivalent.

A stack of maps: the classic scoped symbol table

1class ScopedSymbols {
2  private stack: Map<Symbol, Decl>[] = [new Map()]   // index 0 is global
3 
4  enterScope() { this.stack.push(new Map()) }
5  exitScope()  { this.stack.pop() }
6 
7  declare(name: Symbol, d: Decl): Decl | null {
8    const top = this.stack[this.stack.length - 1]
9    const existing = top.get(name)
10    if (existing) return existing        // redeclaration in the SAME scope
11    top.set(name, d)
12    return null
13  }
14 
15  lookup(name: Symbol): Decl | undefined {
16    for (let i = this.stack.length - 1; i >= 0; i--) {
17      const hit = this.stack[i].get(name)
18      if (hit) return hit                // innermost wins: this is shadowing
19    }
20    return undefined
21  }
22}

Three lines carry the whole semantics. declare checking only the top map is why redeclaring in an inner block is legal and redeclaring in the same block is not. lookup walking from the top down is why the innermost binding wins, which is [[shadowing]]. And exitScope discarding the map is why a block-local name is invisible afterwards — the binding is not deleted, the whole scope is.

A stack of maps, or one map with scope ids

The stack-of-maps design above is the textbook one, and it is the right choice for a batch compiler doing a single ordered walk. Its cost is that a scope ceases to exist when you leave it, which is fine if nothing will ever ask about that scope again — and fatal if something will.

Something will. An editor asks "what is in scope at line 42" long after the walk that built line 42's scope has finished. A debugger asks the same question about a program counter. An incremental compiler wants to reuse a scope that did not change. All three need scopes to be *persistent objects with identity*, not stack frames.

The alternative is one flat map keyed by (scope id, name), plus a parent pointer per scope. Lookup walks the scope chain by id instead of walking a stack, so it costs the same; but every scope survives the walk, can be stored in a side table keyed by node id, and can be queried at any time from anywhere. This is what frontends that serve editors do, and it is the same "keep the structure addressable rather than transient" instinct that pushed [[ast-node-design]] toward arena indices.

Two scoped symbol table designstypical

	Stack of maps	One map + scope ids
Lookup	Walk the stack from the top	Walk the scope chain by parent id
Cost of lookup	O(depth) map probes	O(depth) map probes — the same
After the walk	Scopes are gone	Every scope still addressable by id
"What is in scope at line 42?"	Re-walk the file to that point	One lookup of the scope id at that node
Memory	Only the active chain	Every scope in the file, for the whole session
Fits	Batch compilers, interpreters, teaching implementations	Language servers, incremental compilers, debug info generation

One table, or several namespaces

A detail that surprises people the first time: many languages have more than one namespace, so Point the type and Point the constructor function can coexist, and struct stat and the function stat are different entities in C. That means either several maps per scope keyed by namespace, or one map whose key includes the namespace.

Getting this wrong produces a distinctive bug. If the compiler uses a single namespace where the language has several, a program that is legal — a type and a variable sharing a name — is rejected with a confusing redeclaration error. If it uses several where the language has one, two genuinely conflicting declarations both succeed and one silently wins at every use site.

The same question extends to overloads. In a language with [[ad-hoc-polymorphism]], a name does not map to *a* declaration but to a set of them, and picking the right one needs the argument types — which means resolution and type checking cannot be cleanly separated. That is a real cost of overloading, and it is paid in the symbol table's shape.

C: separate namespaces for ordinary identifiers, struct/union/enum tags, labels, and struct members.
Rust: separate type and value namespaces, so struct Foo; and fn Foo() do not collide, and a use may import from both at once.
Java: separate namespaces for types, variables, methods and packages — int String = 0; is legal and unwise.
A name with overloads maps to a *set* of declarations, and resolution needs argument types to choose — see [[name-resolution]].
Labels, in languages that have goto or labelled break, are a namespace with function-wide scope that ignores block nesting entirely.

How it works

The steps, in the order the compiler takes them.

Intern every identifier at lexing time so names are integers and comparison is a word compare.
Create a scope on entering a construct that introduces bindings — module, function, block, loop with a binding, comprehension.
Insert each declaration into the current scope, checking the current scope only for a duplicate.
Resolve a use by probing the innermost scope, then its parent, then upward until the name is found or the global scope is exhausted.
Record the resolved declaration on the identifier node, or in a side table keyed by node id, so nothing has to be looked up twice.
Fill in the entry as later phases learn more: the type from type checking, the storage from lowering and register allocation, the mangled name from the backend.
Either discard the scope on exit (stack design) or keep it addressable by id (persistent design), depending on whether anything will ask later.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

The declaration check consults every scope instead of just the current one, and a perfectly legal inner let x is rejected as a redeclaration. Users are told they cannot name a loop variable i because something upstream did.
A scope is entered but not exited on an error path, so bindings from inside a block remain visible afterwards. A variable declared inside an if resolves fine outside it, and the program compiles into something that reads uninitialised memory.
Names are compared as strings without interning, and resolution becomes the dominant cost in the frontend on a large file. The profile blames the hash function and the actual cause is that every occurrence re-hashes the same string.
Two namespaces are collapsed into one, and a program with a type and a function of the same name fails to build with "already defined" — valid code the user cannot fix without renaming.
The entry for a function is shared between two declarations with the same name in different modules, and calls in one module dispatch to the other module's definition. Everything links; the wrong code runs.
The compiler uses a stack of maps and the language server built on it re-parses the whole file to answer "what is in scope here". Completion latency grows with file size and nobody can point at a single slow function.

When it helps

Every name-related question in a compiler or an editor: resolution, go-to-definition, find-all-references, rename, completion, hover.
Producing precise diagnostics — "x is declared here but not initialised" needs both the use site and the declaration site, and only the table has both.
Generating debug information, which is largely a serialisation of the symbol table with scopes and storage locations attached.

When it hurts

Dynamic languages where names can be created at runtime. Python's globals()[name] = v and JavaScript's with defeat static tables entirely, and compilers for those languages fall back to runtime dictionary lookup for exactly the names they cannot classify.
Very large whole-program builds, where a global table becomes a memory and contention problem, and per-module tables plus an interface format are the scalable answer — see [[interface-files]].
Languages with rich overload resolution, where the table alone cannot answer "which declaration" and the whole resolution question becomes entangled with type inference.

What it costs

Every one of these is paid by something.

A hash map per scope buys O(1) lookup within a scope and costs an allocation for every scope entered — which, in a function with many small blocks, is many allocations, and is why some implementations use a single vector with markers instead.
Interning names buys word-sized keys and cheap comparison and costs a global intern table with its own concurrency story, which becomes contended in a parallel frontend.
Keeping every scope addressable buys editor and debugger queries and costs memory proportional to the whole file rather than the current path, held for the life of the session.
Storing resolution results on the node buys never resolving twice and costs a field or a side-table entry per identifier, in a structure with one entry per identifier occurrence in the program.
Separate namespaces buy the ability to reuse a name across kinds and cost a more complex key, more maps and a class of bugs where a lookup consults the wrong namespace and silently finds nothing.

What else you could do

What a different compiler or language does instead, and when that is better.

A persistent immutable map — a HAMT or a balanced tree — where entering a scope produces a new map sharing structure with the old. Lookup is one probe rather than a chain walk, the old scope stays valid, and you pay a slower insert and more allocation. Used by frontends that need snapshots at arbitrary points.
Association lists, as in small functional interpreters: a linked list of name-value pairs where entering a scope conses onto the front. Trivial to implement and O(n) lookup, which is fine for a teaching interpreter and nothing else.
De Bruijn indices, which eliminate names entirely by numbering how many binders outward a variable refers to. No table and no shadowing question at all; unreadable to humans, so anything user-facing must keep the names alongside for diagnostics.
Runtime dictionary lookup, as CPython does for globals and attributes. No static table needed, names can appear at any time, and every access costs a hash lookup — which is a large part of why dynamic attribute access is slow and why [[inline-caches]] exist.

See it for yourself

The flag, dump or tool that shows you this directly.

Python: symtable.symtable(src, "f.py", "exec") exposes CPython's own symbol table, including whether each name is local, global, free or a cell — the classification that decides which bytecode is emitted for every load.
C: objdump -t file.o or nm file.o shows the symbols that survived to the object file, which is the small subset of the table with external linkage.
Rust: rustc -Z unpretty=hir shows resolved paths; rust-analyzer's hover shows the resolved declaration for any identifier under the cursor.
Debug info: objdump --dwarf=info a.out or llvm-dwarfdump shows DW_TAG_lexical_block and DW_TAG_variable entries, which are the compiler's scope tree and symbol table serialised for the debugger.
Our scope and symbol-table viewer at /compilers/scopes steps the table as the walk enters and leaves each scope.

Plausible wrong readings

Stated the way a confident engineer states them.

"The symbol table maps names to types." It maps names to declarations. The type is one field, and it is not filled in until type checking runs — several passes after the entry exists.
"One table per program." One table per scope, arranged in a tree that mirrors the program's nesting. Flattening them is how block-local names leak.
"Lookup is O(1) because it is a hash map." Lookup within one scope is O(1); resolution walks the scope chain, so it is O(depth), which is why deeply nested code resolves marginally slower and why some compilers cache the answer on the node.
"Symbols in the compiler are the same symbols the linker sees." The linker sees only entities with external linkage, after mangling. Everything local — which is most of the table — never becomes a linker symbol at all.

Misconceptions

The claim, and what is actually true.

The symbol table is built once and read thereafter.

It is written by several phases. Resolution creates entries, type checking adds types, lowering adds storage, and the backend adds linkage — each entry accumulates over the whole compilation.

Shadowing is a special case the table has to handle.

Shadowing is what falls out of "return the first hit walking outward". It requires no special code; preventing it would.

If a name is not in the symbol table, the program is invalid.

In a dynamic language it may be created at runtime, and in a static language it may be in another module's interface. Absence from *this* table means "not resolved here", not "does not exist".

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

When the compiler meets the identifier x, it needs to know which x. The symbol table is the structure that answers: a map from names to declarations, one map per scope, arranged so that the innermost scope is consulted first. That single ordering rule gives you shadowing, gives you block-local variables, and gives you the error message when a name is not found anywhere.

practical

If names resolve wrongly, instrument the table rather than the resolver: log every scope enter and exit with its span, and every declare and lookup with the answer. Almost all resolution bugs are one of three things — a scope entered and not exited, a declaration inserted into the wrong scope (usually a collection pass that descended too far), or a lookup consulting the wrong namespace. All three are obvious in the log and invisible in the code.

advanced

The design question that separates a batch compiler from a language server is whether scopes are transient or addressable. A stack of maps is a beautiful fit for one ordered walk and a dead end for anything that must answer questions afterwards, because "what is in scope at this position" becomes "re-run the walk". Making scopes first-class objects with ids, stored in a side table keyed by AST node, costs memory for the whole file and turns that question into a single lookup. It is the same trade as arena-indexed AST nodes, made for the same reason, and a frontend that made one of those choices and not the other is usually mid-migration.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationCPython builds a symbol table in a dedicated pass and uses it to classify each name as local, global, free or cell, which determines whether the compiler emits LOAD_FAST, LOAD_GLOBAL or LOAD_DEREF. That classification is static; the *lookup* for globals and attributes remains a runtime dictionary probe. So the same language has a compile-time symbol table and a runtime name lookup, and confusing the two leads to wrong conclusions about why attribute access is slow.

typicalInterning identifiers is near-universal in production frontends (Clang's IdentifierTable, rustc's Symbol, V8's internalised strings) and absent from most teaching implementations, where string keys are used for clarity. If you are reading a compiler and names are strings, you are reading a small compiler or a slow one; the difference shows up on files with hundreds of thousands of identifier occurrences.

simplifiedOur table maps a name to exactly one declaration. Real tables for languages with overloading map a name to a candidate set and defer the choice to overload resolution, and tables for languages with imports must additionally model re-exports, glob imports and ambiguity — cases where a name resolves to several declarations and the language must define which, if any, wins.

If you were asked this in an interview

Sketch a scoped symbol table. Which line of it produces shadowing, and which line produces the redeclaration error?
What is the complexity of resolving a name, and what is it a function of?
Why would a language server not use a stack of maps?
A language allows a type and a function with the same name. What does that require of the table?

Connections

DSAhash-table hash-map stack n-ary-tree

Performancecpu-profiling

Domains that do not exist yet

Programming Languages & Runtime Internals — Runtime name lookup: dictionaries, property maps, hidden classes and inline caching
Names that cannot be resolved statically are resolved at runtime by a structurally similar map, and making that fast is a runtime problem. This lesson stops where the compiler stops knowing the answer.