David Galles
MODERN COMPILER DESIGN
Softcover pp. 361, plus X
Scott/Jones Inc. Publishers, El Granada, CA, USA, 2005
ISBN 1-57676-105-3

Intended readership

The text book covers compiler design theory, as well as implementation details for writing a compiler using JavaCC and Java. This book comes with a student CD which has answer files and source code with implemetation details for creating a compiler using C, Lex and Yacc.

The intended audiences of this book are undergraduate compiler design course students. The book is conceived and structured as a comprehensive tutorial for basic compiler design. Since it is based on Java programming language, a solid level of programming skills in Java are required for understanding presented material and successfully completing exercises. Anyone fulfilling there prerequisites will be able to create a simple compiler after reading the book and completing all exercises. Therefore, this is a very practical text - all theoretical topics contain illustrative examples.

Organization of the text

Chapter 1 is introductory and starts with overview of compilation process. It explains why compiler design is important even to those main goal is not compiler development.

Chapter 2 covers lexical analysis in more depth. This chapter also introduces two important mathematical formalisms: regular expressions and deterministic finite automata. These two formalisms are not useful exclusively in compiler design and are widely used in all other programming disciplines. From a practical standpoint this chapter demonstrates how to create a lexical analyzer, or scanner, for simpleJava using Java and JavaCC - a lexical analyzer and parser generator. The enclosed CD shows how to use C and Lex to build a lexical analyzer for simpleJava.

Chapter 3 is theoretical chapter describing context-free grammars which are used to describe the syntax of programming languages.

Chapters 4 and 5 deal with parsers and parser generators. Chapter 4 offers more detailed description of top-down parsers and JavaCC parser generator. Chapter 5 covers bottom-up parsers. The enclosed CD shows how to use C and Yacc to build a parser for simpleJava.

Chapter 6 presents Abstract Syntax Trees. This chapter demonstrates usage of JavaCC for generating Abstract Syntax Trees for a simple language. For the purpose of traversing abstract tree structures the visitor software design pattern is also described. The enclosed CD shows how to use C and Yacc for creating an Abstract Syntax Tree for simpleJava.

Chapter 7 deals with semantic analysis. The enclosed CD shows how to implement a semantic analyzer for simpleJava in C.

Chapter 8 covers process of creation of Abstract Assembly Trees. These structures are simple tree-like versions of the actual assembly the compiler will generate. The enclosed CD shows how to implement Abstract Assembly Trees in C.

Topic of chapter 9 is code generation. This is the process of converting Abstract Assembly Tree into actual MIPS assembly. This step also includes different optimizations which are also discussed in this chapter. This chapter shows how to write a code generator that produces MIPS assembly code. The enclosed CD contains more detailed material covering generating of x86 assembly from Abstract Assembly Tree.

Chapter 10 is presenting different memory management techniques, including stack-based, heap-based and static storage. Some advanced memory management topics like programmer-controlled memory managers and garbage collection schemes are discussed at the end of this chapter.

Chapter 11 extends the material presented so far with object-oriented concepts like adding methods to classes, inheritance, virtual methods and access control.

Appendix A is a reference manual for simpleJava, the example programming language that the author is using throughout this book.

Appendix B is much more theory intensive than other chapters in the book. It covers the theory behind analyzer generators. This includes non -deterministic automata, conversion of a regular expression to non-deterministic automaton, conversion of a non- deterministic finite automaton to a deterministic type and state minimization. While this theoretical knowledge is not necessary for creating compiler it is still important for engineers designing production class compilers.

The included CD contains source code for all components of simpleJava compiler developed throughout the book written in Java and C. Documents portion of the CD contains the supplemental document explaining LEX and YACC in more detail and C language version of bottom-up parsing, abstract syntax trees, semantic analysis, abstract assembly generation and code generation. Finally, the CD also contains the document supplementing chapter 9 and contains x86 specifics for code generation.

Intended usage

I believe this book will represent an invaluable resource to all instructors teaching compiler courses. The material presented in the book can fully cover one-semester course for undergraduate studies and can be used as introductory material for graduate level courses.

The book has user support WEB site at http://www.cs.usfca.edu/galles/compilerdesign. It contains sample source code files (C and Java) presented throughout the book as well as a maintained list of errors and corrections found in the text so far.