Compiler construction literature has always been an interesting mixture of clever tricks and deep theory. Most textbooks try to deal with both aspects, usually emphasizing theory at the beginning and then moving on to the tricks necessary to support specific programming paradigms and machine architectures. Reghizzi et al. take a different path, restricting themselves to “the principles and algorithms to be used for defining the syntax of languages and for implementing simple translators.” As the title implies, the book deals primarily with applying the theory of formal languages to compiler tasks. Readers are expected to be familiar with basic mathematical theories and notations from set theory, algebra, and logic.

The first of four main chapters introduces formal language theory and uses it to describe the characteristics of regular and context-free languages. Regular expressions and grammars are defined as descriptive mechanisms, and the next two chapters explain how automata that recognize sentences in those languages can be constructed from the descriptions. The last chapter moves away from formal language theory after presenting purely syntactic translation schemata; it uses attribute grammars to describe semantic translation and static program analysis, and refers to the existing literature for a detailed theoretical treatment of attribute grammars.

Formal languages and compilation meets its goal of providing the theoretical background for implementing simple translators. The treatment is complete, and the presentation is clear and pitched at an appropriate level for a university course. A professor considering this book for use in a compiler course should carefully consider whether its strategy meets the goals of that course in the curriculum. It would be most suitable for a curriculum that emphasizes the importance of theory in supporting robust mechanisms for significant problems. There it might be useful for a course that develops a theory and ties that theory to a practical application.

From my perspective, the most valuable contribution of this book is that it provides a complete theoretical treatment of structural analysis algorithms. Readers who want a deep understanding of these algorithms can therefore consult a single volume rather than tracking down a large number of individual papers.