Introduction to Compiler Design

Höfundur: Torben Ægidius Mogensen (Útgáfa: 3)
Introduction to Compiler Design

Kaup valmöguleikar

The third edition of this textbook has been fully revised and adds material about the SSA form, polymorphism, garbage collection, and pattern matching. It presents techniques for making realistic compilers for simple to intermediate-complexity programming languages. The techniques presented in the book are close to those used in professional compilers, albeit in places slightly simplified for presentation purposes.

"Further reading" sections point to  material about the full versions of the techniques. All phases required for translating a high-level language to symbolic machine language are covered, and some techniques for optimising code are presented. Type checking and interpretation are also included. Aiming to be neutral with respect to implementation languages, algorithms are mostly presented in pseudo code rather than in any specific language, but suggestions are in many places given for how these can be realised in different language paradigms.

Nánar um bókina

Útgefandi
Springer Nature
ISBN
9783031464607
Print ISBN
9783031464591
Format
ePub
Útgáfa
3
Höfundar
Torben Ægidius Mogensen
Tungumál
English
Útgefið
2024-01-01
Prent takmörkun á líftíma
100
Prent takmörkun
2
Afritunar takmörkun
2

Kaflar

  • Undergraduate Topics in Computer Science
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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.2.1 Allocating Arrays
  • 6.8.2.2 Multi-dimensional Arrays
  • 6.8.2.3 Index Checks
  • 6.8.2.4 Non-zero-based 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
  • 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
  • 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
  • 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 FP
  • 9.11.4 Register Stacks
  • 9.12 Optimisations for Function Calls
  • 9.12.1 Inlining
  • 9.12.2 Tail-Call Optimisation
  • 9.12.2.1 Tail-Recursion Optimisation
  • 9.12.2.2 Identifying Tail Calls
  • 9.13 Further Reading
  • 9.14 Exercises
  • 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
  • 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
  • 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
  • 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