Semantic Analysis — Missing Symbol Table Crashed Platform

Every time you write code that passes the syntax check but the compiler still yells at you — 'cannot assign int to string', 'variable not declared in this scope', 'method does not exist on this type' — that's semantic analysis doing its job. And trust me, you want that yelling early. It's the phase of compilation that sits between parsing and code generation, and it's the last line of defense before your program gets turned into machine instructions. Skip it, and you get undefined behavior, type confusion, or worse — silent runtime corruption.

What is Semantic Analysis?

Semantic analysis is the compiler phase that ensures the program's structure is meaningful. After the parser builds an Abstract Syntax Tree (AST), the semantic analyzer walks that tree, associates identifiers with their declarations (via symbol tables), checks that all operations are type-consistent, and resolves variable references to the correct scope. Without it, you could write int x = "hello"; and the parser would happily accept it — the grammar allows assignments, but the semantics forbid assigning a string to an integer variable.

Your job as a compiler engineer is to implement these checks efficiently. Most compilers do this by annotating each AST node with additional information (decorated AST) using attribute grammars. The result is a validated, well-typed intermediate representation that can safely be lowered to machine code.

But there's more: semantic analysis also validates control flow — ensures break/continue are inside loops, checks that return statements exist in non-void functions, and enforces access modifiers. It's the phase where the compiler truly understands your code's intent.

package io.thecodeforge.compiler;

import java.util.*;

public class SemanticAnalyzer {
    private SymbolTable symTable = new SymbolTable();
    
    public ASTNode analyze(ASTNode ast) {
        return checkNode(ast, new Scope(null));
    }
    
    private ASTNode checkNode(ASTNode node, Scope scope) {
        if (node instanceof VariableDeclaration) {
            VariableDeclaration decl = (VariableDeclaration) node;
            // Check that the variable is not already declared in scope
            if (scope.lookupLocal(decl.name) != null) {
                throw new SemanticException("Variable '" + decl.name + "' already defined");
            }
            SymEntry entry = new SymEntry(decl.name, decl.type, decl.line);
            scope.define(entry);
            symTable.add(entry);
            // Check the initializer type matches
            if (decl.initializer != null) {
                Type initType = inferType(decl.initializer, scope);
                if (!decl.type.isAssignableFrom(initType)) {
                    throw new SemanticException("Type mismatch: cannot assign '" + initType + "' to '" + decl.type + "'");
                }
            }
        } else if (node instanceof BinaryOp) {
            // Type check operands
        }
        return node;
    }
}

Type Checking: Static vs Dynamic and Coercion Rules

Type checking ensures that operations are applied to compatible types. There are two major approaches: static type checking (at compile time) and dynamic type checking (at runtime). Most statically typed languages (C++, Java, Rust) perform full static checking, while dynamically typed languages (Python, JavaScript) defer most checks to runtime.

But the real complexity lies in implicit type coercion — the automatic conversion between types. For example, int + float in C promotes the int to float. That sounds simple, but coercion rules differ wildly across languages. In Java, short + int promotes both to int, but assigning that result back to short requires an explicit cast. Misunderstanding these rules leads to precision loss, overflow, or even security vulnerabilities in production code.

Your compiler's type checker must implement a coercion lattice — a partial order that defines which types can be implicitly converted to which. Incorrect coercion can allow dangerous narrowing conversions silently. For example, in C, long l = 3.14; truncates the fractional part without warning, which has caused real bugs in financial calculations. The worst part? The compiler often stays silent unless you explicitly ask for warnings.

package io.thecodeforge.compiler;

public class TypeChecker {
    
    /**
     * Checks if sourceType can be implicitly converted to targetType.
     * Uses a coercion lattice defined by the language spec.
     */
    public static boolean isAssignable(Type source, Type target) {
        if (source.equals(target)) return true;
        // Coercion rules: narrower to wider is okay
        if (source.isNumeric() && target.isNumeric()) {
            // Lattice: byte->short->int->long->float->double
            int srcRank = numericRank(source);
            int tgtRank = numericRank(target);
            if (srcRank < tgtRank) return true;
            // Integral promotions: char to int is also allowed
            if (source.getKind() == TypeKind.CHAR && target.getKind() == TypeKind.INT) return true;
        }
        // Reference types: subtype to supertype (covariance)
        if (source.isReference() && target.isReference()) {
            return target.isAssignableFrom(source);
        }
        return false;
    }
}

Symbol Tables and Scope Management

The symbol table is the central repository of all identifiers in a program — variables, functions, classes, etc. It maps names to their attributes (type, scope, line declared, mutability). Scopes are nested regions of code where names are valid. The simplest implementation uses a stack of hash maps: when entering a block, push a new map; when exiting, pop.

In languages with lexical (static) scoping, a name refers to the innermost declaration. That means when you look up a variable, you search from the top of the stack downward — the first match wins. If nothing found, you either generate an error (statically typed languages) or fall back to the global scope (dynamically typed).

Production compilers don't use a simple stack — they flatten scopes into a hash table keyed by a fully qualified name (e.g., io.thecodeforge.compiler.SemanticAnalyzer.sum). This speeds up lookup from O(depth) to O(1) at the cost of more memory. But it requires care with shadowed declarations: you must store multiple entries for the same name and resolve based on the current scope depth.

A common optimization: use a spacer or version number on each key to avoid rehashing when entering/exiting scopes. This is especially helpful in languages like JavaScript with deep nesting.

package io.thecodeforge.compiler;

import java.util.*;

public class SymbolTable {
    // Using a list of maps for hierarchical scopes
    private List<Map<String, SymEntry>> scopes = new ArrayList<>();
    
    public SymbolTable() {
        // Global scope
        scopes.add(new HashMap<>());
    }
    
    public void enterScope() {
        scopes.add(new HashMap<>());
    }
    
    public void exitScope() {
        if (scopes.size() > 1) {
            scopes.remove(scopes.size() - 1);
        }
    }
    
    public SymEntry lookup(String name) {
        // Search from innermost to outermost
        for (int i = scopes.size() - 1; i >= 0; i--) {
            SymEntry entry = scopes.get(i).get(name);
            if (entry != null) return entry;
        }
        return null;
    }
    
    public void define(SymEntry entry) {
        Map<String, SymEntry> current = scopes.get(scopes.size() - 1);
        if (current.containsKey(entry.name)) {
            throw new SemanticException("Duplicate variable: " + entry.name);
        }
        current.put(entry.name, entry);
    }
}

Scope Resolution: How Names Get Resolved to Declarations

Scope resolution is the algorithm that connects a name usage (a reference) to its declaration in the symbol table. In block-scoped languages (C, Java), the rule is simple: search the enclosing blocks from innermost outward. But real languages have many wrinkles:

• Forward references: In C, you can call a function before declaring it if it has a prototype. In Java, classes can reference methods defined later. This requires a two-pass approach: first collect all declarations, then resolve references.
• Overloading: Same name, different signatures (Java methods, C++ functions). Resolution must consider the number and types of arguments and choose the best match.
• Inheritance: this.x might refer to x in the current class or in a parent class. The resolution must walk the inheritance chain.
• Import/using directives: In C# or Java, using System; brings all names from that namespace into scope without qualification. Implementation usually expands these into full names at compile time.

A common mistake: treating all names equally. For example, in Java, System.out first resolves System as a class, then out as a static field of that class. If you resolve out globally without context, you might find a local variable named out and silently bind the wrong thing. Production compilers use a hierarchical resolution strategy: type first, then member access.

And then there's C++ Argument-Dependent Lookup (ADL), a notorious source of surprise. If you call swap(x, y) and x is a type from namespace myspace, the compiler will look for swap in myspace too — even if you didn't qualify it. That's great for customization, but it can bind to the wrong overload if you're not careful.

package io.thecodeforge.compiler;

public class ScopeResolver {
    
    public DeclResolution resolveName(String name, int line, int col, Scope scope) {
        // Strategy: first try direct lookup
        SymEntry entry = scope.lookup(name);
        if (entry != null) {
            return new DeclResolution(entry, ResolvedType.DIRECT);
        }
        
        // If not found, try unresolvable -> error
        // But if we are in a class context, try inherited names
        if (scope.getCurrentClass() != null) {
            DeclResolution inherited = resolveInherited(name, scope.getCurrentClass());
            if (inherited != null) return inherited;
        }
        
        // Try imported names
        for (String imp : scope.getImports()) {
            // Resolve imp.name
            DeclResolution imported = resolveQualified(imp + "." + name);
            if (imported != null) return imported;
        }
        
        // Still not found -> error
        return null;
    }
}

Attribute Grammars: The Mathematical Foundation

Attribute grammars are the formal framework for specifying semantic rules on top of a context-free grammar. Each grammar symbol (nonterminal) can have a set of attributes that carry computed values up and down the parse tree. There are three kinds of attributes:

• Synthesized attributes: computed from children (bottom-up). E.g., the type of an expression is synthesized from its subexpressions.
• Inherited attributes: passed from parent or siblings (top-down or sideways). E.g., the expected type of an expression in an assignment is inherited.
• Intrinsic attributes: inherent to a terminal, like the lexeme of an identifier.

Most compilers implement attribute grammars implicitly by decorating AST nodes and walking them in a specific order. L-attributed grammars (left-to-right, depth-first) are common because they can be evaluated in a single pass. S-attributed grammars (only synthesized) are even simpler but cannot handle context-sensitive checks like 'is this variable already declared?' without a helper data structure.

In practice, you don't need the full formalism — you just need to annotate AST nodes with fields like type, expectedType, scope, etc., and write the evaluation rules as methods on those nodes. But understanding the theory helps you prove that your analyzer is correct: every attribute should be defined exactly once per node, and the dependency graph should be acyclic.

A useful mental trick: draw the attribute flow graph before writing any code. If you see a cycle, you're doing something wrong. In real compilers, circular attribute dependencies are rare but can happen with mutually recursive type declarations.

package io.thecodeforge.compiler;

import java.util.*;

// Simplified attribute evaluator for a small expression grammar
public class AttributeEvaluator {
    
    public void evaluate(ASTNode node) {
        // Postorder traversal for synthesized attributes
        for (ASTNode child : node.children) {
            evaluate(child);
        }
        // Now compute our own attributes
        switch (node.kind) {
            case LITERAL:
                node.attributes.put("type", node.literalType());
                node.attributes.put("value", node.literalValue());
                break;
            case BINARY_OP:
                Type left = (Type) node.children.get(0).attributes.get("type");
                Type right = (Type) node.children.get(1).attributes.get("type");
                if (!left.isCompatible(right)) {
                    throw new SemanticException("Binary OP type mismatch");
                }
                node.attributes.put("type", promoteType(left, right));
                break;
            case ASSIGNMENT:
                // Inherit expected type from parent context (not shown)
                break;
        }
    }
}

Error Recovery and Reporting in Semantic Analysis

A good semantic analyzer shouldn't stop at the first error — it should recover and report as many errors as possible in one compilation run. But semantic errors are trickier than syntax errors because they often involve chains: a variable not being declared means that any use of it is also a type error. The challenge is to avoid cascading errors that drown the user in noise.

Production compilers like clang use sophisticated error recovery that even suggests corrections. The real art is deciding which errors are independent and which are consequences.

One more trick: deduplicate identical errors. If the same missing symbol is referenced ten times, report it once with a count. Otherwise you bury the root cause in noise.

package io.thecodeforge.compiler;

import java.util.*;

public class ErrorReporter {
    private List<CompilerError> errors = new ArrayList<>();
    private Set<String> reportedVariables = new HashSet<>();
    
    public void report(String message, int line, int col) {
        errors.add(new CompilerError(message, line, col));
    }
    
    public void reportUndeclaredVariable(String name, int line, int col) {
        // Only report the first occurrence of an undeclared variable
        if (!reportedVariables.contains(name)) {
            reportedVariables.add(name);
            errors.add(new CompilerError("Variable '" + name + "' not declared", line, col));
        }
    }
    
    public void reportAll() {
        errors.sort(Comparator.comparingInt(CompilerError::getLine)
                               .thenComparingInt(CompilerError::getCol));
        for (CompilerError e : errors) {
            System.err.printf("%s:%d:%d: error: %s%n", e.file, e.line, e.col, e.message);
        }
    }
}

Frequently Asked Questions