Semantic Analysis
The phase between "this parses" and "this means something". It resolves names, enforces scopes, checks types, and asks the control-flow questions the grammar could not express — every variable assigned before use, every path returning a value, no statement after a `return`.
What does a compiler check after parsing succeeds, and why could the parser not check it?
Input is a syntactically valid AST that asserts structure and nothing else. Output is the same tree with a symbol on every identifier and a type on every expression, plus the guarantee that the program is well-formed — [[annotated-ast]]. The representation exists to answer the questions a context-free grammar structurally cannot: whether a name refers to anything, whether it refers to the *right* thing, and whether the operations applied to it are defined.
Semantic analysis may assume the tree is grammatical, that every node kind is one the grammar can produce, and that spans are intact — the parser has already rejected everything else, and where it could not, it has left explicit error nodes that this phase must tolerate rather than crash on. It may assume nothing about names or types, since establishing those is its own job. What it produces, everything downstream is entitled to assume: an optimizer may take for granted that the program type-checked, because a program that did not would never have reached it. That entitlement is why an optimizer is allowed to reason from types at all.
Key points
- Every semantic check is about something *elsewhere* in the program, which is exactly what a context-free grammar cannot express.
- The five families are names, scopes, types, control flow and declaration context; a compiler error belongs to one of them, and knowing which locates the bug.
- Definite assignment, missing return and unreachable code are control-flow checks, not type checks, and need a CFG to be done properly.
- Declarations must be collected before uses are resolved, or forward references fail.
- Everything downstream is entitled to assume the program type-checked; that entitlement is what licenses type-based optimization.
- An error type that unifies with everything is what prevents one mistake from producing a page of messages.
What the grammar structurally cannot say
A context-free grammar can say that an assignment consists of a name, an equals sign and an expression. It cannot say that the name must have been declared, because "declared somewhere earlier in an enclosing scope" is not a property of the local shape of the input — it depends on unbounded context, which is exactly what "context-free" rules out. The classic result is that [[context-free-grammars]] cannot express declare-before-use for arbitrarily many distinct identifiers, and this is not an engineering limitation you can grammar your way around.
So the work is deferred to a separate phase that walks the tree with state. That phase is semantic analysis, and every check it performs has the same shape: something must be true that involves a part of the program *elsewhere*. The declaration is elsewhere. The function's parameter list is elsewhere. The other branch of the if that also has to return a value is elsewhere.
Deferring it is also a diagnostic decision, and a good one. A parser that tried to enforce declaration would have to stop at the first undeclared name; a separate phase can report all of them, plus the type errors, plus the unreachable code, in one run. That is [[diagnostic-quality]] bought by phase separation.
The five families of check
Semantic analysis is not one algorithm; it is a bundle of checks that happen to need the same walk and the same symbol table. They divide cleanly into five families, and knowing which family a compiler error belongs to tells you immediately where to look.
The control-flow family is the one people forget, and it is the one that catches real bugs. Definite assignment — has this variable been given a value on every path that reaches this use — is not a name question or a type question. Neither is "does every path through this function return a value", nor "is this statement reachable at all". All three are [[data-flow-framework]] problems solved on a [[control-flow-graph]], and in a compiler that has not built one yet they are solved by an ad-hoc tree walk that is subtly weaker.
| Family | Example check | Needs | Reports |
|---|---|---|---|
| Names | x refers to a declaration that exists | A symbol table and the scope rules | "cannot find value x in this scope" |
| Scopes | x is not declared twice in the same scope; the inner x shadows the outer | Nested scopes with a defined lookup order | "the name x is defined multiple times" |
| Types | + is defined for the operand types; the argument count matches | Resolved symbols and a type for every expression | "expected int, found string" |
| Control flow | Assigned before use; every path returns; no unreachable statement | A control-flow graph, or a weaker tree approximation | "use of possibly-uninitialized variable x" |
| Declarations | A return is inside a function; break is inside a loop; the entry point exists | The enclosing-construct chain from the traversal | "break outside of a loop" |
| Not checked heretypical | Whether the loop terminates, whether the index is in range, whether the answer is right | Undecidable, or a runtime property | Nothing — this is what tests and [[static-analysis]] are for |
Why it needs more than one pass
The naive design is one walk that resolves each name as it meets it. It works until a function calls another function defined later in the file, at which point the resolver reaches a name that does not exist yet and must either fail or guess. Almost every language allows that call, so almost every compiler collects declarations first and resolves second — the subject of [[declaration-order]].
Type checking adds a second ordering constraint. It needs resolved symbols, because the type of f(1) depends on which f; and resolution sometimes needs types, because in a language with methods, x.foo() cannot be resolved until the type of x is known. That mutual dependency is real, and languages resolve it in different ways: by requiring annotations at the points where the cycle would bite, by iterating to a fixed point, or by ordering the work so that the cycle never closes.
Error handling adds a third. A phase that stops at the first bad name reports one error per compile, which makes a compiler that is technically correct and practically hostile. The standard answer is an *error type* (or error symbol) that unifies with everything and suppresses cascades: undeclared + 1 produces one message about undeclared, not a second about adding an error to an integer.
- Pass one collects declarations so that forward references resolve.
- Pass two resolves uses against the symbol table and records the answer on each identifier.
- Pass three computes types bottom-up, using the resolved symbols — see
[[ast-traversal]]for why that order is forced. - Flow checks run afterwards, once the types are known and a CFG can be built.
- An error type and an error symbol keep one mistake from producing twenty messages.
How it works
The steps, in the order the compiler takes them.
- Walk the tree collecting declarations into scoped symbol tables, without resolving anything inside bodies.
- Walk again, resolving each identifier to a declaration by looking outward through enclosing scopes, and attach the resulting symbol to the node.
- Walk bottom-up computing a type for each expression from its children's types and the resolved symbols, recording each result in a side table.
- Build a control-flow graph (or approximate it on the tree) and run definite-assignment, reachability and return-path analyses over it.
- Check declaration-context rules using the enclosing-construct chain the traversal already maintains:
returninside a function,breakinside a loop. - Emit diagnostics with spans as they are found, substituting error types and error symbols so that later checks continue instead of cascading.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- The resolver stops at the first undeclared name. The user fixes one typo, recompiles, finds the next one, and a file with six mistakes takes six build cycles.
- No error type exists, so a single undeclared variable produces forty type errors about it. The real message is buried and the user reads the last one first.
- Definite assignment is approximated on the tree instead of a CFG, and a variable assigned in both arms of an
if/elseis still reported as possibly uninitialized. Users learn to add a dummy initialiser, which suppresses the check permanently and hides a real bug later. - A check runs before the pass that produces its input — types read before resolution — and expressions report type
unknownin correct code, but only in files where the declaration comes later. - The declaration-collection pass descends into function bodies, and a local variable is registered as a top-level name. A completely unrelated function now resolves a name to it, and the program compiles into something the user did not write.
- Diagnostics carry no span, so the message is right and points at line 1. The user cannot find the construct being complained about.
When it helps
- Catching the entire class of errors that are cheap to find statically and expensive to find at runtime: misspelled names, wrong argument counts, missing returns, unreachable branches.
- Producing the annotated tree that makes every later phase simpler — lowering, code generation and optimization all read the symbols and types this phase computed.
- Powering editors: go-to-definition, hover types, find-all-references and rename are all this phase's output, queried instead of compiled — see
[[language-server]].
When it hurts
- Believing that passing semantic analysis means the program is correct. It means the program is well-formed. Off-by-one errors, wrong logic and wrong algorithms all type-check perfectly.
- Dynamic languages, where most of these checks cannot run at all before execution: the declarations are not statically known and the types are values. What can be checked shrinks to almost nothing.
- Very large codebases with whole-program inference, where the phase becomes the compile-time bottleneck and each edit re-checks far more than it needs to — the motivation for
[[incremental-compilation]].
What it costs
Every one of these is paid by something.
- Separating semantic analysis from parsing buys complete diagnostics in one run and costs an extra full traversal plus a second data structure — the symbol table — that must be kept consistent with the tree.
- More checks buy earlier bug detection and cost compile time on every build, plus false positives that users learn to suppress, which is worse than not having the check.
- Error types and recovery buy multiple diagnostics per run and cost real complexity: every downstream check must handle the error type without producing nonsense, and every test suite must pin the exact cascade behavior.
- Doing flow analysis properly buys sound definite-assignment and unreachable-code results and costs building a CFG in the frontend, which is a substantial piece of machinery to add before lowering.
- Checking more at compile time buys runtime safety and costs expressiveness: every check that rejects a wrong program also rejects some right programs the checker cannot see are right.
What else you could do
What a different compiler or language does instead, and when that is better.
- Check at runtime instead. Python and JavaScript resolve names and check operations when the code executes, so nothing is rejected in advance and everything can be redefined dynamically. The cost is that the error arrives in production rather than at build time — see
[[static-vs-dynamic-typing]]. - Fold semantic checks into the parser via a context-sensitive parser or semantic predicates, as some parser generators allow. Fewer passes and faster compilation; you lose multi-error reporting and any hope of a resilient tree for an editor.
- Defer checks to a separate tool. Python's type checkers, Ruby's Sorbet and JavaScript's TypeScript all bolt a semantic phase onto a language whose implementation does not have one, which is a
[[gradual-typing]]design and buys adoption at the cost of the checks being optional. - Prove more, later: dependent types and refinement types push array bounds and value ranges into the checkable set. Far stronger guarantees, far more annotation burden, and the checker itself becomes a research artifact.
See it for yourself
The flag, dump or tool that shows you this directly.
- Rust:
rustc --error-format=json file.rsshows the structured diagnostics with spans and suggested fixes, which is this phase's output in machine-readable form. - C:
clang -fsyntax-only -Wall -Wuninitialized file.cruns the frontend and stops — everything it reports comes from semantic analysis, and nothing from code generation. - Java:
javac -Xlint:allsurfaces the flow checks (definite assignment, fall-through, unreachable code) that the language specification requires the compiler to perform. - TypeScript:
tsc --noEmitis exactly this phase with no output artifact, which is why it is the standard CI check for a language whose runtime ignores types entirely. - Our scope and symbol-table viewer at
/compilers/scopesshows the table being built and consulted as the walk proceeds.
Plausible wrong readings
Stated the way a confident engineer states them.
- "Semantic analysis is type checking." Type checking is one of five families. Name resolution, scope rules, flow analysis and declaration context are the others, and most compiler errors a beginner meets are not type errors.
- "If it compiles, it works." It is well-formed. Every logic bug you have ever written compiled.
- "The parser should catch undeclared variables." A context-free grammar cannot express it. That is a theorem, not a design preference.
- "Unreachable-code warnings are a lint." In several languages they are specified compiler behavior — Java requires a compile error for unreachable statements, and definite assignment is in the language specification, not in a style guide.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
After the parser proves the program is grammatical, something has to prove it means anything. That is semantic analysis: it finds what every name refers to, checks that the scope rules allow it, checks that the operations make sense for the types involved, and checks the flow questions a grammar cannot ask — is this variable set before it is read, does every path return, can this line ever run.
practical
When a compiler error confuses you, classify it first. "Cannot find X" is name resolution and the fix is a declaration, an import or a scope. "Expected A found B" is type checking and the fix is at the expression. "Possibly uninitialized" or "not all paths return" is flow analysis and the fix is on a path you did not think about — often an early return or an exception path. The classification narrows the search far faster than reading the message a fourth time.
advanced
The design tension in this phase is between soundness and helpfulness, and they pull hard against each other. A sound flow analysis rejects some correct programs, because proving assignment on every path is undecidable in general and every approximation errs on one side. Java chose to reject and require an initialiser; C chose to say nothing and leave it undefined; Rust chose to reject and invested heavily in the analysis being precise enough that the rejections feel fair. All three are defensible, and the choice is a language-design decision about who pays — the compiler author, the programmer, or the person debugging in production.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
-Wuninitialized misses cases and why the same source is diagnosed by one compiler and silently miscompiled by another.If you were asked this in an interview
- Name three things a compiler checks after parsing that the grammar could not have expressed, and say why not.
- A compiler reports forty errors for one typo. What is missing from its design?
- Is "not all code paths return a value" a type error? What kind of analysis produces it?
- Why do most compilers collect declarations in a separate pass before resolving any name?
Connections
- Testing & Reliability Engineering — What a class of defect costs depending on where it is caughtThe argument for doing more work in this phase is an economic one about defect cost curves, and that argument is owned there. What is ours is the mechanism: which checks are possible before execution, and what each one costs in compile time and in rejected-but-correct programs.