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.
(Whiteknight) (Discuss) (Book Foundry) (Current Books) (VBD Edit)
- Do not add sub-pages to this outline.
- Any user may edit this outline, but Whiteknight maintains complete editorial control on this page.
- This page may be deleted without warning.
This outline was last edited on 17 September 2007. Last edit over 207 months ago. Please update.
This is going to serve as a rewrite of the Compiler Construction book. --Whiteknight (talk) (projects) 00:47, 17 April 2007 (UTC)
Preface
editTable of Contents
editIntroduction
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
editThe 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.