程序设计语言 设计与实现 第3版 英文版PDF电子书下载

PartⅠConcepts 1

1 The Study of Programming Languages 2

1.1 Why Study Programming Languages? 2

1.2 A Short History of Programming Languages 5

1.2.1 Development of Early Languages 5

1.2.2 Role of Programming Languages 9

1.3 What Makes a Good Language? 12

1.3.1 Attributes of a Good Language 12

1.3.2 Application Domains 16

1.3.3 I anguage Standardization 19

1.4 Effects of Environments on Languages 23

1.4.1 Batch-Processing Environments 23

1.4.2 Interactive Environments 24

1.4.3 Embedded System Environments 25

1.4.4 Programming Environments 26

1.5 Suggestions for Further Reading 30

1.4.5 Environment Frameworks 30

1.6 Problems 31

2 Language Design Issues 33

2.1 The Structure and Operation of a Computer 33

2.1.1 The Hardware of the Computer 35

2.1.2 Firmware Computers 39

2.1.3 Translators and Software-Simulated Computers 41

2.2 Virtual Computers and Binding Times 45

2.2.1 Syntax and Semantics 46

2.2.2 Virtual Computers and Language Implementations 47

2.2.3 Hierarchies of Computers 48

2.2.4 Binding and Binding Time 50

2.3 Language Paradigms 55

2.4 Suggestions for Further Reading 59

2.5 Problems 59

3.1 Programming Language Syntax 61

3 Language Translation Issues 61

3.1.1 General Syntactic Criteria 62

3.1.2 Syntactic Elements of a Language 66

3.1.3 Overall Program-Subprogram Structure 69

3.2 Stages in Translation 72

3.2.1 Analysis of the Source Program 74

3.2.2 Synthesis of the Object Program 77

3.3 Formal Translation Models 79

3.3.1 BNF Grammars 80

3.3.2 Finite-State Automata 89

3.3.3 Pushdown Automata 93

3.3.4 Efficient Parsing Algorithms 95

3.3.5 Semantic Modeling 98

3.4 Suggestions for Further Reading 102

3.5 Problems 103

4.1.1 Data Objects, Variables, and Constants 107

4.1 Properties of Types and Objects 107

4 Data Types 107

4.1.2 Data Types 112

4.1.3 Specification of Elementary Data Types 113

4.1.4 Implementation of Elementary Data Types 117

4.1.5 Declarations 119

4.1.6 Type Checking and Type Conversion 121

4.1.7 Assignment and Initialization 127

4.2.1 Numeric Data Types 130

4.2 Elementary Data Types 130

4.2.2 Enumerations 137

4.2.3 Booleans 139

4.2.4 Characters 140

4.2.5 Internationalization 141

4.3 Structured Data Types 142

4.3.1 Structured Data Objects and Data Types 142

4.3.2 Specification of Data Structure Types 143

4.3.3 Implementation of Data Structure Types 145

4.3.4 Declarations and Type Checking for Data Structures 149

4.3.5 Vectors and Arrays 151

4.3.6 Records 160

4.3.7 Lists 167

4.3.8 Character Strings 172

4.3.9 Pointers and Programmer-Constructed Data Objects 175

4.3.10 Sets 178

4.3.11 Executable Data Objects 181

4.3.12 Files and Input-Output 181

4.4 Suggestions for Further Reading 187

4.5 Problems 187

5 Abstraction I: Encapsulation 195

5.1 Abstract Data Types 196

5.1.1 Evolution of the Data Type Concept 197

5.1.2 Information Hiding 198

5.2.1 Subprograms as Abstract Operations 200

5.2 Encapsulation by Subprograms 200

5.2.2 Subprogram Definition and Invocation 203

5.2.3 Subprogram Definitions as Data Objects 208

5.3 Type Definitions 209

5.3.1 Type Equivalence 211

5.3.2 Type Definitions with Parameters 215

5.4 Storage Management 216

5.4.1 Major Run-Time Elements Requiring Storage 217

5.4.2 Programmer-and System-Controlled Storage Management 219

5.4.3 Static Storage Management 220

5.4.4 Stack-Based Storage Management 221

5.4.5 Heap Storage Management: Fixed-Size Elements 223

5.4.6 Heap Storage Management: Variable-Size Elements 231

5.5 Suggestions for Further Reading 234

5.6 Problems 234

6 Sequence Control 238

6.1 Implicit and Explicit Sequence Control 238

6.2 Sequencing with Arithmetic Expressions 239

6.2.1 Tree-Structure Representation 240

6.2.2 Execution-Time Representation 248

6.3 Sequencing with Nonarithmetic Expressions 253

6.3.1 Pattern Matching 253

6.3.2 Unification 257

6.3.3 Backtracking 263

6.4 Sequence Control Between Statements 264

6.4.1 Basic Statements 264

6.4.2 Structured Sequence Control 270

6.4.3 Prime Programs 279

6.5 Suggestions for Further Reading 284

6.6 Problems 284

7 Subprogram Control 286

7.1 Subprogram Sequence Control 286

7.1.1 Simple Call-Return Subprograms 288

7.1.2 Recursive Subprograms 292

7.2 Attributes of Data Control 294

7.2.1 Names and Referencing Environments 295

7.2.2 Static and Dynamic Scope 300

7.2.3 Block Structure 303

7.2.4 Local Data and Local Referencing Environments 305

7.3 Shared Data in Subprograms 311

7.3.1 Parameters and parameter Transmission 312

7.3.2 Explicit Common Environments 330

7.3.3 Dynamic Scope 333

7.3.4 Static Scope and Block Stucture 337

7.4 Suggestions for Further Reading 344

7.5 Problems 345

8 Abstraction Ⅱ: Inheritance 350

8.1 Abstract Data Types Revisited 351

8.2 Inheritance 358

8.2.1 Derived Classes 359

8.2.2 Methods 362

8.2.3 Abstract Classes 364

8.2.4 Objects and Messages 366

8.2.5 Abstraction Concepts 370

8.3 Polymorphism 372

8.4 Suggestions for Further Reading 373

8.5 Problems 374

9 Advances in Language Design 375

9.1 Variations on Subprogram Control 377

9.1.1 Exceptions and Exceptions Handlers 377

9.1.2 Coroutines 382

9.1.3 Scheduled Subprograms 383

9.1.4 Nonsequential Execution 385

9.2 Parallel Programming 385

9.2.1 Concurrent Execution 387

9.2.2 Guarded Commands 388

9.2.3 Tasks 391

9.2.4 Synchronization of Tasks 393

9.3 Formal Properties of Languages 404

9.3.1 Chomsky Hierarchy 405

9.3.2 Undecidability 408

9.3.3 Algorithm Complexity 413

9.4 Language Semantics 416

9.4.1 Denotational Semantics 416

9.4.2 Program Verification 423

9.4.3 Algebraic Data Types 428

9.4.4 Resolution 431

9.5 Hardware Developments 433

9.5.1 Processor Design 433

9.5.2 System Design 436

9.6 Software Architecture 438

9.6.1 Persistent Data and Transaction Systems 438

9.6.2 Networks and Client/Server Computing 440

9.6.3 Desktop Publishing 441

9.7 Suggestions for Further Reading 444

9.6.4 Programming Language Trends 444

9.8 Problems 445

PartⅡ Paradigms and Languages 449

10 Simple Procedural Languages 451

10.1 FORTRAN 451

10.1.1 History 452

10.1.2 Hello World 452

10.1.3 Brief Overview of the Language 453

10.1.4 Data Objects 457

10.1.5 Sequence Control 462

10.1.6 Subprograms and Storage Management 468

10.1.7 Abstraction and Encapsulation 470

10.1.8 Language Evaluation 471

10.2 C 471

10.2.2 Hello World 472

10.2.3 Brief Overview of the Language 472

10.2.1 History 472

10.2.4 Data Objects 477

10.2.5 Sequence Control 482

10.2.6 Subprograms and Storage Management 485

10.2.7 Abstraction and Encapsulation 489

10.2.8 Language Evaluation 489

10.3 Suggestions for Further Reading 490

10.4 Problems 490

11 Block-Structured Procedural Languages 492

11.1 Pascal 492

11.1.1 History 493

11.1.2 Hello World 494

11.1.3 Brief Overview of the Language 494

11.1.4 Data Objects 498

11.1.5 Sequence Control 505

11.1.6 Subprograms and Storage Management 509

11.1.8 Language Evaluation 516

11.1.7 Abstraction and Encapsulation 516

11.2 Suggestions for Further Reading 518

11.3 Problems 518

12 Object-Based Languages 520

12.1 Ada 520

12.1.1 History 520

12.1.2 Hello World 522

12.1.3 Brief Overview of the Language 522

12.1.4 Data Objects 527

12.1.5 Sequence Control 536

12.1.6 Subprograms and Storage Management 540

12.1.7 Abstraction and Encapsulation 547

12.1.8 Language Evaluation 549

12.2 C++ 550

12.2.1 History 550

12.2.3 Brief Overview of the Language 551

12.2.2 Hello World 551

12.2.4 Data Objects 556

12.2.5 Sequence Control 561

12.2.6 Subprograms and Storage Management 562

12.2.7 Abstraction and Encapsulation 564

12.2.8 Language Evaluation 564

12.3 Smalltalk 565

12.3.1 History 565

12.3.3 Brief Overview of the Language 566

12.3.2 Hello World 566

12.3.4 Data Objects 570

12.3.5 Sequence Control 572

12.3.6 Subprograms and Storage Management 574

12.3.7 Abstraction and Encapsulation 577

12.3.8 Language Evaluation 577

12.4 Suggestions for Further Reading 578

12.5 Problems 579

13.1 LISP 581

13 Functional Languages 581

13.1.2 Hello World 582

13.1.1 History 582

13.1.3 Brief Overview of the Language 583

13.1.4 Data Objects 587

13.1.5 Sequence Control 589

13.1.6 Subprograms and Storage Management 593

13.1.7 Abstraction and Encapsulation 599

13.1.8 Language Evaluation 599

13.2.2 Hello World 600

13.2 ML 600

13.2.1 History 600

13.2.3 Brief Overview of the Language 601

13.2.4 Data Objects 603

13.2.5 Sequence Control 607

13.2.6 Subprograms and Storage Management 611

13.2.7 Abstraction and Encapsulation 613

13.3 Suggestions for Further Reading 616

13.2.8 Language Evaluation 616

13.4 Problems 617

14 Logic Programming Languages 620

14.1 Prolog 620

14.1.1 History 621

14.1.2 Hello World 621

14.1.3 Brief Overview of the Language 622

14.1.4 Data Objects 625

14.1.5 Sequence Control 626

14.1.6 Subprograms and Storage Management 628

14.1.7 Abstraction and Encapsulation 629

14.1.8 Language Evaluation 630

14.2 Suggestions for Further Reading 630

14.3 Problems 630

References 632

Index 641