1 Introduction

1.1 Language Processors

1.2 The Structure of a Compiler

1.3 The Evolution of Programming Languages

1.4 The Science of Building a Compiler

1.5 Applications of Compiler Technology

1.6 Programming Language Basics

1.7 Summary of Chapter 1

1.8 References for Chapter 1

2 A Simple Syntax-Directed Translator

2.1 Introduction

2.2 Syntax Definition

2.3 Syntax-Directed Translation

2.4 Parsing

2.5 A Translator for Simple Expressions

2.6 Lexical Analysis

2.7 Symbol Tables

2.8 Intermediate Code Generation

2.9 Summary of Chapter 2

3 Lexical Analysis

3.1 The Role of the Lexical Analyzer

3.2 Input Buffering

3.3 Specification of Tokens

3.4 Recognition of Tokens

3.5 The Lexical-Analyzer Generator Lex

3.6 Finite Automata

3.7 From Regular Expressions to Automata

3.8 Design of a Lexical-Analyzer Generator

3.9 Optimization of DFA-Based Pattern Matchers

3.10 Summary of Chapter 3

3.11 References for Chapter 3

4 Syntax Analysis

4.1 Introduction

4.2 Context-Free Grammars

4.3 Writing a Grammar

4.4 Top-Down Parsing

4.5 Bottom-Up Parsing

4.6 Introduction to LR Parsing: Simple LR

4.7 More Powerful LR Parsers

4.8 Using Ambiguous Grammars

4.9 Parser Generators

4.10 Summary of Chapter 4

4.11 References for Chapter 4

5 Syntax-Directed Translation

5.1 Syntax-Directed Definitions

5.2 Evaluation Orders for SDD's

5.3 Applications of Syntax-Directed Translation

5.4 Syntax-Directed Translation Schemes

5.5 Implementing L-Attributed SDD's

5.6 Summary of Chapter 5

5.7 References for Chapter 5

6 Intermediate-Code Generation

6.1 Variants of Syntax Trees

6.2 Three-Address Code

6.3 Types and Declarations

6.4 Translation of Expressions

6.5 Type Checking

6.6 Control Flow

6.7 Backpatching

6.8 Switch-Statements

6.9 Intermediate Code for Procedures

6.10 Summary of Chapter 6

6.11 References for Chapter 6

7 Run-Time Environments

7.1 Storage Organization

7.2 Stack Allocation of Space

7.3 Access to Nonlocal Data on the Stack

7.4 Heap Management

7.5 Introduction to Garbage Collection

7.6 Introduction to Trace-Based Collection

7.7 Short-Pause Garbage Collection

7.8 Advanced Topics in Garbage Collection

7.9 Summary of Chapter 7

7.10 References for Chapter 7

8 Code Generation

8.1 Issues in the Design of a Code Generator

8.2 The Target Language

8.3 Addresses in the Target Code

8.4 Basic Blocks and Flow Graphs

8.5 Optimization of Basic Blocks

8.6 A Simple Code Generator

8.7 Peephole Optimization

8.8 Register Allocation and Assignment

8.9 Instruction Selection by Tree Rewriting

8.10 Optimal Code Generation for Expressions

8.11 Dynamic Programming Code-Generation

8.12 Summary of Chapter 8

8.13 References for Chapter 8

9 Machine-Independent Optimizations

9.1 The Principal Sources of Optimization

9.2 Introduction to Data-Flow Analysis

9.3 Foundations of Data-Flow Analysis

9.4 Constant Propagation

9.5 Partial-Redundancy Elimination

9.6 Loops in Flow Graphs

9.7 Region-Based Analysis

9.8 Symbolic Analysis

9.9 Summary of Chapter 9

9.10 References for Chapter 9