Semantic Analysis — Type Checking & Scope

Semantic analysis checks meaning beyond syntax. The parser ensures the program is grammatically correct. The semantic analyzer ensures it makes logical sense.

"x + y" is syntactically valid. But if x is a string and y is an integer, it may be semantically invalid (in statically-typed languages). If z is used but never declared — semantic error.

Symbol Table:
The central data structure of semantic analysis. Maps identifiers to their attributes:
- Name → type, scope level, memory location, whether initialized
- Built during parsing/semantic analysis, used throughout compilation
- Implemented as a hash table or linked list of scopes

Scope:
- Block scope: each { } introduces a new scope
- Nested scopes form a scope chain: inner scopes can see outer scope names
- Name resolution: look up identifier in current scope, then enclosing scopes outward
- Shadowing: inner declaration hides outer one with same name

Scope implementation — scope stack:
- Enter scope: push new hash table onto stack
- Declare variable: insert into top table
- Look up variable: search from top of stack downward
- Exit scope: pop top table (all local variables "disappear")

Type Checking:
- Static typing (C, Java, Rust): types checked at COMPILE TIME. Type errors = compile errors. Better performance, earlier bug detection.
- Dynamic typing (Python, JS): types checked at RUNTIME. Type errors = runtime exceptions. More flexible.
- Strong typing: implicit type conversion not allowed (Python: "3" + 3 is an error)
- Weak typing: implicit coercion allowed (JS: "3" + 3 = "33")

Type inference (Hindley-Milner):
Modern languages (Rust, Haskell, TypeScript, Python with mypy) can infer types without explicit annotations. Unification algorithm propagates type constraints. "let x = 5" → x inferred as int.

Attribute Grammar:
Formal framework for semantic analysis. Each grammar symbol has ATTRIBUTES (type, value, etc). Semantic RULES compute attribute values as the parse tree is traversed.

Synthesized attributes: computed from children (bottom-up). Type of expression = type of subexpressions.
Inherited attributes: passed from parent/siblings (top-down). Scope environment passed down.

Common semantic errors:
- Undeclared variable: use before declaration
- Type mismatch: incompatible types in operation
- Wrong number of arguments to function
- Return type mismatch
- Duplicate declaration in same scope
- Use of uninitialized variable

1from dataclasses import dataclass, field
2from typing import Optional
3
4# ── Types ──────────────────────────────────────────────
5class Type:
6    pass
7
8class IntType(Type):
9    def __repr__(self): return "int"
10
11class FloatType(Type):
12    def __repr__(self): return "float"
13
14class StringType(Type):
15    def __repr__(self): return "string"
16
17class BoolType(Type):
18    def __repr__(self): return "bool"
19
20class FunctionType(Type):
21    def __init__(self, params, ret):
22        self.params = params
23        self.ret    = ret
24    def __repr__(self): return f"({', '.join(str(p) for p in self.params)}) -> {self.ret}"
25
26INT    = IntType()
27FLOAT  = FloatType()
28STRING = StringType()
29BOOL   = BoolType()
30
31# ── Symbol Table ───────────────────────────────────────
32@dataclass
33class Symbol:
34    name:        str
35    type:        Type
36    scope_level: int
37    initialized: bool = False
38
39class SymbolTable:
40    def __init__(self):
41        self.scopes = [{}]   # stack of dicts
42        self.level  = 0
43
44    def enter_scope(self):
45        self.scopes.append({})
46        self.level += 1
47        print(f"  → Enter scope {self.level}")
48
49    def exit_scope(self):
50        exiting = self.scopes.pop()
51        print(f"  ← Exit scope {self.level} (vars: {list(exiting.keys())})")
52        self.level -= 1
53
54    def declare(self, name: str, typ: Type):
55        if name in self.scopes[-1]:
56            raise NameError(f"Variable '{name}' already declared in this scope")
57        sym = Symbol(name, typ, self.level)
58        self.scopes[-1][name] = sym
59        print(f"  Declare: {name}: {typ} at scope {self.level}")
60        return sym
61
62    def lookup(self, name: str) -> Optional[Symbol]:
63        for scope in reversed(self.scopes):
64            if name in scope:
65                return scope[name]
66        return None
67
68    def lookup_required(self, name: str) -> Symbol:
69        sym = self.lookup(name)
70        if sym is None:
71            raise NameError(f"Undeclared variable: '{name}'")
72        return sym
73
74# ── Type Checker ───────────────────────────────────────
75class TypeChecker:
76    def __init__(self):
77        self.sym_table = SymbolTable()
78        self.errors    = []
79
80    def error(self, msg):
81        self.errors.append(f"TYPE ERROR: {msg}")
82        print(f"  ✗ TYPE ERROR: {msg}")
83
84    def check_expr(self, node) -> Type:
85        if isinstance(node, Num):
86            return FLOAT if isinstance(node.value, float) else INT
87        if isinstance(node, Var):
88            sym = self.sym_table.lookup_required(node.name)
89            if not sym.initialized:
90                self.error(f"Variable '{node.name}' used before initialization")
91            return sym.type
92        if isinstance(node, BinOp):
93            lt = self.check_expr(node.left)
94            rt = self.check_expr(node.right)
95            return self.type_of_binop(lt, node.op, rt)
96        if isinstance(node, UnaryOp):
97            t = self.check_expr(node.operand)
98            if node.op == "-" and t not in (INT, FLOAT):
99                self.error(f"Unary '-' not applicable to {t}")
100            return t
101        raise ValueError(f"Unknown node: {node}")
102
103    def type_of_binop(self, lt, op, rt) -> Type:
104        if op in ("+", "-", "*", "/"):
105            if lt == INT and rt == INT:   return INT
106            if lt in (INT, FLOAT) and rt in (INT, FLOAT): return FLOAT
107            self.error(f"Cannot apply '{op}' to {lt} and {rt}")
108            return INT
109        if op in ("==", "!=", "<", ">", "<=", ">="):
110            if lt != rt:
111                self.error(f"Cannot compare {lt} and {rt}")
112            return BOOL
113        raise ValueError(f"Unknown operator: {op}")
114
115    def check_stmt(self, node):
116        if isinstance(node, Assign):
117            sym = self.sym_table.lookup(node.name)
118            val_type = self.check_expr(node.value)
119            if sym is None:
120                # implicit declaration (like Python)
121                sym = self.sym_table.declare(node.name, val_type)
122            elif sym.type != val_type:
123                self.error(f"Cannot assign {val_type} to {sym.name}: {sym.type}")
124            sym.initialized = True
125            print(f"  ✓ {node.name} = <expr of type {val_type}>")
126        elif isinstance(node, If):
127            cond_type = self.check_expr(node.condition)
128            self.sym_table.enter_scope()
129            for s in node.then_body: self.check_stmt(s)
130            self.sym_table.exit_scope()
131            if node.else_body:
132                self.sym_table.enter_scope()
133                for s in node.else_body: self.check_stmt(s)
134                self.sym_table.exit_scope()
135        elif isinstance(node, Return):
136            ret_type = self.check_expr(node.value)
137            print(f"  ✓ return <expr of type {ret_type}>")
138
139# ── Test type checking ─────────────────────────────────
140print("=== Type Checking ===
141")
142checker = TypeChecker()
143
144# Valid program
145program = [
146    Assign("x", Num(10)),
147    Assign("y", Num(3.14)),
148    Assign("z", BinOp(Var("x"), "+", Var("y"))),
149    Return(Var("z")),
150]
151print("Valid program:")
152for stmt in program:
153    checker.check_stmt(stmt)
154
155# Invalid: use undeclared variable
156print("
157Invalid program (undeclared variable):")
158checker2 = TypeChecker()
159try:
160    checker2.check_stmt(Assign("a", BinOp(Var("undeclared"), "+", Num(1))))
161except NameError as e:
162    print(f"  Caught: {e}")