编程语言——设计与实现(影印版) (2008 年度畅销榜NO.9193 )

本书系统地讲述了编程语言，包括C、C++、Java和PERL等11种语言，内容包括编程语言简史、编程环境、编程语言语法、语言模型、基本数据类型、封装、继承、程序控制、子程序控制、存储管理、分布式处理和网络编程等。\r\n\r\n 本书的范例以多种编程语言表述，显示了编程技巧的通用性。本书内容丰富，适合专、本科学生和程序员使用。\r\n
\r\n

Preface \r\n\r\n Language Design Issues \r\n\r\n 1.1 Why Study Programming Languages? \r\n\r\n 1.2 A Short History of Programming Languages \r\n\r\n 1.2.1 Development of Early Languages \r\n\r\n 1.2.2 Evolution of Software Architectures \r\n\r\n 1.2.3 Application Domains \r\n\r\n 1.3 Role of Programming Languages \r\n\r\n 1.3.1 What Makes a Good Language? \r\n\r\n 1.3.2 Language Paradigms \r\n\r\n 1.3.3 Language Standardization \r\n\r\n 1.3.4 Internationalization \r\n\r\n 1.4 Programming Environments \r\n\r\n 1.4.1 Effects on Language Design \r\n\r\n 1.4.2 Environment Frameworks \r\n\r\n 1.4.3 Job Control and Process Languages \r\n\r\n 1.5 C Overview \r\n\r\n 1.6 Suggestions for Further Reading \r\n\r\n 1.7 Problems \r\n\r\n 2 Impact of Machine Architectures \r\n\r\n 2.1 The Operation of a Computer \r\n\r\n 2.1.1 Computer Hardware \r\n\r\n 2.1.2 Firmware Computers \r\n\r\n 2.1.3 Translators and Virtual Architectures \r\n\r\n 2.2 Virtual Computers and Binding Times \r\n\r\n 2.2.1 Virtual Computers and Language Implementations \r\n\r\n 2.2.2 Hierarchies of Virtual Machines \r\n\r\n 2.2.3 Binding and Binding Time \r\n\r\n 2.2.4 Java Overview \r\n\r\n 2.3 Suggestions for Further Reading \r\n\r\n 2.4 Problems \r\n\r\n 3 Language Translation Issues \r\n\r\n 3.1 Programming Language Syntax \r\n\r\n 3.1.1 General Syntactic Criteria \r\n\r\n 3.1.2 Syntactic Elements of a Language \r\n\r\n 3.1.3 Overall Program-Subprogram Structure \r\n\r\n 3.2 Stages in Translation \r\n\r\n 3.2.1 Analysis of the Source Program \r\n\r\n 3.2.2 Synthesis of the Object Program \r\n\r\n 3.3 Formal Translation Models \r\n\r\n 3.3.1 BNF Grammars \r\n\r\n 3.3.2 Finite-State Automata \r\n\r\n 3.3.3 Perl Overview \r\n\r\n 3.3.4 Pushdown Automata \r\n\r\n 3.3.5 General Parsing Algorithms \r\n\r\n 3.4 Recursive Descent Parsing \r\n\r\n 3.5 Pascal Overview \r\n\r\n 3.6 Suggestions for Further Reading \r\n\r\n 3.7 Problems \r\n\r\n 4 Modeling Language Properties \r\n\r\n 4.1 Formal Properties of Languages \r\n\r\n 4.1.1 Chomsky Hierarchy \r\n\r\n 4.1.2 Undecidability \r\n\r\n 4.1.3 Algorithm Complexity \r\n\r\n 4.2 Language Semantics \r\n\r\n 4.2.1 Attribute Grammars \r\n\r\n 4.2.2 Denotational Semantics \r\n\r\n 4.2.3 ML Overview \r\n\r\n 4.2.4 Program Verification \r\n\r\n 4.2.5 Algebraic Data Types \r\n\r\n 4.3 Suggestions for Further Reading \r\n\r\n 4.4 Problems \r\n\r\n Elementary Data Types \r\n\r\n 5.1 Properties of Types and Objects \r\n\r\n 5.1.1 Data Objects, Variables, and Constants \r\n\r\n 5.1.2 Data Types \r\n\r\n 5.1.3 Declarations \r\n\r\n 5.1.4 Type Checking and Type Conversion \r\n\r\n 5.1.5 Assignment and Initialization \r\n\r\n 5.2 Scalar Data Types \r\n\r\n 5.2.1 Numeric Data Types \r\n\r\n 5.2.2 Enumerations \r\n\r\n 5.2.3 Booleans \r\n\r\n 5.2.4 Characters \r\n\r\n 5.3 Composite Data Types \r\n\r\n 5.3.1 Character Strings \r\n\r\n 5.3.2 Pointers and Programmer-Constructed Data Objects \r\n\r\n 5.3.3 Files and Input-Output \r\n\r\n 5.4 FORTRAN Overview \r\n\r\n 5.5 Suggestions for Further Reading \r\n\r\n 5.6 Problems \r\n\r\n Encapsulation \r\n\r\n 6.1 Structured Data Types \r\n\r\n 6.1.1 Structured Data Objects and Data Types \r\n\r\n 6.1.2 Specification of Data Structure Types \r\n\r\n 6.1.3 Implementation of Data Structure Types \r\n\r\n 6.1.4 Declarations and Type Checking for Data Structures \r\n\r\n 6.1.5 Vectors and Arrays \r\n\r\n 6.1.6 Records \r\n\r\n 6.1.7 Lists \r\n\r\n 6.1.8 Sets \r\n\r\n 6.1.9 Executable Data Objects \r\n\r\n 6.2 Abstract Data Types \r\n\r\n 6.2.1 Evolution of the Data Type Concept \r\n\r\n 6.2.2 Information Hiding \r\n\r\n 6.3 Encapsulation by Subprograms \r\n\r\n 6.3.1 Subprograms as Abstract Operations \r\n\r\n 6.3.2 Subprogram Definition and Invocation \r\n\r\n 6.3.3 Subprogram Definitions as Data Objects \r\n\r\n 6.4 Type Definitions \r\n\r\n 6.4.1 Type Equivalence \r\n\r\n 6.4.2 Type Definitions with Parameters \r\n\r\n 6.5 C++ Overview \r\n\r\n 6.6 Suggestions for Further Reading \r\n\r\n 6.7 Problems \r\n\r\n Inheritance \r\n\r\n 7.1 Abstract Data Types Revisited \r\n\r\n 7.2 Inheritance \r\n\r\n 7.2.1 Derived Classes \r\n\r\n 7.2.2 Methods \r\n\r\n 7.2.3 Abstract Classes \r\n\r\n 7.2.4 Smalltalk Overview \r\n\r\n 7.2.5 Objects and Messages \r\n\r\n 7.2.6 Abstraction Concepts \r\n\r\n 7.3 Polymorphism \r\n\r\n 7.4 Suggestions for Further Reading \r\n\r\n 7.5 Problems \r\n\r\n Sequence Control \r\n\r\n 8.1 Implicit and Explicit Sequence Control \r\n\r\n 8.2 Sequencing with Arithmetic Expressions \r\n\r\n 8.2.1 Tree-Structure Representation \r\n\r\n 8.2.2 Execution-Time Representation \r\n\r\n 8.3 Sequence Control Between Statements \r\n\r\n 8.3.1 Basic Statements \r\n\r\n 8.3.2 Structured Sequence Control \r\n\r\n 8.3.3 Prime Programs \r\n\r\n 8.4 Sequencing with Nonarithmetic Expressions \r\n\r\n 8.4.1 Prolog Overview \r\n\r\n 8.4.2 Pattern Matching \r\n\r\n 8.4.3 Unification \r\n\r\n 8.4.4 Backtracking \r\n\r\n 8.4.5 Resolution \r\n\r\n 8.5 Suggestions for Further Reading \r\n\r\n 8.6 Problems \r\n\r\n 9 Subprogram Control \r\n\r\n 9.1 Subprogram Sequence Control \r\n\r\n 9.1.1 Simple Call-Return Subprograms \r\n\r\n 9.1.2 Recursive Subprograms \r\n\r\n 9.1.3 The Pascal Forward Declaration \r\n\r\n 9.2 Attributes of Data Control \r\n\r\n 9.2.1 Names and Referencing Environments \r\n\r\n 9.2.2 Static and Dynamic Scope \r\n\r\n 9.2.3 Block Structure \r\n\r\n 9.2.4 Local Data and Local Referencing Environments \r\n\r\n 9.3 Parameter Transmission \r\n\r\n 9.3.1 Actual and Formal Parameters \r\n\r\n 9.3.2 Methods for Transmitting Parameters \r\n\r\n 9.3.3 Transmission Semantics \r\n\r\n 9.3.4 Implementation of Parameter Transmission \r\n\r\n 9.4 Explicit Common Environments \r\n\r\n 9.4.1 Dynamic Scope \r\n\r\n 9.4.2 Static Scope and Block Structure \r\n\r\n 9.5 Suggestions for Further Reading \r\n\r\n 9.6 Problems \r\n\r\n 10 Storage Management \r\n\r\n 10.1 Elements Requiring Storage \r\n\r\n 10.2 Programmer- and System-Controlled Storage \r\n\r\n 10.3 Static Storage Management \r\n\r\n 10.4 Heap Storage Management \r\n\r\n 10.4.1 LISP Overview \r\n\r\n 10.4.2 Fixed-Size Elements \r\n\r\n 10.4.3 Variable-Size Elements \r\n\r\n 10.5 Suggestions for Further Reading \r\n\r\n 10.6 Problems \r\n\r\n 11 Distributed Processing \r\n\r\n 11.1 Variations on Subprogram Control \r\n\r\n 11.1.1 Exceptions and Exception Handlers \r\n\r\n 11.1.2 Coroutines \r\n\r\n 11.1.3 Scheduled Subprograms \r\n\r\n 11.2 Parallel Programming \r\n\r\n 11.2.1 Concurrent Execution \r\n\r\n 11.2.2 Guarded Commands \r\n\r\n 11.2.3 Ada Overview \r\n\r\n 11.2.4 Tasks \r\n\r\n 11.2.5 Synchronization of Tasks \r\n\r\n 11.3 Hardware Developments \r\n\r\n 11.3.1 Processor Design \r\n\r\n 11.3.2 System Design \r\n\r\n 11.4 Software Architecture \r\n\r\n 11.4.1 Persistent Data and Transaction Systems \r\n\r\n 11.4.2 Networks and Client-Server Computing \r\n\r\n 11.5 Suggestions for Further Reading \r\n\r\n 11.6 Problems \r\n\r\n 12 Network Programming \r\n\r\n 12.1 Desktop Publishing \r\n\r\n 12.1.1 LATEX Document Preparation \r\n\r\n 12.1.2 WYSIWYG Editors \r\n\r\n 12.1.3 Postscript \r\n\r\n 12.1.4 Postscript Virtual Machine \r\n\r\n 12.2 The World Wide Web \r\n\r\n 12.2.1 The Internet \r\n\r\n 12.2.2 CGI Scripts \r\n\r\n 12.2.3 Java Applets \r\n\r\n 12.2.4 XML \r\n\r\n 12.3 Suggestions for Further Reading \r\n\r\n 12.4 Problems \r\n\r\n A Language Summaries \r\n\r\n A.1 Ada \r\n\r\n A.I.1 Data Objects \r\n\r\n A.l.2 Sequence Control \r\n\r\n A.2 C \r\n\r\n A.2.1 Data Objects \r\n\r\n A.2.2 Sequence Control \r\n\r\n A.3 C++ \r\n\r\n A.3.1 Data Objects \r\n\r\n A.3.2 Sequence Control \r\n\r\n A.4 FORTRAN \r\n\r\n A.4.1 Data Objects \r\n\r\n A.4.2 Sequence Control \r\n\r\n A.5 Java \r\n\r\n A.5.1 Data Objects \r\n\r\n A.5.2 Sequence Control \r\n\r\n A.6 LISP \r\n\r\n A.6.1 Data Objects \r\n\r\n A.6.2 Sequence Control \r\n\r\n A.7 ML \r\n\r\n A.7.1 Data Objects \r\n\r\n A.7.2 Sequence Control \r\n\r\n A.8 Pascal \r\n\r\n A.8.1 Data Objects \r\n\r\n A.8.2 Sequence Control \r\n\r\n A.9 Peri \r\n\r\n A.9.1 Data Objects \r\n\r\n A.9.2 Sequence Control \r\n\r\n A.10 Postscript \r\n\r\n A.10.1 Data Objects \r\n\r\n A.10.2 Painting Commands \r\n\r\n A.11 Prolog \r\n\r\n A.11.1 Data Objects \r\n\r\n A.11.2 Sequence Control \r\n\r\n A.12 Smalltalk \r\n\r\n A.12.1 Data Objects \r\n\r\n A.12.2 Sequence Control \r\n\r\n A.13 Suggestions for Further Reading \r\n\r\n References \r\n\r\n Index \r\n
\r\n

This fourth edition of Programming Languages: Design and Implementation continues the tradition developed in the earlier editions to describe programming language design by means of the underlying software and hardware architecture that is required for execution of programs written in those languages. This provides the programmer with the ability to develop software that is both correct and efficient in execution. In this new edition, we continue this approach, as well as improve on the presentation of the underlying theory and formal models that form the basis for the decisions made in creating those languages.

Programming language design is still a very active pursuit in the computer science community as languages are born, age, and eventually die. This fourth edition represents the vital languages of the early 21st century. Postscript, Java, HTML, and Perl have been added to the languages discussed in the third edition to reflect the growth of the World Wide Web as a programming domain. The discussion of Pascal, FORTRAN, and Ada has been deemphasized in recognition of these languages' aging in anticipation of possibly dropping them in future editions of this book.

At the University of Maryland, a course has been taught for the past 25 years that conforms to the structure of this book. For our junior-level course, we assume the student already knows C, Java, or C-H- from earlier courses. We then emphasize Smalltalk, ML, Prolog, and LISP, as well as include further discussions of the implementation aspects of C++. The study of C++ furthers the students' knowledge of procedural languages with the addition of object-oriented classes, and the inclusion of LISP, Prolog, and ML provides for discussions of different programming paradigms. Replacement of one or two of these by FORTRAN, Ada, or Pascal would also be appropriate.

It is assumed that the reader is familiar with at least one procedural language, generally C, C++, Java, or FORTRAN. For those institutions using this book at a lower level, or for others wishing to review prerequisite material to provide a framework for discussing programming language design issues, Chapters 1 and 2 provide a review of material needed to understand later chapters. Chapter 1 is a general introduction to programming languages, while Chapter 2 is a brief overview of the underlying hardware that will execute the given program.

The theme of this book is language design and implementation issues. Chapter3, and 5 through 12 provide the basis for this course by describing the underlying grammatical model for programming languages and their compilers (Chapter 3), elementary data types (Chapter 5), data structures and encapsulation (Chapter 6), inheritance (Chapter 7), statements (Chapter 8), procedure invocation (Chapter 9), storage management (Chapter 10), distributed processing (Chapter 11) and network programming (Chapter 12), which form the central concerns in language design.

Chapter 4 is a more advanced chapter on language semantics that includes an introduction to program verification, denotational semantics, and the lambda calculus. It may be skipped in the typical sophomore- or junior-level course. As with the previous editions of this book, we include a comprehensive appendix that is a brief summary of the features in the 12 languages covered in some detail in this book.

The topics in this book cover the 12 knowledge units recommended by the 1991 ACM/IEEE Computer Society Joint Curriculum Task Force for the programming languages subject area [TUCKER et al. 1991].

Although compiler writing was at one time a central course in the computer science curriculum, there is increasing belief that not every computer science student needs to be able to develop a compiler; such technology should be left to the compiler specialist, and the hole in the schedule produced by deleting such a course might be better utilized with courses such as software engineering, database engineering, or other practical use of computer science technology. However, we believe that aspects of compiler design should be part of the background for all good programmers. Therefore, a focus of this book is how various language structures are compiled, and Chapter 3 provides a fairly complete summary of parsing issues.

The 12 chapters emphasize programming language examples in FORTRAN, Ada, C, Java, Pascal, ML, LISP, Perl, Postscript, Prolog, C++, and Smalltalk. Additional examples are given in HTML, PL/I, SNOBOL4, APL, BASIC, and COBOL as the need arises. The goal is to give examples from a wide variety of languages and let the instructor decide which languages to use as programming examples during the course.

Although discussing all of the languages briefly during the semester is appropriate, we do not suggest that the programming parts of this course consist of problems in each of these languages. We think that would be too superficial in one course. Ten programs, each written in a different language, would be quite a chore and would provide the student with little in-depth knowledge of any of these languages. We assume that each instructor will choose three or four languages and emphasize those.

All examples in this book, except for the most trivial, were tested on an appropriate translator; however, as we clearly point out in Section 1.3.3, correct execution on our local system is no guarantee that the translator is processing programs according to the language standard. We are sure that Mr. Murphy is at work here, and some of the trivial examples may have errors. If so, we apologize for any problems that may cause.

To summarize, our goals in producing this fourth edition were as follows:

Provide an overview of the key paradigms used in developing modern programming languages;

Highlight several languages, which provide those features, in sufficient detail to permit programs to be written in each language demonstrating those features;

Explore the implementation of each language in sufficient detail to provide the programmer with an understanding of the relationship between a source program and its execution behavior;

Provide sufficient formal theory to show where programming language design fits within the general computer science research agenda;

Provide a sufficient set of problems and alternative references to allow students the opportunity to extend their knowledge of this important topic.

We gratefully acknowledge the valuable comments received from the users of the third edition of this text and from the hundreds of students of CMSC 330 at the University of Maryland who provided valuable feedback on improving the presentation contained in this book.

Changes to the Fourth Edition. For users familiar with the third edition, the fourth edition has the following changes:

1. A chapter was added (Chapter 12) on the World Wide Web. Java was added as a major programming language, and an overview of HTML and Postscript were added to move the book away from the classical "FORTRAN number-crunching" view of compilers.

2. The material on object-oriented design was moved earlier in the text to indicate its major importance in software design today. In addition, numerous other changes were made by moving minor sections around to better organize the material into a more consistent presentation.

3. We have found that the detailed discussions of languages in Part II of the third edition were not as useful as we expected. A short history of each of the 12 languages was added to the chapter that best represents the major features of that language, and the language summaries in Part II of the third edition were shortened as the appendix. Despite these additions, the size of the book has not increased because we deleted some obsolete material.

Terry Pratt, Howardsville, Virginia

Marv Zelkowitz, College Park, Maryland