Crafting A Compiler

This Is The Ebook Of The Printed Book And May Not Include Any Media, Website Access Codes, Or Print Supplements That May Come Packaged With The Bound Book. Crafting A Compiler Is A Practical Yet Thorough Treatment Of Compiler Construction. It Is Ideal For Undergraduate Courses In Compilers Or For Software Engineers, Systems Analysts, And Software Architects. Crafting A Compiler Is An Undergraduate-level Text That Presents A Practical Approach To Compiler Construction With Thorough Coverage Of The Material And Examples That Clearly Illustrate The Concepts In The Book. Unlike Other Texts On The Market, Fischer/cytron/leblanc Uses Object-oriented Design Patterns And Incorporates An Algorithmic Exposition With Modern Software Practices. The Text And Its Package Of Accompanying Resources Allow Any Instructor To Teach A Thorough And Compelling Course In Compiler Construction In A Single Semester. It Is An Ideal Reference And Tutorial For Students, Software Engineers, Systems Analysts, And Software Architects. Contents 1 Introduction 1.1 History of Compilation 1.2 What Compilers Do 1.2.1 Machine Code Generated by Compilers 1.2.2 Target Code Formats 1.3 Interpreters 1.4 Syntax and Semantics 1.4.1 Static Semantics 1.4.2 Runtime Semantics 1.5 Organization of a Compiler 1.5.1 The Scanner 1.5.2 The Parser 1.5.3 The Type Checker (Semantic Analysis) 1.5.4 Translator (Program Synthesis) 1.5.5 Symbol Tables 1.5.6 The Optimizer 1.5.7 The Code Generator 1.5.8 Compiler Writing Tools 1.6 Programming Language and Compiler Design 1.7 Computer Architecture and Compiler Design 1.8 Compiler Design Considerations 1.8.1 Debugging (Development) Compilers 1.8.2 Optimizing Compilers 1.8.3 Retargetable Compilers 1.9 Integrated Development Environments Exercises 2 A Simple Compiler 2.1 An Informal Definition of the ac Language 2.2 Formal Definition of ac 2.2.1 Syntax Specification 2.2.2 Token Specification 2.3 Phases of a Simple Compiler 2.4 Scanning 2.5 Parsing 2.5.1 Predicting a Parsing Procedure 2.5.2 Implementing the Production 2.6 Abstract Syntax Trees 2.7 Semantic Analysis 2.7.1 Symbol Tables 2.7.2 Type Checking 2.8 Code Generation Exercises 3 Scanning—Theory and Practice 3.1 Overview of a Scanner 3.2 Regular Expressions 3.3 Examples 3.4 Finite Automata and Scanners 3.4.1 Deterministic Finite Automata 3.5 The Lex Scanner Generator 3.5.1 Defining Tokens in Lex 3.5.2 The Character Class 3.5.3 Using Regular Expressions to Define Tokens 3.5.4 Character Processing Using Lex 3.6 Other Scanner Generators 3.7 Practical Considerations of Building Scanners 3.7.1 Processing Identifiers and Literals 3.7.2 Using Compiler Directives and Listing Source Lines 3.7.3 Terminating the Scanner 3.7.4 Multicharacter Lookahead 3.7.5 Performance Considerations 3.7.6 Lexical Error Recovery 3.8 Regular Expressions and Finite Automata 3.8.1 Transforming a Regular Expression into an NFA 3.8.2 Creating the DFA 3.8.3 Optimizing Finite Automata 3.8.4 Translating Finite Automata into Regular Expressions 3.9 Summary Exercises 4 Grammars and Parsing 4.1 Context-Free Grammars 4.1.1 Leftmost Derivations 4.1.2 Rightmost Derivations 4.1.3 Parse Trees 4.1.4 Other Types of Grammars 4.2 Properties of CFGs 4.2.1 Reduced Grammars 4.2.2 Ambiguity 4.2.3 Faulty Language Definition 4.3 Transforming Extended Grammars 4.4 Parsers and Recognizers 4.5 Grammar Analysis Algorithms 4.5.1 Grammar Representation 4.5.2 Deriving the Empty String 4.5.3 First Sets 4.5.4 Follow Sets Exercises 5 Top-Down Parsing 5.1 Overview 5.2 LL(k) Grammars 5.3 Recursive-Descent LL(1) Parsers 5.4 Table-Driven LL(1) Parsers 5.5 Obtaining LL(1) Grammars 5.5.1 Common Prefixes 5.5.2 Left Recursion 5.6 A Non-LL(1) Language 5.7 Properties of LL(1) Parsers 5.8 Parse Table Representation 5.8.1 Compaction 5.8.2 Compression 5.9 Syntactic Error Recovery and Repair 5.9.1 Error Recovery 5.9.2 Error Repair 5.9.3 Error Detection in LL(1) Parsers 5.9.4 Error Recovery in LL(1) Parsers Exercises 6 Bottom-Up Parsing 6.1 Overview 6.2 Shift-Reduce Parsers 6.2.1 LR Parsers and Rightmost Derivations 6.2.2 LR Parsing as Knitting 6.2.3 LR Parsing Engine 6.2.4 The LR Parse Table 6.2.5 LR(k) Parsing 6.3 LR(0) Table Construction 6.4 Conflict Diagnosis 6.4.1 Ambiguous Grammars 6.4.2 Grammars that are not LR(k) 6.5 Conflict Resolution and Table Construction 6.5.1 SLR(k) Table Construction 6.5.2 LALR(k) Table Construction 6.5.3 LALR Propagation Graph 6.5.4 LR(k) Table Construction Exercises 7 Syntax-Directed Translation 7.1 Overview 7.1.1 Semantic Actions and Values 7.1.2 Synthesized and Inherited Attributes 7.2 Bottom-Up Syntax-Directed Translation 7.2.1 Example 7.2.2 Rule Cloning 7.2.3 Forcing Semantic Actions 7.2.4 Aggressive Grammar Restructuring 7.3 Top-Down Syntax-Directed Translation 7.4 Abstract Syntax Trees 7.4.1 Concrete and Abstract Trees 7.4.2 An Efficient AST Data Structure 7.4.3 Infrastructure for Creating ASTs 7.5 AST Design and Construction 7.5.1 Design 7.5.2 Construction 7.6 AST Structures for Left and Right Values 7.7 Design Patterns for ASTs 7.7.1 Node Class Hierarchy 7.7.2 Visitor Pattern 7.7.3 Reflective Visitor Pattern Exercises 8 Symbol Tables and Declaration Processing 8.1 Constructing a Symbol Table 8.1.1 Static Scoping 8.1.2 A Symbol Table Interface 8.2 Block-Structured Languages and Scopes 8.2.1 Handling Scopes 8.2.2 One Symbol Table or Many? 8.3 Basic Implementation Techniques 8.3.1 Entering and Finding Names 8.3.2 The Name Space 8.3.3 An Efficient Symbol Table Implementation 8.4 Advanced Features 8.4.1 Records and Typenames 8.4.2 Overloading and Type Hierarchies 8.4.3 Implicit Declarations 8.4.4 Export and Import Directives 8.4.5 Altered Search Rules 8.5 Declaration Processing Fundamentals 8.5.1 Attributes in the Symbol Table 8.5.2 Type Descriptor Structures 8.5.3 Type Checking Using an Abstract Syntax Tree 8.6 Variable and Type Declarations 8.6.1 Simple Variable Declarations 8.6.2 Handling Type Names 8.6.3 Type Declarations 8.6.4 Variable Declarations Revisited 8.6.5 Static Array Types 8.6.6 Struct and Record Types 8.6.7 Enumeration Types 8.7 Class and Method Declarations 8.7.1 Processing Class Declarations 8.7.2 Processing Method Declarations 8.8 An Introduction to Type Checking 8.8.1 Simple Identifiers and Literals 8.8.2 Assignment Statements 8.8.3 Checking Expressions 8.8.4 Checking Complex Names 8.9 Summary Exercises 9 Semantic Analysis 9.1 Semantic Analysis for Control Structures 9.1.1 Reachability and Termination Analysis 9.1.2 If Statements 9.1.3 While, Do, and Repeat Loops 9.1.4 For Loops 9.1.5 Break, Continue, Return, and Goto Statements 9.1.6 Switch and Case Statements 9.1.7 Exception Handling 9.2 Semantic Analysis of Calls 9.3 Summary Exercises 10 Intermediate Representations 10.1 Overview 10.1.1 Examples 10.1.2 The Middle-End 10.2 Java Virtual Machine 10.2.1 Introduction and Design Principles 10.2.2 Contents of a Class File 10.2.3 JVM Instructions 10.3 Static Single Assignment Form 10.3.1 Renaming and Φ-functions Exercises 11 Code Generation for a Virtual Machine 11.1 Visitors for Code Generation 11.2 Class and Method Declarations 11.2.1 Class Declarations 11.2.2 Method Declarations 11.3 The MethodBodyVisitor 11.3.1 Constants 11.3.2 References to Local Storage 11.3.3 Static References 11.3.4 Expressions 11.3.5 Assignment 11.3.6 Method Calls 11.3.7 Field References 11.3.8 Array References 11.3.9 Conditional Execution 11.3.10 Loops 11.4 The LHSVisitor 11.4.1 Local References 11.4.2 Static References 11.4.3 Field References 11.4.4 Array References Exercises 12 Runtime Support 12.1 Static Allocation 12.2 Stack Allocation 12.2.1 Field Access in Classes and Structs 12.2.2 Accessing Frames at Runtime 12.2.3 Handling Classes and Objects 12.2.4 Handling Multiple Scopes 12.2.5 Block-Level Allocation 12.2.6 More About Frames 12.3 Arrays 12.3.1 Static One-Dimensional Arrays 12.3.2 Multidimensional Arrays 12.4 Heap Management 12.4.1 Allocation Mechanisms 12.4.2 Deallocation Mechanisms 12.4.3 Automatic Garbage Collection 12.5 Region-Based Memory Management Exercises 13 Target Code Generation 13.1 Translating Bytecodes 13.1.1 Allocating memory addresses 13.1.2 Allocating Arrays and Objects 13.1.3 Method Calls 13.1.4 Example of Bytecode Translation 13.2 Translating Expression Trees 13.3 Register Allocation 13.3.1 On-the-Fly Register Allocation 13.3.2 Register Allocation Using Graph Coloring 13.3.3 Priority-Based Register Allocation 13.3.4 Interprocedural Register Allocation 13.4 Code Scheduling 13.4.1 Improving Code Scheduling 13.4.2 Global and Dynamic Code Scheduling 13.5 Automatic Instruction Selection 13.5.1 Instruction Selection Using BURS 13.5.2 Instruction Selection Using Twig 13.5.3 Other Approaches 13.6 Peephole Optimization 13.6.1 Levels of Peephole Optimization 13.6.2 Automatic Generation of Peephole Optimizers Exercises 14 Program Optimization 14.1 Overview 14.1.1 Why Optimize? 14.2 Control Flow Analysis 14.2.1 Control Flow Graphs 14.2.2 Program and Control Flow Structure 14.2.3 Direct Procedure Call Graphs 14.2.4 Depth-First Spanning Tree 14.2.5 Dominance 14.2.6 Simple Dominance Algorithm 14.2.7 Fast Dominance Algorithm 14.2.8 Dominance Frontiers 14.2.9 Intervals 14.3 Introduction to Data Flow Analysis 14.3.1 Available Expressions 14.3.2 Live Variables 14.4 Data Flow Frameworks 14.4.1 Data Flow Evaluation Graph 14.4.2 Meet Lattice 14.4.3 Transfer Functions 14.5 Evaluation 14.5.1 Iteration 14.5.2 Initialization 14.5.3 Termination and Rapid Frameworks 14.5.4 Distributive Frameworks 14.6 Constant Propagation 14.7 SSA Form 14.7.1 Placing Φ-Functions 14.7.2 Renaming Exercises Bibliography Abbreviations Pseudocode Guide Index A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

clear Description Of Algorithms And Clean Design Of Compiler Components. crafting A Compiler presents A Practical Approach To Compiler Construction With Thorough Coverage Of The Material And Examples That Clearly Illustrate The Concepts In The Book. Unlike Other Texts On The Market, Fischer/cytron/leblanc Uses Object-oriented Design Patterns And Incorporates An Algorithmic Exposition With Modern Software Practices. An Ideal Reference And Tutorial.

market: Software Engineers, Systems Analysts, Software Architects