Introduction to Compilers and Programming Languages

What compilation must preserve, from source text to machine instructions

About this course

A compiler end to end: lexing and parsing into an abstract syntax tree, interpreters and operational semantics, scope and type checking, lowering to an intermediate representation, dataflow analysis and SSA, behaviour-preserving optimisation, instruction selection and register allocation, calling conventions, and the evidence that the whole thing is correct.

What you will be able to do

  • Turn source text into tokens and an AST, with errors that name a real source location
  • State what execution means with operational semantics, scope rules and a type checker
  • Lower a program to an IR with explicit control flow, basic blocks and SSA
  • Prove an optimisation preserves behaviour, traps included, before applying it
  • Select instructions, allocate registers and test the compiler differentially

What this course covers

  • Observation contract for optimization
  • Straight-line scope and IR boundary assumptions
  • Roots of backward analysis: which instructions cannot be removed
  • Forward constant propagation: two-map design and invariant
  • Constant folding rules including known-overflow preservation
  • Mutation and shadowing in forward propagation
  • Backward dead-value elimination rules
  • Interaction between forward and backward passes
  • Algebraic identities do not justify unsafe rewrites
  • Static rejection precedes optimization; negative controls validate tests
  • Compiler correctness and observable behavior
  • Sprig integer semantics and overflow
  • Two-phase failure boundary
  • Scanning: tokenisation and source spans
  • Parsing: syntax trees, precedence and associativity
  • Name resolution and scope rules
  • Reference interpreter execution model
  • Stack machine execution and the expression stack invariant
  • Compilation contract, testing strategy and limits
  • Machine Configuration and Execution State
  • Work-List Evaluation Order and Continuation Frames
  • Fuel, Trace Caps, and Suspension vs. Completion
  • Environment, Name Resolution, and Declaration Semantics
  • Conditional (if-zero) and Selective Evaluation
  • Calling Convention and Runtime Distinction
  • Language Subset and Observation Contract
  • Argument Evaluation Order and Staging
  • Activation Records and Frame Layout
  • Continuations and Return Mechanics
  • Register Convention: Caller-Saved and Callee-Saved Obligations
  • Recursive Activation Stack and Unfinished Work
  • Failure Semantics: Traps, Depth Limits, and Observation Boundaries
  • Compiler Expression Invariant and Target Validation
  • Typed Three-Address Intermediate Representation
  • Source Language Obligations Carried into the Target
  • Fresh Temporaries vs. Mutable Binding Slots
  • Lowering: Translating Source Expressions to Instruction Sequences
  • Shadowing, Block Cleanup, and Binding Lifetimes
  • Checked Arithmetic, Overflow Semantics, and Source Focus Retention
  • Simulation Argument, Differential Testing, and Negative Controls
  • Sprig F15 language scope and compiler pipeline
  • Observation model and equivalence relation
  • Driver commands and exit-status contract
  • Front end: scanning, parsing, and validation
  • Lowering invariant and register calling convention
  • Target legality vs. translation correctness
  • Differential testing, mutation, and oracle limits
  • Failure reduction: predicate, metric, and limits
  • Bundle integrity, packaging, and claim boundaries
  • Control Flow Graphs and Basic Blocks
  • Reachability and Dominance
  • Immediate Dominators and the Dominator Tree
  • Static Single Assignment Form and Phi Instructions
  • Phi Operand Availability and SSA Verification
  • Dominance Frontiers and Phi Placement
  • Behavioral Preservation and Guarded Overflow
  • Scanner obligations: complete match and source provenance
  • Cursor trace and skipped-region accounting
  • Token record fields and their consumers
  • Half-open spans and the EOF marker
  • Longest-match identifier recognition and keyword classification
  • Integer token recognition and separation from literal validation
  • Minus token, comment/whitespace skipping, and scanner termination
  • Coordinate units: code points, bytes, and display positions
  • Audit strategy: invariants, negative controls, and performance accounting
  • Names, Declarations, Bindings, and Values
  • Lexical Scope and the Resolver Scope Stack
  • Source-Order Visibility and the Initializer Boundary
  • Shadowing vs. Duplicate Declaration
  • Mutable Bindings, Assignment, and the Mutability Check
  • Static Resolution Failures and the Two-Phase Model
  • The Resolved Tree, Runtime Store, and Commit Boundary
  • Resolver Invariant and Scope-Based Renaming
  • Instruction selection problem and target machine contract
  • Preservation contract and observable equivalence
  • Virtual register machine instruction set
  • Copy-before-destructive-arithmetic pattern
  • Overflow flag adjacency rule and checked arithmetic template
  • Small-immediate range and register fallback
  • Selector algorithm: pattern matching, commutativity, and dead-load removal
  • Cost model and its limits
  • Diagnostic metadata, type preservation, and scope correctness
  • Test strategy and scope of the implementation
  • Liveness Analysis via Backward Scan
  • Register Pressure and Spill Motivation
  • Interference Graph Construction
  • Graph-Coloring Register Assignment (Simplify and Select)
  • Spill Code Rewriting with Scratch Registers
  • The Home Invariant and Replay Correctness
  • Limitations and Extensions of the Model
  • Types vs. Values and the Limits of Static Checking
  • Typing Judgments and Operator Signatures
  • Building a Derivation Tree Bottom-Up
  • Types Belonging to Resolved Declaration Identities
  • The Checked Tree as Compiler Output
  • Structured Diagnostics and Phase Ordering
  • The Type-Soundness Invariant, Runtime Obligations, and Carry-Forward Ideas
  • Data flow analysis overview and motivation
  • Fact domains, program points, and the 'may' semantics
  • Lattice structure and boundary conditions
  • Transfer functions: gen/kill and use/def
  • Work-list iteration and termination
  • Least fixed point and schedule independence
  • Liveness analysis and backward information flow
  • Distributivity, path feasibility limits, and safe use of results
  • Ambiguity in context-free grammars
  • Context-free grammar components and derivations
  • Concrete parse trees and their validity checks
  • Layered grammar encoding precedence and associativity
  • Role of parentheses and unary minus in grammar
  • Concrete vs. abstract syntax trees and grammar testing
  • Separating grammatical structure from semantic validity
  • Parser responsibilities and cursor contract
  • Recursive descent parsing with grammar levels
  • Primary parsing: operands, prefix negation, and parentheses
  • Binding power (Pratt) parsing
  • Abstract syntax tree design and source location metadata
  • Literal range checking and arithmetic boundary handling
  • Precise syntax diagnostics and entry-point completeness

Syllabus

  1. From Source to Syntax

    1. L1 · From Source Code to Observable Behavior
    2. L2 · Lexical Analysis and Source Locations
    3. L3 · Grammars Ambiguity and Parse Trees
    4. L4 · Building a Parser and Abstract Syntax Tree

  2. Meaning: Interpreters, Names and Types

    1. L5 · Interpreters and Operational Semantics
    2. L6 · Names Bindings and Lexical Scope
    3. L7 · Types Type Checking and Useful Diagnostics

  3. Lowering and Analysis

    1. L8 · Lowering to Intermediate Representation
    2. L9 · Control Flow Basic Blocks and SSA
    3. L10 · Dataflow Analysis and Fixed Points

  4. Optimisation and Code Generation

    1. L11 · Optimizations That Preserve Behavior
    2. L12 · Instruction Selection and Machine Constraints
    3. L13 · Liveness and Register Allocation

  5. The Whole Compiler

    1. L14 · Functions Calling Conventions and Runtime Support
    2. L15 · Build Test and Audit the Complete Compiler