Introduction to Compilers and Language Design

Citation

Thain, D. (2020). Introduction to Compilers and Language Design (2nd ed.). Self-published. Free official edition: https://dthain.github.io/books/compiler/

Chapter Summary

Chapter 1: Introduction

The opening chapter does the work of a preface. It defines a compiler as a translator from a source language to a target language, separates compilers from interpreters (with Java bytecode and just-in-time compilation as the in-between case), and gives reasons to study the subject, from writing better code to building small domain-specific languages. Thain argues that the way to learn compilers is to build one, in C, targeting a widely used processor, and explains that the book gives less weight to optimization theory than most compiler texts and more to engineering and language-design trade-offs.

Chapter 2: A Quick Tour

This short chapter places the compiler inside the Unix toolchain (preprocessor, compiler proper, assembler, static and dynamic linkers) and then names the internal stages: scanner, parser, semantic routines, intermediate representation, optimizers and code generator. A single statement, height = (width+56) * factor(foo);, is followed through every stage, from tokens to an abstract syntax tree, a linear IR with unlimited registers, and finally X86 assembly. The exercises ask the reader to run each toolchain stage by hand and compare optimization levels.

Chapter 3: Scanning

The chapter starts with the kinds of tokens a language needs and a hand-written C scanner that uses ungetc to push back characters, then shows why a more rigorous approach is needed. It defines regular expressions, deterministic and nondeterministic finite automata, and the three conversion algorithms (regular expression to NFA, subset construction from NFA to DFA, and Hopcroft-style DFA minimization). After explaining why finite automata cannot match arbitrarily nested parentheses, it turns to the Flex scanner generator, with a complete specification, and closes with practical issues such as keywords and tracking source locations.

Chapter 4: Parsing

This is the most theoretical chapter. It defines context-free grammars, derivations and ambiguity, then develops LL(1) parsing: eliminating left recursion and common prefixes, computing FIRST and FOLLOW sets, and writing both recursive-descent and table-driven parsers. The second half covers bottom-up parsing: shift-reduce parsing, the LR(0) automaton, SLR, canonical LR(1) and LALR, with worked automata and parse tables. It ends by relating the grammar classes (LL(1) ⊂ SLR ⊂ LALR ⊂ LR(1) ⊂ CFG) and presenting the Chomsky hierarchy.

Chapter 5: Parsing in Practice

Here the theory is put to work with the Bison parser generator. Using one LALR grammar for arithmetic expressions, the chapter builds three programs in turn: a validator that only accepts or rejects input, an interpreter that computes results during parsing, and a version that builds an expression tree which can then be evaluated or printed. This prepares the reader to write the full parser for the project language.

Chapter 6: The Abstract Syntax Tree

The chapter defines the AST for B-Minor, the C-like language used for the course project, as five C structures: declarations, statements, expressions, types and parameters. It distinguishes these terms carefully, shows how each kind of program fragment maps to tree nodes, and ends by building the whole tree automatically from Bison actions.

Chapter 7: Semantic Analysis

Semantic analysis is presented as name resolution followed by type checking. The chapter first surveys type systems along three axes (safe or unsafe, static or dynamic, explicit or implicit), with short examples in C, C#, Go and Rust, and discusses design choices such as structures, unions, variant types and conversions between unlike types. It then specifies the strict B-Minor type system, builds a nested symbol table with a scope stack, resolves names in declarations and expressions, implements expr_typecheck and stmt_typecheck, and gives advice on writing useful error messages.

Chapter 8: Intermediate Representations

The chapter compares several kinds of IR and their trade-offs. It starts with the AST itself, then moves to a directed acyclic graph in which common subexpressions are shared and constant folding is easy, followed by control-flow graphs, static single assignment form, linear (three-address) IR and stack-machine IR. Real examples from GCC's GIMPLE, LLVM and the Java Virtual Machine show how production systems apply these ideas.

Chapter 9: Memory Organization

Before generating code, the book explains how a running program uses memory: logical segments for code, data, heap and stack, and how hardware segmentation gave way to paging. It shows a simple linked-list implementation of malloc and free, compares stack-based and register-based calling conventions, explains how the compiler locates globals, locals, parameters and array elements, and describes program loading.

Chapter 10: Assembly Language

Thain claims that a compiler needs only a small subset of an instruction set, around 30 instructions, and teaches it for two architectures in parallel, self-contained sections. For X86-64 and then ARM, the chapter covers registers and data types, addressing modes, arithmetic, comparisons and jumps or branches, the stack, the calling convention (System V ABI for X86), and complete leaf and non-leaf functions, finishing with the differences in 64-bit ARM.

Chapter 11: Code Generation

This chapter produces working X86-64 code by a deliberately simple method that treats each AST node on its own. It sets up helper functions for scratch registers and labels, then writes expr_codegen as a post-order traversal, handles function calls, generates statements, conditional expressions and declarations, and points to the next chapter for better code. The exercises ask for the complete code generator, a comparison with gcc output, and an optional second back end for ARM or LLVM.

Chapter 12: Optimization

The final chapter is an overview, not a full treatment. It distinguishes local, global and interprocedural optimization, and first advises programmers to fix algorithms and profile before relying on the compiler. It then describes high-level transformations (constant folding, strength reduction, loop unrolling, code hoisting, function inlining, dead-code detection), low-level ones (peephole optimization and instruction selection by tree coverage), and register allocation using live ranges, conflict graphs and graph colouring. Short sections warn about optimizations that change program meaning and about how optimizations interact.

Appendices A–C: Sample Course Project, The B-Minor Language, Coding Conventions

Appendix A lays out the semester project as a series of assignments (scanner, parser, pretty-printer, typechecker, optional IR, code generator, optional language extension). Appendix B describes B-Minor by example rather than by formal grammar, on purpose, so students must extract the precise specification themselves. Appendix C lists the author's coding rules for C projects, such as using version control, moving "from working to working" and deleting dead code.

Key Concepts

Chapters 1–2: Introduction and A Quick Tour

• Compiler versus interpreter: a compiler emits a translated program, while an interpreter executes the source directly; JIT compilation mixes the two.
• Compiler stages: scanner, parser, semantic routines, IR, optimizers and code generator, each consuming the previous stage's output.

Chapter 3: Scanning

• Regular expressions and finite automata: equivalent descriptions of token patterns; an RE becomes an NFA, then a DFA, which can be minimized.
• Scanner generator: a tool such as Flex that turns a list of regular expressions with C actions into scanner code.

Chapter 4: Parsing

• Context-free grammar: rules with a single non-terminal on the left, able to describe nested structures that regular expressions cannot.
• LL(1) parsing: top-down parsing that chooses a rule from the current non-terminal and one token of lookahead, usually written as recursive descent.
• LR parsing: bottom-up shift-reduce parsing driven by an automaton; LALR is the practical compromise used by generators.

Chapters 5–6: Parsing in Practice and The Abstract Syntax Tree

• Bison actions: C code attached to grammar rules, used to validate, interpret, or build tree nodes during the parse.
• Abstract syntax tree: a tree of declarations, statements, expressions, types and parameters that records program structure without parsing details.

Chapter 7: Semantic Analysis

• Type system axes: safe/unsafe, static/dynamic and explicit/implicit, which together describe how a language checks values.
• Symbol table: a stack of scopes mapping names to declarations, used to resolve every identifier before type checking.

Chapter 8: Intermediate Representations

• DAG: a simplified, graph-shaped IR that shares common subexpressions and makes constant folding straightforward.
• Static single assignment (SSA): a form in which each variable is assigned exactly once, simplifying many analyses.

Chapters 9–10: Memory Organization and Assembly Language

• Logical segments: the conventional layout of code, data, heap and stack in a process's address space.
• Calling convention: the agreed rules for passing arguments, returning values and saving registers, such as the System V ABI.

Chapters 11–12: Code Generation and Optimization

• Post-order code generation: emitting instructions for a node after its children, with scratch registers holding intermediate values.
• Register allocation by graph colouring: building a conflict graph from live ranges and colouring it so that conflicting variables get different registers.
• Strength reduction: replacing an expensive operation with a cheaper equivalent, for example a multiplication by a shift.

Critical Analysis

Strengths

• One project from start to finish. Every chapter feeds a single compiler for B-Minor, and the exercises are mostly code that extends it. Appendix A turns this into a ready-made sequence of assignments, which makes the book easy to adopt for a one-semester course.
• Concrete, real tools and targets. Readers write C, use Flex and Bison, read GIMPLE, LLVM and JVM examples, and generate real X86-64 (with a parallel ARM treatment). The claim that about 30 instructions are enough keeps assembly manageable.
• Language design is part of the story. The chapter on semantic analysis compares type-system choices across C, C#, Go and Rust, and B-Minor itself is designed with deliberate quirks (Pascal-style type syntax, a print statement that needs type inference, operators that need runtime support) to provoke discussion.
• Short and readable. At around 230 pages, the book explains each algorithm with a small worked example (subset construction, LR automata, a DAG for x=(a+10)*(a+10), a register-conflict graph) instead of dense formal notation.

Limitations

• Light on optimization and analysis. The author says this openly: Chapter 12 is a tour, SSA form appears only briefly in Chapter 8, and analyses such as liveness and reachability are sketched rather than developed. Students heading into compiler research need a more advanced text afterwards.
• Assumes C and some architecture knowledge. The code is C throughout, and Chapters 9–10 move quickly through memory layout and calling conventions; students without a systems or computer organization course will find these demanding.
• Uneven exercises. Chapters 3 and 4 have pencil-and-paper problems, but Chapters 9 and 10 have no exercises at all, and the project language is deliberately specified only by example, which requires an instructor or careful reading to resolve ambiguities.
• Narrow language coverage. The model is a statically typed, C-like procedural language. Garbage collection, closures and object-oriented features are not covered, and dynamic typing appears only in the general discussion of Chapter 7.

Where It Fits in the Course

Within this course list, Thain's book is the compact, project-driven option, alongside Robert Nystrom's Crafting Interpreters. The two complement each other: Nystrom builds interpreters for a dynamically typed language with hand-written parsers, while Thain builds a compiler for a statically typed language, covers grammar theory (LL and LR parsing) and scanner and parser generators, and ends at real assembly code. Students who want to understand both the theory behind parsing and the path to native code should start with Thain.

Cooper and Torczon's Engineering a Compiler and Aho, Lam, Sethi and Ullman's Compilers: Principles, Techniques, and Tools are the natural next steps; Thain himself recommends the latter as a comprehensive graduate-level reference, and both are generally described as covering optimization and analysis far more deeply than Chapter 12 does. Pierce's Types and Programming Languages, which Chapter 7 lists for further reading, is the place to go for the formal side of type systems that Thain treats only informally.

How to Use This Book

The book is written for undergraduates who already program comfortably in C and have taken data structures and an introductory computer organization or architecture course. No previous compiler or formal-language background is assumed; automata and grammars are developed from scratch in Chapters 3 and 4.

For a semester course or self-study, follow the order of the book and the assignments in Appendix A. Chapters 1–2 can be read in one sitting. Work through Chapter 3 with Flex and Chapters 4–5 with Bison, doing the paper exercises on FIRST/FOLLOW sets and LR automata, since these are what most courses examine. Chapters 6 and 7 are the core of the project (the AST and the type checker). Chapter 8 can be skimmed if you generate code straight from the AST, as the author does in his own course. Read Chapters 9 and 10 before writing Chapter 11's code generator; choose X86 or ARM and read only that half of Chapter 10 at first. Treat Chapter 12 as a menu of extensions for the final weeks.

Test every stage with small programs before moving on, and compare your output with gcc -S, as the exercises suggest. The author's website links to a GitHub repository with example scanners and parsers, starter code and test cases for each stage.

Edition and Sources

This guide is based on the second edition (2020), read in the complete free PDF (compilerbook.pdf, revision dated 28 July 2026) from the author's official page, https://dthain.github.io/books/compiler/ (also reachable as compilerbook.org). It draws on the contributions page, full table of contents and list of figures, all twelve chapters (Chapters 1–2 in full; for Chapters 3–12 the openings, every section heading, the central worked examples and the end-of-chapter exercises and further reading), and Appendices A–C.