程 序 设 计 语 言
P ro g ra m m i ng L a ng ua g e
D e s i g n a nd I m pl e m e nt a t i o n
网络教学程序设计语言 ----------集中复习
程序设计语言种类很多，各有其自身的特点。
本课程不是为了介绍某种具体的程序设计语言的规范、使用，而是抽象出程序设计语言的共同特点，力图系统讲述程序设计语言的语法、
语义和编译实现之间的关系，介绍数据结构、
顺序控制、子程序、封装、继承等概念及其实现技术，涉及函数式语言、逻辑式语言、命令式语言和面向对象的语言。讨论程序设计语言的一般设计和实现方法。
本课程要求学习和复习重点内容
第 2,3,5,6,7,8,9章。
第 2章要求掌握的知识点是,计算机的硬件结构；固件计算机；翻译；编译；解释；虚拟计算机；绑定时间等 。
重点掌握 编译和解释的概念、实现原理和各自的特点；虚拟计算机的概念、层次结构；哪些元素需要进行绑定，它们的绑定时间分别是什么。
第 3章要求掌握的知识点是,语法；语义；二义性；独立子程序定义；独立数据定义；嵌套子程序定义；独立接口定义；词法分析；语法分析；语义分析；优化；连接与载入；语法树；
BNF文法等 。
重点语法、语义、二义性的特点，二义性与语法树之间的关系； 词法分析、语法分析、语分析和代码优化的概念、实现原理； BNF范式的推导。
第 5章要求掌握的知识点是：数据对象、变量、
常量、数据类型、类型检查、类型转换、标量数据类型、复合数据类型等。
重点掌握基本数据类型的概念、存储表示、实现方法；动态类型检查与静态类型检查的特点。
第 6章要求掌握的知识点是：封装、结构化数据类型、数据结构上的操作、向量,数组、记录、列表、集合、数据抽象、信息隐藏、类属子程序、类型定义 等。
重点掌握封装的概念、封装的特点、向量的特点、向量地址的计算、数据结构上操作的实现原理。
第 7章要求掌握的知识点是：抽象、对象、类、
封装、成员、属性、方法、消息、继承、多态、
重载、覆盖等。
重点掌握上述知识点的基本概念、过程抽象和数据抽象的特点、继承的实现方法。重载与覆盖的区别。
第 8章要求掌握的知识点是：顺序控制、表达式的顺序、前缀表示法、中缀表示法、后缀表示法、前缀计算法、中缀计算法、后缀计算法、
一致求值规则、语句级顺序控制、结构化顺序控制 。
重点掌握表达式的优先级别；前缀、中缀、后缀的语法表示方法，并且灵活掌握它们的计算方法的实现原理；结构化定理的概念以及结构化定义所阐述的问题 。
第 9章要求掌握的知识点是：调用、返回、基于堆栈的实现、声明、命名、引用环境、可见性、静态作用域、动态作用域、局部数据、局部引用环境、实际参数、形式参数、参数传递、
静态类型检查、非局部引用共享显式变量等。
重点掌握简单调用 -返回子程序的顺序控制方法、引用环境、各种参数传递的基本思想、变量的作用域。
第 10章要求掌握的知识点是：初始分配、存储单元回收、压缩、存储单元再用、静态存储管理、固定单元大小、引用计数、无用单元、悬挂引用、无用单元回收、可变长单元、首次满足、最佳满足、存储器碎片等。
重点掌握：无用单元以及悬挂引用的概念、存在的危害以及具体的解决方法。
第 11章要求掌握的知识点是：异常、异常处理程序、异常引发、异常传播、协同程序、调度程序、并发运行、任务、任务管理、任务同步、
中断、信号量、消息、任务存储管理、互斥、
临界区、管程、消息传递等。
重点掌握：异常的特点、任务存储管理的具体方法以及消息传递。
通过本门课程的学习：
我们知道程序设计语言经过了低级语言（机器语言、汇编语言）到高级语言的发展，而且仍在继续不断的发展和变化。 经历着应用程序的
,简单性,到,复杂性,；编程强调,技巧性,到,可读性,；追求实现的,高效性,到
,可维护性,和强调,可移植性,的演变。
影响程序设计语言的主要因素有：计算机性能，
应用领域的要求，编程方法，实现方法和标准化。
程序一般计算模型有：命令式语言、应用式语言、基于规则语言和面向对象语言四种，各自具有优点。目前主要使用的仍然是命令式语言和面向对象语言。
程序设计语言具有六个基本特征：数据，基本操作，顺序控制，数据存取，存储管理和操作环境。
固件计算机是一台可进行微编程的硬件计算机上通过微程序模拟实现的计算机。
高级语言程序必须经过翻译成目标语言程序才能在目标计算机上运行。可通过编译和软件解释两种途径。
翻译是将用高级语言编写的源程序转换成实际计算机上等价的机器语言程序（目标程序）。
计算机上的硬件可以直接运行目标程序。翻译是由翻译程序完成的，翻译程序将源程序作为输入，输出结果是功能等价的目标语言程序。
解释是通过使用一台主机上运行的程序来模拟一台机器语言是高级语言的计算机的执行。即使用主机上的机器语言来构造一组程序软件
（模拟软件或解释软件）来模拟或解释运行用高级语言编写的程序所需要的算法和数据结构。
编译与解释的相同点是：二者都接受高级语言作为输入。
编译与解释的不同点是：
– 功能不同：翻译将源程序 — >等价的目标语言程序；
解释直接执行源程序（用户角度看）。
– 顺序控制：翻译遵循输入的物理序列语句；解释遵循程序的逻辑控制流程。
– 执行次数：翻译对每条语句只处理一次；解释则可能对同一条语句反复解释处理（如循环），也可能完全忽略一些语句（如控制流不能到达的语句）。
– 信息完整性：翻译可能造成源程序信息丢失，调试、
测试较为困难；解释不会。
– 代价：翻译需要耗费更大的存储空间；解释需要较长的执行时间（解码时间）。
虚拟计算机是一个层次性的结构，典型的虚拟计算机可分成 7个层次。下层为上层提供支持和服务。
绑定是指程序元素与其特性或性质的约束关系。
绑定时间是指绑定所发生的时间，主要有翻译或时和执行时。绑定和绑定时间可由语言定义或由实现来确定。
绑定时间对于程序设计语言的效率和灵活性起重要的作用。对于追求效率为主要目标的语言，
通常应尽可能进行早绑定。而追求灵活性为主要目标的语言，应采用迟绑定。对于两个兼顾的语言，应提供绑定时间选择机制。
语法是以句子中词的排列来表明它们的彼此关系。它描述了组成一个合法程序的符号的系列，
是理解一个程序的重要手段，也为将源程序翻译成目标程序提供了必要的信息。
通用语法的标准是：好的可读性、可写性、容验证性、易翻译性和无二义性。
二义性是指相同的语法形式允许存在两种或更多的语义解释。二义性的显著特点是存在两棵语法树。无二义性是每个程序语言设计的中心问题。
通常解决二义性的方法是,1）使用定界符； 2）
选择多种语义中的一种作为唯一合理的解释。
翻译可分成两个主要的部分：源程序分析和目标程序的综合。源程序分析包括词法分析、语法分析和语义分析阶段。目标程序的综合包括优化、代码的生成、连接和载入等阶段。
BNF文法是一种结构简单，功能较强的上下文无关文法。 BNF扩充文法进一步增强它的功能。
数据对象的存储与实际计算机数据存储组织的区别在于实际计算机的数据存储区的结构相对简单，以比特流方式组成字节或字（线性结构），具有静态特性。而程序设计语言的虚拟机的数据存储的组织较为复杂，如数组、记录、
堆栈等，具有动态变化的特性 。
每个数据对象都有生存期。如果在生存期内，
一个对象包含的数据值总是作为一个单位操作，
则称该对象为基本数据对象；如果它是其他数据对象的集合，则称为数据结构。
一个数据类型规范的基本组件包括属性、值域和操作。
基本数据类型的实现由三个部分组成，即存储表示、该类型的值和类型操作的算法或过程的集合。
操作可用三种方法实现，即硬件、作为函数或过程子程序、作为嵌入的代码系列。
声明是将程序执行时所需要的数据对象的名字和类型的信息传递给编译器的程序语句。许多语言提供隐式或默认声明。
类型检查是为了检查程序执行的操作是否接收到正确数目的正确类型参数。
类型检查有动态类型检查和静态类型检查两种。
动态类型检查与静态类型检查之比较而言动态类型检查较静态灵活；动态类型检查的执行效率较低；基于动态类型检查的程序调试较难；动态类型检查的存储代价较高。
标量数据对象是指只有单一属性的基本数据对象。
而复合数据对象具有多种属性。一般，标量数据对象随计算机硬件结构的不同而变化。而复合数据类型不是由硬件实现的数据对象，从而与硬件无关。
创建新的数据类型及其操作有 4种机制：结构化的数据、子程序、类型声明和继承。
数据结构是一个包含其他数据对象作为其元素和成员的数据对象。
数据结构的主要属性包括：成员的数目、成员的类型、成员的名字、成员数目最大值以及成员的组织。
数据结构有两种基本表示方法：即顺序表示：
一般用于表示固定大小的数据结构，也用于同构的可变长数据结构。链式表示：一般用于可变长数据结构。
向量是指包含固定数目的同种成员的简单线性系列的数据结构。其成员通过下标选择。
子程序是由程序员定义的抽象操作。子程序构成了程序结构的基本构件。 子程序的定义包括两部分：说明和实现。 子程序的实现由程序员完成，但由程序语言本身提供的数据结构和操作来实现的。
子程序定义是程序的一个静态属性，是实际存在的程序段，如果调用了一个子程序，则创建了一个子程序活动。调用完成后，该活动被消除。子程序的活动是一个动态属性，只在程序的执行过程中存在。从子程序模板创建子程序活动时，较好的方法是将模板分成两个部分：静态部分和动态部分。静态部分：常量和可执行代码组成。所有活动可以共享单一的副本。动态部分：不同活动具有相同结构，但具有不同的值。
程序设计语言 ----------集中复习 (二 )
类型相同的判别方法有：类型名字相同和结构相同。类型名字相同的缺点是,1）不允许匿名类型。 2）需要使用全局类型定义。结构相同的缺点是,1）难以判断结构相同； 2）静态类型检查容易漏检； 3）翻译开销大。
对象是对现实世界中事物的抽象，是面向对对象程序的基本封装单位，是类的实例：
类是对象的抽象，是数据和操作的封装体。类是对象的抽象和归纳，对象是类的实例。
属性是事物静态特征的抽象，在程序中用数据成员加以描述；
操作是事物动态特征的抽象，在程序中用成员方法来实现。
抽象可分为过程抽象和数据抽象两类。
过程抽象是指：软件开发者可以把任何一个完成确定功能的操作序列都看作是一个单一的实体。
运用过程抽象，软件开发者可以把一个复杂的功能分解为一些子功能（模块）。使用过程抽象有利于控制、降低整个程序的复杂度，但是，这种方法允许在全系统范围内进行功能的描述，本身自由度大，难于规范化和标准化，不易保证软件的质量，而且操作起来也有一定难度。
数据抽象把系统中需要处理的数据和施加于这些数据之上的操作结合在一起,根据功能,性质,
作用等因素抽象成不同的抽象数据类型 。 数据抽象把数据和操作结合为一个不可分的系统单位一对象,对象的外部只需要知道这个对象能做什么,
而不必知道它是如何做的 。
对象具有三个基本特征：
– 对象标识：即对象的名字,是用户和系统识别它的唯一标志 。
– 属性：用来描述对象的静态特征 。
– 方法：也称为服务或操作,它是对象动态特征
（ 行为 ） 的描述 。
描述一个类需要指明下述三个方面内容：
– 类标识：类的一个有别于其他类的名字 。
– 属性说明：用来描述相同对象的静态特征 。
– 方法说明：用来描述相同对象的动态特征 。
封装也称为信息隐藏，是指利用抽象数据类型将数据和基于数据的操作封装在一起，使其构成一个不可分割的独立实体，数据被保护在抽象数据类型的内部，尽可能地隐藏内部的细节，只保留一些对外接口使之与外部发生联系。
封装能够进行信息隐藏,只保留一些对外接口使之与外部发生联系。系统的其他部分只有通过包裹在数据外面的被授权的操作来与这个抽象数据类型交流与交互。即用户无需知道对象内部方法的实现细节，但可以根据对象提供的外部接口（对象名和参数）访问该对象。
在面向对象的系统中,对象之间的联系是通过消息传递来实现的 。
对象间的联系,只能通过消息传递来进行 。 对象也只有在收到消息时,才被激活,去完成消息要求的功能 。
消息就是向对象发出服务请求,是对数据成员和成员方法的引用 。 它含有下述信息：
– 对象名,提供服务的对象标识；
– 方法名,服务标识；
– 实际参数,输入信息；
– 返回值或操作结果,回答信息 。
多态是指一个操作符或子程序名能够根据参数和结果的数据类型，引用某些函数中的任意一个。
多态描述的是同名方法可以根据发送消息的对象传送参数的不同，采取不同的行为方式的特性。面向对象系统中采用多态，大大提高了程序的抽象程度和简洁性，更重要的是，它最大限度地降低了类和程序模块之间的耦合性，提高了类模块的封闭性，使得它们不需了解对方的具体细节，就可以很好地共同工作。
Java中提供两种多态机制：重载与覆盖。
在同一类中定义了多个同名而不同内容的成员方法时，我们称这些方法是重载的方法。重载的方法主要通过形式参数列表中参数的个数、
参数的数据类型和参数的顺序等方面的不同来区分。
允许子类对父类的同名方法重新进行定义,即在子类中定义与父类中已定义的相同名而内容不同的方法 。 这种多态被称为覆盖,由于覆盖的同名方法是存在于子类对父类的关系中,所以只需在方法引用时指明引用的是父类的方法还是子类的方法,就可以很容易地把它们区分开来 。
方法的覆盖与数据成员的隐藏的不同之处在于：
子类隐藏父类的数据成员只是使之不可见，父类同名的数据成员在子类对象中仍然占有自己的独立的内存空间；子类方法对父类同名方法的覆盖将清除父类方法占用的内存，从而使父类方法在子类对象中不复存在。
继承的优点是：继承避免了对一般类和特殊类之间共同特征进行的重复描述 ;通过继承可以清晰地表达每一项共同特征所适应的概念范围 —— 在一般类中定义的属性和操作适应于这个类本身以及它以下的每一层特殊类的全部对象 。 ;运用继承使得系统模型比较简练,也比较较清晰 。
顺序控制按控制结构可分为：优先级控制、条件控制、基于规则的控制和调用控制。按控制主体可分为：隐式控制和显式控制。
树结构表明了表达式的控制结构。处在低层的数据和操作先计算，其结果作为高层操作的操作数。
树结构表达式的语法有三种表示方法：
– 前缀表示法 (波兰式 )：操作符在操作数的前面。
– 中缀表示法：操作符在操作数的中间。
– 后缀表示法 (逆波兰式 )：操作符在操作数的后面。
前缀语义表示法计算利用执行堆栈处理，规则是：
如果是操作符，则压栈；
如果是操作数，则压栈；
如果栈顶有 n个操作数，且仅挨 n个操作数的是一个 n元操作符，则 n个操作数和 n元操作符弹栈，并操作计算，并将操作结果压栈。
前缀计算的优缺点：
优点：
可在一次扫描后计算出结果。
省略了括号；
机械解码相对容易。
缺点：
但由于需要知道操作数的数目，一元操作符与二元操作符需要语义分开。
需要进行操作数项数与操作符的元数匹配检查。
后缀语义表示计算仍然使用执行堆栈处理，规则是：
– 如果是操作数，则压栈；
– 如果是 n元操作符，那么其操作数必然是栈顶的 n个项目，则 n个操作数弹栈，操作计算，并将操作结果压栈。
后缀计算的优点：
– 可在一次扫描后计算出结果。
– 省略了括号；
– 机械解码相对容易。
– 无需进行操作数项数与操作符的元数匹配检查。
结构定理：任何基本程序都能转换成仅仅用
while和 if 语句构成的程序。
结构化程序并不等于好程序。它仅仅意味着使用了具有少量框的基本控制结构，如果开始是差劲的意大利面条式代码，那么变换后仍然是差劲的结构代码。
子程序的定义是指程序中的子程序声明和实现语句代码段，用户可见。子程序活动是每次子程序被激活而生成可执行代码段和记录，它包含两个部分：具有静态特性的代码段和具有动态特性的活动记录。
简单的 call-return子程序的实现可分为以下阶段：
– 主程序执行阶段：为主程序生成一个活动记录。
– 子程序被激活阶段：控制权转交子程序。
– 断点保护阶段：将断点保存在被调用子程序活动记录的返回点数据对象中。
– 子程序执行阶段：解释器将按 CIP中的内容读取和执行指令。
– 子程序返回阶段：从该子程序活动记录的返回点取出存储的 IP和 EP并赋值给 CIP和 CEP。
将控制权交回调用程序。
– （主程序）调用程序继续运行阶段：调用程序重新获得控制权后从断点开始继续执行。
引用环境是指：供程序或子程序执行期间使用的标识符关联。子程序的引用环境在子程序被调用时创建，且在执行期间保持不变。其主要组成部分是：局部引用环境、非局部引用环境、
全局引用环境和预定义引用环境。
如果一个标识符的关联是子程序的引用环境的一部分，则该关联在子程序中可见，否则称之为不可见（或隐藏）。
数据对象在其生存期中可能存在多个名字。当一个可见数据对象在单一引用环境中有多个名字时，每个名字成为该数据对象的别名。互为别名的数据对象拥有相同的引用环境。
别名使程序的可读性变差，同时由于别名相互依赖，使得编译过程中的代码优化相当麻烦。
别名与同名有很大的区别。别名是指：相同数据对象具有不同的名字，这些不同名字的右值是相同的。他们的引用环境相同。而同名是指：
相同的名字对应着不同的数据对象，从虚拟机的角度看，它们是完全互不相关的。
程序中的每个声明或其他标识符的定义都有一定的作用范围,我们称之为静态作用域 。 静态作用域将程序文本中名字的声明和引用相联系；
而动态作用域在程序运行期间将引用和名字相联系 。 这两者的关系是：作用域规则必须一致 。
静态作用域能够提高程序的运行效率，保证可靠性。静态作用域规则提高了程序的可读性。
它无需跟踪程序的执行就可将程序中引用的名字和其声明相关联。
有两种方式来实现动态作用域规则：保留、删除。保留方式的实现方法是：将包含保留变量的局部环境表作为子程序代码段的一部分而生成。删除方式的实现方法是：将包含删除变量的局部环境表作为子程序活动记录的一部分。
按名调用：将子程序调用看做是用子程序体替代该调用 。 该方式 可能会引起二义性问题 。
按引用调用：该方法是最常用的参数传递机制 。
它将数据对象的地址指针 （ 即左值 ） 传递子程序,而不改变数据对象本身在内存中的位置 。
按值调用：将实参的值（即右值）传递给形参。
按值 -结果调用：将形式参数与实际参数一样看作是相同数据类型的局部变量（数据对象）。
按常数调用,该方法是通过常数传递参数，形式参数在子程序执行期间类似于局部常数。
按结果调用：类似于按值 -结果调用，但是从子程序中返回结果。
存储管理需要研究的的三个主要方面是：初始分配；存储单元回收；压缩和再用。、
静态分配的基本思想是：存储器的分配在翻译过程中完成,而且在程序的执行过程中保持不变 。 翻译器可以为所有的数据产生直接的左值地址 。 静态存储不需要运行时的存储管理软件的支持,因而没有必要考虑存储空间的回收和再用 。 它的优点是,效率比较高；缺点是,1）
静态存储分配无法处理递归子程序的调用,2）
无法处理大小依赖于所计算值或输人值的数据结构 。 3） 静态存储分配无法满足语言中的其他一些重要特色 。
引用计数通过提供了一个检查指向一给定元素的指针个数的方法来解决悬挂引用问题。其优点是：大多数情况下避免无用单元的产生和悬挂引用。其缺点是：维护开销和额外存储开销太大。
无用单元回收通过调用无用单元回收器来寻找并恢复其所占用的单元，从而解决悬挂引用问题。无用单元回收过程包括两个阶段,1）标记阶段，该过程比较复杂。 2）扫描阶段：该过程比较简单。
异常：在程序执行过程中,由于出现一些使得正常程序不能被执行的事件或条件 （ 如出错,读文件不存在 ）,需要调用相关的子程序进行特殊处理 。 这些事件或条件称之为异常 。 异常有两个来源,1)虚拟计算机检测到的； 2） 由程序设计语言语义产生的 。
异常处理程序：执行特殊处理的子程序 。 通常异常处理子程序的激活不需要显式调用,一般不需要名字或者参数 。 异常处理程序的定义通常包括：
1） 一组局部变量的说明 （ 也可以没有 ） ； 2） 可执行语句的序列 。
引发异常：捕获异常,中断程序执行,并且转移控制到异常处理程序的操作 。
异常的传播：当一个异常不是在引发异常的子程序中处理时,就称异常沿着引发点到处理点进行传播 。 异常传播在处理异常时使得子程序仍然作为一个程序员定义的抽象操作 。
如果允许子程序在全部执行完之前返回到它们的调用者,这种子程序叫做协同程序 。 此时,
调用程序和被调用程序之间是对称的 。 两个子程序之间不是调用者与被调用者的关系,它们之间是平等的,两者交替运行 。
如果子程序在调用时不必立即运行，就产生了子程序调度的问题。
其他的子程序调度技术有,1） 使一个子程序在另一个子程序之前或之后运行； 2） 使得一个子程序在一布尔表达式为真时才开始执行；
3） 基于模拟时间标尺的调度,4,按优先级调度子程序；
子程序调度是指调度子程序的活动,调度是运行时的操作 。 在一般性的子程序调度中,程序员不再写主程序 。 主程序是系统定义的调度程序,它管理当前被调度的子程序活动,它们按运行先后顺序排列 。
信号量是用于任务间同步的数据对象 。 一个信号量由两部分组成,1） 一个整数计数器； 2）
一个等待信号量发出的任务队列 。
信号量数据对象 P上定义了两个基本操作：
Signal（ P） 和 Wait（ P） 。 signal和 wait语句的语义都很简单,只有每个操作运行完毕后,
其他的并发操作才能访问共享数据 。 这种原子性能够防止某些不期望的非确定性发生 。
信号量的缺点是,1） 一个任务在一个时刻只能等待一个信号量； 2） 可能导致整个任务系统死锁； 3） 使对程序的理解,调试和证明都变得困难； 4） 在并发环境下,signal和 wait的语义暗示着所有访问信号量任务都共享存储器 。
消息是从一个任务到另一个任务的信息传输。
它为每个任务提供了使该任务的作与其他任务同步的机制。在该机制中，当任务不需要同步时，仍可自由地继续运行。其基本概念类似于管道。
消息具有很强的能力 。 但消息传递的实现比较复杂 。 解决某些消息丢失的方法是,1） 包含一个在接收者能够处理前,把这些消息存储在一个队列 （ 或叫做缓冲区 ） 中的机制； 2） 发送消息的任务自己在接收者能够接收消息前被放人队列中等待 。
任务存储管理的基本思想：任务被定义为在一个给定程序中几个同时运行的执行序列。每一个任务都拥有自己的存储管理，通常是一个栈。
在单台计算机上通常利用单栈、多栈和单堆的方法实现多个栈。
单栈是通常采用的方法。它能够充分地利用了存储空间。 多栈适用于有足够的存储空间的场合，在有了现代的虚拟存储系统的情况下，这是一种有效的解决方法。单堆的优点是适用于只有有限存储空间的系统。缺点是,1）额外的时间开销很大； 2）存在严重的存储器碎片问题。
P ro g ra m m i ng L a ng ua g e
D e s i g n a nd I m pl e m e nt a t i o n
网络教学程序设计语言 ----------集中复习
程序设计语言种类很多，各有其自身的特点。
本课程不是为了介绍某种具体的程序设计语言的规范、使用，而是抽象出程序设计语言的共同特点，力图系统讲述程序设计语言的语法、
语义和编译实现之间的关系，介绍数据结构、
顺序控制、子程序、封装、继承等概念及其实现技术，涉及函数式语言、逻辑式语言、命令式语言和面向对象的语言。讨论程序设计语言的一般设计和实现方法。
本课程要求学习和复习重点内容
第 2,3,5,6,7,8,9章。
第 2章要求掌握的知识点是,计算机的硬件结构；固件计算机；翻译；编译；解释；虚拟计算机；绑定时间等 。
重点掌握 编译和解释的概念、实现原理和各自的特点；虚拟计算机的概念、层次结构；哪些元素需要进行绑定，它们的绑定时间分别是什么。
第 3章要求掌握的知识点是,语法；语义；二义性；独立子程序定义；独立数据定义；嵌套子程序定义；独立接口定义；词法分析；语法分析；语义分析；优化；连接与载入；语法树；
BNF文法等 。
重点语法、语义、二义性的特点，二义性与语法树之间的关系； 词法分析、语法分析、语分析和代码优化的概念、实现原理； BNF范式的推导。
第 5章要求掌握的知识点是：数据对象、变量、
常量、数据类型、类型检查、类型转换、标量数据类型、复合数据类型等。
重点掌握基本数据类型的概念、存储表示、实现方法；动态类型检查与静态类型检查的特点。
第 6章要求掌握的知识点是：封装、结构化数据类型、数据结构上的操作、向量,数组、记录、列表、集合、数据抽象、信息隐藏、类属子程序、类型定义 等。
重点掌握封装的概念、封装的特点、向量的特点、向量地址的计算、数据结构上操作的实现原理。
第 7章要求掌握的知识点是：抽象、对象、类、
封装、成员、属性、方法、消息、继承、多态、
重载、覆盖等。
重点掌握上述知识点的基本概念、过程抽象和数据抽象的特点、继承的实现方法。重载与覆盖的区别。
第 8章要求掌握的知识点是：顺序控制、表达式的顺序、前缀表示法、中缀表示法、后缀表示法、前缀计算法、中缀计算法、后缀计算法、
一致求值规则、语句级顺序控制、结构化顺序控制 。
重点掌握表达式的优先级别；前缀、中缀、后缀的语法表示方法，并且灵活掌握它们的计算方法的实现原理；结构化定理的概念以及结构化定义所阐述的问题 。
第 9章要求掌握的知识点是：调用、返回、基于堆栈的实现、声明、命名、引用环境、可见性、静态作用域、动态作用域、局部数据、局部引用环境、实际参数、形式参数、参数传递、
静态类型检查、非局部引用共享显式变量等。
重点掌握简单调用 -返回子程序的顺序控制方法、引用环境、各种参数传递的基本思想、变量的作用域。
第 10章要求掌握的知识点是：初始分配、存储单元回收、压缩、存储单元再用、静态存储管理、固定单元大小、引用计数、无用单元、悬挂引用、无用单元回收、可变长单元、首次满足、最佳满足、存储器碎片等。
重点掌握：无用单元以及悬挂引用的概念、存在的危害以及具体的解决方法。
第 11章要求掌握的知识点是：异常、异常处理程序、异常引发、异常传播、协同程序、调度程序、并发运行、任务、任务管理、任务同步、
中断、信号量、消息、任务存储管理、互斥、
临界区、管程、消息传递等。
重点掌握：异常的特点、任务存储管理的具体方法以及消息传递。
通过本门课程的学习：
我们知道程序设计语言经过了低级语言（机器语言、汇编语言）到高级语言的发展，而且仍在继续不断的发展和变化。 经历着应用程序的
,简单性,到,复杂性,；编程强调,技巧性,到,可读性,；追求实现的,高效性,到
,可维护性,和强调,可移植性,的演变。
影响程序设计语言的主要因素有：计算机性能，
应用领域的要求，编程方法，实现方法和标准化。
程序一般计算模型有：命令式语言、应用式语言、基于规则语言和面向对象语言四种，各自具有优点。目前主要使用的仍然是命令式语言和面向对象语言。
程序设计语言具有六个基本特征：数据，基本操作，顺序控制，数据存取，存储管理和操作环境。
固件计算机是一台可进行微编程的硬件计算机上通过微程序模拟实现的计算机。
高级语言程序必须经过翻译成目标语言程序才能在目标计算机上运行。可通过编译和软件解释两种途径。
翻译是将用高级语言编写的源程序转换成实际计算机上等价的机器语言程序（目标程序）。
计算机上的硬件可以直接运行目标程序。翻译是由翻译程序完成的，翻译程序将源程序作为输入，输出结果是功能等价的目标语言程序。
解释是通过使用一台主机上运行的程序来模拟一台机器语言是高级语言的计算机的执行。即使用主机上的机器语言来构造一组程序软件
（模拟软件或解释软件）来模拟或解释运行用高级语言编写的程序所需要的算法和数据结构。
编译与解释的相同点是：二者都接受高级语言作为输入。
编译与解释的不同点是：
– 功能不同：翻译将源程序 — >等价的目标语言程序；
解释直接执行源程序（用户角度看）。
– 顺序控制：翻译遵循输入的物理序列语句；解释遵循程序的逻辑控制流程。
– 执行次数：翻译对每条语句只处理一次；解释则可能对同一条语句反复解释处理（如循环），也可能完全忽略一些语句（如控制流不能到达的语句）。
– 信息完整性：翻译可能造成源程序信息丢失，调试、
测试较为困难；解释不会。
– 代价：翻译需要耗费更大的存储空间；解释需要较长的执行时间（解码时间）。
虚拟计算机是一个层次性的结构，典型的虚拟计算机可分成 7个层次。下层为上层提供支持和服务。
绑定是指程序元素与其特性或性质的约束关系。
绑定时间是指绑定所发生的时间，主要有翻译或时和执行时。绑定和绑定时间可由语言定义或由实现来确定。
绑定时间对于程序设计语言的效率和灵活性起重要的作用。对于追求效率为主要目标的语言，
通常应尽可能进行早绑定。而追求灵活性为主要目标的语言，应采用迟绑定。对于两个兼顾的语言，应提供绑定时间选择机制。
语法是以句子中词的排列来表明它们的彼此关系。它描述了组成一个合法程序的符号的系列，
是理解一个程序的重要手段，也为将源程序翻译成目标程序提供了必要的信息。
通用语法的标准是：好的可读性、可写性、容验证性、易翻译性和无二义性。
二义性是指相同的语法形式允许存在两种或更多的语义解释。二义性的显著特点是存在两棵语法树。无二义性是每个程序语言设计的中心问题。
通常解决二义性的方法是,1）使用定界符； 2）
选择多种语义中的一种作为唯一合理的解释。
翻译可分成两个主要的部分：源程序分析和目标程序的综合。源程序分析包括词法分析、语法分析和语义分析阶段。目标程序的综合包括优化、代码的生成、连接和载入等阶段。
BNF文法是一种结构简单，功能较强的上下文无关文法。 BNF扩充文法进一步增强它的功能。
数据对象的存储与实际计算机数据存储组织的区别在于实际计算机的数据存储区的结构相对简单，以比特流方式组成字节或字（线性结构），具有静态特性。而程序设计语言的虚拟机的数据存储的组织较为复杂，如数组、记录、
堆栈等，具有动态变化的特性 。
每个数据对象都有生存期。如果在生存期内，
一个对象包含的数据值总是作为一个单位操作，
则称该对象为基本数据对象；如果它是其他数据对象的集合，则称为数据结构。
一个数据类型规范的基本组件包括属性、值域和操作。
基本数据类型的实现由三个部分组成，即存储表示、该类型的值和类型操作的算法或过程的集合。
操作可用三种方法实现，即硬件、作为函数或过程子程序、作为嵌入的代码系列。
声明是将程序执行时所需要的数据对象的名字和类型的信息传递给编译器的程序语句。许多语言提供隐式或默认声明。
类型检查是为了检查程序执行的操作是否接收到正确数目的正确类型参数。
类型检查有动态类型检查和静态类型检查两种。
动态类型检查与静态类型检查之比较而言动态类型检查较静态灵活；动态类型检查的执行效率较低；基于动态类型检查的程序调试较难；动态类型检查的存储代价较高。
标量数据对象是指只有单一属性的基本数据对象。
而复合数据对象具有多种属性。一般，标量数据对象随计算机硬件结构的不同而变化。而复合数据类型不是由硬件实现的数据对象，从而与硬件无关。
创建新的数据类型及其操作有 4种机制：结构化的数据、子程序、类型声明和继承。
数据结构是一个包含其他数据对象作为其元素和成员的数据对象。
数据结构的主要属性包括：成员的数目、成员的类型、成员的名字、成员数目最大值以及成员的组织。
数据结构有两种基本表示方法：即顺序表示：
一般用于表示固定大小的数据结构，也用于同构的可变长数据结构。链式表示：一般用于可变长数据结构。
向量是指包含固定数目的同种成员的简单线性系列的数据结构。其成员通过下标选择。
子程序是由程序员定义的抽象操作。子程序构成了程序结构的基本构件。 子程序的定义包括两部分：说明和实现。 子程序的实现由程序员完成，但由程序语言本身提供的数据结构和操作来实现的。
子程序定义是程序的一个静态属性，是实际存在的程序段，如果调用了一个子程序，则创建了一个子程序活动。调用完成后，该活动被消除。子程序的活动是一个动态属性，只在程序的执行过程中存在。从子程序模板创建子程序活动时，较好的方法是将模板分成两个部分：静态部分和动态部分。静态部分：常量和可执行代码组成。所有活动可以共享单一的副本。动态部分：不同活动具有相同结构，但具有不同的值。
程序设计语言 ----------集中复习 (二 )
类型相同的判别方法有：类型名字相同和结构相同。类型名字相同的缺点是,1）不允许匿名类型。 2）需要使用全局类型定义。结构相同的缺点是,1）难以判断结构相同； 2）静态类型检查容易漏检； 3）翻译开销大。
对象是对现实世界中事物的抽象，是面向对对象程序的基本封装单位，是类的实例：
类是对象的抽象，是数据和操作的封装体。类是对象的抽象和归纳，对象是类的实例。
属性是事物静态特征的抽象，在程序中用数据成员加以描述；
操作是事物动态特征的抽象，在程序中用成员方法来实现。
抽象可分为过程抽象和数据抽象两类。
过程抽象是指：软件开发者可以把任何一个完成确定功能的操作序列都看作是一个单一的实体。
运用过程抽象，软件开发者可以把一个复杂的功能分解为一些子功能（模块）。使用过程抽象有利于控制、降低整个程序的复杂度，但是，这种方法允许在全系统范围内进行功能的描述，本身自由度大，难于规范化和标准化，不易保证软件的质量，而且操作起来也有一定难度。
数据抽象把系统中需要处理的数据和施加于这些数据之上的操作结合在一起,根据功能,性质,
作用等因素抽象成不同的抽象数据类型 。 数据抽象把数据和操作结合为一个不可分的系统单位一对象,对象的外部只需要知道这个对象能做什么,
而不必知道它是如何做的 。
对象具有三个基本特征：
– 对象标识：即对象的名字,是用户和系统识别它的唯一标志 。
– 属性：用来描述对象的静态特征 。
– 方法：也称为服务或操作,它是对象动态特征
（ 行为 ） 的描述 。
描述一个类需要指明下述三个方面内容：
– 类标识：类的一个有别于其他类的名字 。
– 属性说明：用来描述相同对象的静态特征 。
– 方法说明：用来描述相同对象的动态特征 。
封装也称为信息隐藏，是指利用抽象数据类型将数据和基于数据的操作封装在一起，使其构成一个不可分割的独立实体，数据被保护在抽象数据类型的内部，尽可能地隐藏内部的细节，只保留一些对外接口使之与外部发生联系。
封装能够进行信息隐藏,只保留一些对外接口使之与外部发生联系。系统的其他部分只有通过包裹在数据外面的被授权的操作来与这个抽象数据类型交流与交互。即用户无需知道对象内部方法的实现细节，但可以根据对象提供的外部接口（对象名和参数）访问该对象。
在面向对象的系统中,对象之间的联系是通过消息传递来实现的 。
对象间的联系,只能通过消息传递来进行 。 对象也只有在收到消息时,才被激活,去完成消息要求的功能 。
消息就是向对象发出服务请求,是对数据成员和成员方法的引用 。 它含有下述信息：
– 对象名,提供服务的对象标识；
– 方法名,服务标识；
– 实际参数,输入信息；
– 返回值或操作结果,回答信息 。
多态是指一个操作符或子程序名能够根据参数和结果的数据类型，引用某些函数中的任意一个。
多态描述的是同名方法可以根据发送消息的对象传送参数的不同，采取不同的行为方式的特性。面向对象系统中采用多态，大大提高了程序的抽象程度和简洁性，更重要的是，它最大限度地降低了类和程序模块之间的耦合性，提高了类模块的封闭性，使得它们不需了解对方的具体细节，就可以很好地共同工作。
Java中提供两种多态机制：重载与覆盖。
在同一类中定义了多个同名而不同内容的成员方法时，我们称这些方法是重载的方法。重载的方法主要通过形式参数列表中参数的个数、
参数的数据类型和参数的顺序等方面的不同来区分。
允许子类对父类的同名方法重新进行定义,即在子类中定义与父类中已定义的相同名而内容不同的方法 。 这种多态被称为覆盖,由于覆盖的同名方法是存在于子类对父类的关系中,所以只需在方法引用时指明引用的是父类的方法还是子类的方法,就可以很容易地把它们区分开来 。
方法的覆盖与数据成员的隐藏的不同之处在于：
子类隐藏父类的数据成员只是使之不可见，父类同名的数据成员在子类对象中仍然占有自己的独立的内存空间；子类方法对父类同名方法的覆盖将清除父类方法占用的内存，从而使父类方法在子类对象中不复存在。
继承的优点是：继承避免了对一般类和特殊类之间共同特征进行的重复描述 ;通过继承可以清晰地表达每一项共同特征所适应的概念范围 —— 在一般类中定义的属性和操作适应于这个类本身以及它以下的每一层特殊类的全部对象 。 ;运用继承使得系统模型比较简练,也比较较清晰 。
顺序控制按控制结构可分为：优先级控制、条件控制、基于规则的控制和调用控制。按控制主体可分为：隐式控制和显式控制。
树结构表明了表达式的控制结构。处在低层的数据和操作先计算，其结果作为高层操作的操作数。
树结构表达式的语法有三种表示方法：
– 前缀表示法 (波兰式 )：操作符在操作数的前面。
– 中缀表示法：操作符在操作数的中间。
– 后缀表示法 (逆波兰式 )：操作符在操作数的后面。
前缀语义表示法计算利用执行堆栈处理，规则是：
如果是操作符，则压栈；
如果是操作数，则压栈；
如果栈顶有 n个操作数，且仅挨 n个操作数的是一个 n元操作符，则 n个操作数和 n元操作符弹栈，并操作计算，并将操作结果压栈。
前缀计算的优缺点：
优点：
可在一次扫描后计算出结果。
省略了括号；
机械解码相对容易。
缺点：
但由于需要知道操作数的数目，一元操作符与二元操作符需要语义分开。
需要进行操作数项数与操作符的元数匹配检查。
后缀语义表示计算仍然使用执行堆栈处理，规则是：
– 如果是操作数，则压栈；
– 如果是 n元操作符，那么其操作数必然是栈顶的 n个项目，则 n个操作数弹栈，操作计算，并将操作结果压栈。
后缀计算的优点：
– 可在一次扫描后计算出结果。
– 省略了括号；
– 机械解码相对容易。
– 无需进行操作数项数与操作符的元数匹配检查。
结构定理：任何基本程序都能转换成仅仅用
while和 if 语句构成的程序。
结构化程序并不等于好程序。它仅仅意味着使用了具有少量框的基本控制结构，如果开始是差劲的意大利面条式代码，那么变换后仍然是差劲的结构代码。
子程序的定义是指程序中的子程序声明和实现语句代码段，用户可见。子程序活动是每次子程序被激活而生成可执行代码段和记录，它包含两个部分：具有静态特性的代码段和具有动态特性的活动记录。
简单的 call-return子程序的实现可分为以下阶段：
– 主程序执行阶段：为主程序生成一个活动记录。
– 子程序被激活阶段：控制权转交子程序。
– 断点保护阶段：将断点保存在被调用子程序活动记录的返回点数据对象中。
– 子程序执行阶段：解释器将按 CIP中的内容读取和执行指令。
– 子程序返回阶段：从该子程序活动记录的返回点取出存储的 IP和 EP并赋值给 CIP和 CEP。
将控制权交回调用程序。
– （主程序）调用程序继续运行阶段：调用程序重新获得控制权后从断点开始继续执行。
引用环境是指：供程序或子程序执行期间使用的标识符关联。子程序的引用环境在子程序被调用时创建，且在执行期间保持不变。其主要组成部分是：局部引用环境、非局部引用环境、
全局引用环境和预定义引用环境。
如果一个标识符的关联是子程序的引用环境的一部分，则该关联在子程序中可见，否则称之为不可见（或隐藏）。
数据对象在其生存期中可能存在多个名字。当一个可见数据对象在单一引用环境中有多个名字时，每个名字成为该数据对象的别名。互为别名的数据对象拥有相同的引用环境。
别名使程序的可读性变差，同时由于别名相互依赖，使得编译过程中的代码优化相当麻烦。
别名与同名有很大的区别。别名是指：相同数据对象具有不同的名字，这些不同名字的右值是相同的。他们的引用环境相同。而同名是指：
相同的名字对应着不同的数据对象，从虚拟机的角度看，它们是完全互不相关的。
程序中的每个声明或其他标识符的定义都有一定的作用范围,我们称之为静态作用域 。 静态作用域将程序文本中名字的声明和引用相联系；
而动态作用域在程序运行期间将引用和名字相联系 。 这两者的关系是：作用域规则必须一致 。
静态作用域能够提高程序的运行效率，保证可靠性。静态作用域规则提高了程序的可读性。
它无需跟踪程序的执行就可将程序中引用的名字和其声明相关联。
有两种方式来实现动态作用域规则：保留、删除。保留方式的实现方法是：将包含保留变量的局部环境表作为子程序代码段的一部分而生成。删除方式的实现方法是：将包含删除变量的局部环境表作为子程序活动记录的一部分。
按名调用：将子程序调用看做是用子程序体替代该调用 。 该方式 可能会引起二义性问题 。
按引用调用：该方法是最常用的参数传递机制 。
它将数据对象的地址指针 （ 即左值 ） 传递子程序,而不改变数据对象本身在内存中的位置 。
按值调用：将实参的值（即右值）传递给形参。
按值 -结果调用：将形式参数与实际参数一样看作是相同数据类型的局部变量（数据对象）。
按常数调用,该方法是通过常数传递参数，形式参数在子程序执行期间类似于局部常数。
按结果调用：类似于按值 -结果调用，但是从子程序中返回结果。
存储管理需要研究的的三个主要方面是：初始分配；存储单元回收；压缩和再用。、
静态分配的基本思想是：存储器的分配在翻译过程中完成,而且在程序的执行过程中保持不变 。 翻译器可以为所有的数据产生直接的左值地址 。 静态存储不需要运行时的存储管理软件的支持,因而没有必要考虑存储空间的回收和再用 。 它的优点是,效率比较高；缺点是,1）
静态存储分配无法处理递归子程序的调用,2）
无法处理大小依赖于所计算值或输人值的数据结构 。 3） 静态存储分配无法满足语言中的其他一些重要特色 。
引用计数通过提供了一个检查指向一给定元素的指针个数的方法来解决悬挂引用问题。其优点是：大多数情况下避免无用单元的产生和悬挂引用。其缺点是：维护开销和额外存储开销太大。
无用单元回收通过调用无用单元回收器来寻找并恢复其所占用的单元，从而解决悬挂引用问题。无用单元回收过程包括两个阶段,1）标记阶段，该过程比较复杂。 2）扫描阶段：该过程比较简单。
异常：在程序执行过程中,由于出现一些使得正常程序不能被执行的事件或条件 （ 如出错,读文件不存在 ）,需要调用相关的子程序进行特殊处理 。 这些事件或条件称之为异常 。 异常有两个来源,1)虚拟计算机检测到的； 2） 由程序设计语言语义产生的 。
异常处理程序：执行特殊处理的子程序 。 通常异常处理子程序的激活不需要显式调用,一般不需要名字或者参数 。 异常处理程序的定义通常包括：
1） 一组局部变量的说明 （ 也可以没有 ） ； 2） 可执行语句的序列 。
引发异常：捕获异常,中断程序执行,并且转移控制到异常处理程序的操作 。
异常的传播：当一个异常不是在引发异常的子程序中处理时,就称异常沿着引发点到处理点进行传播 。 异常传播在处理异常时使得子程序仍然作为一个程序员定义的抽象操作 。
如果允许子程序在全部执行完之前返回到它们的调用者,这种子程序叫做协同程序 。 此时,
调用程序和被调用程序之间是对称的 。 两个子程序之间不是调用者与被调用者的关系,它们之间是平等的,两者交替运行 。
如果子程序在调用时不必立即运行，就产生了子程序调度的问题。
其他的子程序调度技术有,1） 使一个子程序在另一个子程序之前或之后运行； 2） 使得一个子程序在一布尔表达式为真时才开始执行；
3） 基于模拟时间标尺的调度,4,按优先级调度子程序；
子程序调度是指调度子程序的活动,调度是运行时的操作 。 在一般性的子程序调度中,程序员不再写主程序 。 主程序是系统定义的调度程序,它管理当前被调度的子程序活动,它们按运行先后顺序排列 。
信号量是用于任务间同步的数据对象 。 一个信号量由两部分组成,1） 一个整数计数器； 2）
一个等待信号量发出的任务队列 。
信号量数据对象 P上定义了两个基本操作：
Signal（ P） 和 Wait（ P） 。 signal和 wait语句的语义都很简单,只有每个操作运行完毕后,
其他的并发操作才能访问共享数据 。 这种原子性能够防止某些不期望的非确定性发生 。
信号量的缺点是,1） 一个任务在一个时刻只能等待一个信号量； 2） 可能导致整个任务系统死锁； 3） 使对程序的理解,调试和证明都变得困难； 4） 在并发环境下,signal和 wait的语义暗示着所有访问信号量任务都共享存储器 。
消息是从一个任务到另一个任务的信息传输。
它为每个任务提供了使该任务的作与其他任务同步的机制。在该机制中，当任务不需要同步时，仍可自由地继续运行。其基本概念类似于管道。
消息具有很强的能力 。 但消息传递的实现比较复杂 。 解决某些消息丢失的方法是,1） 包含一个在接收者能够处理前,把这些消息存储在一个队列 （ 或叫做缓冲区 ） 中的机制； 2） 发送消息的任务自己在接收者能够接收消息前被放人队列中等待 。
任务存储管理的基本思想：任务被定义为在一个给定程序中几个同时运行的执行序列。每一个任务都拥有自己的存储管理，通常是一个栈。
在单台计算机上通常利用单栈、多栈和单堆的方法实现多个栈。
单栈是通常采用的方法。它能够充分地利用了存储空间。 多栈适用于有足够的存储空间的场合，在有了现代的虚拟存储系统的情况下，这是一种有效的解决方法。单堆的优点是适用于只有有限存储空间的系统。缺点是,1）额外的时间开销很大； 2）存在严重的存储器碎片问题。
