Compiler Design & Language Theory

Compiler Design & Language Theory

A compiler translates source code to a target language (machine code, bytecode, or another high-level language). Understanding compilers teaches you how programming languages work, why certain optimizations are possible, and how type systems actually enforce correctness.

Compilation Phases

Lexical Analysis (Lexing/Scanning): converts a character stream to a token stream. Tokens are the basic symbols of the language: keywords (if, while), identifiers (myVariable), literals (42, "hello"), operators (+, =), and punctuation ({, }). The lexer is typically implemented as a finite automaton — each token type is a regular language recognized by a pattern. Tools: lex, flex, or hand-rolled.

Syntax Analysis (Parsing): converts the token stream to an Abstract Syntax Tree (AST) using the grammar. The AST captures structure, not text: a binary expression node has an operator, a left operand, and a right operand — regardless of whitespace or parentheses used to express it.

Parser types:

• Recursive descent: a hand-written top-down parser where each grammar rule becomes a function. Readable, good error messages, handles LL(k) grammars.
• LL parsers: Left-to-right scanning, Leftmost derivation. Predictive parsers using a parsing table. Cannot handle left-recursive grammars.
• LR parsers (LALR, SLR): more powerful than LL, handle most programming languages. Generated by tools like yacc/bison. Used for C, Java compilers.

Semantic Analysis: the AST is traversed to check properties beyond syntax. Type checking ensures operations are applied to compatible types. Symbol resolution associates identifier uses with declarations. Scope rules determine which declaration a name refers to. The output is a type-decorated AST.

Intermediate Representation (IR): most compilers translate to an IR before emitting target code. LLVM IR and GCC's GIMPLE are architecture-independent, enabling the same optimizations for all target platforms. SSA form (Static Single Assignment) makes dataflow analysis tractable.

Optimization: the IR is transformed to improve performance without changing semantics. Key optimizations:

• Constant folding/propagation: evaluate constant expressions at compile time (2 + 3 → 5), propagate constants through the program
• Dead code elimination: remove code that cannot affect the output
• Inlining: replace function calls with the function body — eliminates call overhead and enables further optimizations
• Loop optimizations: hoisting invariant computations out of loops, unrolling loops to reduce branching
• Register allocation: assign variables to CPU registers, minimizing memory accesses (NP-hard in general; modeled as graph coloring)

Code Generation: translates optimized IR to target instructions (x86, ARM, WASM). Instruction selection matches IR patterns to target instructions. Register allocation assigns physical registers. Instruction scheduling reorders instructions to avoid pipeline stalls.

Type Systems

A type system assigns types to expressions and enforces constraints at compile time (static) or runtime (dynamic). Strong type systems catch entire classes of bugs before execution.

Type soundness: a type system is sound if a well-typed program never encounters a type error at runtime. "Well-typed programs don't go wrong" (Milner, 1978). Java and Haskell have sound type systems; C's does not (undefined behavior, pointer casts).

Hindley-Milner type inference (used in Haskell, ML, OCaml, inferred parts of TypeScript) can determine the most general type of any expression without annotations. The algorithm (Algorithm W) works via unification: when two type expressions must match, their type variables are unified. This enables type-safe code with nearly no annotations.

Parametric polymorphism (generics): a function identity<T>(x: T): T works for any type T. The compiler instantiates it for each concrete type — monomorphization in Rust/C++, or uses a uniform representation with type erasure (Java, Go).

Dependent types (Agda, Coq, Idris) allow types to depend on values: a function that returns an array of exactly n elements has type Array[n]. This enables proofs of program correctness as types — the foundation of formal verification.

Interpretation vs Compilation

Compiled languages (C, Rust, C++, Go) produce native machine code at compile time. Execution is fast — no runtime overhead, direct CPU instructions.

Interpreted languages (Python, Ruby) execute source code (or bytecode) via a runtime interpreter. Slower per instruction (10-100x) but faster to develop, debug, and run on multiple platforms without recompilation.

JIT compilation (JavaScript V8, Java JVM, Python PyPy) compiles hot code paths at runtime using profiling information. Gets close to compiled performance while retaining the flexibility of interpretation. V8 compiles JavaScript functions after seeing them called frequently, using type feedback to specialize for the actual types observed.

Domain-Specific Languages (DSLs)

A DSL is a language specialized for a domain. SQL is a DSL for relational queries. HTML is a DSL for document structure. Regex is a DSL for pattern matching. Build systems (Make, Gradle) are DSLs for build logic.

Building a DSL — even a simple one — uses the same pipeline: lexer, parser, AST, interpreter or code generator. Modern meta-programming (macros in Rust/Lisp, decorators in Python, template literals in JavaScript) enables embedded DSLs without a separate compiler.