The road to compiler design

This book systematically introduces the design and implementation of a practical Pascal compiler, Neo Pascal. Combined with the source code of Neo Pascal, it describes in detail the core topics of compiler design, such as LL(1) syntax analyzer, symbol table system, intermediate representation, type system, optimization technology, runtime storage management, code generator, etc. Each chapter is accompanied by a small number of exercises based on practical applications, which can be used as reading questions or as course design topics. Compared with other domestic books introducing compiler technology, this book focuses more on the implementation details of the compiler, rather than just theoretical explanations. This book can be read by engineers engaged in compiler design-related work, and can also be used as a reference book for compiler theory courses in computer science majors in colleges and universities. Chapter 1 Overview 1 1.1 Overview of Compilation Technology 1 1.1.1 Basics of Programming Languages ​​1 1.1.2 Translation Mechanism of Programming Languages ​​4 1.1.3 Basic Structure of Compiler 5 1.2 Basics of Pascal Language 8 1.2.1 Introduction to Pascal Language 8 1.2.2 Basic Composition of Pascal Program 9 1.2.3 Declaration Part of Pascal 10 1.2.4 Pascal Types 12 1.2.5 Pascal Operators 15 1.2.6 Pascal Statements 17 1.3 Development Environment and Delphi Basics 18 1.3.1 Development Environment and File List 18 1.3.2 Delphi Basics 19 1.4 In-depth Study 24 1.5 Practice and Thinking 25 1.6 Master Style - Niklaus Wirth 25 Chapter 2 Lexical Analysis 26 2.1 Overview of Lexical Analysis 26 2.1.1 Tasks of Lexical Analysis 26 2.1.2 Classification of words 28 2.2 Design of lexical analyzer 28 2.2.1 Identify words 28 2.2.2 Transformation graph 29 2.2.3 Construct lexical analyzer 31 2.3 Implementation of lexical analyzer 35 2.3.1 Lexical definition 35 2.3.2 Construct transformation graph and transformation table 36 2.3.3 Related data structure 38 2.3.4 Source code implementation 40 2.4 In-depth study 44 2.5 Practice and thinking 45 2.6 Master style - Dennis M. Ritchie 45 Chapter 3 Syntax Analysis 47 3.1 Syntax Description of Programming Language 47 3.1.1 Context-free grammar 47 3.1.2 Derivation 52 3.1.3 Syntax tree 54 3.1.4 Introduction to reduction 57 3.2 Overview of syntax analysis 58 3.2.1 3.2 The task of syntax analysis 58 3.2.2 Top-down syntax analysis 59 3.2.3 Constructing a syntax analyzer 64 3.3 Implementation of a syntax analyzer 71 3.3.1 Grammar definition 71 3.3.2 Syntax analysis table 76 3.3.3 Source code implementation 86 3.4 In-depth study 90 3.5 Practice and thinking 91 3.6 Master style - Edsger Wybe Dijkstra 92 Chapter 4 Symbol table system 93 4.1 Overview of semantic analysis 93 4.1.1 Semantics of programming languages ​​93 4.1.2 Tasks of semantic analysis and IR generation 94 4.1.3 Syntax-directed translation 95 4.2 Symbol table design 98 4.2.1 Overview of symbol table 98 4.2.2 Logical structure of symbol table 99 4.2.3 Example analysis of symbol table 109 4.3 Implementation of declaration part 111 4.3.1 Related Data Structures 111 4.3.2 Main Program Header Declaration 113 4.3.3 Include File Declaration 114 4.3.4 Label Declaration 118 4.3.5 Constant Declaration 119 4.3.6 Type Declaration 120 4.3.7 Variable Declaration 149 4.3.8 Procedure and Function Declaration 152 4.4 In-depth Study 154 4.5 Practice and Thinking 155 4.6 Master Style - John Backus 155 Chapter 5 Intermediate Representation 156 5.1 IR Overview 156 5.1.1 The Role of IR 156 5.1.2 IR Design and Levels 157 5.1.3 The Importance of Designing IR 159 5.2 IR Generation 160 5.2.1 Overview of Three-Address Code 160 5.2.2 Implementation of Three-Address Code in Neo Pascal 164 5.2.3 Translation Mechanism Overview 168 5.3 Statement Translation Overview 170 5.3.1 Statement Translation Basics 170 5.3.2 Translation Auxiliary Functions and Their Implementation 173 5.4 if Statement 176 5.4.1 Translation of if Statement 176 5.4.2 Source Code Implementation 177 5.5 while/repeat Statement 181 5.5.1 Translation of while Statement 181 5.5.2 Source Code Implementation 181 5.5.3 Translation of repeat Statement 184 5.6 for Statement 184 5.6.1 Translation of for Statement 184 5.6.2 Source Code Implementation 186 5.7 case Statement 192 5.7.1 Translation of case Statement 192 5.7.2 Source Code Implementation 193 5.8 Other Statements 199 5.8.1 Translation of break and continue Statements 199 5.8.2 goto 5.8.3 ASM Statement Translation 204 5.9 In-depth Study 208 5.10 Practice and Thinking 208 5.11 Master Style - Kenneth E. Iverson 209 Chapter 6 Expression Semantics 210 6.1 Expression Overview 210 6.2 Type System Basics 211 6.2.1 Type Basics 211 6.2.2 Type System 212 6.2.3 Type Conversion 217 6.3 Type System Implementation 218 6.3.1 Type System Design 218 6.3.2 IR Operands 221 6.3.3 Type Compatibility Implementation 222 6.3.4 Type Inference Implementation 223 6.4 Expression Translation 226 6.4.1 Expression Translation Basics 226 6.4.2 In-depth Expression Translation 229 6.4.3 Implementation of Expression Translation 230 6.5 Operand Translation 247 6.5.1 Address and Form of Operands 247 6.5.2 Basics of Operand Translation 248 6.5.3 Translation of Simple Variable Operands 252 6.5.4 Translation of Record Field Operands 262 6.5.5 Basics of Array Translation 265 6.5.6 Translation of Array Element Operands 270 6.5.7 Translation of Pointer Operations 280 6.6 In-depth Study 286 6.7 Practice and Thinking 286 6.8 Master Style - Alan Kay 287 Chapter 7 Optimization Technology 288 7.1 Overview of Optimization 288 7.1.1 What is Optimization 288 7.1.2 Optimization Level 289 7.2 Control Flow Analysis 290 7.2.1 Flow Graph and Basic Block 290 7.2.2 Data Structure of Flow Graph 292 7.2.3 Construction of flow graph 293 7.2.4 Optimized classification 297 7.3 Data flow analysis 298 7.3.1 Concepts related to data flow 298 7.3.2 Strategies of data flow analysis 298 7.3.3 Active variable analysis 299 7.3.4 ud chain and du chain 301 7.3.5 More data flow issues 302 7.4 Implementation of data flow analysis 303 7.4.1 The basis of fixed value point and reference point analysis 303 7.4.2 Related data structures for fixed value point and reference point analysis 305 7.4.3 Implementation of fixed value point and reference point analysis 307 7.4.4 Implementation of active variable analysis 312 7.4.5 Implementation of ud chain and du chain analysis 314 7.5 Constant propagation and constant folding 321 7.5.1 The basis of constant propagation 321 7.5.2 Implementation of Constant Propagation 324 7.6 Copy Propagation 328 7.6.1 The Basics of Copy Propagation 328 7.6.2 Implementation of Copy Propagation 330 7.7 Algebraic Simplification 333 7.7.7.8 Jump Optimization 339 7.8.1 Jump Optimization Basics 339 7.8.2 Conditional Jump Optimization Implementation 341 7.8.3 Continuous Jump Optimization Implementation 343 7.9 Redundant Code Removal 345 7.9.1 Redundant Code Removal Basics 345 7.9.2 Dead Code Removal Implementation 346 7.9.3 Unreachable Code Removal Implementation 348 7.10 In-depth Study 350 7.11 Practice and Thinking 350 7.12 Master Style—Richard Stallman 351 Chapter 8 Memory Management at Runtime 352 8.1 Overview of Memory Management 352 8.1.1 Memory Area 352 8.1.2 Memory Layout 354 8.1.3 Memory Allocation Basics 356 8.2 8.2.1 Basics of Stack Memory Allocation 357 8.2.2 i386 Stack Memory Allocation 360 8.2.3 In-depth Understanding of Stack Memory Allocation 365 8.3 Implementation of Memory Allocation 368 8.4 Memory Optimization 372 8.4.1 Basics of Memory Optimization 372 8.4.2 Implementation of Memory Optimization 374 8.5 In-depth Learning 381 8.6 Practice and Thinking 382 8.7 Master Style—Bjarne Stroustrup 382 Chapter 9 Target Code Generation 383 9.1 Overview of Target Code Generation 383 9.1.1 Basics of Target Code Generation 383 9.1.2 Instruction Selection 384 9.1.3 Register Allocation 385 9.2 Introduction to Target Machine 386 9.2.1 Target Machine Structure 386 9.2.2 Floating Point Processing Unit 387 9.2.3 Operand Addressing Mode 391 9.2.4 PTR Operator 392 9.2.5 A Complete Assembler 393 9.3 Constructing a Code Generator 393 9.3.1 The Basics of Automatic Code Generator 393 9.3.2 Instruction Templates 394 9.3.3 Register Description 397 9.3.4 Register Allocation 398 9.3.5 The Basic Structure of a Code Generator 402 9.4 In-depth Study 413 9.5 Practice and Thinking 413 9.6 Master Style - Peter Naur 413 Chapter 10 Overview of the GCC Kernel and Modern Compilation Technology 414 10.1 The Current Status and Development of Compilation Technology 414 10.2 Analysis of the GCC Kernel 415 10.2.1 The Basic Structure of GCC 415 10.2.2 GENERIC 416 10.2.3 GIMPLE 416 10.2.4 SSA 426 10.2.5 RTL Overview 428 10.2.6 RTX 430 10.3 Introduction to Dynamic Compilation Technology 436 10.3.1 Basics of Dynamic Compilation Technology 436 10.3.2 Runtime Specificization 437 10.3.3 Dynamic Binary Translation 439 10.4 Introduction to Parallel Compilation Technology 441 10.4.1 Basics of Parallel Compilation Technology 441 10.4.2 Parallel Computers and Compilation Systems 443 10.5 In-depth Study 446 10.6 Master Style - Alan Perlis 447 References 448