Crafting A Compiler

Cover......Page 1
Contents......Page 18
1 Introduction......Page 30
 1.1 History of Compilation......Page 31
  1.2.1 Machine Code Generated by Compilers......Page 33
  1.2.2 Target Code Formats......Page 36
 1.3 Interpreters......Page 38
 1.4 Syntax and Semantics......Page 39
  1.4.1 Static Semantics......Page 40
  1.4.2 Runtime Semantics......Page 41
 1.5 Organization of a Compiler......Page 43
  1.5.2 The Parser......Page 45
  1.5.4 Translator (Program Synthesis)......Page 46
  1.5.6 The Optimizer......Page 47
  1.5.8 Compiler Writing Tools......Page 48
 1.6 Programming Language and Compiler Design......Page 49
 1.7 Computer Architecture and Compiler Design......Page 50
  1.8.1 Debugging (Development) Compilers......Page 51
  1.8.3 Retargetable Compilers......Page 52
 1.9 Integrated Development Environments......Page 53
 Exercises......Page 55
2 A Simple Compiler......Page 60
 2.1 An Informal Definition of the ac Language......Page 61
  2.2.1 Syntax Specification......Page 62
  2.2.2 Token Specification......Page 65
 2.3 Phases of a Simple Compiler......Page 66
 2.4 Scanning......Page 67
 2.5 Parsing......Page 68
  2.5.1 Predicting a Parsing Procedure......Page 70
  2.5.2 Implementing the Production......Page 72
 2.6 Abstract Syntax Trees......Page 74
 2.7 Semantic Analysis......Page 75
  2.7.1 Symbol Tables......Page 76
  2.7.2 Type Checking......Page 77
 2.8 Code Generation......Page 80
 Exercises......Page 83
3 Scanning—Theory and Practice......Page 86
 3.1 Overview of a Scanner......Page 87
 3.2 Regular Expressions......Page 89
 3.3 Examples......Page 91
 3.4 Finite Automata and Scanners......Page 93
  3.4.1 Deterministic Finite Automata......Page 94
 3.5 The Lex Scanner Generator......Page 98
  3.5.1 Defining Tokens in Lex......Page 99
  3.5.2 The Character Class......Page 100
  3.5.3 Using Regular Expressions to Define Tokens......Page 102
  3.5.4 Character Processing Using Lex......Page 105
 3.6 Other Scanner Generators......Page 106
  3.7.1 Processing Identifiers and Literals......Page 108
  3.7.2 Using Compiler Directives and Listing Source Lines......Page 112
  3.7.3 Terminating the Scanner......Page 114
  3.7.4 Multicharacter Lookahead......Page 115
  3.7.5 Performance Considerations......Page 116
  3.7.6 Lexical Error Recovery......Page 118
 3.8 Regular Expressions and Finite Automata......Page 121
  3.8.1 Transforming a Regular Expression into an NFA......Page 122
  3.8.2 Creating the DFA......Page 123
  3.8.3 Optimizing Finite Automata......Page 126
  3.8.4 Translating Finite Automata into Regular Expressions......Page 129
 3.9 Summary......Page 132
 Exercises......Page 135
4 Grammars and Parsing......Page 142
 4.1 Context-Free Grammars......Page 143
  4.1.2 Rightmost Derivations......Page 145
  4.1.3 Parse Trees......Page 146
  4.1.4 Other Types of Grammars......Page 147
  4.2.1 Reduced Grammars......Page 149
  4.2.2 Ambiguity......Page 150
 4.3 Transforming Extended Grammars......Page 151
 4.4 Parsers and Recognizers......Page 152
  4.5.1 Grammar Representation......Page 156
  4.5.2 Deriving the Empty String......Page 157
  4.5.3 First Sets......Page 159
  4.5.4 Follow Sets......Page 163
 Exercises......Page 167
5 Top-Down Parsing......Page 172
 5.1 Overview......Page 173
 5.2 LL(k) Grammars......Page 174
 5.3 Recursive-Descent LL(1) Parsers......Page 178
 5.4 Table-Driven LL(1) Parsers......Page 179
 5.5 Obtaining LL(1) Grammars......Page 183
  5.5.1 Common Prefixes......Page 185
  5.5.2 Left Recursion......Page 186
 5.6 A Non-LL(1) Language......Page 188
 5.7 Properties of LL(1) Parsers......Page 190
 5.8 Parse Table Representation......Page 192
  5.8.1 Compaction......Page 193
  5.8.2 Compression......Page 194
 5.9 Syntactic Error Recovery and Repair......Page 197
  5.9.2 Error Repair......Page 198
  5.9.4 Error Recovery in LL(1) Parsers......Page 200
 Exercises......Page 202
6 Bottom-Up Parsing......Page 208
 6.1 Overview......Page 209
 6.2 Shift-Reduce Parsers......Page 210
  6.2.2 LR Parsing as Knitting......Page 211
  6.2.3 LR Parsing Engine......Page 213
  6.2.4 The LR Parse Table......Page 214
  6.2.5 LR(k) Parsing......Page 216
 6.3 LR(0) Table Construction......Page 220
 6.4 Conflict Diagnosis......Page 226
  6.4.1 Ambiguous Grammars......Page 228
  6.4.2 Grammars that are not LR(k)......Page 231
  6.5.1 SLR(k) Table Construction......Page 233
  6.5.2 LALR(k) Table Construction......Page 238
  6.5.3 LALR Propagation Graph......Page 240
  6.5.4 LR(k) Table Construction......Page 248
 Exercises......Page 253
 7.1 Overview......Page 264
  7.1.1 Semantic Actions and Values......Page 265
  7.1.2 Synthesized and Inherited Attributes......Page 266
  7.2.1 Example......Page 268
  7.2.2 Rule Cloning......Page 272
  7.2.3 Forcing Semantic Actions......Page 273
  7.2.4 Aggressive Grammar Restructuring......Page 275
 7.3 Top-Down Syntax-Directed Translation......Page 276
  7.4.1 Concrete and Abstract Trees......Page 279
  7.4.2 An Efficient AST Data Structure......Page 280
  7.4.3 Infrastructure for Creating ASTs......Page 281
 7.5 AST Design and Construction......Page 283
  7.5.1 Design......Page 285
  7.5.2 Construction......Page 287
 7.6 AST Structures for Left and Right Values......Page 290
  7.7.1 Node Class Hierarchy......Page 293
  7.7.2 Visitor Pattern......Page 294
  7.7.3 Reflective Visitor Pattern......Page 297
 Exercises......Page 301
8 Symbol Tables and Declaration Processing......Page 308
 8.1 Constructing a Symbol Table......Page 309
  8.1.2 A Symbol Table Interface......Page 311
  8.2.1 Handling Scopes......Page 313
  8.2.2 One Symbol Table or Many?......Page 314
  8.3.1 Entering and Finding Names......Page 315
  8.3.2 The Name Space......Page 318
  8.3.3 An Efficient Symbol Table Implementation......Page 319
 8.4 Advanced Features......Page 322
  8.4.2 Overloading and Type Hierarchies......Page 323
  8.4.4 Export and Import Directives......Page 325
  8.4.5 Altered Search Rules......Page 326
  8.5.1 Attributes in the Symbol Table......Page 327
  8.5.2 Type Descriptor Structures......Page 328
  8.5.3 Type Checking Using an Abstract Syntax Tree......Page 329
  8.6.1 Simple Variable Declarations......Page 332
  8.6.2 Handling Type Names......Page 333
  8.6.3 Type Declarations......Page 334
  8.6.4 Variable Declarations Revisited......Page 337
  8.6.5 Static Array Types......Page 340
  8.6.6 Struct and Record Types......Page 341
  8.6.7 Enumeration Types......Page 342
 8.7 Class and Method Declarations......Page 345
  8.7.1 Processing Class Declarations......Page 346
  8.7.2 Processing Method Declarations......Page 350
 8.8 An Introduction to Type Checking......Page 352
  8.8.1 Simple Identifiers and Literals......Page 356
  8.8.3 Checking Expressions......Page 357
  8.8.4 Checking Complex Names......Page 358
 8.9 Summary......Page 363
 Exercises......Page 365
 9.1 Semantic Analysis for Control Structures......Page 372
  9.1.1 Reachability and Termination Analysis......Page 374
  9.1.2 If Statements......Page 377
  9.1.3 While, Do, and Repeat Loops......Page 379
  9.1.4 For Loops......Page 382
  9.1.5 Break, Continue, Return, and Goto Statements......Page 385
  9.1.6 Switch and Case Statements......Page 393
  9.1.7 Exception Handling......Page 398
 9.2 Semantic Analysis of Calls......Page 405
 9.3 Summary......Page 413
 Exercises......Page 414
10 Intermediate Representations......Page 420
 10.1 Overview......Page 421
  10.1.1 Examples......Page 422
  10.1.2 The Middle-End......Page 424
 10.2 Java Virtual Machine......Page 426
  10.2.1 Introduction and Design Principles......Page 427
  10.2.2 Contents of a Class File......Page 428
  10.2.3 JVM Instructions......Page 430
 10.3 Static Single Assignment Form......Page 439
  10.3.1 Renaming and Φ-functions......Page 440
 Exercises......Page 443
11 Code Generation for a Virtual Machine......Page 446
 11.1 Visitors for Code Generation......Page 447
 11.2 Class and Method Declarations......Page 449
  11.2.1 Class Declarations......Page 451
  11.2.2 Method Declarations......Page 453
  11.3.1 Constants......Page 454
  11.3.2 References to Local Storage......Page 455
  11.3.4 Expressions......Page 456
  11.3.5 Assignment......Page 458
  11.3.6 Method Calls......Page 459
  11.3.7 Field References......Page 461
  11.3.8 Array References......Page 462
  11.3.9 Conditional Execution......Page 464
  11.3.10 Loops......Page 465
  11.4.1 Local References......Page 466
  11.4.2 Static References......Page 467
  11.4.4 Array References......Page 468
 Exercises......Page 470
12 Runtime Support......Page 474
 12.1 Static Allocation......Page 475
 12.2 Stack Allocation......Page 476
  12.2.1 Field Access in Classes and Structs......Page 478
  12.2.2 Accessing Frames at Runtime......Page 479
  12.2.3 Handling Classes and Objects......Page 480
  12.2.4 Handling Multiple Scopes......Page 482
  12.2.5 Block-Level Allocation......Page 484
  12.2.6 More About Frames......Page 486
  12.3.1 Static One-Dimensional Arrays......Page 489
  12.3.2 Multidimensional Arrays......Page 494
  12.4.1 Allocation Mechanisms......Page 497
  12.4.2 Deallocation Mechanisms......Page 500
  12.4.3 Automatic Garbage Collection......Page 501
 12.5 Region-Based Memory Management......Page 508
 Exercises......Page 511
13 Target Code Generation......Page 518
 13.1 Translating Bytecodes......Page 519
  13.1.2 Allocating Arrays and Objects......Page 522
  13.1.3 Method Calls......Page 525
  13.1.4 Example of Bytecode Translation......Page 527
 13.2 Translating Expression Trees......Page 530
 13.3 Register Allocation......Page 534
  13.3.1 On-the-Fly Register Allocation......Page 535
  13.3.2 Register Allocation Using Graph Coloring......Page 537
  13.3.3 Priority-Based Register Allocation......Page 545
  13.3.4 Interprocedural Register Allocation......Page 546
 13.4 Code Scheduling......Page 548
  13.4.1 Improving Code Scheduling......Page 552
  13.4.2 Global and Dynamic Code Scheduling......Page 553
 13.5 Automatic Instruction Selection......Page 555
  13.5.1 Instruction Selection Using BURS......Page 558
  13.5.2 Instruction Selection Using Twig......Page 560
 13.6 Peephole Optimization......Page 561
  13.6.1 Levels of Peephole Optimization......Page 562
  13.6.2 Automatic Generation of Peephole Optimizers......Page 565
 Exercises......Page 567
14 Program Optimization......Page 576
 14.1 Overview......Page 577
  14.1.1 Why Optimize?......Page 578
 14.2 Control Flow Analysis......Page 584
  14.2.1 Control Flow Graphs......Page 585
  14.2.2 Program and Control Flow Structure......Page 588
  14.2.4 Depth-First Spanning Tree......Page 589
  14.2.5 Dominance......Page 594
  14.2.6 Simple Dominance Algorithm......Page 596
  14.2.7 Fast Dominance Algorithm......Page 600
  14.2.8 Dominance Frontiers......Page 610
  14.2.9 Intervals......Page 614
  14.3.1 Available Expressions......Page 627
  14.3.2 Live Variables......Page 630
  14.4.1 Data Flow Evaluation Graph......Page 633
  14.4.2 Meet Lattice......Page 635
  14.4.3 Transfer Functions......Page 637
  14.5.1 Iteration......Page 640
  14.5.2 Initialization......Page 644
  14.5.3 Termination and Rapid Frameworks......Page 645
  14.5.4 Distributive Frameworks......Page 649
 14.6 Constant Propagation......Page 652
 14.7 SSA Form......Page 656
  14.7.1 Placing Φ-Functions......Page 658
  14.7.2 Renaming......Page 660
 Exercises......Page 665
Bibliography......Page 680
Abbreviations......Page 690
Pseudocode Guide......Page 692
 A......Page 696
 C......Page 697
 D......Page 699
 E......Page 700
 G......Page 701
 I......Page 702
 J......Page 703
 L......Page 704
 M......Page 705
 P......Page 706
 R......Page 707
 S......Page 708
 T......Page 710
 V......Page 711
 Z......Page 712