This book provides a qualitative discussion and clear presentation of the principles and techniques involved in compiler design and construction. It is organized into twelve chapters, two appendices, and a comprehensive Index. The details of each chapter are as follows:
Chapter 1 (Introduction, pp. 1-38) introduces the reader to different forms of language translator. High-level aspects of compiler design are discussed. Trends in programming languages and machine architecture that are shaping compiler are considered. In addition, applications of compiler technology and basics of programming languages are presented.
Chapter 2 (A Simple Syntax-Directed Translator, pp. 39-107) treats the front-end of a compiler. The main themes considered here are with syntax definition, syntax-directed translation, parsing, a translator for simple expressions, lexical analysis, symbol-table creation, and intermediate code generation.
Chapter 3 (Lexical Analysis, pp. 109-190) covers the scanning of the source program character by character in order to recognize the basic language symbols like identifiers, reserved words, integer number, operators, etc., which make up the program. More details about input buffering, specification and recognition of tokens, finite automata, design of lexical-analyzer generator, and optimization of DFA based pattern matchers, are given.
Chapter 4 (Syntax Analysis, pp. 191-302) is devoted to parsing methods that are typically used in compilers. The discussion begins with presentation pf the basic concepts, continues with techniques suitable for hand implementation, and ends with algorithms that are used in automated tools. Reading this chapter the reader can find interesting material related to context-free grammars, writing a grammar, top-down and bottom-up parsing, LR-parsing and LR parsers, using ambiguous grammars, and parser generators.
Chapter 5 (Syntax-Directed Translation, pp. 305-355) concentrates on translation of languages guided by context-free grammars. The main themes considered here are with syntax-directed definitions (SDDs) as a context-fee grammar with attributes and rules, evaluation orders for SDDs, applications of syntax-directed translation techniques (SDTs) SDT schemes, and implementation of L-attributed SDD's.
Chapter 6 (Intermediate-Code Generation, pp. 357-426) covers intermediate representation, static type checking, and intermediate code generation. The hottest topics considered here are with variant of syntax trees, three-address code, type and declarations, translation of expressions, type checking, control flow, back-patching, switch statements, and intermediate code for procedures.
Chapter 7 (Run-Time Environments, pp. 427-503) looks at run-time environment in which the compiler assumes that its target programs are executed. Two themes are in the focus of interest, the allocation of storage locations and access to variables and data. The discussion includes details concerning the storage organization, stack allocation of space, access to non-local data on the stack, heap management, introduction to garbage-collection (GB) and trace based collection, short-pause GB, and advanced topics in GB.
Chapter 8 (Code Generation, pp. 505-581) presents algorithms that code generators use to translate the intermediate representation (IR) into a sequence of target language instructions for simple register machines. The discussion includes details about issues in the design of a code generator, the target language, addresses in the target code, basic blocks and flow graphs, optimization of basic blocks, a simple code generator, peephole optimization, register allocation and assignment, instruction selection by thee rewriting, optimal code generation for expressions, and dynamic programming code-generation.
Chapter 9 (Machine-Independent Optimization, pp. 583-705) is devoted to elimination of unnecessary instructions in object code. In other words it concentrates on the replacement of one sequence of instructions by a faster sequence that does the same task. It explains in more details basic principles and techniques used for identification of principal sources of optimization, data-flow analysis, constant propagation, partial-redundancy elimination, loops in flow graphs, region based analysis, and symbolic analysis.
Chapter 10 (Instruction-Level Parallelism, pp. 707-767) examines the problems accompanied with instruction-level optimization. The main idea is based on extraction parallelism from small code sequences and scheduling them on single processors. The discussion begins with processor architecture that can issue several operations in a single clock cycle, continues with explanation of code-scheduling constraints, basic-block scheduling, global code-scheduling, and concludes with description of software-pipelining algorithms.
Chapter 11 (Optimization for Parallelism and Locality, pp. 769-902) discusses how compiler can enhance parallelism and locality in computationally intensive programs involving arrays to speed-up target programs running on multiprocessor systems. In other words, it focuses on techniques for optimizing the class of numerical applications that use arrays as data structures and access them with simple regular patterns. Useful and interesting details concerning iteration spaces, data reuse, array data-dependence analysis, synchronization between parallel loops, pipelining, locality optimization, and others, are given.
Chapter 12 (Inter-Procedural Analysis, pp. 903-964) points to the importance of inter-procedural analysis and discusses a number of important optimization problems that cannot be solved with inter-procedural analysis. The hottest topics considered here are with logical representation of data flow, pointer-analysis algorithm, context-insensitive inter-procedural analysis, context-sensitive pointer analysis, and datalog implementation by binary decision diagrams.
The book contains two appendices. Appendix A (A Complete Front-End, pp.
965-987) briefly describes a compiler front-end, while Appendix B (Finding
Linearly Independent Solutions, pp. 989- 992) concentrates on explanation of
an algorithm that finds a maximal set of linearly independent solutions for
, and expresses them as rows of matrix 
.