从为什么学习程序设计语言入手，深入细致地讲解了命令式语言的主要结构及其设计与实现，内容涉及变量、数据类型、表达式和赋值语句、控制语句、子程序、数据抽象机制、对面向对象程序设计的支持（继承和动态方法绑定）、并发、异常处理和事件处理等方面。
程序设计语言原理（英文版·原书第12版）
Concepts of Programming Languages, Twelfth Edition
[美]罗伯特·W. 塞巴斯塔（Robert W. Sebesta） 著
第12版的更新
本书第12版的目标、总体结构以及撰写方法与之前的11个版本相同。第一个目标是介绍现代程序设计语言的基本结构，并为读者提供对现有以及未来的程序设计语言进行严格评估的工具。第二个目标是为学习编译器设计做好准备，为此，本书深入讨论了程序设计语言的结构，展示了描述语法的形式化方法，并介绍了词法和语法分析方法。
与第11版相比，第12版有多个方面的变化。为了保持本书内容不落伍，几乎全部删除了对某些程序设计语言（尤其是Lua和Objective-C）的讨论，而有关较新的程序设计语言Swift的内容则被添加到若干章中。
此外，在第6章中新增了关于可选类型的一节。8.3.4节增加了一些内容以介绍Python中的迭代器。书中还做了一些小改动，以对一些讨论内容进行改正或澄清。具体变化如下：
第2章：增加2.16.4节，介绍Swift；增加2.16.5节，介绍Delphi；删除2.18.6节，不再关注Lua。
第5章：重写5.5.3节的若干段落，改正并澄清一些错误。
第6章：6.3.2节增加一段，介绍Swift对字符串的支持；6.4.2节增加一段，介绍Swift对枚举类型的支持；6.5.3节增加一段，介绍Swift对数组的支持；6.6.1节增加一段，介绍Swift对关联数组的支持；删除6.6.1节中的访谈；增加6.12节，介绍可选类型。
第8章：8.3.1.1节增加一个设计问题，并对其进行了简要讨论；8.3.4节增加几个段落，描述Python中的迭代器。
第9章：9.5.4节增加一段，介绍Swift参数。
第11章：删除11.4.2节，不再关注Objective-C的抽象数据类型。
第12章：删除12.4.5节，不再关注Objective-C；删除表12.1中Objective-C一列；在小结中增加一段，介绍反射。
本书总体框架
本书主要介绍程序设计语言的基本概念。为此，书中讨论了各种语言结构的设计问题，研究了一些常见语言在语言结构上的设计选择，并对设计备选方案进行了严格的比较。
对程序设计语言进行的任何细致研究都无法脱离一些相关的主题，包括描述程序设计语言语法和语义的形式化方法，第3章将介绍这些方法。此外，还必须考虑各种语言结构的实现技术，第4章将讨论词法和语法分析，第10章将介绍子程序链接的实现。本书还将讨论其他语言结构的实现技术。
章节概述
第1章从学习程序设计语言的基本原理开始，然后讨论用于评估程序设计语言和语言结构的标准，同时分析了影响语言设计的主要因素、语言设计中的权衡以及语言实现的基本方法。
第2章概述书中所讨论的语言的发展过程。虽然没有试图完整地描述任何一种语言，但是对每种语言的起源、目标和贡献都会进行讨论。这样的历史回顾是很有价值的，因为它为我们理解当代语言设计的实践和理论基础提供了必要的背景。这也推动了对语言设计与评估的进一步研究。因为本书的其余部分都不依赖于第2章，所以这一章可以独立于其他章节单独阅读。
第3章介绍用于描述程序设计语言的BNF范式的主要形式化方法，首先讨论用于描述语言的语法和静态语义的属性文法，然后探讨语义描述的难点，并对三种最常见的语义方法（操作语义、指称语义和公理语义）进行了简要介绍。
第4章介绍词法分析和语法分析。这一章主要面向那些在课程体系中不设置编译器设计课程的计算机科学院系。与第2章类似，这一章独立于除了第3章之外的所有部分，可以单独阅读。
第5～14章详细讨论程序设计语言中主要结构的设计问题。对于每一种语言结构，都讲述了几种示例语言的设计选择并对其进行了评估。具体来说，第5章介绍变量的一些特性，第6章介绍数据类型，第7章解释表达式和赋值语句，第8章介绍控制语句，第9和10章讨论子程序及其实现，第11章研究数据抽象机制，第12章深入讨论支持面向对象程序设计的语言特性（继承和动态方法绑定），第13章讨论并发程序单元，第14章讨论异常处理并简要介绍事件处理。
第15和16章介绍另外两种重要的程序设计范型：函数式程序设计与逻辑程序设计。注意，第6和8章已经讨论过函数式程序设计语言的某些数据结构和控制构造。第15章介绍Scheme，包括其基本函数、特殊形式、函数形式，以及一些使用Scheme语言编写的简单函数示例。此外，还简要介绍了ML、Haskell和F＃，以说明函数式程序设计的一些不同方向。第16章介绍逻辑程序设计以及逻辑程序设计语言Prolog。
可供使用的语言处理器
本书所讨论的某些程序设计语言的处理器以及相关信息可在以下网站找到：
C、C++、FORTRAN和Ada gcc.gnu.org
C#和F# microsoft.com
Java java.sun.com
Haskell haskell.org
Scheme www.plt-scheme.org/software/drscheme
Perl www.perl.com
Python www.python.org
Ruby www.ruby-lang.org
几乎所有浏览器都包含JavaScript，而PHP事实上也包含在所有Web服务器中。
致授课教师
一般应详细讲解第1和3章。对于第2章，尽管学生会认为很有趣且阅读起来很轻松，但由于缺乏严格的技术内容，不建议安排较多的课时。如前所述，由于后续各章中的内容都不依赖于第2章，因此这一章也可以直接跳过。如果单独设置了编译器设计课程，那么也不需要讲授第4章。
对于那些具有较为丰富的C++、Java或C#编程经验的学生，第5~9章学习起来应该相对容易。第10~14章的内容更具挑战性，需要进行更加详细的讲授。
第15和16章对于大多数低年级学生来说是全新的。在理想情况下，应该为需要学习这些章节的学生提供Scheme和Prolog的语言处理器。充足的学习材料可以使学生通过一些简单的程序来学习。
面向本科生的课程可能无法涵盖本书最后两章的内容。但面向研究生的课程可以跳过前面几章中有关命令式程序设计语言的内容，这样就可以有足够的课时来讨论最后两章。
补充材料1
可以访问www.pearson.com/cs-resources以获取本书的补充材料，包括：
一套讲义幻灯片。本书中的每一章都有配套的幻灯片。
本书中的所有图片。
几种程序设计语言的迷你手册（约100页的教程）。
通过审核的课程教师可通过我们的教师资源中心（www.pearson.com）来获取习题的参考答案。请与你所在学校的Pearson代表联系，或是访问www.pearson.com进行注册。
计算机\程序设计
本书主要介绍程序设计语言的基本概念，讨论语言结构的设计问题，研究C++、Java、Python等常见语言在语言结构上的设计选择，并对设计备选方案进行了严格的比较。
本书有两个主要目标：
·讲解现代程序设计语言的基本结构，并提供对现有以及未来的程序设计语言进行严格评估的工具。
·为学习编译器设计做好准备，介绍描述语法的形式化方法，以及词法和语法分析方法。
第12版对全书内容做了与时俱进的更新，主要包括：
·删除了相对过时的程序设计语言，例如Lua和Objective-C。
·有关新的程序设计语言Swift的内容被添加到若干章中。
·第6章新增了关于可选类型的一节，8.3.4节增加了一些内容以介绍Python中的迭代器。
[美]罗伯特·W. 塞巴斯塔（Robert W. Sebesta） 著：罗伯特·W. 塞巴斯塔（Robert W. Sebesta） 科罗拉多大学科罗拉多斯普林斯分校计算机科学系荣休副教授，拥有40多年的授课经验，研究兴趣包括程序设计语言的设计和评估以及Web程序设计。他拥有宾夕法尼亚州立大学计算机科学硕士和博士学位。
第1章 预备知识 1
1.1 学习程序设计语言原理的原因 2
1.2 程序设计领域 5
1.3 语言评估标准 7
1.4 影响语言设计的因素 17
1.5 程序设计语言的分类 20
1.6 语言设计中的权衡 21
1.7 实现方法 22
1.8 程序设计环境 29
小结·复习题·习题 30
第2章 主要程序设计语言发展简史 33
2.1 Zuse研制的Plankalkül语言 36
2.2 伪代码 37
2.3 IBM 704计算机和Fortran 40
2.4 函数式程序设计语言：Lisp 45
2.5 迈向成熟的第一步：ALGOL 60 50
2.6 计算机化的商业记录：COBOL 56
2.7 分时处理的开始：Basic 61
访谈：Alan Cooper—用户设计与语言设计 64
2.8 满足所有人的需求：PL/I 66
2.9 两种早期的动态语言：APL 和SNOBOL 69
2.10 数据抽象的开端：SIMULA 67 70
2.11 正交设计：ALGOL 68 71
2.12 ALGOL系列语言的早期后代语言 73
2.13 基于逻辑的程序设计：Prolog 77
2.14 历史上规模最大的语言设计工作：Ada 79
2.15 面向对象程序设计：Smalltalk 83
2.16 结合命令式和面向对象的特性：C++ 85
2.17 基于命令式的面向对象语言：Java 89
2.18 脚本语言 92
2.19 .NET旗舰语言：C# 98
2.20 混合标记程序设计语言 100
小结·文献注记·复习题·习题·程序设计练习 102
第3章 语法和语义描述 109
3.1 概述 110
3.2 语法描述的一般问题 111
3.3 语法描述的形式化方法 113
3.4 属性文法 128
历史注记 128
3.5 描述程序的含义：动态语义 134
历史注记 142
小结·文献注记·复习题·习题 155
第4章 词法和语法分析 161
4.1 概述 162
4.2 词法分析 163
4.3 语法分析问题 171
4.4 递归下降的语法分析 175
4.5 自底向上的语法分析 183
小结·复习题·习题·程序设计练习 191
第5章 名字、绑定和作用域 197
5.1 概述 198
5.2 名字 199
历史注记 199
5.3 变量 200
5.4 绑定的概念 203
5.5 作用域 211
5.6 作用域和生存期 222
5.7 引用环境 223
5.8 命名常量 224
小结·复习题·习题·程序设计练习 227
第6章 数据类型 235
6.1 概述 236
6.2 基本数据类型 238
6.3 字符串类型 242
历史注记 243
6.4 枚举类型 247
6.5 数组类型 250
历史注记 251
历史注记 251
6.6 关联数组 261
6.7 记录类型 263
6.8 元组类型 266
6.9 列表类型 268
6.10 联合类型 270
6.11 指针和引用类型 273
历史注记 276
6.12 可选类型 285
6.13 类型检查 286
6.14 强类型化 287
6.15 类型等价 288
6.16 理论和数据类型 292
小结·文献注记·复习题·习题·程序设计练习 294
第7章 表达式和赋值语句 301
7.1 概述 302
7.2 算术表达式 302
7.3 重载运算符 311
7.4 类型转换 313
历史注记 315
7.5 关系表达式和布尔表达式 316
历史注记 316
7.6 短路求值 318
7.7 赋值语句 319
历史注记 323
7.8 混合方式赋值 324
小结·复习题·习题·程序设计练习 324
第8章 语句级控制结构 329
8.1 概述 330
8.2 选择语句 332
8.3 迭代语句 343
8.4 无条件分支 355
历史注记 356
8.5 防护命令 356
8.6 结论 359
小结·复习题·习题·程序设计练习 360
第9章 子程序 365
9.1 概述 366
9.2 子程序基础 366
9.3 子程序的设计问题 374
9.4 局部引用环境 375
9.5 参数传递方法 376
历史注记 384
历史注记 384
9.6 子程序作为参数 392
历史注记 394
9.7 子程序间接调用 394
9.8 函数设计问题 396
9.9 重载子程序 397
9.10 类属子程序 398
9.11 用户定义的重载运算符 404
9.12 闭包 405
9.13 协同程序 407
小结·复习题·习题·程序设计练习 410
第10章 子程序实现 417
10.1 调用和返回的一般语义 418
10.2 “简单”子程序的实现 419
10.3 具有栈动态局部变量的子程序实现 421
10.4 嵌套子程序 429
10.5 程序块 436
10.6 动态作用域的实现 437
小结·复习题·习题·程序设计练习 441
第11章 抽象数据类型和封装结构 447
11.1 抽象的概念 448
11.2 数据抽象概述 449
11.3 抽象数据类型的设计问题 452
11.4 语言示例 453
访谈：Bjarne Stroustrup—C++的诞生、广泛应用及受到的质疑 454
11.5 参数化的抽象数据类型 466
11.6 封装结构 471
11.7 命名封装 474
小结·复习题·习题·程序设计练习 478
第12章 对面向对象程序设计的支持 483
12.1 概述 484
12.2 面向对象程序设计 485
12.3 面向对象语言的设计问题 489
12.4 特定语言对面向对象程序设计的支持 494
访谈：Bjarne Stroustrup—关于程序设计范型和更好的程序设计 498
12.5 面向对象结构的实现 519
12.6 反射 522
小结·复习题·习题·程序设计练习 528
第13章 并发 533
13.1 概述 534
13.2 子程序级并发概述 539
13.3 信号量 544
13.4 管程 549
13.5 消息传递 551
13.6 Ada对并发机制的支持 552
13.7 Java线程 560
13.8 C＃线程 570
13.9 函数式语言中的并发处理 575
13.10 语句级并发 578
小结·文献注记·复习题·习题·程序设计练习 580
第14章 异常处理和事件处理 587
14.1 异常处理概述 588
历史注记 592
14.2 C++中的异常处理 594
14.3 Java中的异常处理 598
14.4 Python和Ruby中的异常处理 605
14.5 事件处理概述 608
14.6 Java中的事件处理 609
14.7 C#中的事件处理 613
小结·文献注记·复习题·习题·程序设计练习 616
第15章 函数式程序设计语言 623
15.1 概述 624
15.2 数学函数 625
15.3 函数式程序设计语言基础 628
15.4 第一个函数式程序设计语言：Lisp 629
15.5 Scheme概述 633
15.6 Common Lisp 651
15.7 ML 653
15.8 Haskell 658
15.9 F# 663
15.10 主要命令式语言对函数式程序设计的支持 666
15.11 函数式语言和命令式语言的比较 669
小结·文献注记·复习题·习题·程序设计练习 671
第16章 逻辑程序设计语言 679
16.1 概述 680
16.2 谓词演算概述 680
16.3 谓词演算和定理证明 684
16.4 逻辑程序设计概述 686
16.5 Prolog的起源 688
16.6 Prolog的基本元素 688
16.7 Prolog的缺点 703
16.8 逻辑程序设计的应用 709
小结·文献注记·复习题·习题·程序设计练习 710
参考文献 715
Contents
Chapter 1 Preliminaries 1
1.1 Reasons for Studying Concepts of Programming Languages..............2
1.2 Programming Domains.........................................................................5
1.3 Language Evaluation Criteria...............................................................7
1.4 Influences on Language Design .........................................................17
1.5 Language Categories...........................................................................20
1.6 Language Design Trade-Offs..............................................................21
1.7 Implementation Methods....................................................................22
1.8 Programming Environments ..............................................................29
Summary . Review Questions . Problem Set ...............................................30
Chapter 2 Evolution of the Major Programming Languages 33
2.1 Zuse’s Plankalkül ...................................................................36
2.2 Pseudocodes.........................................................................................37
2.3 The IBM 704 and Fortran ..................................................................40
2.4 Functional Programming: Lisp...........................................................45
2.5 The First Step Toward Sophistication: ALGOL 60...........................50
2.6 Computerizing Business Records: COBOL.......................................56
2.7 The Beginnings of Timesharing: Basic...............................................61
Interview: ALAN COOPER—User Design and Language Design.........64
2.8 Everything for Everybody: PL/I.........................................................66
2.9 Two Early Dynamic Languages: APL and SNOBOL........................69
2.10 The Beginnings of Data Abstraction: SIMULA 67 ...........................70
2.11 Orthogonal Design: ALGOL 68 ........................................................71
2.12 Some Early Descendants of the ALGOLs..........................................73
2.13 Programming Based on Logic: Prolog ...............................................77
2.14 History’s Largest Design Effort: Ada..................................................79
2.15 Object-Oriented Programming: Smalltalk.........................................83
2.16 Combining Imperative and Object-Oriented Features: C++.............85
2.17 An Imperative-Based Object-Oriented Language: Java.....................89
2.18 Scripting Languages...........................................................92
2.19 The Flagship .NET Language: C#.....................................................98
2.20 Markup-Programming Hybrid Languages.......................................100
Summary . Bibliographic Notes . Review Questions . Problem Set . Programming Exercises .......................102
Chapter 3 Describing Syntax and Semantics 109
3.1 Introduction.......................................................................110
3.2 The General Problem of Describing Syntax ....................................111
3.3 Formal Methods of Describing Syntax.............................................113
3.4 Attribute Grammars ..........................................................128
History Note .........................................................................128
3.5 Describing the Meanings of Programs: Dynamic Semantics...........134
History Note ..................................................................................142
Summary . Bibliographic Notes . Review Questions . Problem Set ........155
Chapter 4 Lexical and Syntax Analysis 161
4.1 Introduction....................................................................162
4.2 Lexical Analysis...............................................................163
4.3 The Parsing Problem ............................................................171
4.4 Recursive-Descent Parsing................................................................175
4.5 Bottom-Up Parsing ...........................................................183
Summary . Review Questions . Problem Set . Programming Exercises ................................191
Chapter 5 Names, Bindings, and Scopes 197
5.1 Introduction....................................................................198
5.2 Names ......................................................................199
History Note ............................................................................199
5.3 Variables..........................................................................200
5.4 The Concept of Binding ...................................................................203
5.5 Scope................................................................................211
5.6 Scope and Lifetime...........................................................222
5.7 Referencing Environments ...............................................................223
5.8 Named Constants................................................................224
Summary . Review Questions . Problem Set . Programming Exercises ..................................227
Chapter 6 Data Types 235
6.1 Introduction.....................................................................236
6.2 Primitive Data Types..............................................238
6.3 Character String Types.....................................................242
History Note ...............................................................................243
6.4 Enumeration Types ............................................................247
6.5 Array Types.........................................................................250
History Note ...........................................................................251
History Note .......................................................................251
6.6 Associative Arrays ...............................................................261
6.7 Record Types ..................................................................263
6.8 Tuple Types....................................................................266
6.9 List Types........................................................................268
6.10 Union Types .......................................................................270
6.11 Pointer and Reference Types ............................................................273
History Note ...............................................................................276
6.12 Optional Types .....................................................................285
6.13 Type Checking......................................................................286
6.14 Strong Typing.......................................................................287
6.15 Type Equivalence...................................................................288
6.16 Theory and Data Types.....................................................................292
Summary . Bibliographic Notes . Review Questions . Problem Set . Programming Exercises ...........294
Chapter 7 Expressions and Assignment Statements 301
7.1 Introduction........................................................................302
7.2 Arithmetic Expressions.............................................................302
7.3 Overloaded Operators.......................................................................311
7.4 Type Conversions .................................................................313
History Note ...............................................................................315
7.5 Relational and Boolean Expressions .................................................316
History Note ..............................................................................316
7.6 Short-Circuit Evaluation.............................................................318
7.7 Assignment Statements .....................................................................319
History Note ............................................................................323
7.8 Mixed-Mode Assignment..................................................................324
Summary . Review Questions . Problem Set . Programming Exercises ....324
Chapter 8 Statement-Level Control Structures 329
8.1 Introduction.......................................................................330
8.2 Selection Statements ............................................................332
8.3 Iterative Statements..............................................................343
8.4 Unconditional Branching..................................................................355
History Note ...............................................................................356
8.5 Guarded Commands .........................................................................356
8.6 Conclusions ...........................................................................359
Summary . Review Questions . Problem Set . Programming Exercises ....360
Chapter 9 Subprograms 365
9.1 Introduction......................................................................366
9.2 Fundamentals of Subprograms .........................................................366
9.3 Design Issues for Subprograms.........................................................374
9.4 Local Referencing Environments .....................................................375
9.5 Parameter-Passing Methods..............................................................376
History Note ............................................................................384
9.6 Parameters That Are Subprograms ..................................................392
History Note ................................................................................394
9.7 Calling Subprograms Indirectly........................................................394
9.8 Design Issues for Functions ..............................................................396
9.9 Overloaded Subprograms..................................................................397
9.10 Generic Subprograms........................................................................398
9.11 User-Defined Overloaded Operators ...............................................404
9.12 Closures ..........................................................................405
9.13 Coroutines ..........................................................................407
Summary . Review Questions . Problem Set . Programming Exercises .....410
Chapter 10 Implementing Subprograms 417
10.1 The General Semantics of Calls and Returns...................................418
10.2 Implementing “Simple” Subprograms..............................................419
10.3 Implementing Subprograms with Stack-Dynamic Local Variables...........................421
10.4 Nested Subprograms .............................................................429
10.5 Blocks..............................................................................436
10.6 Implementing Dynamic Scoping ......................................................437
Summary . Review Questions . Problem Set . Programming Exercises .....441
Chapter 11 Abstract Data Types and Encapsulation Constructs 447
11.1 The Concept of Abstraction .............................................................448
11.2 Introduction to Data Abstraction......................................................449
11.3 Design Issues for Abstract Data Types .............................................452
11.4 Language Examples..............................................................453
Interview: BJARNE STROUSTRUP—C++: Its Birth,
Its Ubiquitousness, and Common Criticisms............................454
11.5 Parameterized Abstract Data Types..................................................466
11.6 Encapsulation Constructs..................................................................471
11.7 Naming Encapsulations ....................................................................474
Summary . Review Questions . Problem Set . Programming Exercises .....478
Chapter 12 Support for Object-Oriented Programming 483
12.1 Introduction.......................................................................484
12.2 Object-Oriented Programming ........................................................485
12.3 Design Issues for Object-Oriented Languages.................................489
12.4 Support for Object-Oriented Programming in Specific Languages ...........................494
Interview: BJARNE STROUSTRUP—On Paradigms and Better Programming..............................498
12.5 Implementation of Object-Oriented Constructs..............................519
12.6 Reflection ..........................................................................522
Summary . Review Questions . Problem Set . Programming Exercises .....528
Chapter 13 Concurrency 533
13.1 Introduction.......................................................................534
13.2 Introduction to Subprogram-Level Concurrency............................539
13.3 Semaphores...........................................................................544
13.4 Monitors ............................................................................549
13.5 Message Passing .................................................................551
13.6 Ada Support for Concurrency...........................................................552
13.7 Java Threads .....................................................................560
13.8 C# Threads..........................................................................570
13.9 Concurrency in Functional Languages.............................................575
13.10 Statement-Level Concurrency..........................................................578
Summary . Bibliographic Notes . Review Questions . Problem Set . Programming Exercises ..........580
Chapter 14 Exception Handling and Event Handling 587
14.1 Introduction to Exception Handling ................................................588
History Note .....................................................................592
14.2 Exception Handling in C++ ..............................................................594
14.3 Exception Handling in Java...............................................................598
14.4 Exception Handling in Python and Ruby.........................................605
14.5 Introduction to Event Handling .......................................................608
14.6 Event Handling with Java .................................................................609
14.7 Event Handling in C# .......................................................................613
Summary . Bibliographic Notes . Review Questions . Problem Set . Programming Exercises .........................616
Chapter 15 Functional Programming Languages 623
15.1 Introduction.........................................................................624
15.2 Mathematical Functions....................................................................625
15.3 Fundamentals of Functional Programming Languages ...................628
15.4 The First Functional Programming Language: Lisp .......................629
15.5 An Introduction to Scheme...............................................................633
15.6 Common Lisp............................................................................651
15.7 ML .......................................................................................653
15.8 Haskell ..................................................................................658
15.9 F# ............................................................................663
15.10 Support for Functional Programming in Primarily Imperative Languages ....................666
15.11 A Comparison of Functional and Imperative Languages.................669
Summary . Bibliographic Notes . Review Questions . Problem Set . Programming Exercises ...........................671
Chapter 16 Logic Programming Languages 679
16.1 Introduction.................................................................680
16.2 A Brief Introduction to Predicate Calculus ......................................680
16.3 Predicate Calculus and Proving Theorems ......................................684
16.4 An Overview of Logic Programming................................................686
16.5 The Origins of Prolog.......................................................................688
16.6 The Basic Elements of Prolog ..........................................................688
16.7 Deficiencies of Prolog .......................................................................703
16.8 Applications of Logic Programming.................................................709
Summary . Bibliographic Notes . Review Questions . Problem Set . Programming Exercises .......710
Bibliography ............................................................................715
