Semantic Analysis: Scope Resolution, Symbol Tables, and Binding

Compilers Compilers 8 min read 1549 words Beginner ExcellentWiki Editorial Team

Semantic analysis is the phase of compilation that checks whether the source program conforms to the language’s semantic rules — beyond what the syntax (parsing) can verify. The parser ensures that the program has the right sequence of tokens according to the grammar. The semantic analyzer ensures that the program means something valid: variables are declared before use, operations receive operands of compatible types, functions are called with the right number and type of arguments, and language-specific rules (access control, uniqueness of declarations, etc.) are satisfied. This article covers the core data structures (symbol tables), scope resolution strategies, type checking integration, and common semantic analyses performed in production compilers.

The Symbol Table

The symbol table is the central data structure of semantic analysis. It maps identifiers (variable names, function names, type names) to their attributes (type, scope, memory location, constant value, etc.). The symbol table is built and queried as the compiler traverses the AST during semantic analysis.

Symbol Table Entry Structure

Each entry typically stores:

Name — the identifier string
Type — a pointer to the type representation (e.g., int, struct Foo, int (*)(char))
Kind — variable, function, parameter, type alias, module, etc.
Scope — the scope in which the declaration is visible
Attributes — const, static, inline, virtual, etc.
Location — source location for error reporting
Meta — alignment, storage class, linkage, initial value (if constant)

Implementation Strategies

Hash tables are the most common symbol table implementation. The identifier string is hashed to provide O(1) average lookup. C++’s std::unordered_map or a custom perfect hash (when the identifier set is known ahead of time) are common choices.

Trie-based symbol tables are used in some compilers (notably in the Erlang compiler). Tries support prefix matching, which is useful for autocomplete and refactoring tools.

Sorted arrays — for small scopes, a sorted vector (binary search) can be faster than a hash table due to cache locality.

Scoped Symbol Tables

A scope is a region of the program where a set of declarations is active. Scopes nest: inner scopes can access declarations in enclosing scopes, but not vice versa. The symbol table must support this nesting.

The standard implementation uses a scope stack. Each scope is a separate symbol table (hash table or map). When entering a scope (e.g., a function body, a block {}), a new table is pushed onto the stack. When exiting, it is popped. Name lookup searches from the top of the stack downward:

def lookup(name):
    for scope in scope_stack:
        if name in scope:
            return scope[name]
    raise UndefinedVariable(name)

Aggregate vs. Split Tables

Aggregate — one big hash table per scope with all identifiers. Simple but wastes space if many identifiers share the same prefix.

Split — separate tables for different kinds of identifiers. Clang, for instance, keeps DeclContext objects that separate types, values, and namespaces. This speeds up lookup because a context can answer “is there a type named X?” without considering variable names.

Scope Resolution

Scope resolution determines which declaration a name refers to. Different languages use different scoping rules:

Lexical (Static) Scoping

In lexical scoping, the scope of a declaration is determined by the program’s textual structure. An inner block can see declarations in enclosing blocks. Most modern languages (C, Java, Python, Rust) use lexical scoping.

int x = 1;     // global scope
void f() {
    int x = 2; // inner scope hides global x
    {
        int x = 3; // innermost scope
        // x refers to 3 here
    }
    // x refers to 2 here
---

Lexical scoping is implemented with the scope stack approach described above. The key operation is shadowing: an inner declaration with the same name as an outer declaration temporarily hides the outer one.

Dynamic Scoping

In dynamic scoping, the scope is determined by the call stack at runtime, not by the program’s textual structure. A function can access variables that were in scope at the call site but not at the definition site.

Dynamic scoping is used in early Lisp dialects, Emacs Lisp, and some shell languages. It is simpler to implement (just one global symbol table that gets updated on function entry/exit) but makes programs harder to reason about.

Name Mangling

Languages that support overloading (C++, Java, Rust) need to distinguish multiple declarations with the same name but different types. Name mangling encodes the type signature into the symbol name. For example, void foo(int) might be mangled to _Z3fooi (Itanium ABI) or ?foo@@YAXH@Z (MSVC ABI).

The symbol table stores the mangled name alongside the original name. The semantic analyzer uses the mangled name for uniquely identifying declarations.

Type Checking Integration

Type checking is closely integrated with semantic analysis. As the analyzer traverses the AST, it:

Looks up identifier references in the symbol table
Determines the types of expressions
Verifies that operators receive operands of compatible types
Checks assignment compatibility (rvalue type must be assignable to lvalue type)
Verifies function call arguments match parameter types

The details of type checking — including type inference, subtyping, and generic types — are covered in Type Checking.

Additional Semantic Checks

Beyond type checking and scope resolution, semantic analysis performs many language-specific checks:

Declaration Consistency

Duplicate declarations — a name cannot be declared twice in the same scope (unless overloading is allowed)
Forward declarations — verifying that a forward-declared entity is eventually defined
Linkage checks — ensuring consistent linkage specifications across translation units (C++ extern)

Control Flow Checks

Definite assignment — ensuring a variable is initialized before use. Java and C# enforce this at compile time
Reachability — checking that return statements cover all paths in non-void functions
Fallthrough — detecting accidental switch-case fallthrough (C++ warning, Rust error)

Access Control

Public/private/protected — verifying that accesses to members respect visibility
Friend declarations (C++) — allowing private access for specific external functions
Module visibility (C++20, Rust) — enforcing which declarations are visible across module boundaries

Language-Specific Rules

Rust’s borrow checker — verifying references do not outlive the data they point to
C++ constexpr — ensuring constexpr functions satisfy the rules for compile-time evaluation
Java’s checked exceptions — ensuring that thrown exceptions are caught or declared

Dependency Tracking for Incremental Compilation

Modern semantic analysis systems support incremental compilation by tracking dependencies between declarations. When a header file changes, the compiler must re-analyze only the translation units that depend on the changed declarations, not every file that includes the header.

Clang’s -fmodules feature caches the semantic analysis results (including symbol table and type information) for each module as a serialized AST. When a module is recompiled, dependent translation units automatically invalidate their cached results. The dependency graph tracks which declarations reference others — if foo.c uses struct Bar defined in bar.h, a dependency edge exists. When bar.h changes, only foo.c needs recompilation.

Rust’s incremental compilation goes further. The compiler tracks a fine-grained dependency graph where each function or method body is a separate compilation unit. Changing a function body only requires recompiling that function and its callers — not unrelated functions in the same module. The -Zincremental flag enables this, with compilation artifacts cached in the target directory.

Semantic Analysis in Production Compilers

GCC

GCC’s semantic analysis is spread across the frontend. The C and C++ frontends perform name lookup, overload resolution, and type checking during parsing. The symbol table is managed by cxx_binding objects linked to cp_scope chains. Overload resolution in GCC’s C++ frontend is particularly complex, involving partial ordering of templates and argument-dependent lookup (ADL).

Clang

Clang performs semantic analysis incrementally during parsing. Its Sema class manages over 200 semantic actions triggered by parser callbacks. Each action (e.g., ActOnCallExpr, ActOnDeclarator) performs the relevant semantic checks and builds annotated AST nodes. Clang’s design prioritizes clear error messages — most semantic actions produce detailed diagnostics about what went wrong and why.

Rust

Rust’s semantic analysis is performed by several passes in the compiler: name resolution (which resolves path-based names), type checking (using Hindley-Milner inference with subtyping for lifetimes), and the borrow checker (which verifies memory safety). The symbol table is managed by the NameResolver pass, which populates DefId maps that the rest of the compiler queries.

FAQ

What happens if semantic analysis fails? The compiler reports errors and stops before code generation. Semantic errors are fatal in most compilers — generating code for a semantically invalid program could produce incorrect or unsafe executables.

How does a symbol table handle nested scopes? With a stack of tables. Each scope pushes a new table; lookups traverse the stack from top to bottom. Inner scopes shadow outer declarations.

What is the difference between a symbol and an identifier? An identifier is the textual name. A symbol is the semantic entity that the name refers to — it includes the identifier plus all attributes (type, scope, kind, etc.). Multiple identifiers can refer to the same symbol (aliasing).

How does name mangling affect the symbol table? The symbol table stores both the original (unmangled) name and the mangled name. During semantic analysis, lookups use the original name. When generating code, the mangled name is used for external linkage to ensure uniqueness across translation units.