计算机科学与技术学科的方法论课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机科学与技术学科,问题求解的三个过程：,理论：与数学所用方法类似（定义、公理、定理、证明和结果的解释）建立和理解计算机科学与技术学科所依据的数学原理。,抽象（模型化）：源于实验科学（数据采集方法和假设的形式说明、模型的构造与预测、实验和结果分析)。抽象的结果是概念、符号和模型,设计：源于工程学（需求说明、规格说明、设计和实现方法、测试和分析），用来开发求解给定问题的系统。,个重复出现的基本概念,概念和形式模型 抽象层次,演化 按空间排序,按时间排序 效率,大问题的复杂性 一致性和完备性,安全性 折衷与结论,重用 绑定,第一章 编译概述,抽象人类控制复杂度的手段,人机之间存在着一种天然的通讯空隙,人机之间的通讯空隙通常用人工语言作为联系的桥梁,什么是编译程序,实现这种通讯，需要给使用者提供说明这种语言所允许的结构和意义的用户手册，并为计算机提供一种软件，以便通过它，计算机可得到人们用这种语言书写的表示命令或程序的比特流，并将这个输入转换为实现人的意图所需要的内部位组合格式。,复杂的计算机语言：,机器语言：特定计算机的指令系统，它由机器本身的硬件或微程序来解释。,汇编语言：这种“低级”语言充分反映了特定计算机的指令系统。,高级语言：具有复杂的结构并且不依赖于任何特定机器的指令系统和操作系统,语言处理程序：,描述使计算机能理解人们提供的命令与输入的程序。,几个术语：,语言处理程序的两种类型：,解释程序：这样一种程序，它接受的输入是用称为源语言的计算机语言编写的程序，并执行该程序蕴涵的计算。,翻译程序：这样一种程序，它接受的输入是用源语言写的程序，产生的输出是用一种称为目标语言的语言编写的程序。通常目标语言是某个计算机的机器语言。,汇编程序翻译低级语言。,编译程序翻译高级语言。,编译系统：,编译程序与运行系统的合成。,交叉编译（汇编）：,编译（汇编）过程与编译（汇编）输出的目标程序的执行在不同机器上完成时，这种编译（汇编）被称为交叉编译（汇编）。,编译过程概述,编译程序不是一般的数值计算程序，而是一种信息加工程序。,与现有某系统的构造过程进行对照。,这个系统就是人手工进行外文资料翻译系统。,进行外文翻译的人所应具备的能力：,能认识外语的字母及标点、符号。,能识别出文中的各个单词。,会查字典。,懂得此种外语的语法。,具有目标语言的修辞能力。,翻译工作过程：,翻译分析,翻译 综合,外文分析过程,阅读原文,识别单词,分析句子,外文翻译过程,外文综合过程,修辞加工,写出译文,编译程序工作过程,编译程序分析过程,输入并扫视源程序,词法分析,语法分析,编译综合过程,修饰优化,目标代码生成,分析的意义：,找出源程序的结构和原语，决定它的意义。,综合的意义：,建立等价于源程序的目标程序。,分析的两个部分：,决定静态结构的结构分析,确定外加信息和一致性检查的语义分析,综合部分：,代码生成与汇编。,编译程序的逻辑结构,编译程序由八个部分构成：,表格管理,词法分析器,出错处理,语法分析器,语义分析与中间,代码产生器,代码优化器,目标代码生成器,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,示例,; ; . ; ;*;() ;.,词法分析程序,词法扫描器的工作任务：,识别出源程序中的各个基本词法单位；,删除无用的空白字符、回车字符以及其它与输入介质相关的非实质性字符。,删除注释；,进行词法检查，报告所发现的错误。,词法扫描器使用方式：, 词法扫描器作为供语法分析程序调用的子程序。, 将词法分析作为编译过程中的一个独立阶段。,词法扫描器对程序进行处理后的一种可用的输出形式,； ，,， ： ； ：,； ；,;,* ； （,）,单词的一种常用内部表示格式：,（，）,为一整数码，表示单词的类别。,表示单词的值。,例如对程序，可假定语言的单词符号分为四类：,保留字；,专用符号；,标识符；,整数；,程序经词法扫描器处理后，输出的用内部码格式表示的单词符号串如下：,（，）（，） （，；）,（，） （，） （，）,（，） （，） （，）,（，：） （，）（，；）,（，） （，。）,语法分析程序,语法分析的任务：,分析源程序的结构，判别它是否为相应程序语言中的一个合法程序。,分析的一般途径：,由语法分析程序试着为其输入串构造一棵所谓完整的语法树，若成功，则表明输入串在结构上是一个合乎语法的程序；否则源程序中必然有错误。,语法分析的难点：,如何表示语法规则。,如何利用规则机械地进行分析,语义分析,语义分析的主要任务：,规定各语法成分的含义或功能，即规定它们的属性或在程序执行时所应进行的运算及操作。另外还应进行相应的语义检查，例如是否有矛盾的类型说明、表达式中是否有类型不相匹配的运算对象等。,中间代码生成,中间代码（中间语言）引入的原因：,处理上的方便。,便于优化。,便于移植。,中间代码的选取随目标机而异,一般有逆波兰、三元式、四元式、树形结构等,例：程序，若采用四元式作为中间代码，可表示为：,（，）,（，）,（， ，）,（，）,（， ，）,（，）,（，）,（， ，）,（，）,（，）,（，, ，）,（， ，）,（）,注意：,中间代码的产生是与语义分析紧密相连的，通常采用语法制导方法完成，即将产生中间代码工作交给各语义过程来完成。,代码优化,代码优化原因：,前几个阶段的工作较多的考虑语法与语义上的共性，而对源程序间出现的差异考虑交少，所以代码效率较低。,优化范围：,局部、全局优化；与机器有关、无关优化。,编译程序本身的时空复杂度与代码优化是一对矛盾。,对程序，经优化后的代码如下：,（，）,（， ，）,（，）,（， ，）,（，）,（， ，）,（，）,（，）,（，）,（， ，）,（）,目标代码生成,目标代码生成的任务,接受经语义分析之后所产生的中间代码，结合前面各阶段对源程序分析加工得到的有关信息，将中间代码翻译为机器语言或汇编语言形式的目标程序。,翻译目标代码的要求：,生成的代码应尽可能的短。,充分发挥计算机可用资源的效率。,目标代码的三种形式：,具有绝对地址的机器指令代码。,汇编语言形式的目标程序。,模快结构的机器代码,错误检查和处理程序,错误检查和处理程序应具备的基本能力：,报告错误的种类、错误出现的位置以及一定的校错能力。,信息表管理,三类数据：,编译程序所带有的局部数据。,源程序正文的各种中间表示。,含有表示程序正文中上下文依赖关系的信息表格。,例如：常数表、名字表、分析表等,编译程序的组织,所谓遍是指对源程序或其内部形式从头到末扫描一遍并进行有关工作.,多遍扫描的优点:,采用模块结构,各遍功能独立,整个编译程序结构比较清晰。,由于多次扫描、加工，有利于优化。,可按模块逐次调入内存，有利于复盖技术的采用。,编译程序的前后处理器,预处理器,它产生编译程序的输入,完成下面各部分的处理功能,。宏处理：宏是一种较长结构的速记,。文件包含：可将头文件放到程序正文中。例如：的语句。,。合法的预处理器，即用更先进的控制流和数据结构设施来增强原来的语言。,。语言扩充：采用内部宏以增强语言的能力。例如：语言为一种可嵌入语言中去的数据库查询语言，预处理器若取来的是由开始的与语言无关的数据库访问语句，那么可将其翻译为对执行数据库访问的子程序调用。,预处理器要处理两类语句：宏定义和宏调用。,宏定义：一般由特定符号或关键字指定，它由名字和构成其定义的体所组成（可有形参）。,宏调用：由宏名与相应的实参组成。,汇编程序,翻译低级语言的程序。,加载器和连接编辑器,加载过程：取可重定位的机器代码，修改可重定位地址，并将经修改的指令和存储中的数据安装到合适的存储区中。,连接编辑过程：将几个可重定位的机器代码连接成一个单一的程序。,编译技术在软件工程中的应用,语法制导的结构化编辑器,程序格式化工具,软件测试工具：,静态分析器：,读一个源程序，在不运行的情况下加以分析，以发现程序中的潜在错误和异常。,动态结构测试器：,在一组测试用例下实际执行程序，记录程序的实际执行路线，并将实际运行结果与期望结果进行比较以发现错误和异常。,程序理解工具：,确定模块间的调用关系，记录数据的静态属性与结构属性，画出控制流程图以助于理解,高级语言的翻译工具：,高级语言间的翻译,