Writing Compilers and Interpreters

Ronald Mak wrote the earlier editions of this very successful book as well as The Martian Principles for Successful Enterprise Systems: 20 Lessons Learned from NASA's Mars Exploration Rover Mission (also published by Wiley). He is also the author of Java Number Cruncher: The Java Programmer's Guide to Numerical Computing. He develops advanced software systems for organizations from startups to NASA. Currently a research staff member at the IBM Almaden Research Center, he also teaches compiler writing and software engineering at San José State University.

• Introduction xxiChapter 1 Introduction 1Goals and Approach 1What Are Compilers and Interpreters? 2Comparing Compilers and Interpreters 4The Picture Gets a Bit Fuzzy 5Why Study Compiler Writing? 6Conceptual Design 6Syntax and Semantics 8Lexical, Syntax, and Semantic Analyses 10Chapter 2 Framework I: Compiler and Interpreter 11Goals and Approach 11Language-Independent Framework Components 12Front End 13Parser 16Intermediate Tier 34Back End 36Pascal-Specific Front End Components 37Pascal Parser 37Pascal Scanner 39A Front End Factory 41Initial Back End Implementations 43Interpreter 44A Back End Factory 45Program 2: Program Listings 46Chapter 3 Scanning 55Goals and Approach 55Program 3: Pascal Tokenizer 57Syntax Error Handling 65How to Scan for Tokens 72A Pascal Scanner 75Pascal Tokens 77Syntax Diagrams 80Word Tokens 81String Tokens 82Special Symbol Tokens 85Number Tokens 88Chapter 4 The Symbol Table 97Goals and Approach 97Symbol Table Conceptual Design 98The Symbol Table Stack 98Symbol Table Interfaces 100A Symbol Table Factory 105Symbol Table Implementation 107Program 4: Pascal Cross-Referencer I 113Chapter 5 Parsing Expressions and Assignment Statements 121Goals and Approach 121Syntax Diagrams 122Intermediate Code Conceptual Design 125Intermediate Code Interfaces 126An Intermediate Code Factory 129Intermediate Code Implementation 130Printing Parse Trees 135Parsing Pascal Statements and Expressions 141Parsing Statements 145Parsing the Compound Statement 148Parsing the Assignment Statement 149Parsing Expressions 151Program 5: Pascal Syntax Checker I 161Chapter 6 Interpreting Expressions and Assignment Statements 167Goals and Approach 167Runtime Error Handling 168Executing Assignment Statements and Expressions 170The Statement Executor Subclasses 170Executing Statements 173Executing the Compound Statement 175Executing the Assignment Statement 175Executing Expressions 177Program 6: Simple Interpreter I 184Chapter 7 Parsing Control Statements 189Goals and Approach 189Syntax Diagrams 190Error Recovery 191Program 7: Syntax Checker Ii 192Control Statement Parsers 193Parsing Pascal Control Statements 198Parsing the REPEAT Statement 198Parsing the WHILE Statement 202Parsing the FOR Statement 207Parsing the IF Statement 214Parsing the CASE Statement 219Chapter 8 Interpreting Control Statements 233Goals and Approach 233Program 8: Simple Interpreter Ii 233Interpreting Control Statements 234Executing a Looping Statement 236Executing the IF Statement 240Executing the SELECT Statement 241An Optimized SELECT Executor 245Chapter 9 Parsing Declarations 249Goals and Approach 249Pascal Declarations 250Types and the Symbol Table 253Type Specification Interfaces 253Pascal Type Specification Implementation 255A Type Factory 260Scope and the Symbol Table Stack 261How Identifiers Are Defined 266Predefined Types and Constants 268Parsing Pascal Declarations 271Parsing Constant Definitions 277Parsing Type Definitions and Type Specifications 283Parsing Variable Declarations 301Program 9: Pascal Cross-referencer II 306Chapter 10 Type Checking 331Goals and Approach 331Type Checking 331Type Checking Expressions 335Type Checking Control Statements 350Program 10: Pascal Syntax Checker III 358Chapter 11 Parsing Programs, Procedures, and Functions 371Goals and Approach 371Program, Procedure, and Function Declarations 372Nested Scopes and the Symbol Table Stack 375New Declarations Parser Subclasses 378Parsing a Program Declaration 382Parsing Procedure and Function Declarations 382Formal Parameter Lists 388Parsing Procedure and Function Calls 394Calls to Declared Procedures and Functions 398Calls to the Standard Procedures and Functions 400Actual Parameter Lists 408Program 11: Pascal Syntax Checker IV 418Chapter 12 Interpreting Pascal Programs 431Goals and Approach 431Runtime Memory Management 432The Runtime Stack and Activation Records 432The Runtime Display 436Recursive Calls 439Memory Management Interfaces and Implementation 440The Memory Factory 459Executing Statements and Expressions 460The Executor Superclass 461The Statement Executor 462The Assignment and Expression Executors 469Executing Procedure and Function Calls 478Parameter Passing 478Calling Procedures and Functions 478Program 12-1: Pascal Interpreter 493Chapter 13 An Interactive Source-Level Debugger 501Goals and Approach 501Machine-Level vs. Source-Level Debugging 502Debugger Architecture 503Runtime Data Input vs. Debugger Command Input 514Creating a Command-Line Debugger 516A Simple Command Language 517Displaying Values 522Parsing Variable Names 525Executing Commands 529Program 13-1: Command-Line Source-Level Debugger 540Chapter 14 Framework II: An Integrated Development Environment (IDE) 543Goals and Approach 544The IDE Window 544The Edit Window 545The Debug Window 545The Call Stack Window 547The Console Window 548Program 14: Pascal IDE 548The IDE Process and the Debugger Process 549The IDE Framework 549Interprocess Communication 550The Control Interface 560The Debugger Process 566Chapter 15 Jasmin Assembly Language and Code Generation for the Java Virtual Machine 577Goals and Approach 577Organization of the Java Virtual Machine 578The Class Area 578The Heap Area 579The Java Runtime Stack 579JVM Limitations 580The Jasmin Assembly Language 581Assembly Statements 581Program Structure 593Emitting Instructions 604Load and Store Instructions 607Data Manipulation Instructions 617Control Instructions 620Remaining Code Generation Methods 623Chapter 16 Compiling Programs, Assignment Statements, and Expressions 625Goals and Approach 625Compiling Programs 626Program Header 627Class Constructor 627Fields 627Main Method 628Code Generator Subclasses 629Compiling Procedures and Functions 635Parser and Symbol Table Changes 637Generating Code for Procedures and Functions 639Compiling Assignment Statements and Expressions 643The Statement Code Generator 643The Compound Statement Code Generator 645The Assignment Statement Code Generator 646The Expression Code Generator 648The Pascal Runtime Library 655Range Checking 655Pascal Text Input 656Building the Library 657Program 16-1: Pascal Compiler I 657Chapter 17 Compiling Procedure and Function Calls and String Operations 661Goals and Approach 661Compiling Procedure and Function Calls 662Value Parameters and VAR Parameters 664Calls to Declared Procedures and Functions 666Calls to the Standard Procedures and Functions 678The Pascal Runtime Library 691Pascal Input Text 692Building the Library 697Compiling Strings and String Assignments 698Allocating String Variables 698String Assignments 701String Comparisons 705Program 17-1: Pascal Compiler II 711Chapter 18 Compiling Control Statements, Arrays, and Records 719Goals and Approach 719Compiling Control Statements 719Looping Statements 720The IF Statement 730The SELECT Statement 735Compiling Arrays and Subscripted Variables 744Allocating Memory for Arrays 744Subscripted Variables in Expressions and Assignments 757Compiling Records and Record Fields 767Allocating Records 768Record Fields in Expressions and Assignments 772Program 18-1: Pascal Compiler III 777Chapter 19 Additional Topics 791Scanning 791Deterministic Finite Automata (DFA) 791Table-Driven Scanners 793Syntax Notation 796Backus-Naur Form (BNF) 796Extended BNF (EBNF) 797Grammars and Languages 797Parsing 798Top-Down Parsers 798Bottom-Up Parsers 798Context-Free and Context-Sensitive Grammars 800Code Generation 800Instruction Selection 800Instruction Scheduling 801Register Allocation 803Code Optimization 803Debugging Compilers and Optimizing Compilers 804Speed Optimizations 804Runtime Memory Management 807Heap and Stack 807Garbage Collection 808Compiling Object-Oriented Languages 809Method Overloading and Name Mangling 809Inheritance 810Virtual Methods 810Compiler-Compilers 811JavaCC 811Lex and Yacc 813Index 817