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 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 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
    Chapter 1: Intro
  • Language processors
  • Compiler structure
  • Evolution
  • Building
  • Applications
  • Programming language basics
    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 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 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
    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
    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
    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