The fundamental topics of compiler design (lexical analysis, parsing, semantic analysis, and code generation), as well as the theoretical principles that are used in this frame, are considered. The book presents a thorough theoretical basis for compiler design by developing a mathematical approach (formal grammar theory) for the main components of compiler design. For all the topics presented in this book, the authors begin by introducing the theoretical concepts and results of grammar theory related to these problems and develop significant examples written in a real programming language, Modula-2. Each chapter ends with exercises, compiler projects, and a list of references. The book is divided into ten chapters and four appendices.
The first chapter introduces some general facts about compiler design, specifically about compiler structure and grammar elements. Chapter 2 is dedicated to the central mathematical tool used in this presentation: formal language theory. In this framework the authors present the generative devices in the Chomsky hierarchy and related automata.
Chapter 3 deals with topics related to scanners: mathematical models used in this field (regular expressions and grammars, and finite-state automata), and issues in scanner implementation. Chapter 4 discusses problems related to parsing: context-free grammars and push-down automata, LL(k) grammars, extended context-free grammars, parser generators, and the construction of a recursive descent parser starting from an LL(1) context-free grammar.
Chapter 5 deals with some problems in the semantic analysis of programming languages. It is known that lexical analysis and parsing are modeled well by generative devices. For semantics, many approaches are in use at the theoretical level and at the implementation level. The authors, using a uniform way of approaching the models related to compiling, present attribute grammars as a mathematical support for semantics. In this way they present the theoretical concepts and some problems related to the implementation of attributes in a recursive descent algorithm.
Chapter 6 presents some problems in code generation using a syntax-directed approach. An attribute grammar model is used to make possible the generation of code that depends on semantic conditions. The chapter introduces a hypothetical computer to illustrate the code generation problems.
Chapter 7 investigates the bottom-up technique in parsing design. The LR(k), SLR(k), and LALR(k) parsers and error recovery techniques are presented. Attribute evaluation in the LR parsers is also investigated.
Chapter 8 introduces transformational attribute grammar to provide methods of optimization and code generation. A survey of useful transformational optimizations is also given.
Problems related to code generation and optimization are studied in chapter 9. Because code generation is machine dependent, many machine architectures are considered: conventional, RISC, pipeline, and vector processors. Two main classes of optimization problems are presented: memory and register allocation and loop optimizations. The last chapter deals with compiler design problems in applicative programming languages.
The book’s main features are a strong background in formal language theory, a clear description of problems related to compiling, many algorithms presented in Modula-2, exercises, and compiler projects. It is addressed to students studying compiler techniques and to researchers and compiler implementors. The presentation is clear, and the mathematical concepts assure a rigorous approach to the subject.