The Theory and Practice of Compiler Writing

This book provides a practical approach to compiler implementation and shows how the different language features are handled and translated in the compilation process. Unlike most books in this area, The Theory and Practice of Compiler Writing thoroughly covers programming language design and error detection, and recovery techniques in compilation, enabling readers to get a firm grasp on compiler planning and programming. Traditional topics such as lexical analysis, syntactic analysis, symbol table handling, semantic analysis, code generation and code optimization are given balanced coverage.

This book is intended as a text for a one- or two-semester course in compiler design at the senior undergraduate or introductory graduate level. It can also be used as a self-study and reference book in compiler design. The reader should have at least one year of experience in programming a high-level language and an assembly language. In addition, a familiarity with elementary data structures and discrete mathematics is a definite asset.

1. Introduction
1. Programming Languages
2. Translators
3. Model of a C Compiler
2. Notation and Concepts for Languages and Grammars
1. Sets and Strings
1. Basic Concepts of Set Theory
2. Relations
3. Strings
2. Discussion of Grammars
3. Classification of Grammars
4. Context-Free Grammars and parsing
1. Syntax Terminology
2. A View of Parsing
3. Reduced Grammars and Grammars with ε-Rules
4. Extended BNF Notation
3. Programming-Language Design
1. Overview of the Problem
2. Preliminary Considerations
3. Sources of Ideas
4. Goals and Design Philosophies of Programming Languages
1. Human Communication
2. Prevention and Detection of Errors
3. Usability
4. Programming Effectiveness
5. Compilability
6. Efficiency
7. Machine Independence
8. Simplicity
9. Uniformity
10. Orthogonality
11. Generalization and Specialization
12. Other Design Philosophies
5. Detailed Design
1. Microstructure
2. Expression Structure
3. Data Structure
4. Control Structure
5. Compile Structure
6. I&O Structure
6. Reduction of Size
7. Pragmatics
8. Comments on the Design of Ada
1. Evaluation of Ada from a Language Design Viewpoint
• Usability and Program Effectiveness
• Machine Independence and Portability
• Efficiency
• Modularity and Maintainability
• Compilability and Compile Structre
• Simplicty
2. Ada Programming Support Environment
3. Software Technology for Adaptable Reliable Systems (STARS)
4. Scanners
1. The Scanning Process
2. An Elementary Scanner Design and Its Implementation
3. Regular Grammars and Regular Expressions
4. Finite-State Acceptors
1. Deterministic Finite-State Acceptors
2. Nondeterministric Finite-State Acceptors
3. Nondeterministric Finite-State Acceptors with ε-Transitions
5. Equivalence of regular Grammars and Finite-State Acceptors
6. Equivalence of Regular Expressions and Finite-State Acceptors
7. A Scanner Generator
5. Compile-Time Error Handling
1. Overview of Error Handling
2. Error Detection
1. The Nature of Syntax Errors
2. How Errors Are Detected
3. Where Errors Are Detected
3. Error Reporting
4. Error Recovery
1. Ad Hoc Recovery Mechanism
2. Syntax-Directed Recovery
3. Secondary Error Recovery
4. Context-Sensitive Recovery
5. Error Repair
1. Ad Hoc Repair
2. Syntax-Directed Repair
3. Context-Sensitive Repair
4. Spelling Repair
6. Top-Down Parsing
1. General Top-Down Parsing Strategies
1. Brute-Force Approach
2. Recursive-Descent Parsers
• Recursive-Descent Parsing Algorithm
• Error Detection in Recursive-Descent Parsers
3. Notions of Top-Down Parsing with Limited Backup
4. Top-Down Parsing with Limited Backup
2. Top-Down Parsing with No Backup
1. Notions of Parsing with No Backup
2. Simple LL(1) Grammars
3. LL(1) Grammars
4. LL(1) Grammars without ε-Rules
5. LL(1) Grammars with ε-Rules
6. Error Handling for LL(1) Parsers
7. Bottom-Up Parsing
1. Polish Expression and Their Compilation
1. Polish Notation
2. Conversion of Infix Expressions to Polish Notation
3. Error Detection for Infix Expressions
2. Operator Precedence Grammars
1. Notions and Use of Operator Precedence Relations
2. Formal Definition of Operator Precedence Relations
3. Operator Precedence Parsing Algorithm
4. Precedence Functions in Operator Precedence Parsers
5. Error Detection in Operator Precedence Parsers
3. Simple Precedence Grammars
1. Notions and Use of Precedence Relations
2. Formal Definition of Precedence Relations
3. Parsing Algorithm for Simple Precedence Grammars
4. Precedence Functions for Simple Precedence Parsers
5. Error Detection for Simple Precedence Parsers
6. Notions of Extended Precedence
4. LR Grammars
1. Concepts and Terminology
2. LR(0) Parsers
3. SLR(1) Parsers
4. Cononical LR(1) Parsers
5. LALR(1) Parsers
6. Efficient Generation of Lookahead Sets for LALR(1) Parsers
7. Representation and Optimization of LR Parsers
• Sparse-Matrix Representations
• Optimizaation Transformations
8. Error Detection and Recovery in LR Parsers
• Early Methods of Error Recovery
• Application of Graham-Rhodes Method to LR Parsers
• Other LR Error-Recovery Methods
5. Comparison of Parsing Methods
8. Symbol-Table-Handling Techniques
1. Perspective and Motivation
2. When to Construct and Interact with the Symbol Table
3. Symbol-Table Contents
4. Operations on Symbol Tables
5. Symbol-Table Organizations for Non-Block-Structured Languages
1. Unordered Symbol Tables
2. Ordered Symbol Tables
3. Tree-Structured Symbol Tables
4. Hash Symbol Tables
6. Symbol-Table Organization for Block-Structured Languages
1. Block-Structured Language Concepts
2. Stack Symbol Tables
3. Stack-Implemented Tree-Structured Symbol Tables
4. Stack-Implemented Has-Structured Symbol Tables
9. Run-Time Storage Organization and Management
1. Static Storage Allocation
2. Dynamic Storage Allocation
1. Activation Records
2. Parameter Area
3. Display Area
4. Run-Time Address Calculation
5. Handling Recursive Procedures
3. Heap Storage Allocation
1. Implicit Storage Requests
2. Explicit Storage Requests
3. Management of Fixed-Length Blocks
4. Management of Variable-Length Blocks
• First-Fit Heap Storage-Management Strategy
• Boundary-Tag Heap Storage-Management Strategy
• Byddy-System Heap Storage-Management Strategy
5. Free-as-you-Go Storage Release
6. Garbage Collection
7. Compaction
10. Intermediate Forms of Source Programs
1. Polish Notation
2. N-tuple Notation
3. Abstract Syntax Tree
4. Threaded Code
5. Abstract Machine Code
1. Portability and Abstract Machines
2. The P-Code Abstract Machine for PASCAL
11. Semantic Analysis and Code Generation
1. What Is Meant by Semantic Analysis
2. Implicit Stacking in Recursive-Descent Compilation
3. Semantic Stacks in Bottom-Up Compilation
4. Action Symbols in Top-Down Compilation
5. Attributed Translation
1. Attributed Translation Grammar
2. L-Attributed Translation Grammar
6. Example Language Constructs
1. Declarations
• Constant Type
• Variable Declarations
• Procedure Declarations
2. Expressions
3. Assignment Statements
4. Control Statements
• Case-Selection Statement
• Repeat-While Statement
• For Loop Statement
5. Procedure Calls and Returns
• Procedure Calls
• Return Statement and Procedure Termination
6. Input and Output Statements
• Input Statements
• Output Statements
7. Compiler Aids
12. Code Optimization
1. Introduction
2. Basic Blocks
3. Folding
4. Redundant-Subexpression Elimination
5. Optimization within Iterative Loops
1. Loop Unrolling
2. Frequency Reduction
3. Strength Reduction
4. Combining Loop-Optimization Techniques
6. Global Optimization through Flowgraph Analysis
1. Flowgraph Construction
2. Flowgraph Analysis
• Flowgraph-Analysis Problems
• Flow-Analysis Algorithms
3. Applications to Program Optimization
4. Implementation and Further Considerations
13. Machine-Dependent Optimization
1. Introduction to machine-Dependent Optimization
2. Register-Allocation Optimization
1. Register Allocation in Single-Register Machines
2. Register Allocation in Multiregister Machines
3. Machine Architecture and the Generation of real Code
1. The PDP-11
2. The VAX-11
3. The MC68000
14. Compiler-Compilers
1. Introduction to Compiler-Compilers
2. Example of Parser Generators
1. YACC: A LALR(1) Parser Generator
2. An Attributed LL(1) Parser Generator
3. Machine-Independent Code Generation
1. The Production-Quality Compiler-Compiler System
• Introduction
• The Formalization of Instruction-Set Processors and TCOL
• The Code-Generation Process: Its Phases and Organization
2. The Table-Driven Generator of Graham and Glanville
• Introduction
• The Target-Machine Description
• The Code-Generation Process
• Results and Extensions
3. Other Code-Generation Systems
• Fraser's Knowledge-Based Code-Generator Generator
• The Finite-State Approach of Donegan

1. Appendix: Algorithmic Notation
1. Format Conventions
1. Name of Algorithm
2. Introductory Comment
3. Steps
4. Comments
2. Statements and Control Structures
1. Assignment Statement
2. If Statement
3. Case Statement
4. Repeat Statement
5. Go To and Exitloop Statements
6. Exit Statement
7. Variable Names
3. Data Structures
1. Arrays
2. Dynamic Storage
4. Arithmetic Operations and Expressions
5. Strings and String Operations
6. Relations and Relational Operators
7. Logical Operations and Expressions
8. Input and Output
9. Subalgorithms
1. Functions
2. Procedures
3. Parameters

A well researched and pretty complete book, but why must it be so boringly written?