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 52 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

Introduction

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

Lexical Analysis

• 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

• 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

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

Intermediate Representations

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

Optimizations

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

Machine Code Generation

• 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

• 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

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

Resources

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.