Semantic Analysis

A context-free grammar captures nesting and precedence but is provably too weak to express constraints like "every used identifier must appear in some enclosing declaration," because that requires unbounded matching across arbitrary tree distance — the kind of cross-referencing that pushes a language outside the context-free class. Semantic analysis is the compiler phase that supplies this missing power, checking context-sensitive properties by traversing the AST and consulting auxiliary state built during the traversal itself. The formal machinery is the attribute grammar: a grammar where each production is annotated with rules for computing values, called attributes, at the parse-tree nodes it introduces. Attributes come in two flavors. A synthesized attribute at a node is computed purely from the attributes of that node's children (and the node's own local information) — information flows up the tree, exactly like evaluating an expression bottom-up. An inherited attribute at a node is computed from the attributes of its parent and/or siblings — information flows down or sideways, exactly like propagating "what scope am I in" from an enclosing block down to its statements. A grammar using only synthesized attributes is called S-attributed; one using both is L-attributed if the inherited attributes of each symbol depend only on attributes of symbols to its left in the production plus inherited attributes of the parent, which is precisely the restriction that makes single-pass, left-to-right evaluation possible during parsing or in one AST traversal. Two families of context-sensitive check dominate this phase. Declaration and scope analysis builds and threads a symbol table, mapping each identifier to a declaration record (kind, type, storage class, scope) and resolving every use to the innermost enclosing matching declaration, following the language's scoping rules (lexical/static or, less commonly, dynamic). Type analysis — often split out as a distinct, heavier phase called Type Checking in Compilers — assigns a type to every expression and checks that operators, assignments, and calls receive operands of compatible type. Other checks live in this same phase by convention: multiple-declaration detection, use-before-definition, break/continue outside a loop, return-type consistency, and definite-assignment analysis. All of these share the same computational signature: a fact computed at one AST position depends on facts computed elsewhere, and semantic analysis is the discipline of scheduling and computing those facts correctly.

The standard implementation strategy is a single depth-first traversal of the AST, interleaving three kinds of work at each node: (1) consult inherited attributes and the symbol table state handed down from the parent, (2) recurse into children, (3) synthesize this node's own attributes (and any checks) from the children's results, and — if this node introduces a new scope or declaration — update the symbol table before or after the recursive calls as appropriate. The mechanics of scope tracking follow a stack discipline. Entering a block pushes a fresh scope; every declaration inside it inserts a binding into that scope's table; every identifier reference looks up the innermost scope first, falling through enclosing scopes outward (this is exactly a stack of hash tables, searched from the top down); leaving the block pops the scope, discarding its bindings so they are invisible outside. ``` // Attribute records carried through the traversal record ScopeTable { parent : ScopeTable or null // enclosing scope, for fallthrough lookup bindings : map // symbols declared directly in this scope } record DeclInfo { kind, type, line_declared } // Global (mutable) traversal state current_scope : ScopeTable // starts as the single global scope function ANALYZE(node, current_scope): switch node.kind: case Program: current_scope = new ScopeTable(parent = null) for stmt in node.statements: ANALYZE(stmt, current_scope) return // no attribute to synthesize upward case Block: // Inherited attribute: the enclosing scope, passed in as current_scope inner_scope = new ScopeTable(parent = current_scope) for stmt in node.statements: ANALYZE(stmt, inner_scope) // inner_scope discarded here: scope ends, bindings vanish return case VarDecl(name, typeAnnotation, initExpr): if name in current_scope.bindings: report_error("redeclaration of " + name, node.line) else: if initExpr != null: ANALYZE(initExpr, current_scope) // synthesize initExpr.type check_assignable(typeAnnotation, initExpr.type, node.line) current_scope.bindings[name] = DeclInfo(kind=VAR, type=typeAnnotation, line_declared=node.line) return case Assign(target, expr): ANALYZE(target, current_scope) // resolves target, synthesizes target.type ANALYZE(expr, current_scope) // synthesizes expr.type check_assignable(target.type, expr.type, node.line) return case Identifier(name): decl = LOOKUP(name, current_scope) if decl == null: report_error("undeclared identifier " + name, node.line) node.type = ERROR_TYPE // synthesized attribute else: node.type = decl.type // synthesized attribute node.decl = decl // resolution, used by codegen return case BinOp(op, left, right): ANALYZE(left, current_scope) ANALYZE(right, current_scope) node.type = check_op_types(op, left.type, right.type, node.line) // synthesized return case Call(name, args): decl = LOOKUP(name, current_scope) for a in args: ANALYZE(a, current_scope) if decl == null or decl.kind != FUNC: report_error(name + " is not callable", node.line) node.type = ERROR_TYPE else: check_arity_and_types(decl.paramTypes, args, node.line) node.type = decl.returnType // synthesized function LOOKUP(name, scope): s = scope while s != null: if name in s.bindings: return s.bindings[name] s = s.parent return null ``` Two design choices in this pseudocode are worth naming explicitly. First, `current_scope` is an inherited attribute: `Block` receives it from its parent and constructs a child scope to hand to its own children — information travels downward. Second, `node.type` on `Identifier`, `BinOp`, and `Call` is a synthesized attribute: it is computed after the children (or the lookup, which depends on the inherited scope) are done, and it flows back up to whatever expression contains this node. Most real semantic analyzers are exactly this: a single recursive traversal mixing both attribute flows, which is why the L-attributed restriction (inherited attributes depend only on the parent and left siblings) is what permits everything to be computed in one left-to-right pass rather than requiring multiple sweeps.

Time complexity. Each AST node is visited once, and the work done locally at a node — the switch dispatch, a constant number of type-compatibility checks — is O(1) excluding symbol table operations. A symbol lookup walks outward through nested scopes; in the worst case (deeply nested blocks) this is O(d) where d is nesting depth, but with hashed scope tables each individual scope lookup is expected O(1), and d is bounded by source nesting, which is small and effectively constant in practice, though pathological code can push it to O(n) in the number of statements. Declarations are O(1) amortized with a hash-table insert. Overall, semantic analysis runs in O(n) time for a program of n AST nodes under the standard assumption of O(1) amortized hash-table operations and bounded nesting depth; in the fully rigorous worst case with unbounded nesting it is O(n · d_max).

Space complexity. The symbol table stack holds at most O(n) bindings total (one per declaration), plus O(d_max) live scopes on the traversal call stack at any instant; total space is O(n).

Correctness argument. The traversal computes a well-defined result exactly when the attribute dependency structure is acyclic. Model each attribute instance (a specific attribute at a specific node) as a vertex, and draw an edge from attribute A to attribute B whenever B's computation rule reads A. A depth-first, left-to-right evaluation order correctly computes every attribute if and only if this dependency graph is a DAG — cycles would mean an attribute depends on itself, making no evaluation order valid. For an L-attributed grammar this acyclicity is guaranteed by construction: inherited attributes of a node only ever depend on the parent's inherited attributes and the synthesized attributes of strictly earlier siblings, and synthesized attributes only depend on children, so a single left-to-right, pre-order-then-post-order pass respects every dependency edge exactly once. This is why the recursive-descent style traversal in the pseudocode above is sound: `current_scope` (inherited) is always fully known before a child is visited, because it is constructed from the parent's own already-known scope; `node.type` (synthesized) is always computed after children return, because the recursive call finishes before the local computation runs. No node is ever asked for an attribute that has not yet been produced. Termination follows because the AST is a finite tree and each recursive call strictly decreases remaining subtree size.

Honest tradeoffs. A single-pass traversal is not always sufficient. Some languages permit forward references (a function calling another function declared later in the same file, or mutually recursive types), which require either a preliminary pass that only collects top-level declarations before the main analysis pass, or a two-pass symbol table construction. Enforcing this correctly is itself a common design decision: Pascal historically required forward declarations explicitly; C requires prototypes; many modern languages (Java, Python at module scope, Haskell) resolve top-level bindings independent of textual order via an upfront collection pass. This is precisely why real compilers often split semantic analysis into multiple sub-passes rather than one — a tradeoff between implementation simplicity (one pass, strict order dependence) and language expressiveness (multiple passes, forward references allowed).

Consider this snippet in a small C-like language: ``` int x = 5; { int y = x + 1; x = y; } z = 3; ``` Trace the traversal, showing the symbol table stack and every synthesized/inherited value as it is produced.

Two facts this trace makes visible. First, `x` resolves correctly from inside the block because lookup falls through from `S1` to its parent `S0` — this is the inherited scope attribute doing its job, and it is the mechanism that makes lexical scoping work at all. Second, `z` fails: even though `z = 3;` is syntactically indistinguishable in shape from `x = y;`, semantic analysis catches what parsing structurally cannot — that `z` was never declared anywhere in any enclosing scope. This is the entire point of the phase: the grammar accepted both assignments identically, and only the context-sensitive symbol-table check tells them apart.

Every production compiler front end — GCC, LLVM/Clang, javac, the Rust compiler, TypeScript's checker — implements a semantic analysis phase structurally identical to the one described here, even when the engineering is split across many internal passes for modularity. Integrated development environments rely on the same machinery running incrementally: as you type, the editor re-runs (a localized version of) scope resolution and basic checks to underline an undeclared variable in red before you ever compile. Linters and static analyzers reuse the identical symbol-resolution infrastructure to answer questions like "is this variable ever used" or "does this function's return type match its declared signature." Language servers implementing the Language Server Protocol expose "go to definition" and "find all references" directly from the identifier-resolution links built during semantic analysis — the `node.decl` pointer set in the pseudocode above is, essentially, what a "jump to definition" click follows. The two natural continuations of this phase are covered separately: the bookkeeping structure introduced here, the Symbol Table, and the far richer discipline of assigning and checking types, Type Checking in Compilers.

Ask the tutor: How would this traversal change if the language allowed function overloading, where a name's meaning depends on argument types resolved only after visiting the call's children?