Programming Languages ​​and Compilers: Language Design and Implementation (3rd Edition) (Wang Xiaobin)

Programming Languages ​​and Compilers: Design and Implementation of Languages ​​is a \"National Planned Textbook for General Higher Education in the 11th Five-Year Plan\". It is a broad-based textbook for computer majors. The new edition covers all knowledge points of the programming language (PL) module except automata in the CC2001 and CCC2002 tutorials. The content involves the design elements, design ideas, design methods, design techniques and design styles of languages ​​and their compilation systems. The book is divided into two parts. The first part, the design of programming languages, includes: introduction, data types, control structures, programming language design, non-procedural programming languages ​​and an introduction to formal semantics; the second part, the implementation (compilation) of programming languages, includes: compilation overview, lexical analysis, top-down syntax analysis, bottom-up syntax analysis, semantic analysis and intermediate code generation, code optimization and target code generation, and organization of runtime storage space. The learning goal of Programming Languages ​​and Compilers: Design and Implementation of Languages ​​(3rd Edition) is to enable readers to master the basic ideas and methods of designing and implementing a programming language, and have the basic ability to analyze, appreciate, evaluate, select, learn, design and implement a language. Programming Languages ​​and Compilers: Language Design and Implementation (3rd Edition) strives to be concise, popular, and readable. It is a textbook for advanced programming language courses and compilation technology courses in university computer science and software engineering majors, and is also a learning reference book for software developers. Part 1: Design of Programming Languages ​​Chapter 1 Introduction 1.1 Introduction 1.2 Imperative Languages ​​1.2.1 Classification of Programming Languages ​​1.2.2 Von Neumann Architecture 1.2.3 Binding and Binding Time 1.2.4 Variables 1.2.5 Virtual Machines 1.3 Program Units 1.4 Introduction to the Development of Programming Languages ​​1.4.1 Early High-Level Languages ​​1.4.2 Early Language Development Stages 1.4.3 Concept Integration Stage 1.4.4 Another Breakthrough 1.4.5 Extensive Exploration 1.4.6 Ada Language 1.4.7 Fourth Generation Languages ​​1.4.8 Languages ​​for the Internet Age 1.4.9 A New Generation of Programming Languages ​​1.4.10 Chinese Programming Language for the Future 1.4.11 Summary Exercises 1 Chapter 2 Data Types 2.1 Introduction 2.2 Internal Types 2.3 User-Defined Types 2.3.1 Cartesian Product 2.3.2 Finite Maps 2.3.3 Sequences 2.3.4 2.3.5 Determine or 2.3.6 Power set 2.4 Pascal language data type structure 2.4.1 Non-struct type 2.4.2 Aggregate structure 2.4.3 Pointer 2.5 Ada language data type structure 2.5.1 Scalar type 2.5.2 Composite type 2.6 C language data type structure 2.6.1 Non-struct type 2.6.2 Aggregate structure 2.6.3 Pointer 2.6.4 Void type 2.7 Java language data type 2.7.1 Intrinsic type 2.7.2 User defined type 2.8 Abstract data type 2.8.1 SIMULA 67 language class mechanism 2.8.2 CLU language abstract data type 2.8.3 Ada language abstract data type 2.8.4 Modula 2 language abstract data type 2.8.5 C++ language abstract data type 2.8.6 Java language abstract data type 2.9 Type checking 2.10 Type conversion 2.11 Type equivalence 2.12 Implementation Model 2.12.1 Implementation Model for Intrinsic Types and User-Defined Non-Structural Types 2.12.2 Implementation Model for Structural Types Exercise 2 Chapter 3 Control Structures 3.1 Introduction 3.2 Statement-Level Control Structures 3.2.1 Sequence Structures 3.2.2 Selection Structures 3.2.3 Loop Structures 3.2.4 Analysis of Statement-Level Control Structures 3.2.5 User-Defined Control Structures 3.3 Unit-Level Control Structures 3.3.1 Explicitly Calling Dependent Units 3.3.2 Implicitly Calling Units - Exception Handling 3.3.3 SIMULA 67 Language Coroutines 3.3.4 Concurrency Unit Exercise 3 Chapter 4 Design of Programming Languages ​​4.1 Definition of Language 4.1.1 Syntax 4.1.2 Semantics 4.2 Grammar 4.2.1 Definition of Grammar 4.2.2 Classification of Grammars 4.2.3 Languages ​​Generated by Grammars 4.2.4 Syntax Trees 4.3 Design of Languages ​​4.3.1 Design of Expressions 4.3.2 5.3.1 Logic programming language 5.3.2 Prolog language overview 5.3.3 Prospects for logic programming 5.4 Object-oriented programming language 5.4.1 Basic concepts of object orientation 5.4.2 Smalltalk language overview 5.4.3 Evaluation of object-oriented languages ​​5.5 Summary exercises 5 Chapter 6 Introduction to formal semantics 6.1 Introduction 6.2 Classification of formal semantics 6.3 Introduction to axiomatic semantics 6.4 9.1 Introduction9.2 Backtracking Analysis9.2.1 The Reason for Backtracking9.2.2 Extracting the Common Left Factor9.2.3 Eliminating Left Recursion9.3 Recursive Descent Analysis9.3.1 The Construction of a Recursive Descent Parser9.3.2 The Expanded BNF 9.4 Predictive Analysis9.4.1 The Predictive Analysis Process9.4.2 The Construction of a Predictive Analysis Table9.4.3 LL(1) Grammar 9.4.4 Non-LL(1) Grammar Exercise 9 Chapter 10 Bottom-up Syntax Parsing 10.1 Introduction 10.1.1 Parse Tree 10.1.2 Canonical Reduction, Phrases, and Handles 10.2 Operator Precedence Parsing 10.2.1 Operator Precedence Grammar 10.2.2 Operator Precedence Parsing Algorithm 10.2.3 Construction of Operator Precedence Relation Table 10.3 LR Parsing 10.3.1 LR Parsing Process 10.3.2 Viable Prefix 10.3.3 LR(0) Itemset Canonical Family 10.3.4 Construction of LR(0) Parsing Table 10.3.5 Construction of SLR(1) Parsing Table Exercise 10 Chapter 11 Semantic Analysis and Intermediate Code Generation 11.1 Introduction to Semantic Analysis 11.1.1 Tasks of Semantic Analysis 11.1.2 Syntax-Directed Translation 11.2 Intermediate Code 11.3 11.6 Translation of Control Statements 11.6.1 Translation of Boolean Expressions 11.6.2 Translation of Unconditional Transfer Statements 11.6.3 Translation of Conditional Statements 11.6.4 Translation of While Statements 11.6.5 Translation of For Statements 11.6.6 Translation of Procedure Calls Exercises 11 Chapter 12 Code Optimization and Target Code Generation 12.1 Local Optimization 12.1.1 Definition of Optimization 12.1.2 Division of Basic Blocks 12.1.3 Program Flow Graph 12.1.4 Optimization within a Basic Block 12.2 Global Optimization 12.2.1 Definition of Loops 12.2.2 Required Node Sets 12.2.3 Loop Search 12.2.4 Loop Optimization 12.3 Parallel Optimization 12.3.1 Data Dependency Analysis 12.3.2 Vectorized Code Generation 12.3.3 Anti-correlation and Output-correlation Elimination 12.3.4 Scalar Expansion 12.3.5 Loop Striping 12.4 Target Code Generation 12.4.1 A Computer Model 12.4.2 Simple Code Generation Method 12.4.3 Register Allocation in Loops Exercise 12 Chapter 13 Runtime Storage Space Organization 13.1 Program Storage Space 13.1.1 Code Space 13.1.2 Data Space 13.1.3 Activation Record 13.1.4 Variable Storage Allocation 13.1.5 Storage Allocation Mode 13.2 Static Allocation 13.3 Stack Allocation 13.3.1 Stack Allocation with Only Semi-static Variables 13.3.2 Stack Allocation of Semi-dynamic Variables 13.3.3 Non-local Environment 13.3.4 Reference to Non-local Environment 13.4 Parameter Passing 13.4.1 Data Parameter Passing 13.4.2 Subroutine Parameter Passing Exercise 13 Appendix A Formal Language and Automata Introduction Questions