Textbook in PDF format

Introduction
What is a compiler?
The phases of a compiler
Interpreters
Why learn about compilers?
The structure of this book
To the lecturer
Acknowledgements
Permission to use
Lexical Analysis
Introduction
Regular expressions
Shorthands
Examples
Nondeterministic finite automata
Converting a regular expression to an NFA
Optimisations
Deterministic finite automata
Converting an NFA to a DFA
Solving set equations
The subset construction
Size versus speed
Minimisation of DFAs
Example
Dead states
Lexers and lexer generators
Lexer generators
Properties of regular languages
Relative expressive power
Limits to expressive power
Closure properties
Further reading
Exercises
Syntax Analysis
Introduction
Context-free grammars
How to write context free grammars
Derivation
Syntax trees and ambiguity
Operator precedence
Rewriting ambiguous expression grammars
Other sources of ambiguity
Syntax analysis
Predictive parsing
Nullable and FIRST
Predictive parsing revisited
FOLLOW
A larger example
LL(1) parsing
Recursive descent
Table-driven LL(1) parsing
Conflicts
Rewriting a grammar for LL(1) parsing
Eliminating left-recursion
Left-factorisation
Construction of LL(1) parsers summarized
SLR parsing
Constructing SLR parse tables
Conflicts in SLR parse-tables
Using precedence rules in LR parse tables
Using LR-parser generators
Declarations and actions
Abstract syntax
Conflict handling in parser generators
Properties of context-free languages
Further reading
Exercises
Scopes and Symbol Tables
Introduction
Symbol tables
Implementation of symbol tables
Simple persistent symbol tables
A simple imperative symbol table
Efficiency issues
Shared or separate name spaces
Further reading
Exercises
Interpretation
Introduction
The structure of an interpreter
A small example language
An interpreter for the example language
Evaluating expressions
Interpreting function calls
Interpreting a program
Advantages and disadvantages of interpretation
Further reading
Exercises
Type Checking
Introduction
The design space of types
Attributes
Environments for type checking
Type checking expressions
Type checking of function declarations
Type checking a program
Advanced type checking
Further reading
Exercises
Intermediate-Code Generation
Introduction
Choosing an intermediate language
The intermediate language
Syntax-directed translation
Generating code from expressions
Examples of translation
Translating statements
Logical operators
Sequential logical operators
Advanced control statements
Translating structured data
Floating-point values
Arrays
Strings
Records/structs and unions
Translating declarations
Example: Simple local declarations
Further reading
Exercises
Machine-Code Generation
Introduction
Conditional jumps
Constants
Exploiting complex instructions
Two-address instructions
Optimisations
Further reading
Exercises
Register Allocation
Introduction
Liveness
Liveness analysis
Interference
Register allocation by graph colouring
Spilling
Heuristics
Removing redundant moves
Using explicit register numbers
Further reading
Exercises
Function calls
Introduction
The call stack
Activation records
Prologues, epilogues and call-sequences
Caller-saves versus callee-saves
Using registers to pass parameters
Interaction with the register allocator
Accessing non-local variables
Global variables
Call-by-reference parameters
Nested scopes
Variants
Variable-sized frames
Variable number of parameters
Direction of stack-growth and position of FP
Register stacks
Functions as values
Further reading
Exercises
Analysis and optimisation
Data-flow analysis
Common subexpression elimination
Available assignments
Example of available-assignments analysis
Using available assignment analysis for common subexpression elimination
Jump-to-jump elimination
Index-check elimination
Limitations of data-flow analyses
Loop optimisations
Code hoisting
Memory prefetching
Optimisations for function calls
Inlining
Tail-call optimisation
Specialisation
Further reading
Exercises
Memory management
Introduction
Static allocation
Limitations
Stack allocation
Heap allocation
Manual memory management
A simple implementation of malloc and free
Joining freed blocks
Sorting by block size
Summary of manual memory management
Automatic memory management
Reference counting
Tracing garbage collectors
Scan-sweep collection
Two-space collection
Generational and concurrent collectors
Summary of automatic memory management
Further reading
Exercises
Bootstrapping a compiler
Introduction
Notation
Compiling compilers
Full bootstrap
Further reading
Exercises
Set notation and concepts
Basic concepts and notation
Operations and predicates
Properties of set operations
Set-builder notation
Sets of sets
Set equations
Monotonic set functions
Distributive functions
Simultaneous equations
Exercises