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

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

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

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

4、言的区别不在于能力的大小，语义模型* 简单的证明，所有的语言能力都而是形式上的差别： 用反证法证明）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=y8.第五章a）b)c)d)9.e）第六章a）数据对象i. 数据对象的属性ii.

5、 数据值简单数据类型i. 规约：属性，值，操作ii. 实现： 存储表示（ * 实数的表示，带描述算子的， 后一张结构化数组的数据类 型较难一点）操作实现数据对象的声明：i. 声明的内容 ii. 声明的目的类型检查i. 静态和动态类型检查，优缺点和局限性： （ * 思考什么样的情况（什么样的数 据类型） 没法动态检查或静态检查， 为什么会出现运行错 （因为静态检查没有 做或做不到） ）常见基本数据类型的实现：整形，实型，字符（了解软件实现还是硬件实现）i.ii.结构化数据类型： 规约和实现的重点： 不见的数量、 等等）、以及不见的选择和操纵 实现中存在的问题：存储表示（ 部件的访问效率类型、名字

6、、组织方式 （顺序，随机【链表】* 有例子，地址的计算，图形安排）和管理、b)c)i.ii.常见结构化数据类型的实现：数组记录， 子程序：规约和实现1. 规约中存在的问题 定义与激活1. 激活的实现可变记录d） 类型定义i. 类型等价与数据对象相等：1. 类型等价多个对象所具有的类型是否相等， 简单数据类型很容易， 结构化 数组类型等价就比较麻烦（按名判断等价，结构判断等价） ；2. 数据对象相等实在类型等价之后： 即使是等价的数据类型， 数据对象的相 等也不是那么容易判断，非常困难（ * 集合的相等，就很难：不能仅仅判 断 Aj=Bj or not ）10. 第七章a）b)c)d)抽象数据类

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

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

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