Semantic Analysis and Type Checking

A syntactically valid program can still be garbage:

int foo() {
    return bar(x, x);   // bar? x? never declared
}
int main() {
    foo() + "hello";    // int + char* ?
    return;             // missing value in int-returning function
}

None of these are syntax errors — the grammar accepts them. They are semantic errors, and catching them is the job of semantic analysis. Semantic analysis walks the AST produced by the parser, builds supporting data structures, and either annotates the AST with type information or rejects the program with meaningful diagnostics.

The output — a typed AST — is what every downstream phase (IR generation, optimization) can trust. Without it, code generation would have to guess sizes, calling conventions, and memory layouts.

A symbol table maps names to their declarations (type, storage class, visibility). Because scoping rules vary across languages, the table is typically a stack of scopes rather than a flat map.

class Scope:
    def __init__(self, parent=None):
        self.parent = parent
        self.table: dict[str, Symbol] = {}

    def define(self, name: str, sym: Symbol):
        self.table[name] = sym

    def resolve(self, name: str) -> Symbol:
        if name in self.table:
            return self.table[name]
        if self.parent:
            return self.parent.resolve(name)  # walk up
        raise SemanticError(f"Undefined: {name}")

Entering a block ({) pushes a new scope; exiting (}) pops it. Function parameters go into the function's scope. resolve walks up the chain, implementing lexical scoping (inner names shadow outer ones). Closures require a persistent reference to the enclosing scope even after the enclosing function returns.

Name resolution binds each identifier use to its declaration. The order matters:

• Single-pass languages (older C): a name must be declared before it is used. Forward declarations (int foo(int);) exist specifically to break cycles.
• Two-pass languages (Java, most modern languages): the compiler makes a first pass to collect all declarations into the symbol table, then a second pass to resolve uses. Classes can call each other's methods without forward declarations.
• Mutual recursion across files: linker symbols handle the final binding, but the compiler needs at least a type signature to type-check the call site.

C++'s name resolution is notoriously complex: dependent names in templates, ADL (argument-dependent lookup), and using directives interact in ways that require multiple disambiguation passes. This is a primary reason C++ compile times are so long.

Two broad approaches to assigning types to expressions:

Hindley-Milner (HM) is the classic inference algorithm: assign a fresh type variable $\tau_i$ to each expression, emit constraints ($\tau_1 = \tau_2 \to \tau_3$), then unify. If unification succeeds, the principal (most general) type is inferred. HM is the basis of ML, Haskell, and OCaml's type systems.

Rust adds lifetimes and ownership on top of HM, making inference undecidable in the general case — the compiler uses a fixed-point iteration (borrow checker) instead.

Unification takes two type expressions and finds a substitution $\sigma$ that makes them equal. It's a recursive algorithm:

unify(Int, Int)         -> {} (trivially)
unify(a, Int)           -> {a := Int}
unify(a -> b, Int -> c) -> unify(a,Int) ∪ unify(b,c)
                        -> {a := Int, b := c}
unify(Int, Bool)        -> FAIL (type error)
unify(a, List[a])       -> FAIL (occurs check: a inside itself)

The occurs check prevents infinite types: unifying $a$ with $\text{List}[a]$ would produce $\text{List}[\text{List}[\text{List}[\dots]]]$. Most Haskell compilers skip the occurs check by default for performance, accepting a tiny class of programs with infinite types. Unification is $O(n \cdot \alpha(n))$ with union-find, where $\alpha$ is the inverse Ackermann function — effectively constant.

A concrete list of errors that are syntactically valid but semantically wrong:

• Undefined name: return x; when x is not declared in scope.
• Type mismatch: int x = "hello"; — assigning char* to int.
• Arity mismatch: foo(1, 2) when foo takes one argument.
• Return type mismatch: int f() { return true; } — boolean vs. int.
• Use before initialization: int x; return x; (C: undefined behavior; Rust: compile error).
• Duplicate declaration: int x; int x; in the same scope.
• Break outside loop: break; at file scope.
• Non-constant array size in C89: int arr[n]; where n is a variable.

Each requires context (symbol table, current scope, current function's return type) that a context-free grammar cannot encode. That's why semantic analysis is a separate phase.

After name resolution and type checking, the AST is annotated with types. In practice this means every expression node carries a type field:

@dataclass
class BinOpNode:
    op: str
    left: Expr
    right: Expr
    type: Type = None   # filled in by type checker

# Type checking a binary +
def check_binop(node: BinOpNode, scope: Scope) -> Type:
    lt = check_expr(node.left,  scope)
    rt = check_expr(node.right, scope)
    if lt != rt:
        raise TypeError(f"Cannot add {lt} and {rt}")
    node.type = lt      # annotate in place
    return lt

The typed AST is the contract between front-end and back-end. IR generation can call node.type.size_bytes() to know how many bytes to allocate, which calling convention to use, and whether an implicit integer promotion is needed. Implicit coercions (C's usual arithmetic conversions) are often made explicit as CastNode insertions during this phase.

Languages with overloading (C++, Java) add a resolution step on top of type checking: given a call f(1, 2.0), which f among f(int, int), f(double, double), f(int, double) is the best match?

C++ resolution rules:

1. Build the candidate set: all f declarations visible at the call site (including via ADL).
2. Build the viable set: candidates where arguments are convertible to parameters.
3. Pick the best viable function by ranking implicit conversions (exact match > promotion > standard conversion > user-defined conversion).
4. If there's a tie: ambiguous call, compile error.

This is expensive. Clang's overload resolution runs in $O(c \cdot a)$ where $c$ is candidates and $a$ is arguments, with complex tie-breaking logic. Virtual dispatch (runtime polymorphism) is resolved not here but at the call site via a vtable pointer — a topic for the IR phase.

At the end of semantic analysis, the front-end hands the back-end:

• A typed AST with every expression node annotated with its concrete type.
• A symbol table (or its information embedded in AST nodes) giving storage class, linkage, and offset for every variable.
• Implicit cast nodes inserted where the language requires arithmetic promotions.
• Constant-folded literals where the front-end does early evaluation (sizeof(int) → 4).
• A list of diagnostics — zero if the program is accepted.

Modern compilers (Clang, GCC, Rust) keep the typed AST in memory and feed it directly to IR lowering. Some (older GCC) serialized it to a .gcov intermediate file. The key invariant: the IR generator must never need to re-examine source text or re-resolve a name — the typed AST is a complete, self-contained program representation.