User:Whiteknight/Compiler Design

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 207 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)

Preface

edit

Table of Contents

edit

Introduction

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

Optimizations

edit
  • 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)

Resources

edit

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.