Semantic Analysis

Learning Objectives

• Define semantic analysis and explain how it differs from syntax analysis
• Trace scope resolution for nested variable declarations with the same name
• Apply type checking rules to detect mismatched-operand errors
• Explain the role of the symbol table during semantic analysis
• Identify why a syntactically valid program can still fail semantic checks
• Distinguish static semantic errors from runtime errors

Quick Answer

Semantic analysis is the third phase of compilation, coming right after syntax analysis. Where the parser only checks that tokens are arranged in a grammatically legal order, semantic analysis checks whether that legal structure actually means something valid — do variable types match in an expression, has an identifier been declared before use, does a function call pass the right number and type of arguments? It works by walking the abstract syntax tree (AST) while consulting and updating a symbol table, a running record of every declared identifier's type, scope, and other attributes. A program can be perfectly parseable and still be rejected here, which is exactly why this phase exists as a separate step from parsing.

Why Semantic Analysis Is a Separate Phase

Consider int x = "hello";. Every token is legal, and the sequence — keyword, identifier, operator, string literal, semicolon — matches the grammar rule for a declaration-with-initializer. A parser has no complaint. But assigning a string literal to an int variable is meaningless in a statically typed language, and no context-free grammar can express "the right-hand side type must match the left-hand side type," because that requires tracking information (declared types) across the whole program, not just checking local token order. Semantic analysis exists precisely to handle these context-sensitive rules that a CFG structurally cannot encode.

The Symbol Table

The symbol table is the data structure semantic analysis is built around. Every time the analyzer encounters a declaration, it inserts an entry recording the identifier's name, type, scope level, and (for functions) its parameter list. Every time it encounters a use of an identifier, it looks that entry up to check it exists and to retrieve its type for further checks.

Scopes are typically tracked as a stack of tables, one per nested block. Entering a { } block pushes a new table; leaving it pops that table off, which is what makes an inner declaration correctly shadow an outer one without corrupting it.

int main() {
    int x = 10;
    {
        int x = 20;          // inner scope, new symbol-table entry
        printf("%d\n", x);   // resolves to inner x -> prints 20
    }
    printf("%d\n", x);       // inner table popped -> resolves to outer x -> prints 10
}

Why it matters: without scope-aware lookup, the analyzer would have no way to tell the two x variables apart, and either the inner block would corrupt the outer variable's value or the compiler would need to reject all shadowing outright — both far more restrictive than real languages require.

Type Checking

Type checking verifies that every operation is applied to operands of compatible types, using the type information recorded in the symbol table. It happens by annotating each AST node with a type as the tree is walked bottom-up: leaves get their type from declarations or literals, and each internal node's type is derived from its children according to the language's typing rules.

int a = 5;
float b = 2.5;
int c = a + b;   // a is int, b is float

Here the analyzer looks up a and b in the symbol table, sees int and float, and checks the rule for +. Most languages allow this via implicit conversion (promoting a to float for the addition), but then assigning that float result into c (an int) either triggers an implicit narrowing conversion with possible warning, or an outright error, depending on the language's strictness. A stricter language (or a compiler in pedantic mode) would flag both conversions explicitly.

Function calls get the same treatment against the declared parameter types:

void func(int a) { /* ... */ }

func(5);        // OK: int argument matches int parameter
func("hello");  // Type error: string literal does not match int parameter

Why it matters: type checking is what catches an enormous class of bugs before the program ever runs — passing the wrong kind of value into a function, or performing arithmetic that doesn't make sense, is far cheaper to catch here than to debug from a crash or wrong output later.

Other Semantic Checks

Beyond scope and type checking, semantic analysis commonly performs:

• Declaration-before-use checking — flagging any identifier referenced before it has an entry in the symbol table.
• Uniqueness checking — rejecting duplicate declarations within the same scope (two int x in the same block).
• Control-flow sanity checks — such as verifying a break only appears inside a loop or switch, or that a non-void function has a return on every path.

These are all still static checks: they can be decided from the program's text and structure alone, without running it. That's the defining boundary of semantic analysis — it stops at anything requiring actual execution, such as division by zero on a particular input, which is a runtime error, not a semantic one.

Key Terms

Term	Definition	Related Concept
Semantic Analysis	The compiler phase that checks meaning and context-sensitive correctness beyond grammar	Type checking, symbol table
Symbol Table	A data structure recording each identifier's name, type, scope, and attributes	Scope resolution
Scope Resolution	Determining which declaration of an identifier applies at a given point in the program	Symbol table
Type Checking	Verifying that operations are applied to compatible operand types	Type coercion
Type Coercion	An automatic, implicit conversion between compatible types (e.g., int to float)	Type checking
Static Semantic Error	An error detectable from the program's structure without running it	Runtime error
Abstract Syntax Tree (AST)	The tree structure semantic analysis walks and annotates with type information	Syntax analysis
Shadowing	An inner-scope declaration temporarily hiding an outer declaration of the same name	Scope resolution

Common Mistakes

Misconception: If a program compiles past the parser without errors, it's guaranteed to be correct. Why it's wrong: Passing the syntax analysis phase only means the tokens are arranged in a grammatically legal order. It says nothing about whether types match, identifiers are declared, or function calls use correct argument types. Correct understanding: int x = "hello"; parses perfectly but fails semantic analysis due to a type mismatch. A program must pass both syntax and semantic analysis before code generation can even begin.

---

Misconception: Semantic analysis catches all program bugs, including things like division by zero or null pointer dereferences. Why it's wrong: Semantic analysis is a static phase — it only examines the program's text and structure at compile time. It cannot know what value a variable will hold at runtime. Correct understanding: Division by zero, out-of-bounds array access with a runtime-computed index, and null dereferences are runtime errors, caught (if at all) by the running program or a runtime system, not by the compiler's semantic analyzer.

---

Misconception: The symbol table is just a flat list of variable names. Why it's wrong: A flat list can't distinguish two variables with the same name declared in different nested scopes, which is a routine, legal pattern in most languages. Correct understanding: Real symbol tables are scope-aware, typically implemented as a stack of tables (or a tree mirroring block nesting), so that entering and leaving a block correctly shadows and then restores identifier bindings.

Comparison and Connections

Aspect	Syntax Analysis	Semantic Analysis
Checks	Grammatical structure (token order)	Meaning: types, scope, declarations
Detects	int + 5; (illegal token sequence)	int x = "hello"; (illegal type assignment)
Data structure used	Parse tree / grammar rules	Symbol table + annotated AST
Errors are	Structural (syntax errors)	Contextual (semantic errors)
Can it catch runtime bugs?	No	No — only static, compile-time-detectable issues
Comes before/after	Before semantic analysis	After syntax analysis, before code generation

Practice Questions

Recall

1. What is the primary data structure that semantic analysis relies on, and what does it store? Answer guidance: The symbol table. It stores each declared identifier's name, type, scope level, and (for functions) parameter information.

2. Name two kinds of checks performed during semantic analysis. Answer guidance: Any two of: type checking, scope resolution, declaration-before-use checking, duplicate-declaration checking, function-call argument validation, control-flow sanity checks.

Understanding

3. Why can't a context-free grammar alone catch a type mismatch like int x = "hello";? Answer guidance: A CFG only encodes rules about the legal order of terminals and non-terminals; it has no mechanism for remembering that x was declared as int elsewhere and comparing it against the type of a later expression. That requires tracking information across the program, which is what the symbol table and semantic analysis provide.

4. Explain why shadowing (an inner-scope x hiding an outer x) does not corrupt the outer variable. Answer guidance: Scopes are tracked as a stack of symbol tables. Entering the inner block pushes a new table with its own x entry; lookups inside that block resolve to the inner entry. Leaving the block pops that table, so the outer x entry — untouched the whole time — is what subsequent lookups resolve to.

Application

5. A student writes void func(int a) {} and then calls func("hello");. Walk through what the semantic analyzer does when it reaches this call. Answer guidance: It looks up func in the symbol table to retrieve its declared parameter types (int). It then determines the type of the argument expression "hello" (a string/character array). Comparing the two, it finds no valid implicit conversion from string to int for this context and reports a type error.

6. Given int a = 5; float b = 2.5; int c = a + b;, describe the two type-related decisions the analyzer must make, and their possible outcomes. Answer guidance: First, it must resolve the type of a + b — typically by promoting a to float and performing float addition, since the language allows a widening conversion here. Second, it must handle assigning the resulting float back into c (an int) — either through an implicit narrowing conversion (possibly with a compiler warning) or as an outright error, depending on the language's rules.

Analysis

7. Compare a syntax error and a semantic error using the same underlying idea of "wrongness." What fundamentally distinguishes what each phase is capable of detecting? Answer guidance: A syntax error is detectable from local token arrangement alone, using only the grammar's rules — no memory of previously seen declarations is needed. A semantic error requires cross-referencing information gathered earlier in the program (like a declared type in the symbol table) against a later use. Syntax analysis is inherently local; semantic analysis is inherently contextual.

8. Why is "the program successfully compiles" not the same guarantee as "the program is correct"? What category of errors remains even after semantic analysis passes? Answer guidance: Semantic analysis only performs static checks decidable from the program's text, such as type and scope correctness. Runtime errors — division by zero, out-of-bounds access with a dynamic index, null dereferences, logic errors that produce the wrong-but-type-correct result — depend on actual execution and input values, which the compiler cannot fully predict in general (this connects to the halting-problem-adjacent limits of static analysis).

FAQ

Is semantic analysis always a fully separate pass from parsing? Not always in implementation — many production compilers perform semantic actions during parsing itself (in a single pass, attaching type-checking code to grammar productions), rather than building a complete AST first and walking it afterward in a second pass. Conceptually, though, it's still a distinct phase: a distinct set of rules being checked, whether or not the code for it runs interleaved with parsing.

What happens after semantic analysis succeeds? The compiler moves to intermediate code generation, using the AST — now annotated with type information from semantic analysis — to produce a lower-level, often architecture-independent representation that later phases optimize and translate into machine code.

Can semantic analysis catch logic errors, like a program that adds when it should subtract? No. If a + b is written where a - b was intended, both operands are perfectly type-compatible, so semantic analysis has nothing to flag. Semantic analysis only checks the specific set of rules a language defines as violations (types, scope, declarations) — it can't infer programmer intent.

Why do some languages need less semantic analysis than others? Dynamically typed languages (Python, JavaScript) defer most type checking to runtime, so their compilers/interpreters do far less static type checking at this phase. Statically typed languages (C, Java, Rust) push much more work into semantic analysis, which is why type errors in those languages are caught before the program ever runs.

How does semantic analysis relate to IDE features like red squiggly underlines for type errors? Those live-editing error indicators are typically powered by the same kind of type-checking and symbol-resolution logic used in semantic analysis, run incrementally as you type, rather than waiting for a full compile.

Quick Revision

• Semantic analysis is the third compiler phase, following syntax analysis and preceding intermediate code generation
• It checks meaning and context-sensitive correctness — type compatibility, scope, declarations — not grammatical structure
• The symbol table records each identifier's name, type, scope, and attributes; it's the core data structure of this phase
• Scopes are typically tracked as a stack of tables, so entering/leaving a block correctly shadows and restores identifiers
• Type checking annotates the AST bottom-up, deriving each node's type from its children and the language's typing rules
• int x = "hello"; is a classic example: syntactically valid, semantically invalid
• Other checks performed here: declaration-before-use, duplicate-declaration detection, function-call argument matching, control-flow sanity checks
• All semantic checks are static — decidable from program text alone, without executing it
• Runtime errors (division by zero, null dereference) are NOT semantic errors — they can't be caught here
• Passing semantic analysis is necessary but not sufficient for program correctness; logic errors with type-correct code slip through

Related Topics

Prerequisites: Syntax analysis and parse trees, context-free grammars, basic type systems

Related Topics: Symbol table design, static vs. dynamic typing, type inference

Next Topics: Intermediate code generation, code optimization, runtime error handling