北京大学程序设计语言概论考试复习

1、1. 理教103；1.10；8:30-10:30；理科1号楼1809 2. 第一章 a) 程序设计语言的定义 i. 符号+规则 ii. 数据+算法 b) 高级程序设计语言基本特征 i. 形式和编写独立于计算机，比机器语言复杂，跟接近于问题的自然表述 c) 程序设计语言的编程范型 i. 命令型、函数式、逻辑型、面向对象（重要地位） 3. 语言设计要考虑的基本因素 a) 硬件计算机：数据，操作，存储，访问，控制等和语言之间都有一定的对应关系 b) 虚拟计算机（或执行模型） c) 计算模型 4. 语言的实现本质上就是将程序设计语言转换成计算机很处理的数据、指令和算法的过程 a) 翻译、解释 5. 虚

2、拟计算机（重点） a) 程序运行时的数据和算法所定义的计算机 b) 语言中的各种成分最终都会和虚拟计算机中的具体成分绑定起来 i. 绑定和绑定时间：给定一条语句，最终这条语句的成分都需要绑定，关联的时间：运行时、编译时等等（注意） 6. 第三章 a) 语言的语法 i. 一般准则（了解性） ii. 二义性问题、及其解决方法 b) 语言的翻译 i. 分析 1. 词法、语法、语义，各阶段功能 ii. 综合 c) BNF语法（重点 容易出题） i. 文法的推导:从左向右，从右向左 ii. 文法定义的语言：（关键） iii. 语法分析树 iv. 文法的二义性及其解决 d) 有限状态自动机（FSA） i.

3、 FSA的能力 ii. *接受一个句子与识别一个语言的区别：要证明一个文法是上下文无关文法还是正则文法就可以用anbn来判断，因为正则文法是没有办法识别这个语言的，虽然他是可以接受的。 1. 例如：E-E+E|E*E|I正则文法，可以简化为：-|; 2. E-E+E|E*E|i|(E)上下文无关，可以简化为S-aSb|ab： iii. FSA与正则文法、正则表达式的之间的相互装换 e) 下推自动机（PDA） i. 运行原理 的能力PDA ii.7. 第四章 a) 语法模型：乔姆斯基分级文法 i. 形式 ii. 能力 b) 计算模型：图灵机 i. *图灵机的结构、运行原理、能力 ii. 停机问题

4、：图灵机的能力，语言的能力，（*简单的证明，所有的语言能力都是相等的，语言的区别不在于能力的大小，而是形式上的差别：用反证法证明） c) 语义模型 i. 属性文法，表达式的语义：知道一个表达式的属性文法是怎样给出的，课上有一个具体的例子 ii. 公理语义，程序正确性证明：对小型程序来讲不是特别困难，只要给出每一个句子的前置条件和后置条件就可以了 1. 例如t=x; x=y; y=t要证明程序就是做x，y的互换 a) 在每一个语句之前和之后给出它的公理就可以了 i. x=x, y = yt=x,t=x y = yx=y;t=x,x=yy=ty=x,x=y 8. 第五章 a) 数据对象 i. 数据

5、对象的属性 ii. 数据值 b) 简单数据类型 i. 规约：属性，值，操作 ii. 实现：存储表示（*实数的表示，带描述算子的，后一张结构化数组的数据类型较难一点）操作实现 c) 数据对象的声明： i. 声明的内容 ii. 声明的目的 d) 类型检查 i. 静态和动态类型检查，优缺点和局限性：（*思考什么样的情况（什么样的数据类型）没法动态检查或静态检查，为什么会出现运行错（因为静态检查没有做或做不到） e) 常见基本数据类型的实现：整形，实型，字符（了解软件实现还是硬件实现） 9. 第六章 a) 结构化数据类型： i. 规约和实现的重点：不见的数量、类型、名字、组织方式（顺序，随机【链表】等

6、等）、以及不见的选择和操纵 ii. 实现中存在的问题：存储表示（*有例子，地址的计算，图形安排）和管理、部件的访问效率 b) 常见结构化数据类型的实现：数组记录，可变记录 c) 子程序： i. 规约和实现 1. 规约中存在的问题 ii. 定义与激活 激活的实现 1.d) 类型定义 i. 类型等价与数据对象相等： 1. 类型等价多个对象所具有的类型是否相等，简单数据类型很容易，结构化数组类型等价就比较麻烦（按名判断等价，结构判断等价）； 2. 数据对象相等实在类型等价之后：即使是等价的数据类型，数据对象的相等也不是那么容易判断，非常困难（*集合的相等，就很难：不能仅仅判断Aj=Bj or not

7、） 10. 第七章 a) 抽象数据类型 i. 定义与实现： b) 类属的抽象数据类型（*区别与上一个：声明时候int a100，类属抽样数据类型的参数是一个变量，可以有类型参数，如将top = T，而T最后可以用具体类型如int去实例化，给一个抽象数据类型，如何装化为一个类属抽象数据类型；怎样声明一个100个。的堆栈，怎样去实例化） i. 定义与实例化：定义完后事不能直接使用的，需呀实例化 c) 继承 i. 对象的派生（*有很多方式，扩展类或者作为基类，里面某个成分是其他） ii. 方法的继承（*） d) 多态： i. 多台的创建和实现 ii. 动态多态（*书上详细介绍的例子，一个名字有不同参

8、数，根据参数函数有不同的用途，怎样实现多态？并不是要实现很多函数（静态多态），动态多态用一个具体例子） 11. 第八章 a) 算术表达式的顺序控制（主要是命令式控制欲言）： i. 表达式的表示方式 1. 树形的表示方式 a) 树形表示，线性表示 b) 表示方法蕴含（或不蕴含）技术按顺序 i. 前缀后缀都是蕴含，中缀不蕴含 ii. 不同表达方式的计值过程 iii. 计值中存在的问题 1. 计值规则、副作用、出错、布尔表达式短路 a) 计值规则 i. （x=0）?y:y/x积极的计算规则和懒惰的计算规则是有影响的 b) 副作用：表达式中有函数调用时候 c) 布尔表达式短路：xyV()前面为真，后面

9、都不用计算了，就称作布尔表达式的短路 d) *如果出题就会给出这样表达式，让大家有不同的规则去计算结果。 b) 语句的顺序控制 i. 主要控制结构 ii. 结构化程序设计的基本原则 素程序： iii.1. 定义 2. 合式程序的分解 3. 证明不考，*但是会利用将非结构化程序转化为结构化程序，用结构化程序转化为非结构化程序 12. 第九章 a) 简单调用返回（*了解优缺点） i. 基本原理与实现方法 ii. 子程序的激活的实现方式 b) 递归调用：本质上与简单调用没区别，只是一个子程序有多个激活记录而已，一般程序设计语言通过堆栈的方式来实现递归调用 i. 与简单调用返回的异同点 ii. 实现方式 c) 标识符的作用域（或使用范围）与引用环境 i. 静态作用域与动态作用域规则 1. *通过代码段可以知道 2. 动态作用域是通过调用链来决定，如f g intx h,静态作用域只作用域h，而动态作用域而言，如果f（x）g（x）intx hf（x）则动态作用域还有f与g；注意如果f（x）intx g（x）