Compilers : Principles, Techniques and Tools

This introduction to compilers is the direct descendant of the well-known book by Aho and Ullman, Principles of Compiler Design. The authors present updated coverage of compilers based on research and techniques that have been developed in the field over the past few years. The book provides a thorough introduction to compiler design and covers topics such as context-free grammars, fine state machines, and syntax-directed translation.

1. INTRODUCTION TO COMPILING

Compilers
Analysis of the source program
The phases of a compiler
Cousins of the compiler
The grouping of phases
Compiler-construction tools
Bibliographic notes

2. A SIMPLE ONE-PASS COMPILER

Overview Syntax definition
Syntax-directed translation
Parsing
A translator for simple expressions
Lexical analysis
Incorporating a symbol table
Abstract stack machines
Putting the techniques together
Exercises
Bibliographic notes

3. LEXICAL ANALYSIS

The role of the lexical analyzer
Input buffering
Specification of tokens
Recognition of tokens
A language for specifying lexical analyzers
Finite automata
From a regular expression to an NFA
Design of a lexical analyzer generator
Optimization of DFA-based pattern matchers
Exercises
Bibliographic notes

4. SYNTAX ANALYSIS

The role of the parser
Context-free grammars
Writing a grammar
Top-down parsing
Bottom-up parsing
Operator-precedence parsing
LR parsers
Using ambiguous grammars
Parser generators
Exercises
Bibliographic notes

5. SYNTAX-DIRECTED TRANSLATION

Syntax-directed definitions
Construction of syntax trees
Bottom-up evaluation of S-attributed definitions
L-attributed definitions
Top down translation
Bottom-up evaluation of inherited attributes
Recursive evaluators
Space for attribute values at compile time
Assigning spaces at compiler-construction time
Analysis of syntax-directed definitions
Exercises
Bibliographic notes

6. TYPE CHECKING

Type Systems
Specification of a simple type checker
Equivalence of type expressions
Type conversions
Overloading of functions and operators
Polymorphic functions
An algorithm for unification
Exercises
Bibliographic notes

7. RUN-TIME ENVIRONMENTS

Source language issues
Storage organization
Storage-allocation strategies
Access to nonlocal names
Parameter passing
Symbol tables
Language facilities for dynamic storage allocation
Dynamic storage allocation techniques
Storage allocation in Fortran
Exercises
Bibliographic notes

8. INTERMEDIATE CODE GENERATION

Intermediate languages
Declarations
Assignment statements
Boolean expressions
Case statements
Backpatching
Procedure Calls
Exercises
Bibliographic notes

9. CODE GENERATION

Issues in the design of a code generator
The target machine
Run-time storage management
Basic blocks and flow graphs
Next-use information
A simple code generator
Register allocation and assignment
the dag representation of basic blocks
Peephole optimization
Generating code from dags
Dynamic programming code-generation algorithm
Code-generator generators
Exercises
Bibliographic notes

10. CODE OPTIMIZATION

Introduction
The principal sources of optimization
Optimization of basic blocks
Loops in flow graphs
Introduction to global data-flow analysis
Iterative solution of data-flow equations
Code-improving transformations
Dealing with aliases
Data-flow analysis of structured flow graphs
Efficient data-flow algorithms
A tool for data-flow analysis
Estimation of types
Symbolic debugging of optimized code
Exercises
Bibliographic notes

11. WANT TO WRITE A COMPILER?

Planning a compiler
Approaches to compiler development
The compiler-development environment
Testing and maintenance

12. A LOOK AT SOME COMPILERS

EQN, a preprocessor for typesetting mathematics
Compilers for Pascal
The C compilers
The Fortran H compilers
The Bliss/11 compiler
Modula-2 optimizing compiler

APPENDIX: A COMPILER PROJECT

Introduction
A Pascal subset
Program structure
Lexical conventions
Suggested exercises
Evolution of the interpreter
Extensions

BIBLIOGRAPHY
INDEX