计算科学导论课件第三章

程序设计语言与软件开发方法学程序设计语言的发展形式语言与自动机形式语义学程序设计方法学计算语言学软件开发方法学

程序设计语言的发展算法、过程与程序机器指令与机器语言汇编语言与汇编程序高级语言与编译程序MAS与超级语言

返回算法、过程与程序算法:一个有穷规则的集合，其中之规则确定了一个解决某一特定类型问题的运算序列。算法的特性:有穷性、确定性、输入、输出和能行性。过程:一个有穷规则的集合，其中之规则确定了一个解决某一特定类型问题的运算序列。过程的特性:确定性、输入、输出和能行性。程序:是具有特殊功能的指令序列。程序设计:编写程序的过程。返回机器指令与机器语言机器指令的格式:机器指令的分类:1控制指令;2算术运算指令;3逻辑运算指令;4移位操作指令;5传送操作指令;6输入输出指令。机器语言:机器指令系统:机器语言程序机器指令的实现:微指令与微程序RISC:精简指令系统计算机返回操作码地址码汇编语言与汇编程序程序的可读性汇编指令:用英文字母和一些符号对机器语言指令和存储空间及数据进行编码，为0、1串进行命名所得到的指令。操作符:add(加法)mul(无符号乘法)idiv(有符号除法)neg(求补)xchg(交换)test(逻辑比较)jmp(无条件转移)汇编语言程序汇编程序机器语言程序汇编语言的好处:使得程序设计人员从原来记忆0、1串的烦恼中解放出来，变按二进制数字与地址空间的存取与操作为按名存取与操作。返回

高级语言与编译程序高级语言的语句：把人们利用机器语言或汇编语言编程时所用数据的逻辑结构，和对数据进行处理时的操作序列的逻辑结构，归纳抽象为数据类型和语句，利用英文字母、数字和一些符号通过一定规则（语法）对其编码，所用编码的自然语言含义与对应逻辑结构的意义尽量接近。例如：ifabthenx:=aelsex:=b

；高级语言程序编译程序机器语言程序高级语言分类对高级语言多态性的反思

返回高级语言分类过程型语言认为计算机所解决的问题是由一个个小问题的顺次解决而解决的，把解决各个问题的动作及所参加的成员，抽象为操作（语句）和数据。前期高级语言大多是过程型的。常见的有：FORTRAN,ALGOL60,COBOL,BASIC,PASCAL,C,ADA等。函数型语言认为计算机所解决的问题是从一个域到另一个域的函数映射，把要解决的问题划分成一个个相关成员的集合和集合间的函数关系。典型代表如LISP逻辑型语言认为计算机所解决的问题是由已知事实及一定规则进行逻辑推理得到一定结论，把要解决的问题描述为一系列事实与规则的集合。典型代表PROLOG对象型语言认为计算机要解决的问题是参与问题的所有个体及个体间的相互作用的结果，把问题描述为表述个体的对象集合及个体间相互作用的消息集合，典型代表如SMALLTALK，C++,JAVA等。返回对高级语言多态性的反思计算机高级语言虽然种类繁多，但它的产生与发展也受到两方面的限制，其一是实现它的物理机器原理等价性的限制；其二是它所抽象与表术的现实世界同一性的限制。所以会出现过程型、函数型、逻辑型和对象型等高级语言，是因为现实世界在不同领域以不同的表现形式为主，以其它表现形式为辅；还因为人们对于现实世界认识的主观性与片面性。

返回MAS与超级语言把用高级语言解决某问题而设计的一个完整的程序作为整体抽象为一个Agent，把由多个Agent通过交互作用而形成的整体称为多Agent系统（Multi-AgentSystem,简称MAS），把描述MAS中各Agent的组成成份及各Agent间相互作用规则的程序设计语言称为超级语言。程序设计语言的发展目标一是为了提高数据表示的抽象程度，如过程、对象类、Agent类等，二是为了提高程序编制的自动化程度，如指令、语句，规划和目标等。返回

语言及其组成自然语言：音义结合的符号系统。程序设计语言：码义结合的符号系统。形式语言：一个符号选自某个字母表的字符串集合。词法：它规定了什么样的符号组成的字符序列或空间排列是这个语言合法的单词（或字）。文法：是关于用语言的单词构成短语、句子和篇章的规则，在此基础上可以形成各种句子和文章。语法：由词法和文法构成。语义：就是指单词、短语、句子和文章的意义或含义。如“上马”的语义语用：是指在一定的语言环境中语言和它的使用者之间的关系。语境：语言的使用环境。返回形式语言与自动机语言及其组成：语法与巴科斯范式：转换生成语言学理论：语言可以通过字母表和表上定义的一组语法规则经演绎过程生成。乔姆斯基语言与自动机的等价性：语言也是一种计算模型,它在计算机裸机系统与人的思维、描述方式之间架起了一座沟通的桥梁,只是在描述、刻画、表达计算时所处层面和方便程度不同而已。

返回语法与巴科斯范式自然语言的语法结构：〈句子〉〈名词短语〉〈动词短语〉〈名词短语〉〈形容词〉〈名词短语〉〈名词短语〉〈名词〉〈名词〉boy〈形容词〉little……程序设计语言的语法结构：〈表达式〉〈表达式〉+〈表达式〉〈表达式〉〈表达式〉*〈表达式〉〈表达式〉（〈表达式〉）〈表达式〉id……形式语言的语法结构：返回形式语言的语法结构上下文无关文法：CFG=（V，T，P，S），其中：

V：变元的有穷集合；

T：终极符的有穷集合，VT=0；

P：产生式的有穷集合，每个产生式的形式是A，A是变元，是（VT）*中的符号串；

S：是开始变元。例子：CFG

=（{E}，{+，*，（，），id}，P，E），其中P为：EE+EEE*EE（E）Eid……巴科斯—瑙尔范式（BNF）

返回

形式语义学自然语言：语法、语义、语用、语境与本质条件子句与条件语句嵌套的语义问题：

条件子句：ifBthenS；

条件语句：ifBthenS1else

S2；

条件子句与条件语句嵌套：

ifB1thenifB2thenS1else

S2；

条件子句与条件语句嵌套的两种语义解释：1.ifB1then(ifB2thenS1else

S2)；2.ifB1then(ifB2thenS1)else

S2；形式语义（学）：就是指用形式化的方法对语言成分语义的描述（研究）。语义的四种描述方法

返回语义的四种描述方法程序语义（功能）的形式描述：{Q}P{R}其中：

P：表示一程序；

Q：P的前断言，表示P执行前的状态（指影响P运行的所有组成成份的状态）必须满足的条件；

R：P的后断言，表示P执行后的状态必须满足的条件。

例如：

{Q：得到10元钱}P：S1；S2；……；Sn；{R：打回一瓶酒}程序语义的四种描述方法

返回语义的四种描述方法（续）操作语义：用抽象机的基本动作对语言中语句的语义进行描述的方法。即把{Q}P{R}中的S1；S2；…；Sn用抽象机的基本动作O1；O2；…；Om进行描述,以证明P完成了其功能{Q，R}。指称语义：用基本定值函数对语言中语句的语义进行描述的方法。即把{Q}P{R}中的S1；S2；…；Sn用基本定值函数f1；f2；…；fm进行描述，以证明P完成了其功能{Q，R}。公理语义：用基本公理和推导规则对语言中语句的语义进行描述的方法。即从基本公理{Q1}S1{R1}；{Q2}S2{R2}；…；{Qn}Sn{Rn}出发，利用推导规则，以证明P完成了其功能{Q，R}。代数语义：用基本代数规则对语言中语句的语义进行描述的方法。即把{Q}P{R}中的S1；S2；…；Sn用基本代数规则R1；R2；…；Rm进行描述，以证明P完成了其功能{Q，R}。四种描述方法的等价性问题返回程序设计方法学程序理论：程序的结构，程序的正确性，程序的运行效率等。程序设计方法：自顶向下，自底向上，结构化，程序推导，程序变换，面向对象，面向函数，面向逻辑等。程序设计技术：程序验证技术，程序重用技术，约束程序设计技术，并发程序设计技术等。返回程序的结构程序的整体结构程序的数据结构程序的控制结构：

1、顺序：S1；S2；；Sn

2、选择：ifBthenS1else

S2endif3、循环：loopBdoSendloop

返回程序的控制结构

程序的整体结构Ｃ语言程序的总体结构

一个完整的Ｃ语言程序，是由一个main()函数（又称主函数）和若干个其它函数结合而成的，或仅由一个main()函数构成[例1]仅由main()函数构成的Ｃ语言程序。main(){printf(“ThisisaCprogram.\n”);}程序运行结果：

ThisisaCprogram.Ｃ语言程序的总体结构[例2]由main()函数和1个其它函数max()构成的Ｃ语言程序。int

max(intx,inty){return(x>y?x:y);}main(){intnum1,num2;

printf(“Inputthefirstintegernumber:”);

scanf(“%d”,&num1);

printf(“Inputthesecondintegernumber:”);

scanf(“%d”,&num2);

printf(“max=%d\n”,max(num1,num2));}程序运行情况：

Inputthefirstintegernumber:6←┘Inputthesecondintegernumber:9←┘max=9函数的一般结构任何函数都是由函数说明和函数体两部分组成：

[函数类型]函数名(函数参数表)函数说明部分

{说明语句部分；执行语句部分；函数体部分

}函数参数表的格式为：

数据类型形参[,数据类型形参2……]例如，函数max()说明部分如下：

函数类型函数名函数参数表

↓↓↓

intmax(intx,inty)函数体一般由说明语句和可执行语句两部分构成：（1）说明语句部分说明语句部分由变量定义、自定义类型定义、自定义函数说明、外部变量说明等组成。（2）可执行语句main(){intnum1,num2;变量定义部分

printf(“Inputthefirstintegernumber:”);

scanf(“%d”,&num1);

printf(“Inputthesecondintegernumber:”);可执行语句部分函数体

scanf(“%d”,&num2);

printf(“max=%d\n”,max(num1,num2));}函数体程序的数据结构数据(Data)：一切能够由计算机接受和处理的对象。数据元素(Dataelement)：是数据的基本单位，在程序中作为一个整体加以考虑和处理。数据项(Dataitem)：是数据的不可分割的最小单位，在有些场合下，数据项又称为字段或域。数据结构(Datastructure)：数据之间的相互关系，即数据的组织形式。例:数组

返回数组数组是由一些单元组成的，每个单元对应着一组下标值和一个数组元素。n维数组的每个单元对应n个下标值。数组元素可以是基本数据类型，如整数型、实数型、字符型等，也可以是有多个数据项的一种结构。同一数组中各个元素必须是同一数据类型，每个数组元素都占有相同数量的存储单元，才能用下标来唯一的确定数组中的元素。例：[23,56,900,85,67,53,146]

1234567返回计算语言学是计算科学与语言学的一个交叉学科，其主要任务是运用数学和计算科学的理论与技术研究语言学的基本规律。直接应用：开发自然语言理解系统和机器翻译软件。理论工具：本体与主体理论，形式语言与自动机理论，数理逻辑与形式语义学。研究难点：语义与语境、语用的关系语言多义性的几个例子

现状与出路

返回计算语言学语言多义性的几个例子（一）例1

“他的老师当得好。”的多义性。A、他的传授文化、技术的身分担任的好。B、他的（某位）老师把知识、技能传授得好。C、他的（所有）老师把知识、技能传授得好。D、他的（某位）老师家庭主妇的身分担任的好。E、他的（某位）老师人大代表的身分担任的好。

例2语言多义性的几个例子（二）例2

“调个过儿还是一样”——吕叔湘文集A、在家里，我对儿媳像闺女一样，儿媳对我也像亲妈一样。B、在家里，我对儿媳像亲妈一样，儿媳对我也像闺女一样。C、在家里，我对儿媳像亲妈对闺女一样，儿媳对我也像闺女对亲妈一样。D、在家里，我对儿媳像亲妈对闺女一样，儿媳对我也像闺女对亲妈一样。例3语言多义性的几个例子（三）例3

语音处理的困难—同音字词的语义。A、家家爱加佳，加佳进家家B、加佳爱家家，家家进加佳C、加佳爱家家，加佳进家家D、家家爱加佳，家家进加佳

例四神奇图片返回计算语言学现状与出路

1

数理统计方法：语料库，模糊性与特殊语言现象

2

数理逻辑与形式语义学：陆汝占，汉语计算语义学

3

计算语义学模型：形式语言与自动机理论

4

语言的本质：本体与主体理论返回软件开发方法学软件及其分类软件的开发软件开发方法学研究范畴软件开发方法学发展方向：1、软件开发环境的研究：计算机辅助软件工程（CASE）和形式化软件开发方法2、分布式和并行软件开发方法学：MAS（多代理系统），语义Web，WebService，AORBCO

返回软件及其分类软件：是对事先编