Perfectly Awesome
Posts by Topic
Posts by Date
Posts by Title
About
Compiler Theory - book notes
Chap 1: Intro
Definition
Phases
Interpreters
Why learn about compilers?
Book structure
Chap 2: Lexical analysis
Regexes
Non-deterministic finite automata (NFAs)
Regexes to NFAs
Deterministic FAs
NFAs to DFAs
Size vs speed
DFA minimization
Lexers & generators
Regular lanaguage properties
Chap 3: Syntax analysis
Context-free grammars
Derivation
Operator precedence
Other ambiguity sources
Syntax analysis
Predictive parsing
Nullable and FIRST
Predictive parsing (again)
FOLLOW
A larger example
LL(1) parsing
LL(1) parsing & grammar rewriting
SLR parsing
Building SLR parse tables
Precedence rules
LR-parser generators
Context-free language properties
Chap 4: Scopes & symbol tables
Symbol tables
Chap 5: Interpretation
Structure
Small example
Advantages & disadvantages
Chap 6: Type checking
Design space
Attributes
Environments
Type-checking Expressions
Type-checking Function declarations
Type-checking a program
Type-checking: advanced
Chap 7: Intermediate code generation
Intermediate language choices
The intermediate language
Syntax-directed translation
Code from expressions
Translating statements
Logical operators
Advanced control statements
Translating structured data
Translating declarations
Chap 8: Machine code generation
Conditional jumps
Constants
Complex instructions
Optimizations
Chap 9: Register allocation
Liveness
Liveness analysis
Interference
Using graph coloring
Spilling
Heuristics
Chap 10: Function calls
Activation records
Prologues, epilogies & call sequences
Caller-saves vs Callee-saves
Registers & parameter passing
Register allocator
Non-local variables
Variants
Chap 11: Analysis & optimization
Data flow analysis
Common sub-expression elimination
Jump-to-jump elimination
Index-check elimination
Data flow analysis - limitations
Loops
Function call
Specialization
Chap 12: Memory management
Static allocation
Stacks
Heaps
Manual allocation
Auto memory mgmt
Reference counts
Tracing garbage collectors
Summary
Chap 13: Bootstrapping a compiler
Notation
Compiling compilers
Appendix: set notation
Concepts & notation
Set-builder notation
Sets of sets
Set equations
Chapter 1: Intro
Language processors
Compiler structure
Evolution
Building
Applications
Programming language basics
Chapter 2: A simple syntax-directed translator
Syntax
Translation
Parsing
Simple expression translator
Lexical analysis
symbol tables
Intermediate code generation
Chapter 3: Lexical analysis
Role
Input buffering
Tokens
Token recognition
Lex
Finite automata
Regexes to automata
Lexical-analyzer generator design
DFA-based pattern match optimization
Chapter 4: Syntax analysis
Intro
Context-free grammars
Writing a grammar
Top-down parsing
Bottom-up parsing
LR parsing
Advanced LR parsing
Ambiguous grammars
Parser generators
Chapter 5: Syntax-directed translation
Syntax directed definitions (SDDs)
Evaluation order
Applications
Translation schemes
L-attributed SDD
Chapter 6: Intermediate code generation
Syntax tree variants
Three-address code
Types & declarations
Expression translation
Type checking
Control flow
Backpatching
Switch statements
Intermediate code for procedures
Chapter 7: Runtime environments
Storage
Stack allocation
Access to nonlocal data on the stack
Heaps
Garbage collection
Trace-based collection
Short-pause garbage collection
Advanced topics
Chapter 8: Code generation
Design issues
Target language
Target addresses
Basic blocks & flow graphs
Block optimization
Simple code generation
Peephole optimization
Register allocation
Instruction selection by tree rewriting
Optimal code generation for expressions
Dynamic programming code generations
Chapter 9: Machine-independent optimizations
Principal sources
Data flow analysis (DFA)
DFA foundations
Constant propagation
Partial-redundancy elimination
Loops in flow graphs
Region-based analysis
Symbolic analysis
Chapter 10: Instruction-level parallelism
CPU architectures
Code schedule constraints
Basic block scheduling
Global code scheduling
Pipelining
Chapter 11: Optimizing for parallelism & locality
Concepts
Matrix Multiplication
Iteration spaces
Affine array indexes
Data reuse
Array data-dependence analysis
Sync-free parallelism
Parallel loop synchronization
Pipelining
Locality
Affine transforms - other uses
Chapter 12: Inter-procedural analysis
Concepts
Why?
Local representation
Simple pointer-analysis algorithm
Context-insensitive analysis
Context-sensitive pointer analysis
Datalog implementation by binary decision diagrams
Appendix A: A complete front end
Source language
Main
Lexical analyzer
Symbol tables & types
Intermediate code
Jumping code for booleans
Intermediate code for statements
Parser
Creating the front end
Chapter B: Linearly indepedent solutions
Intro
Quick Tour
Toolchain
Stages
Example compilation
Scanning
Kinds of tokens
A hand-made scanner
Regexes
Conversion algorithms
Finite automata limitations
Practical considerations
Parsing
Overview
Context-free grammars
LL grammars
LR grammars
Chomsky hierarchy
Practical Parsing
Bison
Validator
Interpreter
Expression trees
Abstract Syntax Trees (ASTs)
Abstract syntax tree (AST) overview
Declarations
Statements
Expressions
Datatypes
Putting it all together
Building an AST
Semantic Analysis
Type systems
Design
C-Minor type system
Symbol tables
Name resolution
Type checking - implementation
Error messages
Intermediate Representations
Abstract syntax trees (ASTs)
Directed acyclic graphs (DAGs)
Control flow graphs
Static single assignment (SSA) form
Linear IR
Stack machine IR
Examples: GNU, LLVM, JVM
Memory
Logical segments
Heaps
Stacks
Locating data
Program loading
Assembly Language
Intro
Open-source assembler tools
x86
ARM
Resources
Code Generation
Intro
Supporting functions
Generating expressions
Generating statments
Conditional expressions
Generating declarations
Optimization
Overview
Perspective
High-level optimizations
Low-level optimizations
Register allocation
Pitfalls
Interactions
Sample Project
C-minor Language
Overview
Tokens
Types
Expressions
Declarations & statements
Functions
Optional elements
Coding Conventions