Author(s): Douglas Thain
Edition: 2
Year: 2020
Language: English
Pages: 247
Introduction
What is a compiler?
Why should you study compilers?
What's the best way to learn about compilers?
What language should I use?
How is this book different from others?
What other books should I read?
A Quick Tour
The Compiler Toolchain
Stages Within a Compiler
Example Compilation
Exercises
Scanning
Kinds of Tokens
A Hand-Made Scanner
Regular Expressions
Finite Automata
Deterministic Finite Automata
Nondeterministic Finite Automata
Conversion Algorithms
Converting REs to NFAs
Converting NFAs to DFAs
Minimizing DFAs
Limits of Finite Automata
Using a Scanner Generator
Practical Considerations
Exercises
Further Reading
Parsing
Overview
Context Free Grammars
Deriving Sentences
Ambiguous Grammars
LL Grammars
Eliminating Left Recursion
Eliminating Common Left Prefixes
First and Follow Sets
Recursive Descent Parsing
Table Driven Parsing
LR Grammars
Shift-Reduce Parsing
The LR(0) Automaton
SLR Parsing
LR(1) Parsing
LALR Parsing
Grammar Classes Revisited
The Chomsky Hierarchy
Exercises
Further Reading
Parsing in Practice
The Bison Parser Generator
Expression Validator
Expression Interpreter
Expression Trees
Exercises
Further Reading
The Abstract Syntax Tree
Overview
Declarations
Statements
Expressions
Types
Putting it All Together
Building the AST
Exercises
Semantic Analysis
Overview of Type Systems
Designing a Type System
The B-Minor Type System
The Symbol Table
Name Resolution
Implementing Type Checking
Error Messages
Exercises
Further Reading
Intermediate Representations
Introduction
Abstract Syntax Tree
Directed Acyclic Graph
Control Flow Graph
Static Single Assignment Form
Linear IR
Stack Machine IR
Examples
GIMPLE - GNU Simple Representation
LLVM - Low Level Virtual Machine
JVM - Java Virtual Machine
Exercises
Further Reading
Memory Organization
Introduction
Logical Segmentation
Heap Management
Stack Management
Stack Calling Convention
Register Calling Convention
Locating Data
Program Loading
Further Reading
Assembly Language
Introduction
Open Source Assembler Tools
X86 Assembly Language
Registers and Data Types
Addressing Modes
Basic Arithmetic
Comparisons and Jumps
The Stack
Calling a Function
Defining a Leaf Function
Defining a Complex Function
ARM Assembly
Registers and Data Types
Addressing Modes
Basic Arithmetic
Comparisons and Branches
The Stack
Calling a Function
Defining a Leaf Function
Defining a Complex Function
64-bit Differences
Further Reading
Code Generation
Introduction
Supporting Functions
Generating Expressions
Generating Statements
Conditional Expressions
Generating Declarations
Exercises
Optimization
Overview
Optimization in Perspective
High Level Optimizations
Constant Folding
Strength Reduction
Loop Unrolling
Code Hoisting
Function Inlining
Dead Code Detection and Elimination
Low-Level Optimizations
Peephole Optimizations
Instruction Selection
Register Allocation
Safety of Register Allocation
Priority of Register Allocation
Conflicts Between Variables
Global Register Allocation
Optimization Pitfalls
Optimization Interactions
Exercises
Further Reading
Sample Course Project
Scanner Assignment
Parser Assignment
Pretty-Printer Assignment
Typechecker Assignment
Optional: Intermediate Representation
Code Generator Assignment
Optional: Extend the Language
The B-Minor Language
Overview
Tokens
Types
Expressions
Declarations and Statements
Functions
Optional Elements
Coding Conventions
Index
