Modern Compiler Implementation in Java

by Andrew W. Appel , With Jens Palsberg

• ISBN13: 9780521820608
• ISBN10: 052182060X
• Edition: 2nd
• Format: Hardcover
• Copyright: 2002-10-21
• Publisher: Cambridge University Press

Summary

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

Preface	ix
Part I Fundamentals of Compilation
Introduction	3	(13)
Modules and interfaces	4	(1)
Tools and software	5	(2)
Data structures for tree languages	7	(9)
Lexical Analysis	16	(22)
Lexical tokens	17	(1)
Regular expressions	18	(3)
Finite automata	21	(3)
Nondeterministic finite automata	24	(6)
Lexical-analyzer generators	30	(8)
Parsing	38	(48)
Context-free grammars	40	(5)
Predictive parsing	45	(10)
LR parsing	55	(13)
Using parser generators	68	(8)
Error recovery	76	(10)
Abstract Syntax	86	(17)
Semantic actions	86	(3)
Abstract parse trees	89	(4)
Visitors	93	(10)
Semantic Analysis	103	(13)
Symbol tables	103	(8)
Type-checking MiniJava	111	(5)
Activation Records	116	(20)
Stack frames	118	(8)
Frames in the MiniJava compiler	126	(10)
Translation to Intermediate Code	136	(26)
Intermediate representation trees	137	(3)
Translation into trees	140	(15)
Declarations	155	(7)
Basic Blocks and Traces	162	(14)
Canonical trees	163	(6)
Taming conditional branches	169	(7)
Instruction Selection	176	(27)
Algorithms for instruction selection	179	(8)
CISC machines	187	(3)
Instruction selection for the MiniJava compiler	190	(13)
Liveness Analysis	203	(16)
Solution of dataflow equations	205	(9)
Liveness in the Minijava compiler	214	(5)
Register Allocation	219	(30)
Coloring by simplification	220	(3)
Coalescing	223	(4)
Precolored nodes	227	(5)
Graph-coloring implementation	232	(9)
Register allocation for trees	241	(8)
Putting It All Together	249	(8)
Part II Advanced Topics
Garbage Collection	257	(26)
Mark-and-sweep collection	257	(5)
Reference counts	262	(2)
Copying collection	264	(5)
Generational collection	269	(3)
Incremental collection	272	(2)
Baker's algorithm	274	(1)
Interface to the compiler	275	(8)
Object-Oriented Languages	283	(15)
Class extension	283	(1)
Single inheritance of data fields	284	(2)
Multiple inheritance	286	(3)
Testing class membership	289	(3)
Private fields and methods	292	(1)
Classless languages	293	(1)
Optimizing object-oriented programs	293	(5)
Functional Programming Languages	298	(37)
A simple functional language	299	(2)
Closures	301	(1)
Immutable variables	302	(6)
Inline expansion	308	(8)
Closure conversion	316	(3)
Efficient tail recursion	319	(2)
Lazy evaluation	321	(14)
Polymorphic Types	335	(15)
Parametric polymorphism	336	(3)
Polymorphic type-checking	339	(5)
Translation of polymorphic programs	344	(3)
Resolution of static overloading	347	(3)
Dataflow Analysis	350	(26)
Intermediate representation for flow analysis	351	(3)
Various dataflow analyses	354	(5)
Transformations using dataflow analysis	359	(1)
Speeding up dataflow analysis	360	(9)
Alias analysis	369	(7)
Loop Optimizations	376	(23)
Dominators	379	(5)
Loop-invariant computations	384	(1)
Induction variables	385	(6)
Array-bounds checks	391	(4)
Loop unrolling	395	(4)
Static Single-Assignment Form	399	(41)
Converting to SSA form	402	(8)
Efficient Computation of the Dominator Tree	410	(7)
Optimization Algorithms Using SSA	417	(6)
Arrays, pointers, and memory	423	(2)
The control-dependence graph	425	(3)
Converting back from SSA form	428	(2)
A functional intermediate form	430	(10)
Pipelining and Scheduling	440	(24)
Loop scheduling without resource bounds	444	(4)
Resource-bounded loop pipelining	448	(8)
Branch prediction	456	(8)
The Memory Hierarchy	464	(20)
Cache organization	465	(3)
Cache-block alignment	468	(2)
Prefetching	470	(6)
Loop interchange	476	(1)
Blocking	477	(3)
Garbage collection and the memory hierarchy	480	(4)
Appendix: MiniJava Language Reference Manual	484	(3)
A.1 Lexical Issues	484	(1)
A.2 Grammar	484	(2)
A.3 Sample Program	486	(1)
Bibliography	487	(8)
Index	495