Vol 11: Compilers and Formal Languages

This volume turns source text into tokens, syntax trees, IR, and machine code while preserving meaning. Every pass needs preconditions and a verifier; otherwise optimization merely produces the wrong answer faster.

Prerequisites

• Be able to write functions and recursive code and use stacks, trees, and graphs. Volume 1 and Volume 2 cover these foundations.
• Sets, relations, and basic proofs from Math A help with the theory. Target code and ABI lessons also use the machine model from Volume 3.

Coverage

Chapters 1–4 move from grammars and automata to computability and complexity. Chapters 5–8 follow compilation through scanning, parsing, names and types, intermediate representations, optimization, and code generation.

Chapter 1

• 1.1 Alphabet, Strings, and Grammar: First, Define What Counts as Valid
• 1.2 Chomsky Hierarchy and Recognition Boundaries: How Much Memory Do Rules Need

Chapter 2

• 2.1 DFA Design and Execution: Making Every State Meaningful
• 2.2 NFA, Subset Construction and Minimization: From Multiple Possible Paths to a Single State
• 2.3 Regular Expressions and Matching Engines: From Thompson Construction to Performance Boundaries

Chapter 3

• 3.1 CFG, Derivation Trees, and Ambiguity: Ensuring Nested Structures Have a Single Meaning
• 3.2 Pushdown Automata and the CFL Boundary: What Can a Stack Remember?

Chapter 4

• 4.1 Turing Machines, Recognizability, and Decidability: Drawing a Boundary for Algorithmic Power
• 4.2 The Halting Problem, Reduction, and Rice's Theorem: Proving the Nonexistence of a Universal Decider
• 4.3 P, NP, and Reductions: Can We Compute It Within a Budget?

Chapter 5

• 5.1 Token Contracts and Source Positions: Passing Characters to the Parser
• 5.2 Hand-Crafted Scanner: Cursor, Lookahead, and Safety Boundaries
• 5.3 Longest Match, Lexer Mode, and Generators: How Multiple Rules Collaborate

Chapter 6

• 6.1 Recursive Descent and AST: Embedding Precedence into Call Structure
• 6.2 FIRST, FOLLOW, and Error Recovery: Why Predictive Parsing Can Make Decisions
• 6.3 LR Shift-Reduce and Syntax Trees: Reconstructing Structure from Prefixes on the Stack

Chapter 7

• 7.1 Name Resolution and Scope: Who Does a Name Actually Point To?
• 7.2 Type Checking and Conversion: Ensuring Every Operation Meets Language Rules
• 7.3 IR, Control Flow Graphs, and SSA: Enabling Data Dependency Analysis

Chapter 8

• 8.1 Data Flow Analysis and Optimization Legality: When Can Code Be Removed?
• 8.2 Instruction Selection, ABI, and Register Allocation: Getting IR into a Real Machine
• 8.3 AOT, JIT, and Deoptimization: Using Runtime Information and Recovering Safely

Outcomes

• Define a grammar and recognizer for a small language, distinguishing regular, context-free, and decidable problems.
• Trace source positions, scopes, and types from a character stream into an AST and IR.
• Explain why an optimization preserves program meaning and how the target ABI and register constraints affect generated code.

How to use this map

For the theory, start at Chapter 1 and read in order. To build a small language, you can begin with the scanner and expression parser in Chapters 5–6, then revisit the theory they use. Keep inputs, outputs, and error locations visible at each stage. Use a correct, simple implementation as a reference, then check the optimized version against it.