Introduction to Compiler Design

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

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.

Depending on how much of the material from the book is used, it is suitable for both undergraduate and graduate courses for introducing compiler design and implementation.

Author(s): Torben Ægidius Mogensen
Series: Undergraduate Topics in Computer Science
Edition: 3
Publisher: Springer
Year: 2024

Language: English
Commentary: Publisher EPUB | Published: 26 January 2024
Pages: xxii, 287
City: Cham
Tags: Compiler Design; Loop Optimization; Data-flow Analysis; Function Cell Optimization; Code Generation

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