You are previewing Modern Compiler Implementation in Java, Second Edition.
O'Reilly logo
Modern Compiler Implementation in Java, Second Edition

Book Description

This textbook describes all phases of a compiler: lexical analysis, parsing, abstract syntax, semantic actions, intermediate representations, instruction selection via tree matching, dataflow analysis, graph-coloring register allocation, and runtime systems. It includes good coverage of current techniques in code generation and register allocation, as well as the compilation of functional and object-oriented languages, that is missing from most books. The most accepted and successful techniques are described concisely, rather than as an exhaustive catalog of every possible variant, and illustrated with actual Java classes. The first part of the book, Fundamentals of Compilation, is suitable for a one-semester first course in compiler design. The second part, Advanced Topics, which includes the compilation of object-oriented and functional languages, garbage collection, loop optimization, SSA form, instruction scheduling, and optimization for cache-memory hierarchies, can be used for a second-semester or graduate course. This new edition has been extensively rewritten to include more discussion of Java and object-oriented programming concepts, such as visitor patterns. A unique feature is the newly redesigned compiler project in Java, for a subset of Java itself. The project includes both front-end and back-end phases, so that students can build a complete working compiler in one semester.

Table of Contents

  1. Cover
  2. Title Page
  3. Copyright Page
  4. Contents
  5. Preface
  6. Part I Fundamentals of Compilation
    1. 1 Introduction
      1. 1.1 Modules and interfaces
      2. 1.2 Tools and software
      3. 1.3 Data structures for tree languages
    2. 2 Lexical Analysis
      1. 2.1 Lexical tokens
      2. 2.2 Regular expressions
      3. 2.3 Finite automata
      4. 2.4 Nondeterministic finite automata
      5. 2.5 Lexical-analyzer generators
    3. 3 Parsing
      1. 3.1 Context-free grammars
      2. 3.2 Predictive parsing
      3. 3.3 LR parsing
      4. 3.4 Using parser generators
      5. 3.5 Error recovery
    4. 4 Abstract Syntax
      1. 4.1 Semantic actions
      2. 4.2 Abstract parse trees
      3. 4.3 Visitors
    5. 5 Semantic Analysis
      1. 5.1 Symbol tables
      2. 5.2 Type-checking MiniJava
    6. 6 Activation Records
      1. 6.1 Stack frames
      2. 6.2 Frames in the MiniJava compiler
    7. 7 Translation to Intermediate Code
      1. 7.1 Intermediate representation trees
      2. 7.2 Translation into trees
      3. 7.3 Declarations
    8. 8 Basic Blocks and Traces
      1. 8.1 Canonical trees
      2. 8.2 Taming conditional branches
    9. 9 Instruction Selection
      1. 9.1 Algorithms for instruction selection
      2. 9.2 CISC machines
      3. 9.3 Instruction selection for the MiniJava compiler
    10. 10 Liveness Analysis
      1. 10.1 Solution of dataflow equations
      2. 10.2 Liveness in the MiniJava compiler
    11. 11 Register Allocation
      1. 11.1 Coloring by simplification
      2. 11.2 Coalescing
      3. 11.3 Precolored nodes
      4. 11.4 Graph-coloring implementation
      5. 11.5 Register allocation for trees
    12. 12 Putting It All Together
  7. Part II Advanced Topics
    1. 13 Garbage Collection
      1. 13.1 Mark-and-sweep collection
      2. 13.2 Reference counts
      3. 13.3 Copying collection
      4. 13.4 Generational collection
      5. 13.5 Incremental collection
      6. 13.6 Baker's algorithm
      7. 13.7 Interface to the compiler
    2. 14 Object-Oriented Languages
      1. 14.1 Class extension
      2. 14.2 Single inheritance of data fields
      3. 14.3 Multiple inheritance
      4. 14.4 Testing class membership
      5. 14.5 Private fields and methods
      6. 14.6 Classless languages
      7. 14.7 Optimizing object-oriented programs
    3. 15 Functional Programming Languages
      1. 15.1 A simple functional language
      2. 15.2 Closures
      3. 15.3 Immutable variables
      4. 15.4 Inline expansion
      5. 15.5 Closure conversion
      6. 15.6 Efficient tail recursion
      7. 15.7 Lazy evaluation
    4. 16 Polymorphic Types
      1. 16.1 Parametric polymorphism
      2. 16.2 Polymorphic type-checking
      3. 16.3 Translation of polymorphic programs
      4. 16.4 Resolution of static overloading
    5. 17 Dataflow Analysis
      1. 17.1 Intermediate representation for flow analysis
      2. 17.2 Various dataflow analyses
      3. 17.3 Transformations using dataflow analysis
      4. 17.4 Speeding up dataflow analysis
      5. 17.5 Alias analysis
    6. 18 Loop Optimizations
      1. 18.1 Dominators
      2. 18.2 Loop-invariant computations
      3. 18.3 Induction variables
      4. 18.4 Array-bounds checks
      5. 18.5 Loop unrolling
    7. 19 Static Single-Assignment Form
      1. 19.1 Converting to SSA form
      2. 19.2 Efficient computation of the dominator tree
      3. 19.3 Optimization algorithms using SSA
      4. 19.4 Arrays, pointers, and memory
      5. 19.5 The control-dependence graph
      6. 19.6 Converting back from SSA form
      7. 19.7 A functional intermediate form
    8. 20 Pipelining and Scheduling
      1. 20.1 Loop scheduling without resource bounds
      2. 20.2 Resource-bounded loop pipelining
      3. 20.3 Branch prediction
    9. 21 The Memory Hierarchy
      1. 21.1 Cache organization
      2. 21.2 Cache-block alignment
      3. 21.3 Prefetching
      4. 21.4 Loop interchange
      5. 21.5 Blocking
      6. 21.6 Garbage collection and the memory hierarchy
  8. Appendix: MiniJava Language Reference Manual
    1. A.1 Lexical Issues
    2. A.2 Grammar
    3. A.3 Sample Program
  9. Bibliography
  10. Index