Modern Compiler Implementation in C

Describes all phases of a modern compiler, including techniques in code generation and register allocation for imperative, functional and object-oriented languages.

Andrew W. Appel (Author), Maia Ginsburg (With)

9780521607650, Cambridge University Press

Paperback, published 8 July 2004

556 pages, 80 b/w illus. 34 tables 117 exercises
24.3 x 17.9 x 3.1 cm, 0.96 kg

This new, expanded textbook describes all phases of a modern 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 functional and object-oriented languages, that are missing from most books. In addition, more advanced chapters are now included so that it can be used as the basis for a two-semester or graduate course. The most accepted and successful techniques are described in a concise way, rather than as an exhaustive catalog of every possible variant. Detailed descriptions of the interfaces between modules of a compiler are illustrated with actual C header files. 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 advanced chapters, covers the compilation of object-oriented and functional languages, garbage collection, loop optimizations, SSA form, loop scheduling, and optimization for cache-memory hierarchies.

Part I. Fundamentals of Compilation: 1. Introduction
2. Lexical analysis
3. Parsing
4. Abstract syntax
5. Semantic analysis
6. Activation records
7. Translation to intermediate code
8. Basic blocks and traces
9. Instruction selection
10. Liveness analysis
11. Register allocation
12. Putting it all together
Part II. Advanced Topics: 13. Garbage collection
14. Object-oriented languages
15. Functional programming languages
16. Polymorphic types
17. Dataflow analysis
18. Loop optimizations
19. Static single-assignment form
20. Pipelining and scheduling
21. The memory hierarchy
Appendix.

Subject Areas: Programming & scripting languages: general [UMX], Compilers [UMC]