User:Whiteknight/Compiler Design

From Wikibooks, open books for an open world
Jump to navigation Jump to search
This page is an outline for a proposed book or project. This is only a planning page, not an actual book.
  1. Do not add sub-pages to this outline.
  2. Any user may edit this outline, but Whiteknight maintains complete editorial control on this page.
  3. This page may be deleted without warning.

This outline was last edited on 17 September 2007. Last edit over 135 months ago. Please update.

(Whiteknight) (Discuss) (Book Foundry) (Current Books) (VBD Edit)

This is going to serve as a rewrite of the Compiler Construction book. --Whiteknight (talk) (projects) 00:47, 17 April 2007 (UTC)


Table of Contents[edit]


  • Introduction (what is a compiler, compiler components, uses of compiler techniques)
  • Programming Languages (types of languages, evolution of, features, commonality, etc)

Lexical Analysis[edit]

  • Terminology (Lexeme, Token, Pattern, Grammar, Etc)
  • Grammars (recap of regular expressions, syntax-free grammars, formal languages)
  • Automata (recap of automata, transition diagrams, NFA, DFA, etc)
  • Translation Algorithms (Regex <-> DFA, DFA <-> NFA, etc)
  • Lexical Analyzer Generators (introduction to Lex/Flex, brew your own, etc)

Syntax Analysis[edit]

  • Introduction to parsers (Lexical Analysis v. Syntax Analysis)
  • Grammars (left and right recursion, left and right factoring, non-context-free constructions)
  • Top-Down Parsing (LL Parsing, non-recursive predictive parsing, Recursive-descent)
  • Bottom-Up Parsing
  • LR Parsing
  • LALR parsing
  • Parser Generators (Yacc/Bison, brew your own, etc)

Syntax-Directed Translations[edit]

  • Syntax Directed Definitions
  • Evaluation Orders (L- and S-Attributed definitions)
  • Translation Schemes
  • Implementations

Intermediate Representations[edit]

  • Syntax Trees
  • Three-Address Code
  • Ideal Stack Code
  • Translation of Expressions
  • Type Checking
  • Control Flow
  • Backpatching


  • Introduction to Optimizations
  • Data Flow Analysis
  • Partial Redundancy Elimination
  • Flow Graphs
  • Region-Based Analysis
  • Symbolic Analysis

Machine Code Generation[edit]

  • Target Language
  • Address Allocation
  • Blocks and Flow Graphs
  • Block Optimization
  • Peephole Optimization
  • Register Allocation
  • Tree Rewriting
  • Optimal code generation
  • Dynamic programming code generation

Instruction-Level Parallelism[edit]

  • Parallel processor architectures
  • Scheduling and Arbitration
  • Loop Unwrapping
  • Affine Transforms
  • Iteration spaces
  • Affine Array Indexes
  • Data Reuse
  • Data-dependence analysis
  • Synchronization-Free Parallelism
  • Locality Optimizations

Storage and Memory[edit]

  • Storage Allocation (stacks, local and nonlocal data)
  • Heaps and dynamic data allocation
  • Garbage Collection (reachability, trace-based collection, short-pause collection)


The original outline was based, in part on:

  • A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman, "Compilers: Principles, Techniques, & Tools", Pearson/Addison Wesley, Boston, 2006.