Compilers: Principles, Techniques, and Tools

Citation

Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson.

Chapter Summary

The second edition has twelve chapters and two appendices in about 1,000 pages. Each chapter ends with a summary, and most also with a references section. Pearson describes the edition as completely revised, with three new chapters (10 to 12) on instruction-level parallelism, optimizing for parallelism and locality, and interprocedural analysis. The authors state that few readers will go on to construct a compiler, so the book keeps its focus on the broader problems of software design and development.

Chapter 1: Introduction

Language processors, the structure of a compiler, the evolution of programming languages, the science of building a compiler, and programming language basics. It sets out the phases that the rest of the book takes in turn.

Chapter 2: A Simple Syntax-Directed Translator

A small, complete front end: syntax definition, syntax-directed translation, parsing, a translator for simple expressions, lexical analysis, symbol tables and intermediate code generation. It gives a working overview before the later chapters treat each stage in depth.

Chapter 3: Lexical Analysis

The role of the lexical analyzer, input buffering, specification and recognition of tokens, the Lex generator, finite automata, the conversion of regular expressions to automata, the design of a lexical-analyzer generator and the optimization of DFA-based pattern matchers.

Chapter 4: Syntax Analysis

Context-free grammars, writing a grammar, top-down parsing, bottom-up parsing, simple LR parsing, more powerful LR parsers, using ambiguous grammars and parser generators.

Chapter 5: Syntax-Directed Translation

Syntax-directed definitions, evaluation orders, applications of syntax-directed translation, translation schemes and implementing L-attributed definitions.

Chapter 6: Intermediate-Code Generation

Variants of syntax trees, three-address code, types and declarations, translation of expressions, type checking, control flow, backpatching, switch statements and intermediate code for procedures.

Chapter 7: Run-Time Environments

Storage organization, stack allocation of space, access to nonlocal data, heap management, and four sections on garbage collection: an introduction, trace-based collection, short-pause collection and advanced topics.

Chapter 8: Code Generation

Issues in code-generator design, the target language, addresses in target code, basic blocks and flow graphs, optimization of basic blocks, a simple code generator, peephole optimization, register allocation and assignment, instruction selection by tree rewriting, and optimal code generation for expressions by dynamic programming.

Chapter 9: Machine-Independent Optimizations

The principal sources of optimization, an introduction to data-flow analysis, its foundations, constant propagation, partial-redundancy elimination, loops in flow graphs, region-based analysis and symbolic analysis.

Chapters 10–12: Instruction-Level Parallelism; Optimizing for Parallelism and Locality; Interprocedural Analysis

The new chapters of the second edition. Chapter 10 treats processor architectures, code-scheduling constraints, basic-block and global scheduling, and software pipelining. Chapter 11 develops basic concepts, matrix multiplication as an in-depth example, iteration spaces, affine array indexes, data reuse, array data-dependence analysis, synchronization-free parallelism and locality optimizations. Chapter 12 covers interprocedural analysis, including a logical representation of data flow, pointer analysis (context-insensitive and context-sensitive) and a Datalog implementation using BDDs.

Appendices

Appendix A, A Complete Front End, lists the source language, the main program, lexical analyzer, symbol tables and types, intermediate code generation, parser, and creating the front end. Appendix B covers finding linearly independent solutions.

Key Concepts

Chapters 1–5: The front end

• Regular expressions and finite automata: the tools for specifying and recognizing tokens.
• Context-free grammars and LR parsing: the formalism and the main bottom-up parsing algorithms.
• Syntax-directed definitions: attaching computation to grammar productions.

Chapters 6–8: Intermediate code and the back end

• Three-address code: the intermediate representation in Chapter 6.
• Garbage collection: reclaiming heap storage, treated in four sections.
• Register allocation and instruction selection: the code-generation decisions of Chapter 8.

Chapters 9–12: Optimization and analysis

• Data-flow analysis: the framework for reasoning about program properties along flow graphs.
• Software pipelining and iteration spaces: scheduling and loop-transformation ideas for parallelism and locality.
• Interprocedural and pointer analysis: analysis across procedure boundaries, expressed in Datalog.

Critical Analysis

Strengths

• End-to-end coverage. The twelve chapters follow the compiler from lexical analysis through parsing, translation and code generation to optimization, with front-end appendix code.
• Strong treatment of analysis and optimization. Chapters 9 to 12 devote four chapters to data-flow analysis, parallelism, locality and interprocedural analysis.
• Generators and theory together. Lex and parser generators sit beside the automata and grammar theory that underlie them. This pairing suits courses whose labs use tools such as lex and yacc alongside hand-built LL(1) and SLR(1) parsers.
• Consistent structure. Chapters end with summaries and references, and the second edition adds three chapters for modern architectures.

Limitations

• Heavy on the front end and theory for a first project. The book builds a large amount of automata and parsing theory before reaching code generation, so a student who wants a working compiler quickly may prefer a project-based text.
• Back-end topics are advanced. Chapters 10 to 12 treat instruction-level parallelism, affine loop analysis and Datalog-based pointer analysis; they are considerably more demanding than the earlier chapters.
• Dated by edition. This second edition appeared in 2006, twenty years after the first, so later developments in languages and processors are not covered.

Where It Fits in the Course

The Dragon Book is the classical, theory-rich compiler textbook on this reading list. Nystrom's Crafting Interpreters is a hands-on introduction in which the reader builds two interpreters, and is a gentler way to meet scanning, parsing and virtual machines before this book. Thain's Introduction to Compilers and Language Design is a compact, freely available text for a one-semester course built around one project. Cooper and Torczon's Engineering a Compiler covers scanning and parsing briefly and gives more attention to intermediate representations, optimization, instruction selection, scheduling and register allocation, so it is the closest alternative for an undergraduate course; the UT Austin course described below offers the two as optional alternatives without ranking them. Pierce's Types and Programming Languages is the graduate text on type systems and treats type systems far more fully than the type-checking section of Chapter 6.

How to Use This Book

The book suits upper-level undergraduates and beginning graduate students with solid data structures, basic automata and grammars, and some exposure to assembly-level programming. As one concrete benchmark, the UT Austin course below requires prior courses in computer organization and in programming (for example CS429 and CS312 or their ECE equivalents), and expects machine organization, assembly concepts, C++ and basic object-oriented programming.

A practical plan:

• Core for a first course: Chapters 1 to 8, with Chapter 2 read first as a small, whole compiler.
• Optimization: Chapter 9 as the introduction to data-flow analysis; it is also the basis for Chapters 10 to 12.
• Optional and advanced: Chapters 10 to 12, and Appendix A for the working front-end code.
• Garbage collection: Sections 7.5 to 7.8 can be set aside or read as a separate unit.

Pair the reading with a small compiler project; the Appendix A front end shows what a complete one looks like.

How courses use it

Neither course document below lists specific chapter or page assignments, so treat the book as a selective reference rather than a cover-to-cover assignment.

• Reference for a pipeline-and-lab course. A compiler theory and lab course page hosted on IIT Kharagpur's CSE site (course page), with notices dated 2025, lists the book under Books and References without marking it as required. The same list includes Holub's Compiler Design in C, Appel's Modern Compiler Implementation in C, Muchnick's Advanced Compiler Design and Implementation and a lex/yacc reference. Its lab assignments include Lex, LL(1) and SLR(1) parsing, lex/yacc integration, L-attributed grammars, intermediate code for assignments and backpatching. The book treats these topics in Chapters 3 to 6, but the page does not map assignments to textbook sections.
• Optional text for an optimization-oriented course. UT Austin's ECE479K Compilers (Fall 2025; syllabus) has no required textbook. It lists this book (2nd ed.) and Cooper and Torczon's Engineering a Compiler (3rd ed., 2022) as optional alternatives, noting that students are unlikely to need both. The course covers the front end and then concentrates on intermediate representations, runtime environments, control-flow and dataflow analysis, optimization, register allocation, instruction selection and instruction scheduling. Its labs, built on COOL and LLVM, move from parsing through intermediate-code generation and dataflow optimization to backend code generation and register allocation. In a course like this, the closest matches in the book are Chapters 6 to 9, plus the scheduling material in Chapter 10; study those concepts alongside the course's own COOL/LLVM tooling materials.

Edition notes

Both courses list the second edition, the edition listed here. ECE479K gives Addison-Wesley, September 2006. The IIT Kharagpur page gives Addison-Wesley, 2006, and also cites a 2014 Indian edition from Pearson. That 2014 printing is the same second edition, not a new numbered edition.