Dragon Book (Compiler) Table of Contents
By Xah Lee. Date: . Last updated: .
1 Introduction
- 1.1 Language Processors
- 1.2 The Structure of a Compiler
- 1.3 The Evolution of Programming Languages
- 1.4 The Science of Building a Compiler
- 1.5 Applications of Compiler Technology
- 1.6 Programming Language Basics
- 1.7 Summary of Chapter 1
- 1.8 References for Chapter 1
2 A Simple Syntax-Directed Translator
- 2.1 Introduction
- 2.2 Syntax Definition
- 2.3 Syntax-Directed Translation
- 2.4 Parsing
- 2.5 A Translator for Simple Expressions
- 2.6 Lexical Analysis
- 2.7 Symbol Tables
- 2.8 Intermediate Code Generation
- 2.9 Summary of Chapter 2
3 Lexical Analysis
- 3.1 The Role of the Lexical Analyzer
- 3.2 Input Buffering
- 3.3 Specification of Tokens
- 3.4 Recognition of Tokens
- 3.5 The Lexical-Analyzer Generator Lex
- 3.6 Finite Automata
- 3.7 From Regular Expressions to Automata
- 3.8 Design of a Lexical-Analyzer Generator
- 3.9 Optimization of DFA-Based Pattern Matchers
- 3.10 Summary of Chapter 3
- 3.11 References for Chapter 3
4 Syntax Analysis
- 4.1 Introduction
- 4.2 Context-Free Grammars
- 4.3 Writing a Grammar
- 4.4 Top-Down Parsing
- 4.5 Bottom-Up Parsing
- 4.6 Introduction to LR Parsing: Simple LR
- 4.7 More Powerful LR Parsers
- 4.8 Using Ambiguous Grammars
- 4.9 Parser Generators
- 4.10 Summary of Chapter 4
- 4.11 References for Chapter 4
5 Syntax-Directed Translation
- 5.1 Syntax-Directed Definitions
- 5.2 Evaluation Orders for SDD's
- 5.3 Applications of Syntax-Directed Translation
- 5.4 Syntax-Directed Translation Schemes
- 5.5 Implementing L-Attributed SDD's
- 5.6 Summary of Chapter 5
- 5.7 References for Chapter 5
6 Intermediate-Code Generation
- 6.1 Variants of Syntax Trees
- 6.2 Three-Address Code
- 6.3 Types and Declarations
- 6.4 Translation of Expressions
- 6.5 Type Checking
- 6.6 Control Flow
- 6.7 Backpatching
- 6.8 Switch-Statements
- 6.9 Intermediate Code for Procedures
- 6.10 Summary of Chapter 6
- 6.11 References for Chapter 6
7 Run-Time Environments
- 7.1 Storage Organization
- 7.2 Stack Allocation of Space
- 7.3 Access to Nonlocal Data on the Stack
- 7.4 Heap Management
- 7.5 Introduction to Garbage Collection
- 7.6 Introduction to Trace-Based Collection
- 7.7 Short-Pause Garbage Collection
- 7.8 Advanced Topics in Garbage Collection
- 7.9 Summary of Chapter 7
- 7.10 References for Chapter 7
8 Code Generation
- 8.1 Issues in the Design of a Code Generator
- 8.2 The Target Language
- 8.3 Addresses in the Target Code
- 8.4 Basic Blocks and Flow Graphs
- 8.5 Optimization of Basic Blocks
- 8.6 A Simple Code Generator
- 8.7 Peephole Optimization
- 8.8 Register Allocation and Assignment
- 8.9 Instruction Selection by Tree Rewriting
- 8.10 Optimal Code Generation for Expressions
- 8.11 Dynamic Programming Code-Generation
- 8.12 Summary of Chapter 8
- 8.13 References for Chapter 8
9 Machine-Independent Optimizations
- 9.1 The Principal Sources of Optimization
- 9.2 Introduction to Data-Flow Analysis
- 9.3 Foundations of Data-Flow Analysis
- 9.4 Constant Propagation
- 9.5 Partial-Redundancy Elimination
- 9.6 Loops in Flow Graphs
- 9.7 Region-Based Analysis
- 9.8 Symbolic Analysis
- 9.9 Summary of Chapter 9
- 9.10 References for Chapter 9
10 Instruction-Level Parallelism
- 10.1 Processor Architectures
- 10.2 Code-Scheduling Constraints
- 10.3 Basic-Block Scheduling
- 10.4 Global Code Scheduling
- 10.5 Software Pipelining
- 10.6 Summary of Chapter 10
- 10.7 References for Chapter 10
11 Optimizing for Parallelism and Locality
- 11.1 Basic Concepts
- 11.2 Matrix Multiply: An In-Depth Example
- 11.3 Iteration Spaces
- 11.4 Affine Array Indexes
- 11.5 Data Reuse
- 11.6 Array Data-Dependence Analysis
- 11.7 Finding Synchronization-Free Parallelism
- 11.8 Synchronization Between Parallel Loops
- 11.9 Pipelining
- 11.10 Locality Optimizations
- 11.11 Other Uses of Affine Transforms
- 11.12 Summary of Chapter 11
- 11.13 References for Chapter 11
12 Interprocedural Analysis
- 12.1 Basic Concepts
- 12.2 Why Interprocedural Analysis?
- 12.3 A Logical Representation of Data Flow
- 12.4 A Simple Pointer-Analysis Algorithm
- 12.5 Context-Insensitive Interprocedural Analysis
- 12.6 Context-Sensitive Pointer Analysis
- 12.7 Datalog Implementation by BDD's
- 12.8 Summary of Chapter 12
- 12.9 References for Chapter 12
A A Complete Front End
- A.1 The Source Language
- A.2 Main
- A.3 Lexical Analyzer
- A.4 Symbol Tables and Types
- A.5 Intermediate Code for Expressions
- A.6 Jumping Code for Boolean Expressions
- A.7 Intermediate Code for Statements
- A.8 Parser
- A.9 Creating the Front End
B Finding Linearly Independent Solutions
Index
Book Covers