Crafting A Compiler

<p>Chapter 1 Introduction</p> 1.1 Overview and History of Compilation <p>1.2 What Compilers Do</p> <p> 1.2.1 Distinguishing Compilers by the Machine Code Generated</p> <p> 1.2.2 Target Code Formats</p> <p>1.3 Interpreters</p> <p>1.4 Syntax and Semantics of Programming Languages</p> <p> 1.4.1 Static Semantics</p> <p> 1.4.2 Run-time Semantics</p> <p>1.5 Organization of a Compiler</p> <p> 1.5.1 The Scanner</p> <p> 1.5.2 The Parser</p> <p> 1.5.3 The Type Checker (Semantic Analysis)</p> <p> 1.5.4 The Optimizer</p> <p> 1.5.5 The Code Generator</p> <p> 1.5.6 Compiler Writing Tools</p> <p>1.6 Compiler Design and Programming Language Design</p> <p>1.7 Architectural Influences of Computer Design</p> <p>1.8 Compiler Variants</p> <p> 1.8.1 Debugging (Development) Compilers</p> <p> 1.8.2 Optimizing Compilers</p> <p> 1.8.3 Retargetable Compilers</p> <p>1.9 Program Development Environment</p> <p>Chapter 2 A Simple Compiler</p> <p>2.1 An Informal Definition of the ac Language</p> <p>2.2 Formal Definition of ac</p> <p> 2.2.1 Syntax Specification</p> <p> 2.2.2 Token Specification</p> <p>2.3 Phases of a Simple Compiler</p> <p>2.4 Scanning</p> <p>2.5 Parsing</p> <p> 2.5.1 Predicting a Parsing Procedure</p> <p> 2.5.2 Implementing the Production</p> <p>2.6 Abstract Syntax Trees</p> <p>2.7 Semantic Analysis</p> <p> 2.7.1 Symbol Tables</p> <p> 2.7.2 Type Checking</p> <p>2.8 Code Generation</p> <p>Chapter 3 Scanning–Theory and Practice</p> <p>3.1 Overview of a Scanner</p> <p>3.2 Regular Expressions</p> <p>3.3 Examples</p> <p>3.4 Finite Automata and Scanners</p> <p> 3.4.1 Deterministic Finite Automata</p> <p>3.5 The Lex Scanner Generator</p> <p> 3.5.1 Defining Tokens in Lex</p> <p> 3.5.2 The Character Class</p> <p> 3.5.3 Using Regular Expressions to Define Tokens</p> <p> 3.5.4 Character Processing Using Lex</p> <p>3.6 Other Scanner Generators</p> <p>3.7 Practical Considerations of Building Scanners</p> <p> 3.7.1 Processing Identifiers and Literals</p> <p> 3.7.2 Using Compiler Directives and Listing Source Lines</p> <p> 3.7.3 Terminating the Scanner</p> <p> 3.7.4 Multicharacter Lookahead</p> <p> 3.7.5 Performance Considerations</p> <p> 3.7.6 Lexical Error Recovery</p> <p>3.8 Regular Expressions and Finite Automata</p> <p> 3.8.1 Transforming a Regular Expression into an NFA</p> <p> 3.8.2 Creating the DFA</p> <p> 3.8.3 Optimizing Finite Automata</p> <p>3.9 Summary</p> <p>Chapter 4 Grammars and Parsing</p> <p>4.1 Context-Free Grammars: Concepts and Notation</p> <p> 4.1.1 Leftmost Derivations</p> <p> 4.1.2 Rightmost Derivations</p> <p> 4.1.3 Parse Trees</p> <p> 4.1.4 Other Types of Grammars</p> <p>4.2 Properties of CFGs</p> <p> 4.2.1 Reduced Grammars</p> <p> 4.2.2 Ambiguity</p> <p> 4.2.3 Faulty Language Definition</p> <p>4.3 Transforming Extended Grammars</p> <p>4.4 Parsers and Recognizers</p> <p>4.5 Grammar Analysis Algorithms</p> <p> 4.5.1 Grammar Representation</p> <p> 4.5.2 Deriving the Empty String</p> <p> 4.5.3 First Sets</p> <p> 4.5.4 Follow Sets</p> <p>Chapter 5 Top-Down Parsing</p> <p>5.1 Overview</p> <p>5.2 LL(k) Grammars</p> <p>5.3 Recursive-Descent LL(1) parsers</p> <p>5.4 Table-Driven LL(1) Parsers</p> <p>5.5 Obtaining LL(1) Grammars</p> <p> 5.5.1 Common Prefixes</p> <p> 5.5.2 Left-Recursion</p> <p>5.6 A Non-LL(1) Language</p> <p>5.7 Properties of LL(1) Parsers</p> <p>5.8 Parse-Table Representation</p> <p> 5.8.1 Compaction</p> <p> 5.8.2 Compression</p> <p>5.9 Syntactic Error Recovery and Repair</p> <p> 5.9.1 Error Recover</p> <p> 5.9.2 Error Repair</p> <p> 5.9.3 Error Detection in LL(1) Parsers</p> <p> 5.9.4 Error Recovery in LL(1) Parsers</p> <p>Chapter 6 Bottom-Up Parsing</p> <p>6.1 Introduction</p> <p>6.2 Shift-Reduce Parsers</p> <p> 6.2.1 LR Parsers and Rightmost Derivations</p> <p> 6.2.2 LR Parsing as Knitting</p> <p> 6.2.3 LR Parsing Engine</p> <p> 6.2.4 The LR Parse Table</p> <p> 6.2.5 LR(k) Parsing</p> <p>6.3 LR(0) Table Construction</p> <p>6.4 Conflict Diagnosis</p> <p> 6.4.1 Ambiguous Grammars</p> <p> 6.4.2 Grammars that are not LR(k)</p> <p>6.5 Conflict Resolution for LR(0) Tables</p> <p> 6.5.1 SLR(k) Table Construction</p> <p> 6.5.2 LALR(k) Table Construction</p> <p>6.6 LR(k) Table Construction</p> <p>Chapter 7 Syntax-Directed Translation</p> <p>7.1 Overview</p> <p> 7.1.1 Semantic Actions and Values</p> <p> 7.1.2 Synthesized and Inherited Attributes</p> <p>7.2 Bottom-Up Syntax-Directed Translation</p> <p> 7.2.1 Example</p> <p> 7.2.2 Rule Cloning</p> <p> 7.2.3 Forcing Semantic Actions</p> <p> 7.2.4 Aggressive Grammar Restructuring</p> <p>7.3 Top-Down Syntax-Directed Translation</p> <p>7.4 Abstract Syntax Trees</p> <p> 7.4.1 Concrete and Abstract Trees</p> <p> 7.4.2 An Efficient AST Data Structure</p> <p> 7.4.3 Infrastructure for Creating ASTs</p> <p>7.5 AST Design and Construction</p> <p> 7.5.1 Design</p> <p> 7.5.2 Construction</p> <p>7.6 AST Structures for Left and Right Values</p> <p>7.7 Design Patterns for ASTs</p> <p> 7.7.1 Node Class Hierarchy</p> <p> 7.7.2 Visitor Pattern</p> <p> 7.7.3 Reflective Visitor Pattern</p> <p>Chapter 8 Symbol Tables and Declaration Processing</p> <p>8.1 Constructing a Symbol Table</p> <p> 8.1.1 Static Scoping</p> <p> 8.1.2 A Symbol Table Interface</p> <p>8.2 Block-Structured Languages and Scope Management</p> <p> 8.2.1 Handling Scopes</p> <p> 8.2.2 One Symbol Table or Many?</p> <p>8.3 Basic Implementation Techniques</p> <p> 8.3.1 Entering and Finding Names</p> <p> 8.3.2 The Name Space</p> <p> 8.3.3 An Efficient Symbol Table Implementation</p> <p>8.4 Advanced Features</p> <p> 8.4.1 Records and Typenames</p> <p> 8.4.2 Overloading and Type Hierarchies <br> 8.4.3 Implicit Declarations</p> <p>8.4.4 Export and Import Directives</p> <p> 8.4.5 Altered Search Rules</p> <p>8.5 Declaration Processing Fundamentals</p> <p> 8.5.1 Attributes in the Symbol Table</p> <p> 8.5.2 Type Descriptor Structures</p> <p> 8.5.3 Type Checking Using an Abstract Syntax Tree</p> <p>8.6 Semantic Processing of Simple Declarations</p> <p> 8.6.1 Simple Variable Declarations</p> <p> 8.6.2 Handling Type Names</p> <p> 8.6.3 Name References</p> <p> 8.6.4 Type Declarations and References</p> <p>8.6.5 Variable Declarations Revisited</p> <p>8.6.6 Enumeration Types</p> <p>8.7 Semantic Processing for Simple Names and Expressions: An Introduction to Type Checking</p> <p> 8.7.1 Handling Simple Identifiers and and Literal Constants</p> <p> 8.7.2 Processing Expressions</p> <p>8.8 Type Declarations</p> <p>8.9 Static and Dynamic Allocation</p> <p> 8.9.1 Initialization of Variables</p> <p> 8.9.2 Constant Declarations</p> <p>8.10 Classes and Structures</p> <p> 8.10.1 Variant Records and Unions</p> <p>8.11 Arrays</p> <p> 8.11.1 Static One-Dimensional Arrays</p> <p> 8.11.2 Multidimensional Arrays</p> <p>8.12 Implementing Other Types</p> <p>8.13 Key Idea Summary</p> <p>Chapter 9 Expressions and Type Checking</p> <p>9.1 Semantic Analysis for Control Structures</p> <p>9.1.1 If Statements</p> <p>9.1.2 While, Do and Repeat Loops</p> <p>9.1.3 For Loops</p> <p>9.1.4 Break, Continue, Return and Goto Statements</p> <p>9.1.5 Switch and Case Statements</p> <p>9.1.6 Exception Handling</p> <p>9.2 Semantic Analysis of Calls</p> <p>Chapter 10 Intermediate Representations</p> <p>10.1 Overview</p> <p> 10.1.1 Examples</p> <p> 10.1.2 The Middle End</p> <p>10.2 Java Virtual Machine</p> <p> 10.2.1 Introduction and Design Principles</p> <p> 10.2.2 Contents of a Class File</p> <p> 10.2.3 JVM Instructions</p> <p>10.3 Static Single Assignment Form</p> <p> 10.3.1 Renaming and --functions</p> <p>10.4 GCC ILs</p> <p>Chapter 11 Code Generation for a Virtual Machine</p> <p>11.1 Visitors for Code Generation</p> <p>11.2 Class and Method Declarations</p> <p> 11.2.1 Class Declarations</p> <p> 11.2.2 Method Declarations</p> <p>11.3 The MethodBodyVisitor</p> <p> 11.3.1 Constants</p> <p> 11.3.2 References to Local Storage</p> <p> 11.3.3 Static References</p> <p> 11.3.4 Expressions</p> <p> 11.3.5 Assignment</p> <p> 11.3.6 Method Calls</p> <p> 11.3.7 Field References</p> <p> 11.3.8 Conditional Execution</p> <p> 11.3.9 Loops</p> <p>11.4 The LHSVisitor</p> <p> 11.4.1 Local References</p> <p> 11.4.2 Static References</p> <p> 11.4.3 Field References</p> <p>Chapter 12 Runtime Support</p> <p>12.1 Static Allocation</p> <p>12.2 Stack Allocation</p> <p> 12.2.1 Accessing Frames at Run-Time</p> <p> 12.2.2 Handling Classes and Objects</p> <p> 12.2.3 Handling Multiple Scopes</p> <p> 12.2.4 Block-Level Allocation</p> <p> 12.2.5 More About Frames</p> <p>12.3 Heap Management</p> <p> 12.3.1 Allocation Mechanisms</p> <p> 12.3.2 Deallocation Mechanisms</p> <p> 12.3.3 Automatic Garbage Collection</p> <p>Chapter 13 Target Code Generation</p> <p>13.1 Translating Bytecodes</p> <p> 13.1.1 Allocating memory addresses</p> <p> 13.1.2 Allocating Arrays and Objects</p> <p> 13.1.3 Method Calls</p> <p> 13.1.4 Example</p> <p>13.2 Translating Expression Trees</p> <p>13.3 Register Allocation and Temporary Management</p> <p> 13.3.1 On the Fly Register Allocation</p> <p> 13.3.2 Register Allocation Using Graph Coloring</p> <p> 13.3.3 Priority Based Register Allocation</p> <p> 13.3.4 Interprocedural Register Allocation</p> <p>13.4 Code Scheduling</p> <p> 13.4.1 Improving Code Scheduling</p> <p> 13.4.2 Global and Dynamic Code Scheduling</p> <p>13.5 Automatic Instruction Selection</p> <p> 13.5.1 Instruction Selection Using BURS</p> <p> 13.5.2 Instruction Selection Using Twig</p> <p> 13.5.3 Other Approaches</p> <p>13.6 Peephole Optimization</p> <p> 13.6.1 Levels of Peephole Optimization</p> <p> 13.6.2 Automatic Generation of Peephole Optimizers</p> <p>Chapter 14 Program Optimization 505</p> <p>14.1 Introduction</p> <p> 14.1.1 Why Optimize?</p> <p> 14.1.2 Organization</p> <p>14.2 Data Flow Analysis</p> <p> 14.2.1 Introduction and Examples</p> <p> 14.2.2 Formal Specification</p> <p> 14.2.3 Evaluation WARNING this subsection is incomplete</p> <p> 14.2.4 Application of Data Flow Frameworks</p> <p>14.3 Advanced Optimizations</p> <p> 14.3.1 SSA Form</p> <p> 14.3.2 SSA-based Transformations</p> <p> 14.3.3 Loop Transformations</p> <p>Abbreviations</p> <p>Index</p>