（计算机科学与技术专业论文）基于代码层次的软件资源信息挖掘系统的设计与实现.pdf

北京邮电大学硕士研究生毕业论文声明 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期：理! ! 厶 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅l 学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：剑么楚 导师签名： n 功剁 j 日期：丝一? ! 声 日期：趁2 1 ：鱼 _ ) - jj 北京邮电大学硕士研究生毕业论文 基于代码层次的软件资源信息挖掘 系统的设计与实现 摘要 本文在调研了大量国内外文献的基础上，研究了软件资源信息挖 掘的理论和方法，同时调研了软件逆向工程及软件切片的理论和技 术，并将这两项技术应用于软件资源信息挖掘系统的设计和实现当 中。 目前对于一些庞大的软件系统当中存在着大量的隐藏信息，而软 件系统在开发的过程中往往存在设计文档不完善，设计文档与代码不 同步，设计文档丢失，以及设计文档不精确或难以理解等问题，这就 造成了再次对该软件系统进行改进或者在该软件系统上进行实施时 由于对该软件系统一无所知导致无法入手。 鉴于以上问题，本文设计了基于代码层次的软件资源信息挖掘系 统，该系统通过分析基于j a v a 语言平台的客户软件系统的源代码， 提取出系统中类之间的依赖关系，并通过树及有向图这两种数据结构 表示系统中所有类的依赖关系，同时基于系统中类的依赖关系按照一 定的策略对客户软件系统进行模块划分，以使得客户软件系统在进一 步进行改进或者在第三方软件实施系统对其进行实施时可以按模块 独立进行，以尽量少的造成对其它无关模块的影响。同时考虑到系统 会在已有结构的基础上新增一些类，且在分析时不希望破坏原先的依 赖关系结构及模块结构，本系统专门设计了对于保持原结构不变的情 况下对新增类部分的分析，并将新增类部分的结构与系统中原有部分 相关联起来。 本文首先简要的对软件资源信息挖掘的理论做了描述，然后在理 论指导下参与了系统的需求分析，进行了分析系统模型及策略的概要 设计，设计系统包结构及类结构的详细设计，系统实现及系统测试， 并分析了系统设计与实现中遇到的关键问题及解决方案。 关键词：软件资源信息挖掘依赖关系树有向图模块划分 一 j v j了0 k 0 北京邮电大学硕士研究生毕业论文英文摘要 t h ed e s i g na n di m p l 巳m e n l = f 虹i o no f m i n i n gs o f i w a r er e p o s i t o r ys y s t e m b a s e do ns o u r c ec o d ei a y e r a b s t r a c t i nt h i sp a p e r , al a r g en u m b e ro fd o m e s t i ca n di n t e r n a t i o n a ll i t e r a t u r e sa r e r e s e a r c h e da n dt h et h e o r ya n dm e t h o do fm i n i n gs o f t w a r er e p o s i t o r y , a sw e l la s s o f t w a r er e v e r s ee n g i n e e r i n ga n ds o f t w a r es l i c i n g ，a l es t u d i e d a tt h es a m et i m e ，t h e t e c h n o l o g i e so fs o f t w a r er e v e r s ee n g i n e e r i n ga n ds o f t w a r es l i c i n ga r ea p p l i e do nt h e d e s i g na n di m p l e m e n t a t i o no fm i n i n gs o f t w a r er e p o s i t o r ys y s t e m a tp r e s e n t , t h e r ei sl o t so fh i d d e ni n f o r m a t i o ne x i s t i n gi nt h el a r g es o f t w a r e s y s t e m s h o w e v e r , t h e r e a r es o m ep r o b l e m ss u c ha si n c o m p l e t ed o c u m e n t s 。 u n s y n c h r o n i z e dd o c u m e n t sw i t hc o d e ，l o s i n gd o c u m e n t sa n da m b i g u o u sd o c u m e n t s e x i s t i n gi nt h ep r o c e s so fs y s t e md e s i g n t h e s ep r o b l e m sw i l li m p e d et h ef u r t h e r i m p r o v e m e n t so ri m p l e m e n t a t i o no ns o f t w a r es y s t e m i nv i e wo ft h ea b o v e ，i nt h i sp a p e r , t h em i n i n gs o f t w a r er e p o s i t o r ys y s t e mb a s e d o ns o u r c ec o d el a y e ri sd e s i g n e d a c c o r d i n ga n a l y z i n gt h es o u r c ec o d eo fc l i e n t s o f t w a r es y s t e mb a s e do nj a v a , t h es y s t e mc a ne x t r a c tt h es y s t e md e p e n d e n c i e s b e t w e e nc l a s s e s ，a n ds h o wt h e mw i t ht r e es t r u c t u r ea n dd i g r a p hs t r u c t u r e a tt h es a m e t i m e ，t h es y s t e mc a nd i v i d em o d u l e sf o rc l i e n ts o f t w a r es y s t e mb yc e r t a i ns t r a t e g y b a s e do nt h ed e p e n d e n c i e sb e t w e e nc l a s s e s ，s ot h a tt h ef u r t h e ri m p r o v e m e n t so r i m p l e m e n t a t i o no ns o f t w a r es y s t e mb yt h et h i r d p a r t ys o f t w a r es y s t e mc a nb ec a r r i e d o u ti n d e p e n d e n t l yb yt h em o d u l ei no r d e rt om i n i m i z et h er e s u l t i n gi m p a c to no t h e r u n r e l a t e dm o d u l e s t a k i n gi n t oa c c o u n tt h es y s t e mw i l la d ds o m ec l a s s e sb a s e do nt h e e x i s t i n gs t r u c t u r e ，a n di nt h ea n a l y s i st h eo r i g i n a ld e p e n d e n c i e ss t r u c t u r ea n dm o d u l e s t r u c t u r ea r en o tw a n t e dt ob ec h a n g e d ，t h i ss y s t e mi sd e s i g n e dt om a i n t a i nt h e o r i g i n a ls t r u c t u r er e m a i n su n c h a n g e da n da d dn e w c l a s s e sp a r t ，a sw e l la s s o c i a t ew i t h t h eo r i g i n a lp a r t st o g e t h e r i nt h i sp a p e r , b r i e fi n f o r m a t i o no fm i n i n gs o f t w a r er e p o s i t o r yt h e o r yi sd e s c r i b e d h 北京邮电大学硕：王= 研究生毕业论文 英文摘要 t h e ni nt h eg u i d a n c eo ft h e o r y , t h er e q u i r e m e n ta n a l y s i s ，s y s t e md e s i g ni n c l u d i n g s y s t e mm o d e la n ds t r a t e g y , d e t a i ld e s i g ni n c l u d i n gs y s t e mp a c k a g es t r u c t u r ea n dc l a s s s t r u c t u r e ，s y s t e mi m p l e m e n t a t i o na n ds y s t e mt e s ta r ef i n i s h e d a tt h es a m et i m e ，t h e k e yp r o b l e m sa n ds o l u t i o n si nt h ep r o c e s so fs y s t e md e s i g na n di m p l e m e n t a t i o na r e d e s c r i b e d k e y w o r d s ：m i n i n gs o f t w a r er e p o s i t o r y , d e p e n d e n c yr e l a t i o n ，t r e e ， d i g r a p h ，d i v i d i n gm o d u l e s i i i 、 一 j v j j | 北京邮电大学硕士研究生毕业 目录 第一章绪论1 1 1 引言1 1 2 研究现状1 1 3 本文工作1 1 3 1 研究路线和方法1 1 3 2 主要研究内容2 1 3 3 研究任务2 第二章软件资源信息挖掘理论及系统实现技术介绍3 2 1 软件资源信息库3 2 2 软件逆向工程4 2 3 软件切片6 2 4 系统实现关键技术介绍6 2 4 1 正则表达式6 2 4 2j a v a 与】( m l 的绑定7 2 5 描述文件结构介绍8 2 5 1 树8 2 5 2 有向图9 2 6 小结1 0 第三章软件资源信息挖掘系统需求分析1 l 3 1 任务概述1 l 3 1 1 实现目标1 l 3 1 2 系统设计意图1 l 3 1 3 假定和约束1 l 3 2 需求规定：1 2 3 2 1 系统功能的需求规定1 2 3 2 2 系统性能的需求规定1 7 3 3 运行环境规定1 8 3 3 1 设备支持1 8 3 3 2 软件系统支持1 8 i v 北京邮电大学硕士研究生毕业论文目录 3 4 小结1 9 第四章软件资源信息挖掘系统设计2 0 4 1 系统概要设计2 0 4 1 1 系统功能设计2 0 4 1 2 系统类依赖关系生成解决方案2 l 4 1 3 系统模块划分策略2 3 4 1 4 接口设计2 5 4 2 系统详细设计3 0 4 2 1 系统包结构设计3 0 4 2 2 系统类结构设计3 l 4 3 小结3 8 第五章系统实现及系统测试4 0 5 1 系统实现的关键问题及解决方案4 0 5 1 1 依赖关系提取算法4 0 5 1 2 系统信息存储方案选取问题4 0 5 1 3 依赖关系生成过程中关键字的匹配问题4 l 5 1 4 模块划分后模块间依赖关系的生成问题4 l 5 1 5 新增类部分的依赖关系生成问题4 2 5 2 系统测试4 3 5 2 1 测试用例描述4 3 5 2 2c l a s s e s x m l 文件测试4 4 5 2 3s t r u c t x m l 文件测试4 5 5 2 4c l a s s r e l a t i o n s x m l 文件测试4 6 5 2 5r e l a t i o n s x m l 文件测试4 7 5 2 6m o d u l e r e l a t i o n s x m l 文件测试4 8 5 2 7a d d r e l a t i o n s x m l 文件测试4 9 5 2 8a d d m o d u l e r e l a t i o n s x m l 文件澳4 试4 9 5 5 小结5 0 第六章结束语5 l 6 1 工作总结5 l 6 2 下一步的工作展望5 l 参考文献5 3 v 北京邮电大学硕士研究生毕业论文目录 致谢5 5 攻读学位期间发表的学术论文目录5 6 v i - 、 一、z 、 北京邮电大学研究生毕业论文 1 1 引言 第一章绪论 在一个信息化社会不断发展的时代，许多第三方软件实施系统在运行的过程 中需要获取客户软件系统本身的一些信息i l l ，如软件系统的动态更新的实施过 程，所以软件资源本身的信息就变的极为重要，而对于一个规模较大的软件系统， 在开发阶段往往存在设计文档不够详细，设计文档与代码不同步，以及对文档不 够重视而导致文档丢失等现象，即使分析其源代码，重构其设计结构也由于代码 量巨大而导致相当大的工作量，目前的一些u m lt 具，虽然能根据代码逆向生 成u m l 类图，但结果不太精确，无法精确获取各个类之间的依赖关系【2 j ，这些 现象都直接导致了软件系统资源信息不足而阻碍了第三方软件实施系统的实施 过程。因此，设计一个可以挖掘现有软件资源信息的工具用于在第三方软件运行 实施的过程中产生其所需要的软件资源信息是十分必要的。 1 2 研究现状 目前，很多庞大的软件系统中存在一些潜在的、没有文本记录的依赖关系， 这些关系正是一个庞大的软件系统最复杂的部分，也是维护系统耗费成本最高的 一个问题。鉴于此，很多学者致力于软件关联修改的数据挖掘方法研究，而且这 种关联修改的研究已涉及到软件代码的不同层次，包括模块级、文件级、类的级 别、方法的级别甚至代码行级别【3 】。 目前，这些关联研究的应用主要有：提供系统关联修改建议，给出最直接、 最重要的相关修改的推荐；避免不完全的修改，给出所有可能需要修改的建议， 包括不同格式的其他文件，如h t m l 文件的相应修改；帮助新的开发人员迅速 了解软件系统，为软件项目的修改和改进方案提供建议等【4 l 。 1 3 本文工作 t 3 1 研究路线和方法 本文所设计实现的基于代码层次的软件资源信息挖掘系统以在源代码级别 上分析客户软件资源信息为需求导向，结合传统的m i n i n gr c s o u r c cr e p o s i t o r y 北京邮电大学研究生毕业论文 理论，逆向工程理论及软件切片理论作为理论研究依据，结合j a v a 语言的特征 及相关技术对已存在的基于j a 、，a 语言的客户软件系统进行系统资源信息的提取 并根据其源代码逆向重构客户软件系统中类之间的依赖关系并以某种算法策略 对其进行整个系统结构的模块划分。 1 3 2 主要研究内容 本文的主要研究内容为目前在m i n i n gr e s o u r c er e p o s i t o r y ，逆向工程及软件 切片等领域的理论研究及应用以及它们在实际应用中的相互结合及扩展 5 1 ，并在 此理论研究的基础上结合软件资源信息挖掘系统的实际需求设计相关的系统模 型，组织结构，算法策略等。 1 3 3 研究任务 本文的主要研究任务在于引入软件资源信息挖掘的思想，并在源代码层次上 设计实现出基于j a v a 平台软件资源信息挖掘系统，将软件资源信息挖掘理论实 践化。该系统的主要功能是挖掘基于j a v a 平台的客户软件系统中类之间依赖关 系，并在系统中类依赖关系的基础上对系统进行模块划分，同时以某种固定的数 据结构生成描述类之间依赖关系，模块中类的信息及依赖关系以及模块之间依赖 关系的接口文件，以供第三方软件实施系统解析使用。 本系统经历了软件资源信息挖掘，逆向工程及软件切片等相关技术的调研过 程，本文作者作为项目组成员参与了项目组的需求分析和系统设计，在项目组中 以软件业务动态更新系统作为第三方软件实施系统，结合软件业务动态更新系统 的实际需求与导向对本系统做出了详细的需求分析和系统接口设计，并独立完成 了系统的实现及测试过程。 2 北京邮电大学研究生毕业论文 第二章软件资源信息挖掘理论及系统实现技术介绍 2 1 软件资源信息库 目前，很多大的软件开发组织、软件项目均建立了集合软件开发过程所有数 据的软件资源信息库，但大部分软件资源信息库仅用于软件项目的维护以及缺陷 状态的跟踪等 6 1 。2 0 世纪9 0 年代以来，许多软件从业者和研究人员逐渐意识到，软 件资源信息库中包含许多丰富的、隐藏的信息，于是开始采用数据挖掘的方法理 解这些潜在的信息。近年来，这方面的研究得到了更多关注。从2 0 0 4 年的第2 6 届 i e e e 软件工程国际会议( i e e ei n t e r n a t i o n a lc o n f e r e n c eo ns o f t w a r ee n g i n e e r i n g ， i c s e ) 开始，每届均有一个软件资源信息库挖掘的会议 7 1 。在这些会议上讨论了采 用数据挖掘方法深入理解软件资源信息库的多个方面，如软件过程建模、软件开 发进化和模式的理解、软件缺陷的分析、软件系统关联修改、软件模块复用等。 软件资源信息库是软件开发过程中所有相关数据的总和，通常包括以下数据 【8 l l 项目开发过程数据，包括项目开发的里程碑、任务细化、资源等信息。 源代码数据，如项目开发的源代码以及版本修改过程。 项目开发的相关文档，如需求文档、设计文档、测试相关文档等。 项目开发人员的交流历史信息，如e 2 m a i l 存档、论坛交流历史记录等。 缺陷跟踪信息，包括项目开发过程中缺陷状态、类型、修改历史等。 软件资源信息库的挖掘也是从属于数据挖掘理论的一种形态。数据挖掘又称 为数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 。它是一个从大 量数据中抽取挖掘出从前未知、但有很多潜在信息( 如知识规则、约束、规律) 的复杂过程。数据挖掘的过程一般分为四个步骤，分别是数据抽取、数据预处理、 知识发现以及知识表示 9 1 。 进行数据抽取首先需要明确研究目标，有针对性地获得所需要的数据源。例 如，进行源代码的关联修改通常需要得到软件配置管理系统中的代码以及版本修 改历史，若要根据代码从前的缺陷信息预测以后的缺陷密度，还需要进一步得到 缺陷报告数据【l o l 。 数据预处理是软件挖掘工作中非常重要的一部分，数据的预处理质量将直接 影响到研究成果。针对不同的研究目的，要采用不同的预处理策略。对于不可模 拟的、人为因素较高的软件开发信息库来讲，数据清理需要更多的时间和精力【1 1 1 。 数据转换是将数据转换为方便进行研究的形式。它包括1 1 2 l ： 3 北京邮电大学研究生毕业论文 a ) 配置管理系统的数据转换。例如，由于c v s 系统中不包括事务信息，很 多学者需要聚合文件修改记录，提取事务信息。软件配置管理系统记录的修改信 息是文件级别的，为了具体研究源代码修改的关联影响，很多研究者将修改信息 细化，得到方法、类、属性以及它们之间的层次关系。 b ) 缺陷数据的数据转换工作。包括缺陷数据的聚集( 将缺陷数据按照所属 模块、提交的月份、解决缺陷持续的时间、缺陷的级别或缺陷的类别聚集) 。 c ) 项目过程数据中的数据转换。包括新属性值的构造( 构造每个开发阶段所 持续的时间等) 、数据聚集( 按照开发阶段、月份、任务类型等将完成任务的月 数聚集、 等。 如今，在软件开发信息库数据的获取和预处理方面的研究很多，大部分研究 人员需要自己完成复杂的数据预处理过程，尽管出现了一些抽取软件开发信息库 数据的工具，但使用这些工具还要对软件开发信息库的结构、内容有一定的了解， 也需要很多精力，而且即使利用这些工具仍需面对研究上的困难和不确定风险， 即软件开发信息库中的数据可能不完全或某些软件开发数据不连续。 本文将软件资源信息挖掘应用于基于j a v a 平台的软件系统中主要是基于面 向软件源代码数据部分的信息挖掘，并将软件逆向工程技术及粗粒度的软件切片 技术作为软件资源信息挖掘的实现手段，通过挖掘客户软件系统自身源代码的信 息获取客户软件系统中类之间的依赖关系并进行在此基础上的模块划分，进而了 解到客户软件系统的整体架构信息。 2 2 软件逆向工程 软件逆向工程( s o f t w a r er e v e r s ee n g i n e e r i n g ) 又称软件反向工程，是指从可 运行的程序系统出发，运用解密、反汇编、系统分析、程序理解等多种计算机技 术，对软件的结构、流程、算法、代码等进行逆向拆解和分析，推导出软件产品 的源代码、设计原理、结构、算法、处理过程、运行方法及相关文档等【1 3 j 。通常， 人们把对软件进行反向分析的整个过程统称为软件逆向工程，把在这个过程中所 采用的技术都统称为软件逆向工程技术。现实中，人们并不总是完全需要逆向出 目标软件的所有功能，如果那样的话将会是一个艰苦而漫长的过程，大多数情况 下是有目的性的通过对软件进行逆向，从中获取软件的算法，结构及进行功能扩 展等【1 4 i 。 软件逆向工程在执行过程上可以定义为一个分析目标软件系统的过程，它主 要包括两个部分：一是分辨它的组件并分析组件之间的依赖关系；二是建立系统 的另外的或在更高抽象级别上的表达形式【1 卯。上述逆向工程定义的两部分本质上 4 北京邮电大学研究生毕业论文 是一个知识恢复、知识发现的过程。对于软件这种无形的人工产物来说，逆向工 程的主要目的首先是重现考察对象所体现的原有设计知识，其次是能发现一些在 设计中没有明显表示出的、存在于设计人员头脑中的设计知识。本系统主要运用 面向对象的软件逆向工程的第一部分理论基础，即通过分析目标软件系统及源代 码反向构造出系统中类的依赖关系。 面向对象软件中所蕴涵的设计知识和传统程序是不同的，这些不同反映在对 系统组件的确定、组件之间的关系、系统结构的定义、子系统的划分等上面，也 反映在对于设计知识和内容的表达形式上【1 6 1 。 依据对0 0 系统中设计知识的分析，可以按照知识抽象层次由低到高来定义 0 0 软件逆向工程的内容：一是o o 语言本身的语义知识获得，一般用语法分析 器来得到；二是0 0 设计知识的获得，它包括了较广的范围，如对象间关系的抽 取，子系统的分割，方法的大小划分和实现，意外情况的处理，设计模式、域模 型向计算机模型的映射等；最高层是应用域知识的重现，可由系统的框架抽象、 域模型的抽取、文档分析方法等得到。 逆向工程的基本目的是帮助软件理解，而软件理解是软件中存在模式和人脑 中存在模式的匹配。对当前面向对象软件逆向工程方法的研究，按照它们抽取的 设计知识的抽象层次，即生成结果的可理解程度将0 0 软件的逆向工程研究分为 如下4 个层次1 1 7 l ： 幻对象间的实际关系抽取：对象间的实际关系指的是已有定义的，如继承、 聚集、访问等基本的静态对象关系和一些对象之间的协作等动态关系，它们是在 设计中明确定义的简单关系内容。 ”设计模式的识别：每一个设计模式都集中于一个特定的面向对象设计问 题或设计要点，表达的是面向对象系统的局部结构。 00 0 程序的度量：0 0 程序的度量表达了0 0 程序在整体上或局部从统计 的观点来看的一些性质，可以看做是将系统作为整体来考察时的内部关系，它能 揭示在设计时未知、也没有表达出来的内容。 d ) 系统结构和域模型的抽象：域结构表达的是应用域中的固有关系，它是 通过系统分析得到的域的抽象结果。虽然在代码中间蕴涵了此部分内容，但是由 于程序语义和应用域内语义的区别，使得对此部分内容的逆向工程要采用更多的 输入源，如软件文档、域对象和软件对象的映射关系等。 对象间的实际关系抽取是最基本的0 0 软件逆向活动，它是高层抽象的基础。 由于在0 0 程序中考察的对象可有文件、类或对象、方法、成员、语句，这些考 察的对象相同类别之间有复杂的关系，不同类别之间也存在着复杂的关系，对这 些关系的辨别、提取一直是研究的重点。 5 北京邮电大学研究生毕业论文 2 3 软件切片 本系统研究中所引用的软件切片技术是一种新形式的切片技术，即一种基于 软件体系结构的粗粒度的软件切片，它衍生于却有不同于传统的程序切片技术 【1 8 】。 传统的程序切片技术是根据控制流分析和数据流分析而引入的一种系统理 解方法，可以针对一个切片标准，提取出程序中影响关注点变量值的所有语句， 通过计算源程序中每个关注点的切片来达到对整个程序的分析和理解【聊。程序中 某个关注点的切片不仅与在该点定义和使用的变量有关，而且与影响该变量的值 的语句和谓词以及受该变量的值影响的语句和谓词有关。程序切片的概念最早由 m a r k w e i s e r 提出1 2 0 l ，经过多年的发展，在理论方面同趋完善，在软件维护、程 序调试、程序测试以及逆向工程等领域有了广泛的应用。目前的程序切片大都是 以系统依赖图为基础，是一种细粒度的切片技术。 相比较于传统的细粒度的程序切片技术，本系统研究中所使用的软件切片技 术主要是针对于软件系统的体系结构上的切片1 2 ，是一个建立在高级层次上对软 件系统结构的粗粒度的切片，主要作为软件资源信息提取的一种方式运用于软件 系统的维护和实施中，为客户软件系统以系统依赖图为基础进行模块划分。 2 4 系统实现关键技术介绍 2 4 t 正则表达式 正则表达式( r e g u l a re x p r e s s i o n ) 在计算机科学中，是指一个用来描述或者 匹配一系列符合某个句法规则的字符串的单个字符串。在很多文本编辑器或其他 工具里，正则表达式通常被用来检索和替换那些符合某个模式的文本内容。许多 程序设计语言都支持利用正则表达式进行字符串操作 2 2 1 。 一个j 下则表达式通常被称为一个模式( p a t t e r n ) 刚，就是用某种模式去匹配一 类字符串的一个公式，由普通字符( 例如字符a 到z ) 以及特殊字符( 称为元 字符) 组成，用来描述或者匹配一系列符合某个句法规则的字符串。简单的说， 正则表达式就是用一个“字符串一来描述一个特征，然后去验证另一个“字符串” 是否符合这个特征。比如表达式“a b + ”描述的特征是“一个a 和任意个f ”，那么 a b ，a b b ， a b b b b b b b b b 5 都符合这个特征。 正则表达式可以用来：( 1 ) 验证字符串是否符合指定特征，比如验证是否是 合法的邮件地址。( 2 ) 用来查找字符串，从一个长的文本中查找符合指定特征的 字符串，比查找固定字符串更加灵活方便。( 3 ) 用来替换，比普通的替换更强大。 6 北京邮电大学研究生毕业论文 j a v a 对正则表达式提供了强大的支持跚，本系统正是借助于j a v a 中对正 则表达式的强力支持来实现在j 怂，a 源文件中对类之间依赖关系的扫描。 在j a v a 中使用正则表达式匹配字符串的典型调用语句是 p a t t e r n p = p a t t e r n c o m p i l e ( ”a 幸b ”) ； m a t c h e r m = p m a t c h e r ( ”a a a a a b ”) ： b o o l e a n b = m m a t c h e s o ： j a v a u t i l r e g e x p a t t e r n 是正则表达式的编译表示形式，指定为字符串的正则表 达式必须首先被编译为此类的实例。然后，可将得到的模式用于创建 j a v a u t i l r e g e x m a t c h e r 对象，依照正则表达式，该对象可以与任意字符序列匹配。 执行匹配所涉及的所有状态都驻留在匹配器中，所以多个匹配器可以共享同一模 式。最后可通过m a t c h e r m a t c h e s 0 方法验证字符序列与所编译的正则表达式是否 相匹配。 在j a v a 中使用正则表达式查找字符串的典型调用语句是 b o o l e a nb = p a t t e r n c o m p i l e ( r e g e x ) m a t c h e r ( s t r ) f i n d 0 其中r e g e x 是需要编译的正则表达式，s t f 为需要进行查找的文本或字符串， 通过m a t c h e r m a t c h e s 0 方法可以查找文本或字符串s t r 中是否存在符合正则表达 式规则r e g e x 的字符串1 2 5 1 。 2 4 2j a v a 与x 盹的绑定 x m l 即e x t e n s i b l em a r k u pl a n g u a g e ( 可扩展标记语言) 的缩写1 2 6 1 ，是一个用 来定义其他语言的元语言，它简单易懂，是一门既无标签集也无语法的标记语言， 所以它是完全可以扩展的 2 7 1 。x m l 自身定义了语言的核心，并且还提供了一种元 数据类型框架。就x m l 自身而言，它的价值是有限的，它只定义了那个框架。但 是所有基于x m l 的技术为开发者们在数据处理及传输方面提供了空前的便利固1 。 x m l 从一开始就和j a v a 捆绑在一起【2 9 i ，x m l 文档被表示为由业务驱动的 j a v a 类，并且数据从文档被映射为这些j a v a 类的成员变量，这种数据映射一 般被称为数据绑定。数据绑定的基本思想就是获取x m l 文档，并将其转换为j a v a 对象的实例例。 j a v a 为x m l 提供了一套最完整的a p i 集合【3 1 1 ，使得x m l 可直接在j a v a 代 码中使用。主要包括s a x ，d o m ，j a x p ，以及本系统中所采用的d o m 4 j 。 s a x 是x m l 简单a p i ( s i m p l e a p if o rx m l ) 的缩写【3 。它提供了一个用来 解析x m l 数据的基于事件的框架，它是扫描整个文档，并将数据拆解成几个有用 部分的一种处理情况。在该过程的每一步中，s a x 都定义了可能发生的事件。 d o m 是文档对象模型( d o c u m e n to b j e c tm o d e l ) a p i t 3 1 1 。相比之下，s a x 7 2 5 描述文件结构介绍 2 5 1 树 树是一种数据结构，它是由n ( n = 1 ) 个有限结点组成一个具有层次关系的 集合。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树 的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地 位，这个结点称为该树的根结点。 形式地给出树的递归定义如下1 3 3 1 ： 单个结点是一棵树，树根就是该结点本身。 设t 1 ，t 2 ，1 1 【是树，它们的根结点分别为n l ，n 2 ，n k 。用一个新结点n 作为n 1 ，n 2 ，l l l 【的父亲，则得到一棵新树，结点覆就是新树的根。我们 称n 1 ，n 2 ，n k 为一组兄弟结点，它们都是结点1 1 的儿子结点。我们还称 n 1 ，n 2 ，i l l 【为结点n 的子树。 8 北京邮电大学研究生毕业论文 空集合也是树，称为空树。空树中没有结点。 树具有以下几个特点： 每个结点有零个或多个子结点； 每一个子结点只有一个父结点； 没有前驱的结点为根结点； 除了根结点外，每个子结点可以分为m 个不相交的子树； 一颗典型的树如图2 1 所示： 图2 - 1 树的层次结构 树中的一些相关性质如下- 一个结点的儿子结点的个数称为该结点的度。一棵树的度是指该树中结 点的最大度数。 树中度为零的结点称为叶结点或终端结点。 树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结 点统称为内部结点。 如果存在树中的一个结点序列k l ，k 2 ，蝎，使得结点嵇是结点k i + l 的 父结点( 1 = i _ j ) ，则称该结点序列是树中从结点k 1 到结点蜀的一条路径。 如果在树中存在一条从结点k 到结点m 的路径，则称结点k 是结点m 的祖先，也称结点m 是结点k 的子孙或后裔。 树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长 路径的长度。树的高度是指根结点的高度。 2 5 2 有向图 直观来说，若图中的每条边都是有方向的，则称为有向图。有向图中的边是 由两个顶点组成的有序对，有序对通常用尖括号表示，如 表示一条有向边， 其中i l l i l 是边的始点，n 嘲是边的终点。 和 代表两条不同的有向 9 2 6 小结 本章主要对软件资源信息挖掘及软件逆向工程，软件切片技术做了相关理论 和技术的调研，同时将软件资源信息挖掘技术在实现手段上进行了扩展，在细粒 度的程序切片的基础上引入粗粒度的软件切片技术，并将软件的逆向工程及软件 切片作为软件资源信息挖掘技术的实现手段应用于软件资源信息挖掘中。同时， 本章对本基于代码层次的软件资源信息挖掘系统在设计实现中所需要用到的关 键技术及描述文件数据结构做了相关的描述，为系统的设计实现提供了理论依 据。 1 0 北京邮电大学研究生毕业论文 第三章软件资源信息挖掘系统需求分析 3 1 任务概述 3 1 i 实现目标 该软件资源信息挖掘系统的设计是基于代码层面的，其实现目标是通过对基 于j a v a 语言平台的客户软件系统源代码所在目录进行监控，提取出所有类自身 的信息及类之间的依赖关系，并在系统类依赖关系确定的基础上对系统以依赖关 系为基础进行模块划分，同时获取模块之间的依赖关系，使得基于j a v a 语言平 台的客户软件系统在第三方软件实施系统进行实施的过程中各个模块之间独立 进行，以尽量减少对无关模块的影响而降低客户软件系统运行的效率，同时考虑 到在对已有客户软件系统新增源代码文件后仍希望在已有的依赖关系及模块的 基础上增加新类的依赖关系及模块划分，本系统设计了在不破坏原系统依赖关系 结构及模块划分结构的基础上对新增类之间的依赖关系及新增类对系统已存在 的类之间的依赖关系进行独立分析，并对新增类进行单独地模块划分。 3 1 2 系统设计意图 该基于代码层次的软件资源信息挖掘系统属于处于基于j a v a 语言平台的客 户软件系统与对客户软件系统进行运行时实施的第三方软件实施系统( 如软件业 务动态更新系统) 的中间层系统，其主要设计意图为在第三方软件实施系统对客 户软件系统信息一无所知的情况下，通过本软件资源信息挖掘系统以客户软件系 统源代码所在的目录作为输入，在对客户软件系统源代码进行自动分析后，输出 客户软件系统中所有类之间的依赖关系结构及模块划分结构，并以有向图结构或 树结构等数据结构表示，以x m l 作为描述文件类型接口提供给第三方软件实施系 统，以此形式实现了第三方软件实施系统与客户软件系统之间的交互。 3 1 3 假定和约束 为了保证软件资源信息挖掘的准确性及提倡客户软件系统良好的架构设计， 本系统对于客户软件系统的约束如下： 1 客户软件系统中每个j a v a 文件中只编写一个类； 2 客户软件系统中不能出现类之间的循环调用以免在类之间的依赖关系分 北京邮电大学研究生毕业论文 析中出现死循环的问题，如a 调用b ，b 调用c ，c 调用a 。 3 客户软件系统中新增的类源文件须放在同一个目录下，但不必是同一个 包下。 3 2 需求规定 3 2 系统功能的需求规定 该基于代码层次的软件资源信息挖掘系统的主要功能是对已存在的基于 j a v a 语言平台的客户软件系统进行源代码层面的资源信息挖掘提取以产生相应 的软件资源信息，主要包括客户软件系统中所有类本身的信息及类之间的依赖关 系信息，并在系统中类之间依赖关系的基础上以固定的算法策略对客户软件系统 进行模块划分，同时产生模块之间的依赖关系。该系统产生的所有信息以x m l 文件的形式输出，作为与第三方软件实施系统的接口供其在实施过程中使用。 系统产生的信息需求 本系统通过对基于j a v a 语言平台的客户软件系统进行软件资源信息挖掘产 生所需要的软件资源信息，主要软件资源信息包括以下几个方面： 1 ) 客户软件系统中类本身的信息，包括系统中所有类的类名，类的完全限 定名，类所在的j a v a 文件路径。 2 ) 系统中类的整体依赖关系信息，包括类的整体依赖关系的有向图结构和 树状结构，其中两种结构均使用描述清晰、语法结构简单、易被多种语言解 析的可扩展标记语言x m l 进行描述。 系统整体依赖关系有向图结构的描述应包含以下信息： 系统中所有类的类名及完全限定名，每个类作为一个类节点 系统中每个类所依赖的类的完全限定名，即每个类节点下包含其所 依赖的类的引用节点 该结构描述应该能通过每个类所依赖的类的引用节点指向该引用节 点对应的实体类节点 系统整体依赖关系树结构的描述应包含以下信息： 系统中所有类的类名及完全限定名，每个类作为一个类节点 系统中每个类所依赖的类的完全限定名，即每个类节点下包含其所 依赖的类的引用节点 每个类节点下的引用节点还有其所包含的引用节点，以此伸展嵌套， 直到最后的叶子节点 3 ) 客户软件系统基于系统内部所有类之间的依赖关系进行模块划分后的模 1 2 北京邮电大学研究生毕业论文 块信息以及模块内部类之间的依赖关系。具体模块划分要求如下： 模块划分必须均匀，即使得模块的数量及模块的粒度必须适中，划 分模块后不能模块粒度过大而模块数量太少，也不能模块粒度太小 而