Engineering a Compiler

CHAPTER 1 Overview of Compilation

1.1 Introduction

1.2 Compiler Structure

1.3 Overview of Translation

1.3.1 The Front End

1.3.2 The Optimizer

1.3.3 The Back End

1.4 Summary and Perspective

CHAPTER 2 Scanners

2.1 Introduction

2.2 Recognizing Words

2.2.1 A Formalism for Recognizers

2.2.2 Recognizing More Complex Words

2.3 Regular Expressions

2.3.1 Formalizing the Notation

2.3.2 Examples

2.3.3 Closure Properties of REs

2.4 From Regular Expression to Scanner

2.4.1 Nondeterministic Finite Automata

2.4.2 Regular Expression to NFA: Thompson’s Construction

2.4.3 NFA to DFA: The Subset Construction

2.4.4 DFA to Minimal DFA: Hopcroft’s Algorithm

2.4.5 Using a DFA as a Recognizer

2.5 Implementing Scanners

2.5.1 Table-Driven Scanners

2.5.2 Direct-Coded Scanners

2.5.3 Hand-coded Scanners

2.5.4 Handling Keywords

2.6 Advanced Topics

2.6.1 DFA to Regular Expression

2.6.2 Another Approach to DFA Minimization: Brzozowski’s Algorithm

2.6.3 Closure-free Regular Expressions

2.7 Chapter Summary and Perspective

CHAPTER 3 Parsers

3.1 Introduction

3.2 Expressing Syntax

3.2.1 Why Not Regular Expressions?

3.2.2 Context-Free Grammars

3.2.3 More Complex Examples

3.2.4 Encoding Meaning into Structure

3.2.5 Discovering a Derivation for an Input String

3.3 Top-Down Parsing

3.3.1 Transforming a Grammar for Top-Down Parsing

3.3.2 Top-Down Recursive-Descent Parsers

3.3.3 Table-Driven LL(1) Parsers

3.4 Bottom-Up Parsing

3.4.1 The LR(1) Parsing Algorithm

3.4.2 Building LR(1) Tables

3.4.3 Errors in the Table Construction

3.5 Practical Issues

3.5.1 Error Recovery

3.5.2 Unary Operators

3.5.3 Handl