第一部分　基本控制结构

第一章　有限状态模型

1.1　有限状态机

目录

前言

1.2　非确定的FSM

1.3　语言和正规表达式

1.4　正规表达式与FSM的等价性

1.5　计算模型“能力”的描述

1.6　文献概述

第二章　其它控制模型：框图和程序

2.1　框图

2.2　简单程序设计语言的控制结构

2.3　框图与程序的等价性

2.4　文献概述

第三章　其它控制结构

3.1　选择结构

3.2　重复结构

3.3　程式

3.5　文献概述

3.4　小结：等价性、能力和方便性

第四章　控制的表示

4.1　FCL/2结构的表示

4.2　其它控制结构的表示

4.3　程式的表示

4.4　文献概述

第五章　程序的形式描述与证明

5.1　程序的功能描述

5.2　程序证明

5.3　计算wp：语言的语义

5.4　正确性论证的脆弱性

5.5　确认：测试与验证

5.6　文献概述

第六章　计算效率的测定

6.1　两个简单例子

6.2　阶算法

6.3　效率信息的收集和应用

6.4　性能的实验测定

6.5　性能的分析测定

6.6　文献概述

7.1　引言

第七章　数据的数学模型

第二部分　基本数据结构

7.2　存贮器、变量、名字和值

7.3　类型

7.4　类型的描述

7.5　文献概述

第八章　程序设计语言中的数据

8.1　纯量类型

8.2　名字和引用

8.3　构造类型

8.4　程序设计语言中出现的与数据有关的其它问题

8.5　文献概述

第九章　抽象构造类型

9.1　线性结构

9.2　非线性结构

9.3　文献概述

第十章　数据的表示

10.1　数据的表示技术

10.2　栈的表示

10.3　双排队与排队的表示

10.4　树与图的表示

10.5　集合的表示

10.6　多维数组的表示

10.7　文献概述

第十一章　数据表示的正确性

11.1　一个例子：栈类型的证明

11.2　一般方法

11.3　间接引用赋值的最弱前置条件

11.4　文献概述

第十二章　空间要求

12.1　静态空间要求

12.2　动态空间要求

12.3　设计判定和表示权衡

12.4　文献概述

第三部分　控制与数据的相互作用

第十三章　计算模型和文法

13.1　下推自动机

13.2　图灵机

13.3　元语言和产生式

13.4　文献概述

第十四章　递归及其有关问题

14.1　动态数据类型

14.2　递归

14.3　递归的能力

14.4　分而治之

14.5　动态类型上的递归操作：遍历树

14.6　文献概述

第十五章　标识符的解释

15.1　标识符的作用域（续）

15.2　存贮作用期（续）

15.3　标识符与值的结合

15.4　文献概述

16.1　具有静态存贮管理的语言

第十六章　高级语言的运行时表示

16.2　“基于栈的”语言

16.3　外层寻址和层次显示表

16.4　数组的存贮分配

16.5　分程序结构

16.6　过程参数

16.7　参数机构

16.8　堆式存贮分配

16.9　文献概述

17.1　递归程序的证明

第十七章　有关递归的推理

17.2　结构归纳法

17.3　文献概述

第十八章　递归算法的分析

18.1　递归程序代价函数的例子

18.2　几个熟悉的数学递归关系

18.3　代价函数例子的解答

18.4　解答分而治之递归的一般规则

18.5　文献概述

19.1　背景

第十九　章在程序设计中使用FSM：一个例子

第四部分　实例研究

19.2　问题的提出

19.3　基于FSM的解答

19.4　用于解答的抽象程序

19.5　用于解答的具体程序

19.6　词法分析程序的正确性

19.7　词法分析程序的性能

第二十章　集合的快速实现：一个例子

20.1　背景

20.2　问题的提出

20.3　使用表与树的一种实现

20.4　SetofElts类型的使用

20.5　用于解答的程序

20.6　SetofElts类型的正确性

20.7　SetofElts类型的性能

20.8　表示的选择

第二十一章　生成程序：编写在集合上操作的循环

21.1　对集合元素操作的循环

21.2　用穿线树实现的一种解答

21.3　用于解答的程序

21.4　集合操作的再实现

第二十二章　公式处理：定义数据类型的一个练习

22.1　一些定义

22.2　Expression抽象类型

22.3　原问题的解答

22.4　表达式数据类型的实现

22.5　性能问题及其解答

22.6　小结

第二十三章　产生式系统和简化

23.1　产生式系统

23.2　用模式和替换式扩充Expression类型

23.3　简化程式

23.4　小结

参考文献

附录A　术语与记号

A.1　标准的数学与逻辑记号

A.2　离散数学中的标准定义

A.3　本书中引入的记号

附录B　评价程序的标准

B.1 引言

B.2　程序是由人读的

B.3　如何编写好程序？

附录C　本书所用的程序设计语言

附录D　一台简单的计算机

D.1　存贮器

D.2　输入输出设备

D.3　中央处理机

D.4　指令集

附录E　第四部分程序的汇集

E.1　词法分析程序

E.2　SetofElts类型与SetGen类型

E.3　求导程序与简化程序

汉英名词索引