计算机科学导论 课件 第4章 程序设计基础

第4章

程序设计基础目录4.2由机器语言到高级语言4.3程序设计语言的执行过程4.4高级程序设计语言类型4.1什么是程序设计语言4.5高级语言编程示例4.6编程语言及编译器的自主创新之路

第4章

程序设计基础4.1什么是程序设计语言KonradZuse（1910.6-1995.12）数字计算机之父

第4章

程序设计基础什么是程序？为进行某项活动或过程所规定的一系列步骤银行带上存折去银行

3.将存折和取款单递给银行职员

2.填写取款单并到相应窗口排队4.银行职员办理取款事宜

5.拿到钱并离开银行

4.1什么是程序设计语言

第4章

程序设计基础什么是程序？为进行某项活动或过程所规定的一系列步骤程序=====步骤什么是计算机程序？为执行某些操作而编写的有序指令集合计算机程序====计算机能执行的有序指令集合什么是程序设计语言？以某种程序设计语言为工具，编写计算机程序4.1什么是程序设计语言

第4章

程序设计基础4.2由机器语言到高级语言程序设计语言经历了从低级语言到高级语言的发展过程，可以划分为三代：第一代：机器语言（二进制指令，机器能直接执行）第二代：汇编语言（符号代替机器语言，需要翻译）第三代：高级语言（英语和数学语言代替机器语言，需要翻译）由二进制代码表示。如：37+840000000010111000送数到AX寄存器0000000000100101被加数370000000000000101加法0000000001010100加数84用符号代替机器语言。如：37+84MOVAX，37送数37到AX寄存器

ADDAX，84（AX）+84AXA=37+84

第4章

程序设计基础4.2.1机器语言（MachineLanguages）

由二进制编码指令构成的语言。提供最基本的计算机操作--加、减、比较、搬移操作数等。每种计算机都有自己专用的机器指令集合。计算机唯一理解的语言是机器语言。机器语言指令必须由“0”和“1”字符串组成，因为组成计算机内部电路的电子器件只有两种状态：关或开。关—“0”、开—“1”。4.2由机器语言到高级语言

第4章

程序设计基础4.2.1机器语言（MachineLanguages）

优点：占用内存少、执行速度快。缺点：可读性差、难记忆、易错、可移植性差。12345678910111213141516000000000000010000000000000000000101111000001100110000100000000000000010 11101111000101100000000000000101 111011111001111000000000000010111111100010101101110111110000000000010010 011000101101111100000000000101011110111100000010111110110000000000010111111101001010110111011111000000000001111000000011101000101101111100000000001000011110111100000010111110110000000000100100011111101110100010101101 111110001010111011000101000000000010101100000110101000101111101100000000001100011110111100000010111110110000000000110100 000001000000000000111101 0000010000000000001111014.2由机器语言到高级语言

第4章

程序设计基础4.2.2汇编语言与汇编程序

用符号或助记符表示不同的机器语言指令。需要使用汇编程序将助记符翻译成等价的机器语言。每种类型的计算机都有自己的机器语言，所以有多少种机器，就有多少种汇编语言和翻译程序。4.2由机器语言到高级语言

第4章

程序设计基础4.2.2汇编语言与汇编程序

优点：占用内存少、执行速度快、比机器语言易读。缺点：可移植性差，仍然不易编程。12345678910111213141516000000000000010000000000000000000101111000001100110000100000000000000010 11101111000101100000000000000101 111011111001111000000000000010111111100010101101110111110000000000010010 011000101101111100000000000101011110111100000010111110110000000000010111111101001010110111011111000000000001111000000011101000101101111100000000001000011110111100000010111110110000000000100100011111101110100010101101 111110001010111011000101000000000010101100000110101000101111101100000000001100011110111100000010111110110000000000110100 000001000000000000111101 000001000000000000111101Entry main, ^m<r2>subl2 #12,spjsb C$MAIN_ARGSmovab $CHAR_STRING_CONpushal -8(fp)pushal (r2)calls #2,readpushal -12(fp)pushal 3(r2)calls #2,readmull3 -8(fp),-12(fp),-pushal 6(r2)calls #2,printclrl r0ret4.2由机器语言到高级语言

第4章

程序设计基础4.2.3高级语言与编译器

高级程序设计语言与人类的思维和交流方式更接近。使用高级语言，程序设计员就能够用类似于英语的语句编写指令。优点：易学、可读性好、接近自然语言、可移植性。缺点：没有机器语言和汇编语言的执行速度高。思考：1.使用汇编语言或者高级语言编写的程序，计算机能直接执行吗？4.2由机器语言到高级语言

第4章

程序设计基础4.3程序设计语言的执行过程语言的翻译器：将汇编语言或高级语言翻译成机器码的程序。编译器解释器汇编或高级语言编写的程序机器码程序编译或翻译器

第4章

程序设计基础4.3程序设计语言的执行过程1.解释器（Interpreter）：解释一句、执行一句解释器在翻译过语句之后会立即执行这个语句，一条一条的执行目标代码。PYTHON、BASIC和LISP等是解释型语言。

解释源程序解释程序边解释边执行结果用户编辑编辑器出错

第4章

程序设计基础4.3程序设计语言的执行过程2.编译器（Compiler）：整体编译、一次执行把用高级语言编写的程序翻译成机器码，整个程序编译完，整体执行。FORTRAN、C、COBOL等是编译型语言。JAVA是半编译半解释语言。目标程序可执行程序库文件连接程序编译程序编辑器出错编译编译连接编辑用户源程序结果

第4章

程序设计基础4.3程序设计语言的执行过程程序的编译过程：

第4章

程序设计基础4.3程序设计语言的执行过程程序的编译过程：

第4章

程序设计基础4.3程序设计语言的执行过程程序的编译过程：

源程序语义分析和中间代码生成程序语法分析程序词法分析程序代码优化程序目标代码生成程序

目标程序表格管理程序出错处理程序(字符串)

第4章

程序设计基础4.3程序设计语言的执行过程程序的编译过程：例：floatr，h，s；s=2*3.1416*r*(h＋r);STEP1：词法分析-->识别单词词法分析的任务是从左到右逐个字符扫描源程序，进行词法检查并将源程序从字符序列转换成词序列。在这个过程中还要完成过滤掉注释及发现词法错误的任务。基本字float；标识符r、h、s；常数3.1416、2；算符*、+；界符（、）、;、,、=。

第4章

程序设计基础4.3程序设计语言的执行过程

语法分析是编译程序的核心部分，主要任务是确认词法分析的结果—单词序列是否是给定语言的一个正确程序。在语法分析中，给定语言用文法表示，如果给定的单词序列能够识别成符合文法的句子，则程序是正确的，否则就是错误的。

语法单位：<变量>=<表达式>s=2*3.1416*r*(h＋r)STEP2：语法分析-->识别句子

第4章

程序设计基础4.3程序设计语言的执行过程

主要完成两个工作，一是检查每个语法结构的静态语义，即验证语法结构合法的程序是否具有真正意义；二是将程序转换成一种便于处理的中间表达形式。STEP3：语义分析及中间代码生成-->分析句子将s=2

*

3.1416*r*(h＋r)翻译成中间代码(1)(*,2,3.1416,T1)(2)(*,T1, r,T2)(3)(+,h, r,T3)(4)(*,T2,T3,T4)(5)(=,T4,__,s)

第4章

程序设计基础4.3程序设计语言的执行过程

对中间代码进行等价变换，使得变换后的代码比变换前的代码更有效率(执行速度提高及存储空间减小)：STEP4：中间代码优化s=2

*

3.1416*r*(h＋r)中间代码优化后：(1)(*,6.28,r,T2)(2)(+,h,r,T3)(3)(*,T2,T3,T4)(4)(=,T4,__,s)

第4章

程序设计基础4.3程序设计语言的执行过程

将优化后的中间代码转换成特定机器的机器语言并输出目标代码。最后阶段的工作因为目标语言的关系而十分依赖硬件系统。STEP5：目标代码生成

第4章

程序设计基础4.3程序设计语言的执行过程1.表格管理：编译程序在工作过程中需要建立一些表格，以登记源程序中所提供的或在编译过程中所产生的一些信息，编译各个阶段的工作都涉及到构造、查找、修改或存取有关表格中的信息。2.错误处理：一个好的编译程序在编译过程中，应具有广泛的程序查错能力，并能准确地报告错误的种类及出错位置，以便用户查找和纠正。关于表格管理和错误处理

第4章

程序设计基础4.3程序设计语言的执行过程

第4章

程序设计基础4.3程序设计语言的执行过程链接：目标文件是无法直接运行的，把多个目标文件结合，生成一个EXE文件的处理就是链接，运行的程序就称为链接器。链接成功，就会产生一个可执行文件（扩展名为.exe）。加载和运行：

通过链接得到的可执行文件在执行之前，必须被加载到内存中。最后，在CPU的控制下，逐条执行程序中的机器指令。在大多数IDE中，都有一个相应的命令菜单，来运行编译、链接得到的可执行程序。

第4章

程序设计基础4.3程序设计语言的执行过程

AlfredVainoAho

JeffreyDavidUllman获得2020年图灵奖

例如：设计词法分析器的串匹配技术已用于正文编辑器、信息检索系统和模式识别程序；上下文无关文法和语法制导定义已用于创建诸如排版、绘图系统和语言结构化编辑器中；代码优化技术已用于程序验证器和从非结构化的程序产生结构化程序的编程之中。知识扩充：编译技术在软件开发中的应用

第4章

程序设计基础4.4高级程序设计语言类型

根据程序设计语言解决问题的方法及功能，可将高级程序设计语言分为4类。（1）面向过程（2）面向对象（3）函数式（4）逻辑式每种语言都有自己的特色，选用什么语言作为开发工具，关键要看任务。只有适合的，没有最好的.

第4章

程序设计基础4.4高级程序设计语言类型4.4.1面向过程语言自上而下、模块化，易于理解和掌握。表达能力强，应用范围广，能用来实现各种复杂的数据结构的运算。以函数为中心，用函数来作为划分程序的基本单位。流行的面向过程程序设计语言包括FORTRAN、COBOL、BASIC、C、Pascal、Ada等。面向过程语言示例冰箱装大象的操作步骤把冰箱门儿打开。把大象装进去。把冰箱门儿关上。转化为代码（函数式编程）openTheDoor()；pushElephant()；closeTheDoor()；

第4章

程序设计基础4.4高级程序设计语言类型4.3.2面向对象语言面向过程语言中，数据对象是被动的，由程序进行操作。面向对象语言中，对象是主动的，由属性、事件、方法组成。面向对象程序设计的三大特性：封装、继承、多态。主流的面向对象语言有C++、JAVA和C#。面向对象语言示例Step1：先定义一个「冰箱」对象「属性」：当前的冷冻温度、冰箱大象头数「方法」：开门、关门。Step2：再定义一个「大象」对象「属性」：大象的智商、体积「方法」：进冰箱Step3：面向对象编程向冰箱对象下达「开门」的命令。向大象对象下达「进冰箱」的命令。向冰箱对象下达「关门」的命令。

第4章

程序设计基础4.4高级程序设计语言类型4.3.3函数式语言

函数式语言以数学函数为基础，计算被表示为函数求值。程序被看成是一个数学函数。LISP、Scheme是最著名的使用函数式范型的语言。4.3.4逻辑式语言

逻辑式语言又称为声明式语言或说明性语言，它依据逻辑推理的原则响应查询，该语言解决问题的基本算法就是反复的进行归结和推理。

逻辑式语言比较适合用于人工智能这样特定的知识领域。PROLOG是第三代逻辑程序设计语言。

第4章

程序设计基础4.5高级语言编程示例【示例4.1】编写程序，输出“helloworld”（1）C语言程序#include<stdio.h>intmain(){printf("helloworld\n");return0;}（2）C++语言程序#include<iostream>usingnamespacestd;intmain(){cout<<"helloworld"<<endl;return0;}（3）Python语言程序print("helloworld")

第4章

程序设计基础4.5高级语言编程示例【示例4.2】编写程序，输入两个整数，计算并输出二者之和。（1）C语言程序#include<stdio.h>intmain(){inta,b;scanf("%d%d",&a,&b);printf("%d\n",a+b);return0;}（2）C++语言程序#include<iostream>usingnamespacestd;intmain(){inta,b;cin>>a>>b;cout<<a+b<<endl;return0;}（3）Python语言程序a=int(input())b=int(input())print(a+b)

第4章

程序设计基础4.5高级语言编程示例【示例4.3】编写程序，输入两个整数a、b，比较a与b的大小，如果a<b则交换两个变量的值，最后输出a与b的值。（1）C语言程序#include<stdio.h>intmain(){inta,b,temp;scanf("%d%d",&a,&b);if(a<b){temp=a;a=b;b=temp;}printf("交换后：a=%d,b=%d\n",a,b);return0;}（2）C++语言程序#include<iostream>usingnamespacestd;intmain(){inta,b;cin>>a>>b;if(a<b){inttemp=a;a=b;b=temp;}cout<<"交换后：a="<<a<<",b="<<b<<endl;return0;}（3）Python语言程序a=int(input("请输入第一个数a:"))b=int(input("请输入第二个数b:"))ifa<b:a,b=b,aprint(a,b)

第4章

程序设计基础4.5高级语言编程示例【示例4.4】编写程序，给定一个不大于10的正整数，计算并输出该数的阶乘。（1）C语言程序#include<stdio.h>intmain()intn;intfactorial=1;scanf("%d",&n);//输入整数//计算阶乘for(inti=2;i<=n;i++){factorial*=i;}printf("%d",factorial);//输出结果return0;}（2）C++语言程序#include<iostream>usingnamespacestd;intmain(){intn;cin>>n;//输入正整数nintfactorial=1;//阶乘初始值为1for(inti=2;i<=n;++i){factorial*=i;//从2开始累乘}cout<<factorial;//输出结果return0;}（3）Python语言程序n=int(input())factorial=1foriinrange(2,n+1):#从2开始优化计算factorial*=iprint(factorial)

第4章

程序设计基础4.5高级语言编程示例【示例4.5】编写程序：已知数组a有10个整数，在数组中查找整数x，如能找到，输出x对应下标，否则，输出“NotFound”。（1）C语言程序#include<stdio.h>#defineSIZE10//定义数组容量常量intmain(){inta[SIZE];//声明整数数组intx,found=0;printf("请输入10个整数（用空格分隔）:\n");for(inti=0;i<SIZE;i++){scanf("%d",&a[i]);}printf("请输入要查找的整数:");scanf("%d",&x);

//顺序查找算法for(inti=0;i<SIZE;i++){if(a[i]==x){printf("找到元素%d，首次出现位置：%d\n",x,i);found=1;break;//找到后立即终止循环}}//未找到处理if(!found){printf("未找到%d\n",x);}return0;}

第4章

程序设计基础4.5高级语言编程示例（2）C++语言程序#include<iostream>usingnamespacestd;intmain(){inta;//声明包含10个整数的数组intx;//要查找的目标值boolfound=false;//输入数组元素cout<<"请输入10个整数："<<endl;for(inti=0;i<10;++i){cin>>a[i];}//输入要查找的值cout<<"请输入要查找的整数：";cin>>x;

//遍历数组查找目标值for(inti=0;i<10;++i){if(a[i]==x){cout<<"找到元素，下标为："<<i<<endl;found=true;break;//找到第一个匹配项后立即退出}}//未找到的情况处理if(!found){cout<<"NotFound"<<endl;}return0;}

第4章

程序设计基础4.5高级语言编程示例（3）Python语言程序#输入10个整数组成的数组a=list(map(int,