程序设计语言概论 复习要点 1 / 28 程序设计语言概论程序设计语言概论 复习整理复习整理 北京大学北京大学 信息科学技术学院信息科学技术学院 刘凯刘凯 0094827000948270 程序设计语言概论 复习要点 2 / 28 目录目录 第一章 概论 . 3 概念. 3 简述. 3 第二章 计算机体系结构 . 4 概念. 4 简述. 4 第三章 语言翻译 . 5 概念. 5 简述. 6 分析. 6 补充. 7 第四章 语言的语义 . 8 概念. 8 简述. 8 分析. 8 第五章 标量和复合数据 . 9 概念. 9 简述. 9 分析. 9 第六章 封装 . 12 概念. 12 简述. 12 分析. 13 第七章 继承 . 16 概念. 16 简述. 16 分析. 17 第八章 顺序控制 . 18 概念. 18 分析. 18 分析. 19 第九章 子程序控制 . 21 概念. 21 简述. 21 分析. 22 第十章 存储管理 . 25 概念. 25 简述. 25 第十一章 分布式处理 . 26 简述. 26 分析. 26 附加章节 常见程序设计语言 . 28 程序设计语言概论 复习要点 3 / 28 第一章第一章 概论概论 概念概念 程序设计语言程序设计语言 用于书写计算机程序的语言。一般包含语法、语义和实现三个部分。 语法表示程序的结构或形式， 亦即表示构成语言的各个记号之间的组合规律， 但不涉及这些 记号的特定含义，也不涉及使用者。语义表示程序的含义，亦即表示按照各种方法所表示的 各个记号的特定含义，但不涉及使用者。语用表示程序与使用者的关系。 简述简述 好的程序设计语言应该具备的基本性质好的程序设计语言应该具备的基本性质 1. 清晰性、简洁性、以及一致性：清晰性、简洁性、以及一致性：既提供思考算法的概念框架，又提供表示算法的手段； 2. 正交性：正交性：语言特征的任意组合都是有意义的； 3. 运用的自然性：运用的自然性：程序的结构反映了算法的逻辑结构； 4. 对抽象的支持：对抽象的支持：程序的数据反映了要解决的问题； 5. 程序易验证性：程序易验证性：验证程序正确地执行了所需的功能； 6. 编程环境：编程环境：对语言的外部支持； 7. 程序的可移植性程序的可移植性： 最终的程序可以从开发它们的计算机上透明地移植到其他计算机系统 上运行； 8. 使用的代价：使用的代价：程序执行、程序翻译、程序创建、程序维护。 语言的四种基本范型语言的四种基本范型 命令型：语言的目标是要理解机器的状态，如C, Pascal, FORTRAN, COBOL； 函数式：语言的目标是理解产生答案的函数，如ML, LISP； 基于规则：指定能够得到问题的解的规则，如Prolog, BNF解析器； 面向对象：融合了命令式语言和函数式语言的命令式语言，如Java, C+, Smalltalk 高级程序设计语言的设计目标高级程序设计语言的设计目标 1. 程序的解决方案与问题的物理结构相匹配； 2. 全世界广泛使用； 3. 易证明解决方案的正确性。 程序设计语言概论 复习要点 4 / 28 第二章第二章 计算机体系结构计算机体系结构 概念概念 语言设计要考虑的基本因素语言设计要考虑的基本因素 1. 硬件计算机； 2. 虚拟计算机（或执行模型） ； 3. 计算模型。 虚拟计算机虚拟计算机 程序运行时的数据和算法所定义的计算机。 简述简述 翻译和解释翻译和解释 翻译：翻译：利用编译程序把用源语言编写的源程序产生目标程序的过程。 翻译过程：翻译过程：高级语言程序翻译器等价的机器语言程序硬件直接执行 翻译器：翻译器：源语言等价的目标语言 解释：解释：通过运行在一台宿主机上的程序仿真另一台以高级语言为机器语言的计算机。 解释过程：解释过程：用宿主机的机器语言构造一个程序集，仿真计算机接受高级语言程序作为输入， 产生输出。 对比：对比： 翻译和解释均以高级语言程序为输入，但是， 1. 翻译为目标码后再运行于实际计算机上；仿真计算机直接执行输入程序。 2. 翻译器以物理输入顺序处理程序语句， 每个语句只处理一次； 仿真器以逻辑控制流处理 程序，可能重复处理某些语句而完全忽略其他语句。 翻译和仿真各有不同优点：翻译和仿真各有不同优点： 1. 有的程序结构最好翻译成更简单的形式， 如循环中语句多次执行， 翻译可省去解码时间。 有的方面最好保持原有形式，在执行时根据需要处理。 2. 翻译的主要缺点是失去了关于程序的一些信息， 单个的高级语言语句比单条机器语言指 令含有更多信息。 3. 仿真的优缺点基本正好相反， 不需要太多的空间来存储代码序列的多份拷贝。 但解码代 价高。 4. 通常，如源语言结构在目标语言中有直接表示，则代码扩展不太严重，可采用翻译。其 他情形，可采用仿真。 程序设计语言概论 复习要点 5 / 28 第三章第三章 语言翻译语言翻译 概念概念 语法语法 单词的组织方式，用来展示单词之间的关系。程序看起来像什么，可以用BNF（上下文无关 文法）来描述。 语义语义 程序的执行行为，也即程序的含义 ，可以分为静态语义和动态语义。 正则表达式正则表达式 是语言定义的另一种形式，等价于 FSA 和正则文法。它定义了三个操作：连接、或、Kleene 闭包。单个终结符是正则表达式，任意两个正则表达式的链接、或，和一个正则表达式的闭 包也是正则表达式。其他都非正则表达式。 FSA(Finite Status Automata)FSA(Finite Status Automata) 具有有穷个状态，其中有一个开始状态，一个或多个终止状态，以及一组从状态到状态的变 迁，组成的自动机，叫做有限状态自动机。分为确定型有穷状态自动机（DFA）和非确定型 有穷状态自动机（NFA） 。 PDA(PDA(Push Down Automat PDA)Push Down Automat PDA) 是类似于 FSA 的抽象模型机，等价于 BNF 文法，它具有有限个状态，有一个下压栈。 运行原理：运行原理： 1. 同时读入输入符号，和堆栈栈顶的符号. 2. 根据读入的两个符号，机器进入新的状态，并且向下推堆栈写入 0 到多个符号. 3. 如果堆栈为空，则接受输入的字符串。 （换句话说，如果 PDA 进入终止状态，则接受字程序设计语言概论 复习要点 6 / 28 符串。) 语法分析树语法分析树 给定文法，使用替换规则生成语言的串的过程中产生的分析树。 文法定义的语言文法定义的语言 句型：句型：任意由起始符号导出的字符串。 句子：句子：通过不同运用替换操作，从起始符导出的，由终结符构成的字符串成为句子。 语言：语言：由文法 G 产生的语言(记为 L(G)是所有由起始符导出的终结符构成的字符串（即句 子）的集合。即：语言是那些只含有终结符的句型的集合。 简述简述 识别句子和识别语言识别句子和识别语言 识别句子：识别句子：通过一个自动机，自动机能够识别出句子。 识别语言：识别语言：不仅能识别所有句子，并且能够做到，是这个语言的都要能识别，不是这个语言 的也要能把它剔除出去。当且仅当正好能够识别这个语言所定义的所有句子。 例如：FSA 可以识别 AnBn 的句子，但是却不能识别这种语言。 分析分析 BNFBNF 文法的扩展表示文法的扩展表示 语法图（也称为铁道图）语法图（也称为铁道图） 程序设计语言概论 复习要点 7 / 28 FSAFSA 与正则表达式的等价性与正则表达式的等价性 FSAFSA 与正则文法的等价性与正则文法的等价性 FSAFSA和和PDAPDA的能力，例如前者不能识别的能力，例如前者不能识别a an nb bn n，而后者能，而后者能 关键区别：关键区别：FSA不能识别anbn语言。注意任何句子都能够被FSA识别，但是FSA不能识别anbn 语言。（识别句子与识别语言的区别） 而PDA能够识别anbn语言，具体的步骤如下： 1. 先将所有符号a 压栈, 然后，对于每个b, 从堆栈中弹出一个a。 2. 如果在输入结束的同时，堆栈也变为空，则字符串被接受。 文法和机器的等价性：文法和机器的等价性： 补充补充 文法的二义性文法的二义性 对相同的字符串，从相同的文法中，可能到的两种不同的语法分析树。 程序设计语言概论 复习要点 8 / 28 第四章第四章 语言的语义语言的语义 概念概念 属性文法属性文法 属性文法的创建过程就是为文法中的每一条规则都定义相关的语义函数。 继承属性继承属性是一个函数，它将树中非终结符值和树中更高层的非终结符值相关联。换言之，任 何规则右端的非终结符的函数值是左端非终结符的函数。 综合属性综合属性是一个函数， 它将左端非终结符和右端非终结符的值相关联， 这些属性在树中向上 传递信息，即从树中下层信息进行“综合” 简述简述 基本语言模型基本语言模型 文法模型文法模型：扩展定义语言的BNF 文法，使得人们可以从程序的语法分析树上获得额外的信 息如属性文法 操作模型操作模型：定义程序如何在一个虚拟机上执行。就像程序在一个真实的计算机上运行一样。 1970年代的维也纳定义语言 应用模型应用模型：将每个程序的计算定义成一个函数。这种定义一般是分层的指称语义 公理模型公理模型：构造形式化的逻辑证明理论，验证程序是否满足了其规约 规约模型规约模型：描述实现程序的各种函数之间的关系 分析分析 1. 2. 程序设计语言概论 复习要点 9 / 28 第五章第五章 标量和复合数据标量和复合数据 概念概念 数据对象数据对象 虚拟机上一个或多个数据片断运行时的组合为数据对象。 数据类型数据类型 一个数据类型是一类数据对象加上创建及操作它们的一组操作。 常量常量 常量是具有名字的数据对象，其值在其生命期内永久不变。 变量变量 一个简单的变量是有名字的简单数据对象，其内容可以发生变化。 强类型强类型 如果我们可以静态地检测程序中的所有类型错误，则称语言是强赋类型的。 类型转换类型转换 如果在类型检查中，参数的实际类型和操作期望的类型间出现不匹配，则可以通过强制（隐 式的类型转换）来改变实际参数的类型为正确类型。这个转换叫类型转换。 简述简述 数据对象的基本属性数据对象的基本属性 1. 类型：类型：通常在程序翻译时，关联数据对象和它可能的取值集合。 2. 位置：位置：通常不由程序员规定，而是系统存储管理负责。 3. 值：值：由赋值操作完成绑定。 4. 名：名：通常在声明时完成绑定，但可被子程序调用和返回修改 5. 部件：部件：通常用指针值相连，可通过指针的修改而变动。 数据类型的规约数据类型的规约包括包括 1. 区分该类型的数据对象的属性。 2. 该类型数据对象可具有的值。 3. 定义该类型数据对象可能处理的操作。 数据类型的实现包括数据类型的实现包括 1. 存储表示：用于在计算机存储器中表示数据对象。 2. 数据类型操作是以特殊的算法或过程表示的方式， 这些算法和过程操纵数据对象的存储 表示。操作是怎么实现的。 分析分析 比较静态和动态类型检查的优缺点比较静态和动态类型检查的优缺点 类型检查：类型检查：指检查程序中每个操作均接收了正确数目的正确类型参数，可在运行时完成，即程序设计语言概论 复习要点 10 / 28 动态类型检查动态类型检查；或编译时检查，即静态类型检查静态类型检查。 动态类型检查的优点：动态类型检查的优点：编程的灵活性。程序员不需考虑类型问题，具有较高灵活性。缺点：缺点： 程序难于调试，不能完全消去