（计算机应用技术专业论文）程序理解中信息存储与检索技术的研究与实现.pdf

浙江工业大学硕士学位论文 程序理解中信息存储与检索技术的研究与实现 摘要 随着软件工程领域的发展，软件维护问题已成为当前软件产业面i 盔的重要课 题。在软件维护过程中，程序理解是一项枯燥、费时且困难的任务，必须借助程 序理解辅助系统进行辅助分析。而信息的存储与检索效率是影响程序理解辅助系 统效率，乃至程序理解效率的关键因素之一目前，绝大多数程序理解辅助系统 采用专业的数据库管理系统作为信息存储与检索的后台支撵。由于专业数据库管 理系统在其他方面考虑的因素较多，相应地降低了存储与检索的效率。另外，专 业数据库管理系统要求使用特定的检索语言，这也增加了检索操作的处理时间和 程序理解的难度。 针对上述问题，本文的主要工作是研究和实现了一个具有较高存储与检索效 率、支持大型程序和增量式更新的程序信息库。首先，根据程序设计语言的符号 类型，提出信息分类存储的思想。按照类型的不同，将软件源程序信息存储在不 同的信息库文件中，由各个库文件共同组成一个统一的程序信息库：接着在借鉴 专业数据库存储与检索机制的基础上，分析研究了b + 树的性能和索引机制，提 出利用b + 树结构设计程序信息库的存储与检索模型。从“自底向上批量插入关 键字”、“对关键字进行压缩存储”和“选定合适的阶数m 值”三个方面出发对 b + 树的存储结构进行优化设计，并设计b + 树结点间与结点内双层索引；然后根 据程序理解的需要设计了四种不同的检索方式，分别支持程序理解辅助系统四个 窗口中的信息显示要求；最后对一系列由不同数量的信息记录组成的文件进行实 验，在信息的存储空间与检索时阃上测试信息库的存储与检索效率。实验结果表 明，信息库在牺牲部分存储空间的基础上较好地实现了信息的快速存储与检索。 关键词：程序信息库，b + 树，分类存储，前缀压缩，程序理解 浙江工业大学硕士学位论文 s t u d ya n di m p l 】巳m e n t 觚o no n i n f o r 姗o ns t o r a g ea n dr e t r i e 气i t e c h n i q u ef o rp r o g r a mi 小m e r s t a n d i n g a st h ed e v e l o p m e n to fs o f t w a r ee n g i n e e r i n gf i e l d ，t h ep r o b l e mo f s o f t w a r em a i n t e n a n c eh a sb e c o m ea l li m p o r t a n tq u e s t i o nf o rd i s c u s s i o n c u r r e n t l yi ns o f t w a r ei n d u s t r y i nt h ep r o c e s so fs o f t w a r em a i n t e n a n c e ， p r o g r a mu n d e r s t a n d i n gi s ab a l d ，t i m e - c o n s u m i n ga n dd i f f i c u l tt a s k ， w h i c hn e e d sp r o g r a mu n d e r s t a n d i n ga i d e ds y s t e m st oh e l p a n dt h a t ，t h e i n f o r m a t i o ns t o r i n ga n dq u e r y i n ge f f i c i e n c yi so n eo ft h ek e yf a c t o r st h a t i n f l u e n c eo nt h ee f f i c i e n c yo fp r o g r a mu n d e r s t a n d i n ga i d e ds y s t e m s ，s o m u c ha sp r o g r a mu n d e r s t a n d i n g a tp r e s e n t ，m o s tp r o g r a mu n d e r s t a n d i n g t o o l s a d o p tp r o f e s s i o n a l d a t a b a s e m a n a g e m e n ts y s t e m s ( d b m s ) t o r e a l i z et h ef u n c t i o n o f s t o r i n g a n dq u e r y i n g h o w e v e r , p r o f e s s i o n a l d b m st a k eal o to fo t h e rf a c t o r si n t oa c c o u n t ，t h u s ，t h ee f f i c i e n c yo f s t o r i n ga n dq u e r y i n gi sr e d u c e d i na d d i t i o n ，p r o f e s s i o n a ld b m sd e m a n d t ou s es p e c i a lq u e r yl a n g u a g e sw h i c hi n c r e a s e d st h ep r o c e s st i m eo f s t o r i n ga n d t h ed i f f i c u l t yo fp r o g r a mu n d e r s t a n d i n g a i m e da tt h ep r o b l e m sm e n t i o n e da b o v e ，t h em a i nt a s ko ft h i sp a p e r h 浙江工业大学硕士学位论文 i st or e s e a r c ha n dd e s i g nap r o g r a md a t a b a s ew i t hb e t t e re f f i c i e n c yo f s t o r i n ga n dq u e r y i n g ，s u s t a i n i n gl a r g e rp r o g r a m s a n di n c r e m e n t e du p d a t e f i r s t l y , a c c o r d i n gt ot h es y m b o lt y p e so fp r o g r a m m i n gl a n g u a g e ，p o t f o r w a r dt h ei d e ao fi n f o r m a t i o ns o r t e ds t o r i n g a c c o r d i n gt ot h et y p e s ，p u t t h ei n f o r m a t i o ni n t od i f f e r e n tb a s ef i l e s ，t h e nb i n d i n ga l lt h ef i l e st o g e t h e r t of o r map r o g r a md a t a b a s e s e c o r d l y , o nt h eb a s i so fp r o f e s s i o n a l d b m s s t o r i n ga n dq u e r y i n gm e c h a n i s m , a n a l y z et h ec a p a b i l i t y a n d i n d e xm e c h a n i s mo ft h eb + - t r e e p u tf o r w a r dt h ei d e a o fu s i n gt h e s t r u c t u r eo fb + t r e et od e s i g nt h ep r o g r a md a t a b a s em o d e l o p t i m i z et h e s t r u c t u r eo fb + - t r e ef r o mt h r e ea s p e c t s ：i n s e r t i n gb a t c hk e y w o r d sf r o m b o t t o mt ou p ，s t o r i n gk e y w o r d sw i t hc o m p r e s s i n gt e c h n i q u e ，c h o o s i n ga s u i tw a y n u m b e r , a n dd e s i g ni n d e xw i t h i na n da m o n gn o d e s t h i r d l y , a c c o r d i n gt ot h en e e d s o fp r o g r a mu n d e r s t a n d i n g ，d e s i g nf o u rq u e r y m e t h o d s ，s a t i s f y i n g t h ed e m a n d so f f o u rw i n d o w si n p r o g r a m u n d c r s t a n d i n ga i d e ds y s t e m s a tl a s t ，d oe x p e r i m e n t s w i t has e r i e so ff i l e s c o m p o s i n go fd i f f e r e n ta m o u n to fi n f o r m a t i o nr e c o r d s ，t e s tt h ep r o g r a m d a t a b a s es y s t e m ss t o r i n gs p a c ea n dq u e r y i n gt i m e t h er e s u l ts h o w s t h a t u n d e rt h ec i r c u m s t a n c eo fs a c r i f i c i n gs o m es p a c e ，t h ep r o g r a md a t a b a s e a c h i e v e sq u i c k l ys t o r i n ga n dq u e r y i n gc a p a b i l i t y k e yw o r d s ：p r o g r a md a t a b a s e ，b + t r e e ，s o r t e d s t o r i n g ，p r e f i x c o m p r e s s i o n ，p r o g r a mu n d e r s t a n d i n g 1 1 1 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行 研究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江 工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的 法律责任。 作者签名计金乍 日期：为印年2 月2 咖 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密口。 ( 请在以上相应方框内打“v ”) 日期：硼年f 朔巧日 醐：矿位月砧日 应j y 叁多 叶仁 名名套鍪者师怍导 浙江工业大学硕士学位论文 第一章绪论 在软件工程领域，软件维护闯题已成为当前软件产业面临的重要课题。而软 件维护工作的第一步，就是要理解软件源程序。软件源程序的理解是一项枯燥、 费时的工作。因此，穰序理解辅助系统的发展成为软件维护的重要组成部分。而 在程序理解辅助系统中，程序信息的存储与检索效率是影响系统整体性能的关键 因素之一。在此情况下，本文对程序理解中信息的存储与检索技术进行了研究， 设计出适合程序信息库的存储与检索模型，这对促进程序理解辅助系统的发展， 乃至软件维护问题的解决将具有一定的理论意义和现实意义 1 1 程序理解 程序理解是软件工程领域的一个重要组成部分，是软件维护过程中一个必不 可少的环节，越来越受到业界的关注。下面分别从程序理解的定义、演化及其必 要性三方面对程序理解的相关概念作简要阐述。 1 1 1 程序理解的定义 对于程序理解，目前尚没有统一的定义，文献【1 】中列出了一些具有代表性 的定义，其描述如下： 1 程序理解是一个利用已有信息来获取新信息，以最终达到认识源代码为 目标的过程。 2 程序理解是一种通过对软件源程序进行分析、提取和概括，从而获得有 关该软件信息的推导式过程。 3 程序理解是一项通过分析源代码从而得出系统的部分或全部概要设计 的工作过程。 4 程序理解是一个获取计算机程序信息的过程。 从广义上说，涉及源代码或程序员的一切活动，如程序的调试和修改等，都 属于程序理解范畴。 简单来说，程序理解就是一个从软件源程序中获取程序内部信息的过程，是 浙江工业大学硕士学位论文 通过程序源代码探求程序“傲什么”和。怎么做”的过程，是人们将程序及其环 境对应到面向人的概念知识的过程。 1 1 2 程序理解技术的演化 程序理解技术是一种运用计算机代替人工对软件源程序进行有效分析的技 术。到目前为止，对于程序理解的研究一般可分为以下四类【2 1 ： 第1 类的研究从7 0 年代开始，目前仍在继续。它的特点是尽量做到程序隐 含信息的显示表示以及程序内部关系的可视化，如控制流和数据流分析、各种程 序视图的构造等。 第2 类的研究开始于7 0 年代后期，大量的研究主要集中在8 0 年代和9 0 年 代它的特点是从源代码中提取信息。并存放在通用的数据库中，然后通过查询 语言对数据库进行查询 第3 类的研究开始于年代后期，其主要特点是采用知识推理等技术识别 程序概念 第4 类的研究开始于9 0 年代初。这类研究的特点是采用模式匹配、程序变 换等技术识别程序的高层概念，如标准算法、数据结构、语法及语义匹配等。 随着程序理解技术的发展，程序理解的对象从传统的结构化软件进展到面向 对象软件。所谓传统的结构化软件，是指由传统过程性语言和结构化方法开发的 软件。用过程性语言书写的软件源程序一般具有“算法+ 数据结构”的特点。因 此，面向传统软件的程序理解主要从数据结构、控制结构、程序功能、文件知识 以及类型推理几个方面展开研究。而面向对象软件的程序理解，其方法归结起来 一般有1 2 1 ；( 1 ) 基于类层次的理解；( 2 ) 基于对象依赖关系的理解：( 3 ) 基于对象式 程序结构的理解；( 4 ) 基于高层对象系统的理解；( 5 ) 基于对象系统功能设置的理 解；( 6 ) 基于方法多态性的理解；详细编码的理解；( 8 ) 利用度量技术理解面向 对象程序。 大部分程序理解的方法论都是基于源代码分析提出的。程序理解的任务就是 一种揭开隐藏在源代码中的设计思想的过程。文献 2 1 q a 还详细论述了程序理解 技术发展过程中出现的各种程序理解模型和程序理解方法的思想与原理，在此不 作重述。 2 浙江工业大学硕士学位论文 1 1 3 程序理解的必要性 在软件工程领域，程序理解是软件开发过程中的一项重要活动，无论是软件 的维护、测试或是度量都离不开对软件源代码的理解【3 】。 随着社会对软件需求的不断增长，正在使用和开发的软件与日剧增，许多大 型复杂的软件已投放市场。在软件开发领域，最为关心的是如何提高软件开发过 程的生产效率以及所开发软件的产品质量。但是，就目前情况来看，软件开发的 绝大部分精力并不是花在开发新的软件系统，而是在于维护现存的软件系统。根 据统计分析，在整个软件开发周期中，用于软件维护上的资源与时间占了 5 0 - 7 5 1 1 1 1 4 1 。而在软件维护中，4 7 - 6 2 的时间是花在了对被维护软件的程序 理解上阁旧。由此可以看出程序理解在软件工程领域的重要性和必要性。 软件维护问题已成为当前软件产业面临的重要课题。而在软件维护工作的第 一步就是要对软件源程序进行分析和理解。能否准确、快速、全面地理解软件源 程序是决定软件维护工作成败的关键i q 。 尽管如此，软件的程序理解却是一项枯燥、费时的工作。随着软件规模的逐 渐增大，软件的程序源代码越来越庞大，而且历史上遗留下来大量的程序，它们 要么没有文档，要么文档过时或不完整，用传统的手工方式逐句分析源代码根本 不可能在短期内弄清楚软件系统的体系结构、软件程序的内部关系等信息，这些 都给程序理解带来很大的困难。 解决这些问题的一个有效方法就是开发一种程序理解辅助系统，使它能够代 替人工对软件源程序进行有效的分析，提取出源程序中的重要信息，然后用系统 化、结构化、图形化等形式多视角展现分析结果，使程序理解工作能够在辅助系 统的支持下半自动地进行，保证理解过程的准确性和高效性，从而帮助软件开发 人员快速有效地理解软件源程序， 1 2 程序理解辅助系统概述 程序理解辅助系统，即程序理解工具( p c t s ：p r o g r a mc o m p r e h e n s i o nt o o l s ) ， 是一类使得理解计算机程序的结构或功能的过程变得容易的软件工程工具【2 l 。它 是一个集信息分析、信息存储、信息处理和信息利用为一体的软件理解辅助系统。 浙江工业大学硕士学位论文 利用程序理解辅助系统，对软件程序源代码进行有效的分析，提取出源代码 中的重要信息存放于程序信息库中，然后根据不同层次上程序理解的需要从信息 库中检索出所需信息，实现对程序内部信息的快速定位和程序内部关系的可视 化，以减轻维护人员程序理解的智力负担，增强理解的准确性和可靠性，帮助维 护人员提高理解效率 目前已经存在的程序理解辅助工具很多，文献【2 】中根据工具的用途将其分 成六类，在详细讨论每类程序理解辅助工具特征的基础上列举了一些已开发成功 的程序理解工具实例 除此之处，社会上也存在许多商业性程序理解辅助软件，目前较为流行的主 要有以下几种： 黜舀【7 j ； 砌g i 是一个可扩展、可裁剪的逆向工程环境，可以帮助用户更好地理解遗产 软件系统它主要由三部分构成：r i g l - r e v e r s e r 、砌g i - s 渊和r i g i - e d i t 。 r i g i - r e v e r s e r 是程序静态信息解析器，支持c 、c o b o l 等语言。r i g i - s e r v e r 是程 序静态信息库，用于存储从源代码提取的信息。t i g i e d i t 是交互式的窗口图形编 辑器，以图形交互方式展示和操纵程序静态信息。硒舀在其图形编辑器中提供了 两种展示软件结构的方法：( 1 ) 在多个独立的窗口中显示软件结构：( 2 ) 使用嵌 套图表中的特定视图显示软件结构。 l n l a g i x - 4 d 【b 】 i m a g i x 4 d 是一个支持c 和c 的程序理解工具，能在多个层次上分析系统 源程序。这些层次包括高层的设计、建构的细节、类和函数依赖等。它以三维图 形的方式描述软件的重要信息，并可快速定位到相关视图 u n d e r s t a n d i n gc c + + 【9 1 ： u n d e r s t a n dd c + + 支持o “+ 语言，是由s c i t o o l s 公司开发的程序理解辅助 工具。它能够展现各种数据结构定义、函数声明和定义、交叉引用、函数调用等 程序内部信息，可以统计函数的复杂度，控制语句的嵌套深度等。 c b r o w s e r i l o 】： c b r o w s e r 是一个图形化的c c + + 源代码搜索与浏览工具，支持对源程序全 局特征的查看，具有语法高亮显示和全文搜索的功能。它可以通过提供一个历史 4 浙江工业大学硕士学位论文 机制来帮助管理源代码搜索的递归过程，每次查询都被记录，在任何时候都可以 被调用，不需要重新查询数据库它还提供了一个层次型的调用树，函数的调用 图可以被扩展或简化以便显示或隐藏其调用的函数，而该函数的相应代码段内容 显示在一个邻接的窗口中。 c s c o p e l l l j ： c s c o p e 是一个被广泛使用的、交互的、面向屏幕的源代码浏览工具它允 许用户浏览c 语言源程序的指定代码，在代码中查找有关全局定义、函数调用 与被调用关系、文件包含关系、符号引用关系、文本串等程序内部信息 k s c o p e 1 2 1 ： k s c o p e 是遵守g p l 协议的开源软件，是c s c o p e 的k d e 前端。它为大型的 c 语言程序项目( 如l i n u x 内核) 提供了一个源代码编辑环境。k s c o p e 主要用 来对源代码进行编辑和分析，以图形方式显示函数调用关系，能够方便地查看各 种符号间的交叉引用关系其主要特征有：具有多个编辑器窗口、对每个打开的 编辑器提供标签列表、工程管理，会话管理等。 s o u r c ei n s i g h t l l 3 1 ： s o u r c ei n s i g h t 支持c 、c + + 、雠和j a v a 语言。它以工程的方式分析软件源 程序，以图形方式显示各种符号、符号引用树、类继承图、函数调用图等。但其 函数调用图只能展示函数调用关系，按字母顺序罗列被调用函数列表，不能反映 函数控制流程，不方便进行数据流跟踪。 s o u r c en a v i g a t o r i l 4 i ； s o u r c en a v i g a t o r 是遵守g p l 协议的开源软件，具有类似于s o u r c ei n s i g h t 的功能，支持对c 、c + + 、j a v a 、t c l 、i n c rt c l 、f o r t r a n 和c o b o l 等源程序 的分析，使用t c i _ r k 语言编写图形用户接口，通过图形用户界面显示各种符号 信息、符号上下文信息、符号引用树、类继承图、函数调用图等。其设计基于两 个软件组件：一个数据库引擎( d a t a b a s ee n g i n e ) 和一个图形用户接口，用来表 述驻存在数据库内的软件源程序信息。它不能分析并获取局部符号信息，不便于 上下文信息查看，不能查看定位同名符号，而且分析大型软件源程序时速度较慢。 5 浙江工业大学硕士学位论文 1 3 程序信息库 程序理解辅助系统开发过程中的关键技术难题之一就是设计程序信息库。程 序信息库是程序理解辅助系统的关键后台支撑，是存放软件源程序信息的仓库。 同时为程序理解过程中展示程序内部各种关系提供数据源。 随着软件规模的增大，程序分析过程中获取和产生的程序信息量很大，数据 存储与检索频繁，程序信息库的性能直接影响程序理解辅助系统的整体性能。为 程序信息库设计一种高效的存储结构，将系统在程序分析阶段所获得的程序信息 存储到信息库中，并设计一种相应的检索机制，快速地检索出程序理解过程中所 需信息，将程序内部符号信息以及符号间的关联信息展现给用户，这对程序理解 辅助系统的开发具有至关重要的意义，能够为程序理解辅助系统最终实现在多视 角上展现程序内部关系的功能奠定基础。由此可见，程序信息库的存储与检索技 术将是一个至关重要的研究课题。 1 4 研究现状 1 4 1 国外研究现状 程序理解辅助系统可从静态和动态两个角度对软件源程序进行分析。早在 1 9 8 6 年，m m 研究中心就已经开始对程序理解辅助工具进行研究。学者【j n o r e c l e v e l a n d 提出以多视角展示静态分析所得数据的方式为程序员提供一种新的程 序阅读方法的思想旧。学者d o n a l dp a z e l 提出，根据动态分析所得数据创建多种 类型的视图来辅助程序员了解动态数据结构的思想f 埘。从已经搜集到的文献中 可以看出，目前，国外已经存在很多种支持程序理解的软件工具，在这些软件系 统中，其程序信息库设计采用的数据模型主要有三种类型：关系数据模型、面向 对象模型和基于图形模型。 ( 1 ) 基于关系数据模型的程序理解辅助系统： o m e g a 系统1 1 6 l 【1 7 i 嗍：用于p a s c a l 语言，采用关系型数据库存储程序信息， 并使用q u e l 语言进行信息查询。它将程序的所有信息存储在5 8 个关系中，随 着存储在信息库中的程序信息量的增大，程序理解辅助系统的性能会迅速下降。 6 浙江工业大学硕士学位论文 c l a 和c i a + + 系统【”f f 2 0 f f ：z 1 ：分别支持c 语言和c + 借言。其程序信息存 储在关系数据库中，使用s q l 语言进行查询，根据存储在数据库中的概念模型 可获得相应层次上的程序视图。它们的数据模型包含了实体与联系。主要的实体 包括模块、全局变量、文件等。主要的联系包括函数调用、文件包含和变量声明 等。但是，数据库的概念模型只考虑了程序中的全局对象，忽略语句、变量等信 息，因此只能在程序全局层次上建立视图，而不能获得详细的程序结构描述，数 据库存储的信息不够全面、完整。 弱蓼系统【1 9 1 ：r i g i 刚好与c i a 相反，它是一个图形视图产生器，不提供 普通的查询功能，而是对模块、子系统等高层信息进行操作，提取出有关子系统 内聚、耦合和资源流等重要信息，然后以视图的形式反映相应模块的模型。 s o f t w a r eb o o k s h e l l = 【1 q ：一种为针对软件高层粗纹理数据模型设计的数据库 系统。源文件或程序高层实体信息以b o o k 形式来描述，这些b o o k 之间的关系用 一种元组属性语言( t u p l e - a t t r i b u t el a n g u a g e ) 来描述，实体信息及其关系被存储在 一个关系型数据库中。 另外，一些研究机构也在基于关系数据模型的程序信息库设计上进行了深入 研究，具体情况如下： 1 9 7 3 年，美国德克萨斯州奥斯汀信息研究会h a i l e r 等人在其所作的内部报 告中介绍了f a c e s 系统( f o r t r a na u t o m a t i cc o d ee v a l u a t i o ns y s t e m ) 1 2 2 1 。它是 f o r t r a n 分析系统，是为马歇尔航空航天中心开发的，其总策略是由一张表或一 系列表间的链接来实现查询。f a c e s 包括三个主要表：符号表、使用表和节点 表。符号表存储模块中的每个符号项目及符号类型；使用表存储每个符号事件项 目及其相应用法；节点表确定每条语句类型及其逻辑前驱语句和后继语句。各个 表中还存储了到其它表的指针，以便在各表之间进行操作。这种设计使得查询操 作能够有效地执行，但不利于扩展和复杂查询。 1 9 7 8 年，德州大学奥斯汀分校计算机科学系和计算中心研究者j c b r o w n e 和i b m 公司研究者d a v i db j o h n s o n 在第三次软件工程国际会议学报上发表的论 文 f a s t ：a s e c o n dg e n e r a t i o np r o g r a ma n a l y s i ss y s t e m 中介绍了一种用于分析 f o r t r a n 语言的系统f a s t ( f o r t r a na n a l y s i ss y s t e m ) 1 2 3 1 。该系统是通过整合 已有的软件系统并使用现代语言系统开发工具实现的。f a s t 实现了系统地分析 7 浙江工业大学硕士学位论文 程序的功能。 1 9 9 8 年，新加坡国立大学信息系统与计算机科学系学者s t a nj a r z a b e k 提 出一种使用p q l ( p r o g r a mq u e r yl a n g u a g e ) 似】作为程序查询语言的静态程序分 析器体系结构设计方法，将静态程序分析的概念模型与实现问题分离f 1 6 1 。j a t z a b e k 在他的p q l 系统中提出构建一个独立于其实现的数据库系统。p q l 依赖于扩展 的对象模型技术( o m t ) 来描述源文件。在数据库的存储中，这些o m t 模型将 被转换成实体关系数据模型。 ( 2 ) 基于面向对象模型的程序理解辅助系统： g u p r o 系统闭：一种基于g r a x 的知识库系统。用户使用实体关系数据模 型来设计概念模型，使用面向对象数据库来存储程序信息，在对信息库进行检索 时要求使用一种规格化的查询语言g r e q l 来实现。由于g u p r 0 是基于对象的，因 此其概念模型必须对所有程序元素及其相互关系进行完整的描述。 r e h n e 系统【1 6 j ：r e f i n e 利用面向对象数据库存储源代码的语法描述信 息。为了软件维护过程中的程序转换，r e f i n e 根据数据库进行模式的规格化和 匹配。 x r e f x r e f d b t l s j ；一种用于维护面向对象程序的综合性系统，各个子系 统以程序信息库为中心，并共享该程序信息库。 g o o s e l l 8 】：g o o s e 是一个用于分析面向对象软件系统的工具集。其基本 思想是从面向对象程序系统的源文件中提取出面向对象的基本实体信息，如类、 方法、属性等，以及它们之间的继承、引用、聚合等关系。 ( 3 ) 基于图形模型的程序理解辅助系统： g r a s 1 6 2 5 1 ：g r a s 是砌g i 系统中使用的数据库，存储程序分析后的源 代码实体，支持程序信息以图形结构方式显示。1 9 8 5 年，实现了g r a s ( g r a p h s t o r a g e ) 系统的第一个原型，此后该系统的许多升级版本被广泛地应用在软件 工程的不同领域。g r a s 是一种面向图形的数据库系统，使用一种叫做p r o g r e s 的正规标准语言描述特征图形。目前从s u n 工作站可以获得稳定高效舨的g r a s 系统，带有支持m o d u l a - 2 和c 的接口。 g r a p h l o g 硼：一种由学者c o n s e n s 提出的超媒体查询模型，可用来存储及 查询程序代码。其查询实现的方法是将查询转换成谓词逻辑程序。g r a p h l o g 提 8 浙江工业大学硕士学位论文 供了聚集函数和路径总结，但查询图只能表示有限的算术运算嘲。 ( 4 ) 其他 程序信息库通常是基于面向对象或关系型数据库的，为了适应软件的不同需 求，也存在基于其他数据模型的信息库系统： m a r s 系统( m u l t i t e x t a n a l y t i c a l r e p o s i t o r y s y s t e m ) 1 1 6 1 ：在该系统中， 将源代码文件的文本内容加上结构以及语义信息后形成的增补文本存储到一系 列文件中，这些增补文本文件与源代码文本文件一起，构成了一个数据仓库。 m u l t i t e x t l 2 1 1 ：一种结构化的文本检索系统，使用h r m l 、s g 眦、标准邮件 及文字处理器等多种格式对不同种类的结构化文本集进行处理。m u l t i t e x t 不依 赖于特定语言，程序源文件可被看作是某种形式的结构化文本，不同语言编写的 源文件可以一起被存储在同一个数据库中。m u l t i t e x t 设计的文档结构模型不依 赖于固定的样式，能够对文档的结构和内容进行查询，其查询语言是g c l 。 j u p i t e r 系统闭唧：由w a t e r l o o 大学a n t h o n yc o x 和c h a r l e sc l a r k e 等 人设计开发。它使用一种基于注释、索引和属性的数据模型m a i a ，能够存储从 程序中抽取出来的任何句法、类型以及流程信息，使用m e r c u r y 作为其查询语言。 m e r c u r y 是将一种已有的查询语言( g c l ) 与其设计融合一起后形成的，被用来 访问数据库与处理查询操作。j u p i t e r 系统基于结构化文本数据库系统 m u l t i t e x t 的可扩展版本，使用特殊的索引和合适的算法，简单的查询能够在一 秒内完成对i o o g b 数据的操作，对于大型程序需要一个大容量的数据库。 a d a 维护工具包( a m t ) 2 s l ；支持增量式分析，其设计基于结构树，并没 有创建数据库。其它未使用数据库的系统还包括支持c 程序的c s o p e 和支持 i n t e r l i s p 程序的m a s t e r s c o p e 2 l q 。 1 4 2 国内研究现状 国内在程序理解技术上的研究起步较晚，已开发出的程序理解辅助系统也较 少。根据已搜集的文献资料来看，主要有下面的一些研究机构及其开发出的程序 理解辅助系统： 北京大学孙家辅、袁勇等研究者研制开发了逆向工程工具j b r e t j a v a 系统 嘲。该系统采用e e r 模型为被分析的系统源程序建立概念模型，并用关系数据库 9 浙江工业大学硕士学位论文 存储所抽取的程序信息。在j b r e t - j a v a 系统中，程序信息抽取器以增量方式静态 分析程序源代码，抽取程序信息。程序信息表示器生成交互式理解的可视化视图 以及符合青鸟面向对象规范的o o d ( 0 b j e c t - 0 r i e n t e dd e s i g n ) 文档。j b r e t j a v a 支持增量式分析，只分析那些自建立增量库以来修改过的源程序，并更新其增量 数据库，然后将所有的增量数据库重新链接成程序信息库，从而提高了程序分析 效率。另外，j b r e t - j a v a 系统将数据收集和信息浏览相分离，增强了系统的维护 性和可扩展性。 此后，他们对程序理解辅助系统的研究扩展到其他面向对象语言( s m a l l t a l k 等) 以及流行的非面向对象语言( c 、f o r t r a n 、c o b a l 等) 方面。以杨芙清院 士为首的一批研究者设计开发了支持s m a l l t a l k 的程序理解辅助系统b d c o m - s t 和b d c o m c 斗+ ，以及青鸟程序理解系统j b p a s ( j a d e b i r dp r o g r a ma n a l y s i s s y s t e m ) 【冽例。下面分别对这三种程序理解辅助系统作简要描述。 9 0 年代，s m a l l t a l k 的应用呈现出较快的增长趋势，但s m a l l t a l k 环境对其并 没有提供足够的理解支持。在此背景下，北京大学梅宏、杨芙清等研究者开始致 力于设计开发一种针对s m a l l t a l k 的程序理解辅助系统b d c o m s t 。该系统采用 e e r ( e x t e n d e de n t i t yr e l a t i o n s h i p ) 模型来描述s m a l l t a l k 程序信息库结构。 b d c o m s t 系统在分析s m a l l t a l k 程序的基础上，利用类型推导技术来解决动态 行为的理解问题，从源程序逆向生成o o d 文档，结合图形显示来辅助大型复杂 的s m a l l m l k 程序的理解工作。该系统由信息抽取器、信息库服务员和用户界面 三部分组成。由信息抽取器从s m a l l t a l k 源程序中抽取的程序信息通过信息库服 务员存入到程序信息库中，之后根据信息库中已经获得的程序信息来计算程序中 每个表达式的类型信息，用户通过用户界面发送请求并从程序信息库中获得所需 信息。信息库服务员是访问程序信息库的唯一接口，由以下三部分组成：p i a c 解释器、用户管理部分和数据库管理部分。p i a c 解释器负责解释专用的数据操 纵语言；用户管理部分负责管理有关用户的信息和操作：数据库管理部分负责管 理有关数据库的信息和操作，利用o d b c 将通用的数据库访问转换为某种特定 的d b m s 格式。 b d c o m c + + 是一个c + + 程序分析系统的原型版本，包含三个主要构件，一 个信息提取器、一个信息管理器和一个用户界面。该系统采用增量式分析技术对 浙江工业大学硕士学位论文 程序源代码进行静态分析，数据库概念模型采用e e r ( 增强实体关系) 模型， 由数据库链接器将各个增量型数据库链接成一个统一的信息库，在信息库中存储 由信息提取器对c 斗+ 程序分析后所得的程序信息。 j b p a s 是在b d c o m c 斗+ 的基础上开发的一个程序分析系统，包含三个主要 构件：一个c + + 前端、一个信息管理器和一个程序分析工具集。c + + 前端根据数 据库概念模型从c + 源代码中提取出程序信息，并将其存储到增量数据库中信 息管理器通过链接各个增量数据库构造出程序信息库，并为分析工具提供数据库 访问接口。所有工具通过信息管理器共享同一个程序信息库。该系统采用了增强 实体关系e e r ( e n h a n c e de n t i t yr e l a t i o n s h i p ) 为c + + 程序建立概念模型，并用 关系数据库存储所有信息，按照不同的用户需求组织程序信息，辅助用户理解 c | 卜+ 程序。该系统逆向生成源程序的o o d ( o b j e c t o r i e n t e d d e s i g n ) 文档和r o s e 文档。 除了北京大学外，国内还有许多其他研究机构在程序理解技术上进行研究。 2 0 0 1 年，合肥工业大学计算机与信息学院学者何允如和李心科，以及上海 大学计算机学院学者刘宗田提出了一种新的程序信息库的设计模式【3 ，把程序 信息分为实体和关系，采用将实体间关系包含在其属性中的方法，即：为每个实 体赋予一个唯一的编号，同时每个对象又有一个属性用来标识它所属对象的编 号。在此基础上建立的程序信息库c p p i n f o 使用关系数据库存储程序信息，可 直接利用s q l 语言进行信息查询。 南京大学李必信、刘小东、郑国梁等研究者设计开发了一种基于c + + j a v a 的程序分析系统o d p s e 【3 2 l 。该系统支持面向对象程序分析，主要由扫描器、 知识库、分析器、统计工具、波动检测器、度量工具和切片工具等部分组成。由 扫描器进行简单的词法分析和语法分析后生成的其他工具所需的中阃数据被存 放在知识库中。知识库是系统其他工具进行工作的基础，为它们提供数据。知识 库中的知识是以类为单位组织的。关于一个类的所有知识被组织在一个 c c l a s s l n ：f o 类的实例中。源程序中的每一个类对应于知识库中的一个c c l a s s l n f o 对象。 此外，南京大学的研究者还设计开发了软件理解工具t a u s f 4 j 。t a u s 能对 p a s c a l 源程序进行结构分析。其设计思想是根据程序的物理结构和逻辑结构把程 1 1 浙江工业大学硕士学位论文 序划分成较小的程序段分别进行理解，然后通过对程序进行控制流、数据流跟踪 或人工地模拟执行程序，达到对程序抽象的了解，最后把程序细节的理解归纳成 更高级的抽象。 哈尔滨工业大学在2 0 0 1 年设计了一个逆向工程工具r e r p 引该工具能够对 c c + + 语言进行分析，生成可编辑的c 语言程序分析图或“+ 语言程序目标对象 图。但是，它只能部分地辅助程序理解，没有建立一个辅助用户对系统进行全面 分析与理解的集成环境。 复旦大学学者杨玲、张悦秋在文献【3 4 】中所讨论的工具i c s u t ( s o f t w a r e u n d e r s t a n d i n g t 0 0 1 ) 是一个i g c a d 领域内的软件理解工具，提供了一个能够方 便地帮助用户进行l c 领域软件理解的环境。在i c s u t 中，软件理解工作是通过 查看理解环境所提供的一系列图示( v i e w ) 来进行的。这些图示从四个层次： 实现层、结构层、功能层和领域层来展现软件内部结构信息。 除了以上的研究机构和研究人员外，中国科学院计算技术研究所嗍、中国 科学院软件研究所 3 6 1 、西北大学【明【3 町、浙江大学i 蜘脚】 3 9 1 、吉林大学 4 0 l 、东南大 学【4 、西安电子科技大学【4 2 l 、北京航空航天大掣叫等研究机构或高校也有学者 在程序理解领域做了大量的研究。 1 5 研究内容和目标 由文献资料分析得出，基于关系模型的信息库系统，一般易于查询全局对象 信息，但不支持复杂数据类型，对于大型程序，随着信息量的增大，数据库响应 速度慢，影响系统性能；基于对象模型的数据库系统，用关系数据模型描述系统 概念模型，在存储与查询时涉及对象模式与关系模式之间的转换，概念模型设计 时依赖于程序语言；基于图形模型的数据库系统，当多类图形无公共结点时，难 以描述图形间的关系，而且不易于更新。此外，一些信息库系统依赖于特定的数 据库管理系统，概念模型设计依赖于程序语言，信息检索需