Learn compiler design: the best books in order
This curriculum is designed for expert-level learners who already have strong programming and CS theory foundations, and want to deeply master compiler and interpreter construction — from front-end parsing to back-end code generation and optimization. The four stages move from classical theory and hand-built interpreters, through industrial-strength parsing and IR design, to advanced optimization and modern SSA-based compiler architecture, building a complete and rigorous mental model at each step.
Classical Foundations & First Principles
IntermediateEstablish the canonical theoretical and practical vocabulary of compiler design — scanning, parsing, semantic analysis, and basic code generation — using the field's most authoritative references.
▸ Study plan for this stage
Pace: 8–10 weeks, ~40–50 pages/day (Aho chapters 1–6, then Cooper chapters 1–5). Allocate 5–6 weeks for Aho's theoretical foundations, then 3–4 weeks for Cooper's engineering perspective.
- Lexical analysis (scanning): regular expressions, finite automata, and token recognition as the first compiler phase
- Syntax analysis (parsing): context-free grammars, top-down vs. bottom-up parsing, and parse tree construction
- Semantic analysis: symbol tables, type checking, and attribute grammars for enforcing language rules
- Intermediate representation (IR): abstract syntax trees and three-address code as bridges between source and target
- Code generation fundamentals: instruction selection, register allocation strategy, and control flow
- Compiler architecture: the modular pipeline from source text through multiple analysis and synthesis phases
- Practical trade-offs in compiler design: speed vs. code quality, simplicity vs. optimization potential
- Error detection and recovery: how scanners, parsers, and semantic analyzers report and handle errors
- What is the role of lexical analysis, and how do regular expressions and finite automata enable efficient token recognition?
- Explain the difference between top-down and bottom-up parsing, and describe when each approach is practical.
- How do symbol tables and attribute grammars enforce semantic constraints during compilation?
- What is an intermediate representation, and why is it valuable to separate parsing from code generation?
- Describe the basic steps of code generation: how do you map IR constructs to target machine instructions?
- How do modern compilers balance compilation speed, code quality, and implementation complexity?
- Build a lexical analyzer for a simple language (e.g., a calculator or toy imperative language) using Aho's regular expression and finite automaton techniques; test it on sample input.
- Implement a recursive-descent parser for a context-free grammar of your choice; generate and visualize parse trees for valid and invalid inputs.
- Construct a symbol table with scope management and implement type checking for variable declarations and expressions.
- Convert a parse tree into an abstract syntax tree (AST), then into three-address code; trace the transformation on a small program.
- Write a simple code generator that maps three-address code to a target assembly language (real or simulated); test on loops and function calls.
- Implement error recovery in your parser (e.g., panic mode or error productions) and verify that it reports meaningful diagnostics.
Next up: Mastery of these canonical phases and their interactions prepares you to explore advanced topics—optimization, register allocation algorithms, and machine-specific code generation—where you will refine and extend the foundational pipeline you have now built.
The 'Dragon Book' is the definitive reference for compiler theory. Reading it first anchors every subsequent concept — grammars, automata, parse tables, type systems, and intermediate representations — in their rigorous formal context.
A modern, cleaner companion to the Dragon Book that excels at explaining the *why* behind design decisions. Read second to reinforce and clarify the Dragon Book's denser material with better pedagogy and updated coverage of SSA and register allocation.
Interpreters & Hand-Built Front Ends
IntermediateBuild a complete interpreter and hand-written recursive-descent parser from scratch, internalizing lexing, parsing, tree-walking evaluation, and bytecode virtual machines through direct implementation.
▸ Study plan for this stage
Pace: 12–14 weeks, ~40–50 pages/day, with 2–3 days per week dedicated to implementation projects
- Lexical analysis (tokenization): converting source code into a stream of tokens with position tracking and error handling
- Recursive-descent parsing: building an abstract syntax tree (AST) by hand-written recursive functions that respect operator precedence and associativity
- AST representation and tree-walking evaluation: representing programs as tree structures and evaluating them through recursive traversal
- Symbol tables and environments: managing variable scope, bindings, and function definitions during evaluation
- Bytecode compilation and stack-based virtual machine execution: compiling AST to bytecode instructions and executing them on a VM with an operand stack
- Error handling and reporting: propagating and displaying meaningful error messages with source locations
- Built-in functions and standard library integration: extending the interpreter with native functions and data types
- Optimization techniques: constant folding, dead code elimination, and bytecode peephole optimization
- How does a lexer tokenize source code, and what information must each token carry beyond its type?
- What is the relationship between operator precedence and the structure of a recursive-descent parser?
- How does a tree-walking interpreter evaluate an AST, and where do environments/symbol tables fit into this process?
- What are the key differences between tree-walking evaluation and bytecode compilation + VM execution, and when is each approach preferable?
- How do you implement function definitions, closures, and scope in an interpreter or compiler?
- What strategies can you use to provide helpful error messages that pinpoint the location of syntax and runtime errors?
- Build a lexer for a simple expression language (numbers, operators, parentheses) and verify it correctly tokenizes various inputs including edge cases
- Implement a recursive-descent parser that builds an AST for arithmetic expressions, respecting operator precedence without using a precedence-climbing algorithm
- Write a tree-walking evaluator for your AST that handles variables, function calls, and control flow (if/else, loops)
- Extend your interpreter to support user-defined functions with parameters and return values; test with recursive functions like factorial and Fibonacci
- Implement a bytecode compiler that translates your AST into a simple instruction set (e.g., PUSH, POP, ADD, CALL, RETURN)
- Build a stack-based virtual machine that executes your bytecode; compare its performance and code clarity against your tree-walker
- Add support for closures and first-class functions; implement a closure-capturing mechanism and test with higher-order functions
- Implement error recovery in your parser so it can report multiple errors in a single pass rather than stopping at the first error
Next up: This stage equips you with hands-on mastery of the complete pipeline from source code to execution, setting the foundation for advanced topics like type systems, optimization passes, and runtime features that the next stage will explore in depth.
Walks through building a fully working interpreter — lexer, Pratt parser, AST, evaluator — with no external tools. Starting here grounds theory in concrete, runnable code before tackling more complex compiler pipelines.
Directly continues from the interpreter book, extending the same language into a bytecode compiler and stack-based VM. Reading it immediately after cements the transition from tree-walking to compiled execution models.
Builds two complete implementations of the same language — a tree-walk interpreter in Java and a bytecode VM in C. Its depth on closures, garbage collection, and optimization fills gaps left by the Go books and bridges toward industrial compiler concerns.
Parsing Theory & Language Implementation in Depth
ExpertMaster the full spectrum of parsing algorithms and understand how real-world language implementations handle ambiguity, error recovery, and the translation from source to efficient intermediate form.
▸ Study plan for this stage
Pace: 10–12 weeks, ~40–50 pages/day (with implementation breaks). Grune's "Parsing Techniques" (~600 pages) takes 6–7 weeks; Parr's "Language Implementation Patterns" (~400 pages) takes 3–4 weeks. Allocate 1–2 weeks for integration projects.
- Formal grammar foundations: context-free grammars, BNF notation, derivations, and ambiguity detection—essential for understanding why parsing is non-trivial
- Top-down parsing algorithms (LL, recursive descent, predictive parsing) and their limitations, especially handling of left recursion and lookahead requirements
- Bottom-up parsing algorithms (LR, LALR, SLR) and shift-reduce mechanics—the backbone of industrial parser generators
- Handling ambiguity and conflicts: shift-reduce conflicts, reduce-reduce conflicts, and precedence/associativity declarations to resolve them
- Error recovery strategies: panic mode, phrase-level recovery, and error productions—making parsers robust for real-world source code
- Intermediate representations (ASTs, IRs) and semantic actions: translating parse trees into executable or analyzable forms
- Pattern-based language implementation: templates for visitors, tree walkers, and translation schemes that bridge parsing to code generation
- Practical parser construction: using parser generators (yacc/bison style) versus hand-written recursive descent, trade-offs in maintainability and performance
- What is the difference between LL and LR parsing, and why are LR parsers more powerful? When would you choose one over the other?
- How do shift-reduce and reduce-reduce conflicts arise in a grammar, and what are three concrete strategies to resolve them?
- Describe the process of converting a left-recursive grammar into an equivalent right-recursive or iterative form. Why is this necessary for top-down parsers?
- What is an abstract syntax tree (AST), and how does it differ from a concrete parse tree? Why do language implementations prefer ASTs?
- Explain how error recovery works in a production parser. What are the trade-offs between panic mode and phrase-level recovery?
- Design a simple grammar for arithmetic expressions with operator precedence and associativity. Show how to encode precedence in an LL parser versus an LR parser.
- What is a semantic action, and how does it enable a parser to build intermediate representations during parsing rather than in a separate pass?
- Implement a recursive descent parser for a simple expression grammar (e.g., arithmetic with +, -, *, /) without using a parser generator. Verify it handles operator precedence correctly.
- Take a grammar with shift-reduce conflicts (e.g., the classic 'dangling else' problem) and resolve it by rewriting the grammar or adding precedence declarations. Document your solution.
- Build an LL(1) parser table by hand for a small grammar (e.g., a subset of a simple language). Identify any conflicts and explain why they occur.
- Implement a tree-walking interpreter or code generator that consumes an AST produced by your parser. Use the Visitor pattern from Parr's patterns.
- Write a parser with error recovery: make it continue parsing and report multiple errors in a single source file rather than stopping at the first error.
- Compare two implementations of the same language feature: one using a hand-written recursive descent parser, one using a parser generator (e.g., ANTLR, yacc). Measure code size, readability, and performance.
- Implement a simple symbol table and scope management alongside parsing, demonstrating how semantic actions populate and query it during the parse.
Next up: This stage equips you with the algorithmic and practical foundations to parse any language; the next stage will apply these techniques to semantic analysis, type checking, and optimization—transforming a parse tree into a fully analyzed and optimized intermediate representation ready for code generation.
The most comprehensive survey of parsing algorithms in existence — LL, LR, Earley, GLR, PEG, and beyond. Reading it at this stage lets you make informed, principled choices about parser design rather than defaulting to a single approach.
Parr (creator of ANTLR) distills practical patterns for building real language tools. It bridges parsing theory and production implementation, covering symbol tables, type computation, and tree rewriting in a hands-on way.
Advanced Optimization, Code Generation & Modern IR
ExpertAchieve deep expertise in dataflow analysis, SSA form, register allocation, instruction selection, and the architecture of modern optimizing compilers as used in production systems like LLVM.
▸ Study plan for this stage
Pace: 12–14 weeks, ~40–50 pages/day (with 2–3 days/week for exercises and implementation)
- Static Single Assignment (SSA) form: construction, properties, and dominance frontiers
- Dataflow analysis frameworks: lattices, fixed-point iteration, and worklist algorithms for liveness, reaching definitions, and available expressions
- Register allocation via graph coloring and interference graphs; spilling and coalescing strategies
- Instruction selection and code generation: pattern matching, tiling, and lowering IR to machine code
- Control flow graphs (CFGs) and their role in optimization and analysis
- Loop optimization: invariant code motion, strength reduction, and induction variable elimination
- Algorithm design for compiler passes: greedy algorithms, dynamic programming, and graph algorithms applied to register allocation and instruction scheduling
- Modern IR design principles: why SSA and intermediate representations matter in production compilers like LLVM
- How do you construct SSA form from a control flow graph, and what is the role of dominance frontiers in this process?
- Explain the dataflow analysis framework: what is a lattice, how do you compute a fixed point, and how does this apply to liveness analysis?
- What is an interference graph, and how does graph coloring solve the register allocation problem? When and why do you need to spill variables?
- How does instruction selection work, and what are the trade-offs between pattern matching and dynamic programming approaches?
- What optimizations can you perform on loops, and how do induction variables and strength reduction improve code quality?
- How do the algorithms from Introduction to Algorithms (graph algorithms, dynamic programming, greedy methods) directly apply to compiler optimization and code generation?
- Implement SSA construction: write code to compute dominators and dominance frontiers on a CFG, then convert a simple three-address code program into SSA form.
- Build a liveness analysis pass: implement a worklist-based dataflow analysis to compute live-in and live-out sets for each basic block; verify correctness on hand-traced examples.
- Construct an interference graph and implement graph coloring: build the graph from liveness information, implement a greedy coloring algorithm, and handle spilling by inserting load/store instructions.
- Implement instruction selection using pattern matching or dynamic programming: take a simple IR (e.g., tree-based or DAG-based) and generate x86-64 or ARM instructions; measure code quality (instruction count, register usage).
- Optimize a loop: identify loop-invariant code, apply strength reduction to induction variables, and measure the performance improvement on a real benchmark.
- Analyze a real compiler pass: study a dataflow or optimization pass from LLVM or GCC source code; document how it uses the algorithms and data structures from both books.
Next up: This stage equips you with the algorithmic foundations and practical implementation skills to understand and extend production compiler infrastructure; the next stage will likely focus on applying these techniques to domain-specific optimizations, parallelization, or specialized backends.
Appel's book covers the full compiler pipeline with exceptional depth on activation records, liveness analysis, register allocation, and instruction scheduling. Its functional-language framing sharpens thinking about compiler passes as pure transformations.
Many advanced compiler algorithms — graph coloring for register allocation, dominance trees, flow analysis — require algorithmic fluency. Keeping this as a reference and reading relevant chapters alongside the compiler texts ensures the underlying algorithms are fully understood.
Discussion
Keep reading
Paths that share books, cover the same subject, or open a related topic.
