Modern Compiler Design - Second Edition


Dick Grune, Kees van Reeuwijk, Henri E. Bal, Ceriel J.H. Jacobs, and Koen G. Langendoen

VU University Amsterdam, The Netherlands

pp. 823 + xix, 2012; ISBN 978-1-4614-4698-9

The Preface and Table of Contents can be found here.

Description

The book is intended for students who have at least used a compiler and have given some thought to the notion of compilation. It is not an introductory course (although it explains almost everything from basics).

The book consists conceptually of two parts. The first part covers the general compilation process, and contains three chapters based on the analysis/processing/synthesis paradigm: text analysis, context handling and code generation. The second part consists of four chapters, covering the paradigm-specific problems of imperative and object-oriented, functional, logic and parallel and distributed programs. The two parts are separated by a chapter on memory management/garbage collection.

We, the authors, have tried hard to write the book in an intuitively appealing style, concentrating on the reasoning behind and the mechanics of the algorithms rather than emphasizing rigorous formulation and formal correctness proofs.

Although the book covers most of the traditional techniques, it makes a number of strong philosophical and perhaps controversial statements, for which we think the time has come:

  • It recognizes lexical analysis, LR parsing and BURS code generation as instances of bottom-up pattern matching and explains them uniformly using dotted items, thus unifying three important techniques in compiler design, and allowing the students to extend them to fit their needs.
  • A recurrent theme is `precomputation': first a simple, understandable, and obviously correct technique is designed, then all computation that can be done at compiler generation time is performed there. This leads naturally from interpretive lexical analysis to FSAs and allows us to view generated code as an instantiation of an interpreter, thus introducing connections with partial evaluation.
  • It emphasizes closure algorithms wherever possible, thus unifying many seemingly different algorithms.
  • It places compiler construction in a wider frame of file and data conversion, thus enabling the student to see applicability in other programming domains.

The top level structure of the book is:

  • Introduction
  • 
    
  • From Program Text to Abstract Syntax Tree
  • Annotating the Abstract Syntax Tree - The Context
  • Processing the Intermediate Code
  • 
    
  • Memory Management
  • 
    
  • Imperative and Object-Oriented Programs
  • Functional Programs
  • Logic Programs
  • Parallel and Distributed Programs
  • 
    
  • Bibliography
  • Answers to Exercises

Special features are:

  • Techniques for embedded systems:
      object code size reduction
      power consumption reduction
      memory allocation
  • Generalized (non-deterministic) LR parsing, freeing the compiler writer from the limitations of LALR
  • Legacy code handling:
      grammar recovery
      disassembly and/or decompilation of legacy binary code
  • Optimization techniques:
      procedural abstraction
      binary code rewriting
      optimal code generation through exhaustive search
      tail recursion removal

There is a first edition with transalations in French, Spanish, and Brazilian/Portugese.

About the authors

Dick Grune (retired) taught Principles of Programming Languages and Compiler Construction at the Vrije Universiteit Amsterdam. He was involved in constructing Algol 68 compilers in the 1970s and participated in the Amsterdam Compiler Kit in the 1980s. He is co-author of two other books: Parsing Techniques - A Practical Guide - 2nd Ed. and Programming Language Essentials .

Kees van Reeuwijk has been involved in research in programming languages and compiler construction for over 20 years, including projects on hardware description, High Performance Fortran and Java.

Henri Bal is a full professor at the Faculty of Sciences of the Vrije Universiteit Amsterdam. He is the author of more than 120 articles and (co-)author of two other books: Programming Language Essentials and Programming Distributed Systems . He is a recipient of the prestigious "Pionier" Award of NWO (Dutch Organization for Scientific Research) and of numerous other grants.

Ceriel Jacobs worked in several construction projects, among which the Amsterdam Compiler Kit and Orca parallel programming system. He is also coauthor of the book Parsing Techniques - A Practical Guide - 2nd Ed. .

Koen Langendoen is a full professor of Computer Science with Delft University of Technology. He has been working in compiler construction since 1985, and is specialized in code generation and runtime support systems for various imperative, functional, and parallel languages.


[Dick Grune] [Kees van Reeuwijk] [Henri Bal] [Ceriel Jacobs] [Koen Langendoen]
Modern Compiler Design - Second Edition / Dick Grune / dick@dickgrune.com