Introduction to Compiler Design

Preface
The Phases of a Compiler
Interpreters
Why Learn About Compilers?
About the Third Edition of the Book
To the Lecturer
Acknowledgements
Contents
List of Figures
1 Lexical Analysis
1.1 Regular Expressions
1.1.1 Shorthands
1.1.2 Examples
1.2 Nondeterministic Finite Automata
1.3 Converting a Regular Expression to an NFA
1.3.1 Optimisations
1.4 Deterministic Finite Automata
1.5 Converting an NFA to a DFA
1.5.1 Solving Set Equations
1.5.2 The Subset Construction
1.6 Size Versus Speed
1.7 Minimisation of DFAs
1.7.1 Example
1.7.2 Dead States
1.8 Lexers and Lexer Generators
1.8.1 Lexer Generators
1.9 Properties of Regular Languages
1.9.1 Relative Expressive Power
1.9.2 Limits to Expressive Power
1.9.3 Closure Properties
1.10 Further Reading
1.11 Exercises
References
2 Syntax Analysis
2.1 Context-Free Grammars
2.1.1 How to Write Context-Free Grammars
2.2 Derivation
2.2.1 Syntax Trees and Ambiguity
2.3 Operator Precedence
2.3.1 Rewriting Ambiguous Expression Grammars
2.4 Other Sources of Ambiguity
2.5 Syntax Analysis
2.6 Predictive Parsing
2.7 Nullable and FIRST
2.8 Predictive Parsing Revisited
2.9 Follow
2.10 A Larger Example
2.11 LL(1) Parsing
2.11.1 Recursive Descent
2.11.2 Table-Driven LL(1) Parsing
2.11.3 Conflicts
2.12 Rewriting a Grammar for LL(1) Parsing
2.12.1 Eliminating Left-Recursion
2.12.2 Left-Factorisation
2.12.3 Construction of LL(1) Parsers Summarised
2.13 SLR Parsing
2.14 Constructing SLR Parse Tables
2.14.1 Conflicts in SLR Parse-Tables
2.15 Using Precedence Rules in LR Parse Tables
2.16 Using LR-Parser Generators
2.16.1 Conflict Handling in Parser Generators
2.16.2 Declarations and Actions
2.16.3 Abstract Syntax
2.17 Properties of Context-Free Languages
2.18 Further Reading
2.19 Exercises
References
3 Scopes and Symbol Tables
3.1 Symbol Tables
3.1.1 Implementation of Symbol Tables
3.1.2 Simple Persistent Symbol Tables
3.1.3 A Simple Imperative Symbol Table
3.1.4 Efficiency Issues
3.1.5 Shared or Separate Name Spaces
3.2 Further Reading
3.3 Exercises
Reference
4 Interpretation
4.1 The Structure of an Interpreter
4.2 A Small Example Language
4.3 An Interpreter for the Example Language
4.3.1 Evaluating Expressions
4.3.2 Interpreting Function Calls
4.3.3 Interpreting a Program
4.4 Advantages and Disadvantages of Interpretation
4.5 Further Reading
4.6 Exercises
References
5 Type Checking
5.1 The Design Space of Type Systems
5.2 Attributes
5.3 Environments for Type Checking
5.4 Type Checking of Expressions
5.5 Type Checking of Function Declarations
5.6 Type Checking a Program
5.7 Advanced Type Checking
5.8 Further Reading
5.9 Exercises
References
6 Intermediate-Code Generation
6.1 Designing an Intermediate Language
6.2 The Intermediate Language
6.3 Syntax-Directed Translation
6.4 Generating Code from Expressions
6.4.1 Examples of Expression Translation
6.5 Translating Statements
6.5.1 Example of Statement Translation
6.6 Logical Operators
6.6.1 Sequential Logical Operators
6.6.2 Example of Translation of Conditions
6.7 Advanced Control Statements
6.8 Translating Structured Data
6.8.1 Floating-Point Values
6.8.2 Arrays
6.8.3 Strings
6.8.4 Records/Structs and Unions
6.9 Translation of Declarations
6.9.1 Simple Local Declarations
6.9.2 Translation of Function Declarations
6.10 Further Reading
6.11 Exercises
References
7 Machine-Code Generation
7.1 Conditional Jumps
7.2 Constants
7.3 Exploiting Complex Instructions
7.3.1 Two-Address Instructions
7.4 Optimisations
7.5 Further Reading
7.6 Exercises
References
8 Register Allocation
8.1 Liveness
8.2 Liveness Analysis
8.3 Interference
8.4 Register Allocation by Graph Colouring
8.5 Spilling
8.6 Heuristics
8.6.1 Removing Redundant Moves
8.6.2 Using Explicit Register Numbers
8.7 Further Reading
8.8 Exercises
References
9 Functions
9.1 The Call Stack
9.2 Activation Records
9.3 Prologues, Epilogues and Call-Sequences
9.4 Letting the Callee Save Registers
9.5 Caller-Saves Versus Callee-Saves
9.6 Using Registers to Pass Parameters
9.7 Interaction with the Register Allocator
9.8 Local Variables
9.9 Accessing Non-local Variables
9.9.1 Global Variables
9.9.2 Call-by-Reference Parameters
9.10 Functions as Parameters
9.11 Variants
9.11.1 Variable-Sized Frames
9.11.2 Variable Number of Parameters
9.11.3 Direction of Stack-Growth and Position of italic upper F upper PFP
9.11.4 Register Stacks
9.12 Optimisations for Function Calls
9.12.1 Inlining
9.12.2 Tail-Call Optimisation
9.13 Further Reading
9.14 Exercises
References
10 Data-Flow Analysis and Optimisation
10.1 Data-Flow Analysis
10.2 How to Design a Data-Flow Analysis
10.3 Liveness Analysis
10.3.1 Improving Liveness Analysis
10.4 Generalising from Liveness Analysis
10.5 Common Subexpression Elimination
10.5.1 Available Assignments
10.5.2 Example of Available-Assignments Analysis
10.5.3 Using Available Assignment Analysis for Common Subexpression Elimination
10.6 Index-Check Elimination
10.7 Jump-to-Jump Elimination
10.8 Resources Used by Data-Flow Analysis
10.9 Pointer Analysis
10.10 Limitations of Data-Flow Analyses
10.11 SSA Form
10.11.1 Transforming to SSA Form
10.11.2 Using the SSA Form
10.12 Further Reading
10.13 Exercises
References
11 Optimisations for Loops
11.1 Loops
11.2 Code Hoisting
11.3 Memory Prefetching
11.4 Incrementalisation
11.4.1 Rules for Incrementalisation
11.5 Further Reading
11.6 Exercises
Reference
12 More Language Features
12.1 Parametric Polymorphism
12.1.1 Implementing Templates
12.1.2 Variants
12.2 Garbage Collection
12.2.1 Identifying Pointers
12.2.2 The Freelist
12.2.3 Manual Freeing
12.2.4 The Mark Phase
12.2.5 The Sweep Phase
12.2.6 Tying the Knots
12.2.7 Remarks About Heap Memory Management
12.3 Pattern Matching
12.4 Further Reading
12.5 Exercises
References
Appendix A Set Notation and Concepts
A.1 Basic Concepts and Notation
A.1.1 Operations and Predicates
A.1.2 Properties of Set Operations
A.2 Set-Builder Notation
A.3 Sets of Sets
A.4 Set Equations
A.4.1 Monotonic Set Functions
A.4.1.1 Fixed-Point Iteration
A.4.2 Distributive Functions
A.4.3 Simultaneous Equations
Index