``Crafting a Compiler'' by Charles N. Fisher & Richard J. LeBlanc, Jr.
1988. Benjamin/Cummings Publishing Company. Menlo Park, CA.
Brief Contents xvi
1 Introduction 1
2 A Simple Compiler 31
3 Scanning—Theory and Practice 57
4 Grammars and Parsing 113
5 Top-Down Parsing 143
6 Bottom-Up Parsing 179
7 Syntax-Directed Translation 235
8 Symbol Tables and Declaration Processing 279
9 Semantic Analysis 343
10 Intermediate Representations 391
11 Code Generation for a Virtual Machine 417
12 Runtime Support 445
13 Target Code Generation 489
14 Program Optimization 547
Contents xvii
1 Introduction 1
1.1 History of Compilation 2
1.2 What Compilers Do 4
1.2.1 Machine Code Generated by Compilers 4
1.2.2 Target Code Formats 7
1.3 Interpreters 9
1.4 Syntax and Semantics 10
1.4.1 Static Semantics 11
1.4.2 Runtime Semantics 12
1.5 Organization of a Compiler 14
1.5.1 The Scanner 16
1.5.2 The Parser 16
1.5.3 The Type Checker (Semantic Analysis) 17
1.5.4 Translator (Program Synthesis) 17
1.5.5 Symbol Tables 18
1.5.6 The Optimizer 18
1.5.7 The Code Generator 19
1.5.8 Compiler Writing Tools 19
1.6 Programming Language and Compiler Design 20
1.7 Computer Architecture and Compiler Design 21
1.8 Compiler Design Considerations 22
1.8.1 Debugging (Development) Compilers 22
1.8.2 Optimizing Compilers 23
1.8.3 Retargetable Compilers 23
1.9 Integrated Development Environments 24
1.10 Exercises 26
2 A Simple Compiler 31
2.1 An Informal Definition of the ac Language 32
2.2 Formal Definition of ac 33
2.2.1 Syntax Specification 33
2.2.2 Token Specification 36
2.3 Phases of a Simple Compiler 37
2.4 Scanning 38
2.5 Parsing 39
2.5.1 Predicting a Parsing Procedure 41
2.5.2 Implementing the Production 43
2.6 Abstract Syntax Trees 45
2.7 Semantic Analysis 46
2.7.1 Symbol Tables 47
2.7.2 Type Checking 48
2.8 Code Generation 51
2.9 Exercises 54
3 Scanning—Theory and Practice 57
3.1 Overview of a Scanner 58
3.2 Regular Expressions 60
3.3 Examples 62
3.4 Finite Automata and Scanners 64
3.4.1 Deterministic Finite Automata 65
3.5 The Lex Scanner Generator 69
3.5.1 Defining Tokens in Lex 70
3.5.2 The Character Class 71
3.5.3 Using Regular Expressions to Define Tokens 73
3.5.4 Character Processing Using Lex 76
3.6 Other Scanner Generators 77
3.7 Practical Considerations of Building Scanners 79
3.7.1 Processing Identifiers and Literals 79
3.7.2 Using Compiler Directives and Listing Source Lines 83
3.7.3 Terminating the Scanner 85
3.7.4 Multicharacter Lookahead 86
3.7.5 Performance Considerations 87
3.7.6 Lexical Error Recovery 89
3.8 Regular Expressions and Finite Automata 92
3.8.1 Transforming a Regular Expression into an NFA 93
3.8.2 Creating the DFA 94
3.8.3 Optimizing Finite Automata 97
3.8.4 Translating Finite Automata into Regular Expressions 100
3.9 Summary 103
3.10 Exercises 106
4 Grammars and Parsing 113
4.1 Context-Free Grammars 114
4.1.1 Leftmost Derivations 116
4.1.2 Rightmost Derivations 116
4.1.3 Parse Trees 117
4.1.4 Other Types of Grammars 118
4.2 Properties of CFGs 120
4.2.1 Reduced Grammars 120
4.2.2 Ambiguity 121
4.2.3 Faulty Language Definition 122
4.3 Transforming Extended Grammars 122
4.4 Parsers and Recognizers 123
4.5 Grammar Analysis Algorithms 127
4.5.1 Grammar Representation 127
4.5.2 Deriving the Empty String 128
4.5.3 First Sets 130
4.5.4 Follow Sets 134
4.6 Exercises 138
5 Top-Down Parsing 143
5.1 Overview 144
5.2 LL(k) Grammars 145
5.3 Recursive-Descent LL(1) Parsers 149
5.4 Table-Driven LL(1) Parsers 150
5.5 Obtaining LL(1) Grammars 154
5.5.1 Common Prefixes 156
5.5.2 Left Recursion 157
5.6 A Non-LL(1) Language 159
5.7 Properties of LL(1) Parsers 161
5.8 Parse Table Representation 163
5.8.1 Compaction 164
5.8.2 Compression 165
5.9 Syntactic Error Recovery and Repair 168
5.9.1 Error Recovery 169
5.9.2 Error Repair 169
5.9.3 Error Detection in LL(1) Parsers 171
5.9.4 Error Recovery in LL(1) Parsers 171
5.10 Exercises 173
6 Bottom-Up Parsing 179
6.1 Overview 180
6.2 Shift-Reduce Parsers 181
6.2.1 LR Parsers and Rightmost Derivations 182
6.2.2 LR Parsing as Knitting 182
6.2.3 LR Parsing Engine 184
6.2.4 The LR Parse Table 185
6.2.5 LR(k) Parsing 187
6.3 LR(0) Table Construction 191
6.4 Conflict Diagnosis 197
6.4.1 Ambiguous Grammars 199
6.4.2 Grammars that are not LR(k) 202
6.5 Conflict Resolution and Table Construction 204
6.5.1 SLR(k) Table Construction 204
6.5.2 LALR(k) Table Construction 209
6.5.3 LALR Propagation Graph 211
6.5.4 LR(k) Table Construction 219
6.6 Exercises 224
7 Syntax-Directed Translation 235
7.1 Overview 235
7.1.1 Semantic Actions and Values 236
7.1.2 Synthesized and Inherited Attributes 237
7.2 Bottom-Up Syntax-Directed Translation 239
7.2.1 Example 239
7.2.2 Rule Cloning 243
7.2.3 Forcing Semantic Actions 244
7.2.4 Aggressive Grammar Restructuring 246
7.3 Top-Down Syntax-Directed Translation 247
7.4 Abstract Syntax Trees 250
7.4.1 Concrete and Abstract Trees 250
7.4.2 An Efficient AST Data Structure 251
7.4.3 Infrastructure for Creating ASTs 252
7.5 AST Design and Construction 254
7.5.1 Design 256
7.5.2 Construction 258
7.6 AST Structures for Left and Right Values 261
7.7 Design Patterns for ASTs 264
7.7.1 Node Class Hierarchy 264
7.7.2 Visitor Pattern 265
7.7.3 Reflective Visitor Pattern 268
7.8 Exercises 272
8 Symbol Tables and Declaration Processing 279
8.1 Constructing a Symbol Table 280
8.1.1 Static Scoping 282
8.1.2 A Symbol Table Interface 282
8.2 Block-Structured Languages and Scopes 284
8.2.1 Handling Scopes 284
8.2.2 One Symbol Table or Many? 285
8.3 Basic Implementation Techniques 286
8.3.1 Entering and Finding Names 286
8.3.2 The Name Space 289
8.3.3 An Efficient Symbol Table Implementation 290
8.4 Advanced Features 293
8.4.1 Records and Typenames 294
8.4.2 Overloading and Type Hierarchies 294
8.4.3 Implicit Declarations 296
8.4.4 Export and Import Directives 296
8.4.5 Altered Search Rules 297
8.5 Declaration Processing Fundamentals 298
8.5.1 Attributes in the Symbol Table 298
8.5.2 Type Descriptor Structures 299
8.5.3 Type Checking Using an Abstract Syntax Tree 300
8.6 Variable and Type Declarations 303
8.6.1 Simple Variable Declarations 303
8.6.2 Handling Type Names 304
8.6.3 Type Declarations 305
8.6.4 Variable Declarations Revisited 308
8.6.5 Static Array Types 311
8.6.6 Struct and Record Types 312
8.6.7 Enumeration Types 313
8.7 Class and Method Declarations 316
8.7.1 Processing Class Declarations 317
8.7.2 Processing Method Declarations 321
8.8 An Introduction to Type Checking 323
8.8.1 Simple Identifiers and Literals 327
8.8.2 Assignment Statements 328
8.8.3 Checking Expressions 328
8.8.4 Checking Complex Names 329
8.9 Summary 334
8.10 Exercises 336
9 Semantic Analysis 343
9.1 Semantic Analysis for Control Structures 343
9.1.1 Reachability and Termination Analysis 345
9.1.2 If Statements 348
9.1.3 While, Do, and Repeat Loops 350
9.1.4 For Loops 353
9.1.5 Break, Continue, Return, and Goto Statements 356
9.1.6 Switch and Case Statements 364
9.1.7 Exception Handling 369
9.2 Semantic Analysis of Calls 376
9.3 Summary 384
9.4 Exercises 385
10 Intermediate Representations 391
10.1 Overview 392
10.1.1 Examples 393
10.1.2 The Middle-End 395
10.2 Java Virtual Machine 397
10.2.1 Introduction and Design Principles 398
10.2.2 Contents of a Class File 399
10.2.3 JVM Instructions 401
10.3 Static Single Assignment Form 410
10.3.1 Renaming and φ-functions 411
10.4 Exercises 414
11 Code Generation for a Virtual Machine 417
11.1 Visitors for Code Generation 418
11.2 Class and Method Declarations 420
11.2.1 Class Declarations 422
11.2.2 Method Declarations 424
11.3 The MethodBodyVisitor 425
11.3.1 Constants 425
11.3.2 References to Local Storage 426
11.3.3 Static References 427
11.3.4 Expressions 427
11.3.5 Assignment 429
11.3.6 Method Calls 430
11.3.7 Field References 432
11.3.8 Array References 433
11.3.9 Conditional Execution 435
11.3.10 Loops 436
11.4 The LHSVisitor 437
11.4.1 Local References 437
11.4.2 Static References 438
11.4.3 Field References 439
11.4.4 Array References 439
11.5 Exercises 441
12 Runtime Support 445
12.1 Static Allocation 446
12.2 Stack Allocation 447
12.2.1 Field Access in Classes and Structs 449
12.2.2 Accessing Frames at Runtime 450
12.2.3 Handling Classes and Objects 451
12.2.4 Handling Multiple Scopes 453
12.2.5 Block-Level Allocation 455
12.2.6 More About Frames 457
12.3 Arrays 460
12.3.1 Static One-Dimensional Arrays 460
12.3.2 Multidimensional Arrays 465
12.4 Heap Management 468
12.4.1 Allocation Mechanisms 468
12.4.2 Deallocation Mechanisms 471
12.4.3 Automatic Garbage Collection 472
12.5 Region-Based Memory Management 479
12.6 Exercises 482
13 Target Code Generation 489
13.1 Translating Bytecodes 490
13.1.1 Allocating memory addresses 493
13.1.2 Allocating Arrays and Objects 493
13.1.3 Method Calls 496
13.1.4 Example of Bytecode Translation 498
13.2 Translating Expression Trees 501
13.3 Register Allocation 505
13.3.1 On-the-Fly Register Allocation 506
13.3.2 Register Allocation Using Graph Coloring 508
13.3.3 Priority-Based Register Allocation 516
13.3.4 Interprocedural Register Allocation 517
13.4 Code Scheduling 519
13.4.1 Improving Code Scheduling 523
13.4.2 Global and Dynamic Code Scheduling 524
13.5 Automatic Instruction Selection 526
13.5.1 Instruction Selection Using BURS 529
13.5.2 Instruction Selection Using Twig 531
13.5.3 Other Approaches 532
13.6 Peephole Optimization 532
13.6.1 Levels of Peephole Optimization 533
13.6.2 Automatic Generation of Peephole Optimizers 536
13.7 Exercises 538
14 Program Optimization 547
14.1 Overview 548
14.1.1 Why Optimize? 549
14.2 Control Flow Analysis 555
14.2.1 Control Flow Graphs 556
14.2.2 Program and Control Flow Structure 559
14.2.3 Direct Procedure Call Graphs 560
14.2.4 Depth-First Spanning Tree 560
14.2.5 Dominance 565
14.2.6 Simple Dominance Algorithm 567
14.2.7 Fast Dominance Algorithm 571
14.2.8 Dominance Frontiers 581
14.2.9 Intervals 585
14.3 Introduction to Data Flow Analysis 598
14.3.1 Available Expressions 598
14.3.2 Live Variables 601
14.4 Data Flow Frameworks 604
14.4.1 Data Flow Evaluation Graph 604
14.4.2 Meet Lattice 606
14.4.3 Transfer Functions 608
14.5 Evaluation 611
14.5.1 Iteration 611
14.5.2 Initialization 615
14.5.3 Termination and Rapid Frameworks 616
14.5.4 Distributive Frameworks 620
14.6 Constant Propagation 623
14.7 SSA Form 627
14.7.1 Placing φ-Functions 629
14.7.2 Renaming 631
14.8 Exercises 636
Bibliography 651
Abbreviations 661
Pseudocode Guide 663
Index 667
