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
- 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
- C-minor Language
- Overview
- Tokens
- Types
- Expressions
- Declarations & statements
- Functions
- Optional elements