（计算机软件与理论专业论文）概念分析方法在软件再工程中的应用.pdf

山东大学硕士学位论文 摘要 随着软件产业的发展，我们面临的遗产软件不仅在数量上日益增多，而 且在比例上也逐渐上升，能否很好地利用这笔财富，将在很大程度上影响软 件业的生产率。因此，近几年来，遗产软件再工程已经发展为软件工程方法 学的一个重要的研究领域。 实践表明，软件再工程的过程中，程序理解是第步，也是最关键的一 步，目前，随着各种c a s e 工具的出现，程序理解方法也逐渐进入实用的阶 段。 本文在格理论的基础上提出了概念分析方法，该方法以反映一定逻辑关 系的项目表作为切入点，抽取出成员和变量之间共有的信息，应用概念格生 成算法得到概念格。与簇分析方法相比较，概念分析方法并不给出一个确定 的方案，而是通过格来反映变量和类成员之间所有可能的关系。最终得到的 概念格不仅具有最小性、最大分解性以及其他一些重要的语法特性，而且可 以帮助理解程序，通过应用程序对类层次结构的使用可以发现类层次结构的 设计问题，比如存在没有使用的冗余类成员，或者类分割问题等，从而为再 工程的类库重设计提供一些参考。 在该理论的基础上，本文讨论了概念格分析工具c l a t 的实现，工具包 括四个部分：信息抽取、信息管理、信息显示以及类库重设计部分。目前已 经基本完成了信息抽取部分的代码编写工作，对一个v i s u a lc + + 工程，能分 析工程中包含的文件、各文件之间的引用关系、系统中的类信息、以及各个 类成员之间的使用关系等。从结构体系的角度看，该系统不仅具有一定的语 言透明性，可以适用于不同的面向对象语言，而且证明了概念分析方法在遗 产软件再工程中的可行性和实用价值。 关键词：面向对象、遗产软件、再工程、程序理解、概念格。 山东大学硕一l 学位论文 a b s t r a c t a l o n gw i t ht h ed e v e l o p m e n to fs o f t w a r ei n d u s t r y ，n o to n l yt h eq u a n t i t y ，b u t a l s ot h ep e r c e n t a g eo f l e g a c ys o f t w a r ei si n c r e a s i n g h o w t ou s et h et r e a s u r ew i l l a f f e c tt h ep r o d u c t i v i t yo fs o f t w a r ei n d u s t r y t h e r e f o r e ，i nr e c e n ty e a r s ，s o f t w a r e r e e n g i n e e r i n g h a sb e e na l li m p o r t a n td o m a i no fs o f t w a r ee n g i n e e r i n g i np r a c t i c e ，p r o g r a mu n d e r s t a n d i n gi st h ef i r s t ，a n dt h em o s ti m p o r t a n ts t e po f s o f t w a r er e e n g i n e e r i n g a n dn o w , a l o n gw i t l lm o r ea n dm o r ec a s et o o l s s o m e p r o g r a mu n d e r s t a n d i n gt e c h n o l o g i e s h a v eb e c o m e p r a c t i c a b l es t e pb ys t e p i nt h i sa r t i c l e ，b a s eo nl a t t i c et h e o r y , w ep u tf o r w a r dam e t h o do fc o n c e p t l a t t i c e t h ea p p r o a c hb e g i n sw i t hal o g i c a lt a b l e ，t h e na b s t r a c tt h ec o m m o n i n f o r m a t i o no fm e m b e r sa n dv a r i a b l e s ，a n df i n a l l yg e n e r a t eac o n c e ：p tl a t t i c e c o m p a r ew i t h c l u s t e r a r i t h m e t i c ，i tp r o v i d e al a t t i c et h a ts h o wa l l p o s s i b l e r e l a t i o n s h i po fm e m b e r a n dv a r i a b l e s ，r a t h e rt h a nas i n g l ep a r t i t i o n i n gr e s u l tt h e l a t t i c ei sm i n i m a la n dm a x i m a l l yf a c t o r i z e d ，i tc a nh e l pu su n d e r s t a n dp r o g r a m b ya n a l y z i n gt h eu s a g eo f t h eh i e r a r c h y w i t has e to f a p p l i c a t i o n s ，t h et e c h n i q u ei s c a p a b l eo ff i n d i n gd e s i g n a n o m a l i e si nt h eo r i g i nc l a s sh i e r a r c h i e s ，s u c ha s r e d u n d a n tm e m b e ro rs p l i t t i n gac l a s si n t om u l t i p l ec l a s s e s ，w h i c hc a r lh e l pu si n r e s t r u c t u r i n gc l a s sh i e r a r c h i e s w eh a v ea l s od i s c u s s e dt h ei m p l e m e n to fc o n c e p tl a t t i c ea n a l y z et o o l ( c l a t ) ，w h i c hc o n t a i nf o u r m a i np a r t s ：i n f o r m a t i o n a b s t r a c t i n g ，i n f o r m a t i o n m a n a g e m e n t ，i n f o r m a t i o ns h o w i n ga n dr e d e s i g nc l a s sh i e r a r c h y s of a r ，w eh a v e f i n i s h e dr i t ep a r to fi n f o r m a t i o na b s t r a c t i n g ，a n df o rap r o j e c to fv i s u a lc + + ，i tc a n a n a l y z ef i l e st h a tt h ep r o j e c tc o n t a i n s ，t h ei n c l u d er e l a t i o n s h i po ff i l e s ，t h ec l a s s i n f o r m a t i o ni nt h ep r o j e c ta n dt h ei l s er e l a t i o n s h i po ft h em e m b e r so fc l a s s e s 。 f r o mt h ep o i n to f v i e wo f t h ef r a m e w o r k ，t h e r ei ss o m el a n g u a g ei n d e p e n d e n c yi n c l a t , a n di tc a n n o to n l ya d a p tt od i f f e r e n t0 0 l a n g u a g e ，b u ta l s ot e l lu st h a tt h e f e a s i b i l i t ya n dv a l u eo f m e t h o do f c o n c e p t l a t t i c e k e y w o r d s ：o b j e c t o r i e n t ，l e g a c ys o f t w a r e ，s o f t w a r er e e n g i n e e r i n g ，p r o g r a m u n d e r s t a n d i n g ，c o n c e p tl a t t i c e l i i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：! 釜壹熊日期：递生墨：! 兰 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权i 山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：它筮! 塞超导师签名：灶日期：巡。二 山东大学硕士学位论文 第一章绪论 大多数程序员或许都有这么一个体会：写完的程序泼出去的水，切莫回 头再看。这其中当然也有软件工程管理中相关文档不配套等管理性的原因， 不过，即使一个软件系统的文档很完备，理解一个遗产软件( 已经进入维护 期的软件系统) ，尤其是其他程序员编写的遗产软件，还是一件比较困难的事 情。但是现实中的程序员们却经常不得不面对这样的过程，最典型的例子就 是几年前的世界性的“y 2 k 除虫运动”，人们不得不把那些“泼出去的水” 重新收回来，从洪水般的源代码“陈年谷子”中寻找那些芝麻般的“时间变 量”。 另一方面，与3 0 多年来一直遵循摩尔定律发展的计算机硬件相比较，计 算机软件的发展好像“总不在状态”，软件生产始终只能以螺旋形或波动形的 轨迹发展，虽然面向对象方法的提出使软件开发的效率、软件工程的质量以 及软件的重用上有了一个质的飞跃，但是，软件工程方法学理论的进步同时， 我们也应看到如下现象 1 】： 1 新开发软件系统与现存软件维护比例逆转，维护性开发所占的比例 越来越大( 如图1 1 ) ，有资料显示，2 0 世纪9 0 年代以后，先进国家 的现存软件维护性开发已占软件开发总量的8 0 以上。 图1 1 既存软件比例增长情况 目前 间 2 经过一定修补的遗产软件仍运行于世界各地，尤其是使用计算机较 早的一些重要应用领域，例如银行、证券、物流乃至政府、军队等。 3 遗产软件的环境适应性维护周期越来越短，范围也越来越大。半个 山东大学硕士学位论文 世纪以来，大部分软件系统并不能像硬件那样频繁地彻底更新换代， 为了适应硬件的换代，处于维护期的软件系统必须进行一些环境适 应性方面的维护。 2 0 多年前曾有人预言：2 1 世纪的软件业是再工程的软件业，将有很高比 例的软件人员从事维护性开发。从软件价值随生存期变化的规律来看，这并 不违背市场经济的价值规律( 图1 ，2 ) 。 1 。1 什么是再工程? 图1 2 软硬件价值比随系统生存期改变 芦黑挈f 鐾 l再工程 图1 3 给出了一个软件生存期示意图，再工程处于软件生存期的维护期， 是对一次工程后的成品软件进行再次开发，软件维护期的适应性、完善性、 预防性维护都属于再工程范畴。再工程面对的不是原始需求，而是现存软件， 是从现存软件开发出新软件的过程，为了与软件从无到有的第一次开发相区 别，引入如下概念： 正向工程( f o r w a r de n g i n e e r i n g ) ：由抽象的、不依存代码的设计逐步展 开，直至具体代码实现的开发活动，即从需求规格设计到产品初次发布的过 程或子过程。 逆向工程( r e v e r s ee n g i n e e r i n g ) ：分析现存系统识别系统构件及其相 山东大学硕士学位论文 互关系，并生成相应表示的过程。主要分为再文档和设计恢复两种形式。 再工程( r e e n g i n e e r i n g ) ：对现存软件系统进行调查，并将其重构为新系 统的开发过程。逆向过程从源代码出发，旨在取得高一级抽象成果，再工程 则根据对目标系统更深层次的理解将其重构为一个新系统，即：再工程= 逆 向工程+ 正向工程。 1 2 软件再工程的类型 再工程的作用期远大于第一次软件工程期，一般最小也应考虑在5 至1 0 倍以上。例如初次( 一次) 开发工程周期在2 个月一1 年的话，那使用周期 至少应在1 1 0 年。这也是由软件价值高昂、投资回收需要相当周期的一般 市场规则决定的。 正向工程方法学的研究已取得了许多重大进展，在其指导下开发的现存 软件资源越来越多，覆盖面也越来越广，因此软件再工程具有很大的潜在需 求，但是就目前而言，只能说是进入了再工程时代，因为相关的方法学还不 成熟，技术人员也严重匮乏，这使得软件再工程成了新的软件工程瓶颈，且 此危机有愈演愈烈之势。 目前的再工程主要为三类： 1 适应性维护的再工程： 夺伴随硬件和操作系统更新换代或者业务环境变化引起的软件维护。 如由于企业业务的发展和系统使用年限的增加，现存系统的存储媒 体和数据管理系统满足不了数据量及其种类剧增的要求，需要更新 数据库系统。 夺系统运行环境变化带来的软件修正。如由c s 结构变为b s 结构， 这时的系统体系结构必须做相应的改变。 令适应系统开发环境变化的软件维护。有些软件系统，尤其是e r p 这 样的定制系统，企业业务流程的变化需要软件系统做相应的调整。 2 完善性维护的再工程：增加或修改功能，以提高系统的安全性、处理能 力等。 3 预防性维护的再工程：为了提高系统可维护性而进行结构优化、文档重 l 陈大学硕士学位论文 构以及数据重组等。 1 3 论文组织 本文组织如下：第二章回顾相关的基本概念；第三章讨论了面向过程遗 产软件的再工程方法，比较了簇分析方法和概念分析方法；第四章讨论了概 念分析方法在面向对象遗产软件再工程中的应用，分别讨论了构造项目表、 构造概念格以及重构类层次等几个问题；第五章讨论了概念格分析工具 ( c l a t ) 的实现，阐述了分析工具的体系结构，语言透明性，以及针对c + + 语法的分析状态图；第六章讨论了国内外再工程领域的相关著作；第七章是 结论和后续工作。 山自：大学硕士学位论文 第二章基本概念 进一步讨论遗产软件的再工程之前，我们先引入一些基本概念。 概念分析作为识别具有公共属性的对象集合的一种方法，其数学基础是 1 9 4 0 年b i r h o f f 在文献【5 】中提出的格理论。b i r h o f r 证明了针对特定对象和属 性之间的每一个逻辑关系，都可以构造一个概念格对原始的关系有一个透彻 的剖析。同时，概念格也总能转换回原始的关系。 2 1 关系以及对应的格【2 】 夺二元关系：从集合a 到集合a 的二元关系，称为集合a 上的二元关 系，例如正整数集合a 上的关系r ：a b 1 0 。 夺自反关系：设r 是a 上的二元关系，如果满足v a a 等( 口，a ) r ， 称r 是自反关系。例如正整数集合a 上的整除关系r ，相反地，关 系a b 就不是自反关系。 夺对称关系：( d ，b ) r ( 6 ，a ) r ，称r 为对称关系。 反对称关系：( 口，b ) r & 6 1 7 l j ( 6 ，口) r ，称r 为反对称关系。 夺传递关系：( 口，b ) r & ( 6 ，c ) r j ( 口，c ) 月，称r 为传递关系。 夺偏序关系：自反、反对称、传递的二元关系。 夺偏序集：集合a 以及在a 上的一个偏序关系称为偏序集，表示为( a ， r ) 或者( 4 ，s ) 。 夺链：( a ， ) 是一个偏序集，如果a 的一个子集中任何两个元素都相 关，称这个子集为一条链。 夺反链：( a ，) 是一个偏序集，如果a 的一个子集中任何两个元素都 不相关，称这个子集为反链。例如图3 1 偏序集对应的格中， t 2 , b ，c ，p ) ， 4 ，b ，c ， a ，d ，e ) ， a ) 是链，溉c ) ， c ，d ) ， 口) 是反链。 山东人学硕士学位论文 bcde b d d 图2 1 偏序集以及对应的格 夺全序集：如果a 是一条链，那么偏序集( a ，) 称为全序集，此时的 二元关系称为全序关系。 夺极大元、极小元：偏序集( a ，) ，若a 中不 存在任意元素b ，使得b c a 且d b ，则a 称 为极大元。类似地可以定义极小元。极大元 和极小元可能有多个，如图2 2 中，j , k 是极b 大元，a , b ，c 是极小元。 夺上界：设a 和b 是偏序集( a ，) 中的两个元 图2 2 极大元、极小元 素，一个元素c ，若满足口c 和b c ，则c 是a 和b 的上界。例如 图2 2 中h 、i 、j 、k 都是f 和g 的上界 夺上确界：如果c 是a 和b 的一个上界，并且不存在a 和b 的任意上 界d ，使得d c ，则称c 为a 和b 的上确界。如图h 、i 是f 和g 的 上确界。 夺下界、下确界：和上界、上确界类似。 夺格：任何两个元素都具有上确界和下确界的偏序集 夺笛卡儿积：i r ( a ，r 1 ) 和( b r e 两个偏序集，在集合a + b 上定义一个 二元关系r 3 ，使得对于a 中的元素a 1 与a 2 和b 中的元素b l 与b 2 ， ( ( 日】，6 1 ) ，( 盘2 ，6 2 ) ) r 3 ( 口l ，6 1 ) rl ( d 2 ，b 2 ) r 2 ，则r 3 也是一个偏序 关系，偏序集( a + b ，r 3 ) 称n ( a ，r 1 ) 和( b ，r 2 ) 的笛卡儿积c 夺并运算：日v 6 等于a 和b 的上确界，因此口v b 也称为a 和b 的并。 夺交运算：口 6 等于a 和b 的下确界，因此口a b 也称为a 和b 的交。 i f l i l d 山东火学硕士学位论文 2 2 概念格 概念分析方法以一个关系或者逻辑表作为起始点，由对象集合o t ，和属性 集合彳。中元素所组成的集合称项目表r ，很显然r o o a o 。 任何对象集合0 互o o ，公共属性为：仃( d ) = a a l v o 0 ：( o ，a ) t ) ， 同理，任意属性集合a a o 的公共对象为：r ( a ) = 0 0 i v a a ：( o ，口) 7 1 ) 。 如果满足彳= 口( d ) 和0 = f ( 彳) ，那么( o ，彳) 称为一个概念。 通常，一个概念对应表格r 中的一个最大的矩形( 见表2 1 ) ：任意的o o 都具有a 中的所有属性，所有的属性a a 都匹配( ) 中的所有对象。需要注意 的是概念不会因为表的行列转置发生变化。给定表的所有概念通过下式形成 一个偏序关系：( 0 1 ，a i ) ( o z ，a 2 ) 营0 1 曼0 2 ，a 1 3 a 2 。 b i r k h o f f 证明了这个概念集合组成了一个完整的格，称为概念格l ( t ) ， 对于概念格中的两个元素( 0 ，爿，) 和( 0 2 ，a 2 ) ，下确界( 与运算) 定义为： ( d ，a i ) ( 0 2 ，a 2 ) = ( o l n 0 2 ：口( 0 】n 0 2 ) ) 。上确界( 或运算) 定义为： ( d t ，a 1 ) v ( 0 2 ，4 2 ) = ( f ( 一，n 爿2 ) ，aj m a 2 ) ) 。 一个概念c = ( 0 ，a ) 具有外边界e x t ( c ) = 0 以及内边界i n t ( c ) = a ，如果一 个概念是在它内边界范围内具有a 属性的最大的概念( 对象集合最大，属性 集合最小) ，那么相应的格节点c 就采用a 来标识，如果是在外边界范围内具 有。对象的最小的概念( 对象集合最小，属性集合最大) ，那么相应的格节点 就采用。来标识。这个唯一的用a 标示的节点记为 ) ，唯一用。标示的节 点记为r ( 0 1 ，因此有： u ( a ) ：v c l ( t ) l a i n t ( c ) ) ，r ( o ) = c l ( t ) l0 e x t ( c ) 对元素( o ，a ) 而言，具有对象。的最小概念应该小于或等于具有属性a 的 最大的概念，这个基本特性建立了项目表以及对应概念格之间的联系，而且 使得它们可以相互重构：( 。，a ) t 营r ( o ) ( d ) 。 7 山东大学硕士学位论文 因此，可以得出这样的一个重要的结论：在概念格中，对象o 具有的属 性是那些在o 上面的属性，而在属性a 下面的所有对象都有属性a 。因此， 概念格中或节点( 上确界) 表示特定的一些对象具有相同的属性，而与节点 ( 下确界) 表示特定的一些属性匹配公共的对象。换句话说，或节点说明了 共同属性，与节点说明了共同对象。因此，概念格揭示了项目表中的概念簇 层次信息。 s m a l lm e d i u m l a r g e n e a rf a rm o o n m o o r l m e r c u r y v e n u s e a r t h m a r s j u p i t e r s a t u r n u r a n u s n e p t u n e p l u t o n o m 0 0 r l m e r c u r v q u s 表2 1 行星属性表 图2 3 行星属性表对应概念格 表2 1 表示了一个表，图2 3 是对应的概念格 1 0 】。以f 打标示的节点和 表中的最大矩形相对应。这个节点是所有具有f a r 属性的节点的上界：p l u t o ， j u p i t e r , s a t u m ，u r a n u s ，n e p t u n e 是概念格中妇节点下面的节点，表2 1 中的 山东大学硕士学位论文 数据证明了这些行星( 而且也只有这些行星) 是远的。 2 。3 蕴含 原始表和对应的概念格是同一个信息不同角度的表示，下面再补充一个 概念：蕴含集合，假设两个属性集合a ，b 满足b 曼a 。那么我们称a 蕴含 b ，当且仅当任何具有属性a 的对象同时也具有属性b ： 4 争b 亡 v o o ：( v a a ：( o ，n ) t ) j ( v b b ：( d ，6 ) r ) 对于集合b = b l ，b k ) ，a 一召v 6 r b ，3 a _ 6 。蕴含将概念格表示成 如下的方式：一斗b 营 ( 口) 1 a a ，a ( a ) ，z ( 6 ) ，换句话说，属性之间的 蕴含关系可以通过概念格的上行路径寻找。在图2 3 的例子中 ( 扣r ) i t ( m o o n ) ，可以理解成如r 专m o o n ，或者“个比较远的星球具有 卫星”，另一个蕴含的例子是n om o o n 斗n e a r ，s a m u 。 一个概念格具有一个最小的蕴含集合，从这个集合中可以导出其他有效 蕴含：这个基本蕴含集合记为：i ( t ) 。对于表2 1 的数据，其基本蕴含有1 0 个元素，例如：扣r 斗m o o n ，n o m o o n - 2 t n e a r ，s m a l l 等。其他诸如 f a r ，s m a l 斗m o o n ，s m a l lo rn om o o n 斗n e a r 这样的非基本蕴含可以在基本 蕴含的基础上通过逻辑推理而得。 另一方面，借着这种逻辑推理，可以把相关的背景知识融合到项目表中， 这对于再工程有着重要的意义，因为在遗产软件维护，尤其是完善性维护中， 往往需要添加或者删除某些功能，在这种情况下如果添加的业务规则可以使 用这种逻辑蕴含表示的话，则使用概念格方法很容易把这些业务规则融入到 原先的系统中。在项目表中可以通过将x 列的项目复制到y 列的形式实现一 个x 斗y 的蕴含，因为这样在概念格中将会有( x ) p ( y ) 。 山东大学硕士学位论文 第三章面向过程遗产软件再工程 对于面向过程的遗产软件，提高软件结构性的一个可行的途径就是将软 件系统移植到面向对象的技术中。考虑简单一点的情况，本文仅讨论遗产软 件系统中的候选对象的标识问题。 典型的对象标识方法包括如下几个步骤： 1 标识候选类。 2 标识候选方法。 3 通过对象标识为每一个方法选定最合适的类。 对于面向过程的遗产软件，目前已经有几种方法可以进行对象标识，在 讨沦概念分析方法之前，我们先讨论典型的分析方法一簇分析方法： 3 1 簇分析方法 3 。1 1 概述 簇分析是一种在项目集合中寻找相关项目的方法，最初主要针对基于数 据库应用的遗产软件，这类遗产软件最显著的特点是以数据库记录为中- t 3 ， 例如c o b o l 、f o x b a s e 或者d o s 平台下面的f o x p r o 语言编写的软件系统。文 献 3 0 应用簇分析方法分析银行系统( c o b o l 语言编写) 的帐号升级问题，本 文对其进行一定的扩展，使之应用于非数据库软件系统。 p lp 2p 3 p d p 5p 6 n a m 匝 t i t l e i n i t i a l p r e f i x n u m b e r n u m e x t z l p c d s t r e e r c 九y 表3 16 个过程与9 个变量的使用关系表 所有的软件系统都有一个共性：程序有一个主函数作为入口，因此，作 为遗产软件的分析方法，我们只需要关心考虑那些全局变量和主函数中的变 山东大学硕士学位论文 量( 局部变量将直接封装在过程中) 。 假设一个遗产软件系统包括6 个过程，9 个全局变量，过程与变量之间的 使用关系如表3 1 所示。 3 1 2 距离测量 进行簇分析之前，必须先计算出两个变量之间的“距离”，在整个簇分析 过程中，变量之间的“距离”是进行簇分割的主要依据。如果把表中每一行 都看成6 维空间中的一个点坐标，那么可以计算出任何两个变量在6 维空间 中的距离。如果把变量之间的距离组成一个矩阵，可以得到距离矩阵，表3 1 数据对应的距离矩阵见表3 2 第一部分( 为了表述方便，使用数字代替变量 名称) 。 3 1 3 簇分析算法 f o r ( i = 0 ；i 1 ) 如果簇集合的元素个数大于1 记录当前最小的距离 i m i n l e n = l e n g t h a r r a y ( 1 ，0 ) ； f o r ( i ：0 ；i c l u s t e r c o l l e c to e t c o u n t ( ) 一1 ；i + + ) f o r 02i + 1 ；j c l u s t e r c o l l e c t g e t c o u n t 0 ；j + + ) i f ( l e n g t h a r r a y ( i j ) i m i n l e n ) i m i n l e n 2 l e n g t h a r r a y ( i d ) ； ) ) t e m p c l u s t e r = ： 川自时簇 f o r ( i _ 0 ；i f 0 ； r e t u r no ： 图4 1 例子程序p l 就p l 而言，我们可以得到： c l a s s v a r s ( p 1 ) = 口，b ，c ) c l a s s p t r v a r s ( p 1 ) ； a p ，a ：厂，a ：g ，b ：g ，c ：， m e m b e r d c l s ( p 1 ) i d c l ( a ：x ) ，a c t ( a ：厂) ，d c i ( a ：g ) ， d c l ( b ：y ) ，d c l ( b ：g ) ，d c l ( c ：z ) ，d c t ( c ：，) ) m e m b e r d e f s ( p 1 ) ； a e f ( a ：，) ，a e f ( a ：g ) ，a e f ( b ：g ) ，d d ( c ：厂) ) 4 3 构造项目表 该节我们将讨论如何构造项目表。构造项目表的目的是记录变量和类成 员之间的使用关系，下面先提出一些补充的定义。 4 - 3 1 补充定义 对集 c l a s s p t r v a r s ( p ) 中的每个变量，我们需要估计变量v 可能指向的 集合c l a s s v a r s ( p ) 中的那些变量。定义3 描述了由指向分析算法针对集合 p o i n t t o ( p ) 得到的结果，其中包括对每个指针p 可能指向的类变量v 形成的 变量对 ，( 印，6 ，( a p ，c ) ，( 4 ：厂，口 ，( 爿：厂，6 ) ， ， ) 计算一般程序中的指向信息，可以使用下面的算法：对每个类型为+ x 的 指针p ，假设它可能指向一个类型为y 的对象，那么必须满足： 夺y = x 或者y 是从x 继承的一个类 夺如果p 是虚函数x ：m 的t h i s 指针，则在类y 中没有重载n l 的定义。 我们将利用下面的术语来描述函数及方法调用。直接调用指任何对函数 和非虚方法的调用，以及c l a s s v a r s ( p ) 中的一个变量对虚函数的调用。间接 调用指c l a s s p t r v a r s ( p ) 中的一个变量对虚函数的调用，此时需要动态编译机 制支持。 4 3 2 成员函数访问操作的表项目 在项目表t 中，对于集合c l a s s v a r s ( p ) 以及c l a s s p t r v a r s ( p ) 中的每个元 素都有- - c ；与之对应，同样对于集合m e m b e r d c l s ( p ) 和m e m b e r d e f s ( 尸) 中的 每个元素都有一列与之对应。定义4 描述了所有的 形成的集合 m e m b e r a c c e s s ( p ) ， 表示成员m 是通过变量y 访问的。对一个间接调 用p 寸厂( y f j 肋) ，集合m e m b e r a c c e s s ( p ) 中都有一个元素( ，y 与集合 p o i n t s t o ( p ) 中的每个( p ，y ) 相对应。 定义4 ：假设p 是一个程序。则p 中成员访问操作集合可以定义为： 山东大学硕士学位论文 m e m b e r a c c e s s ( p ) 5 ( m ，v ) 1v o c c u r si np ，mi sa c l a s sm e m b e ri n 尸，v c l a s s v a r s ( p ) ) u p o i n t s t o ( p ) ，聊i sav i r t u a lm e t h o di np 上面的三种情况分别表示通过类型变量访问类成员，通过类型指针变量 访问类成员以及通过类型指针变量访问虚方法。注意第三种情况：如果 ( p ，y ) p o i n t s t o ( p ) ，则表示y 可能访问方法指针p 对应的方法( 如a ：f ) ， 此时程序中如果有p 哼m ，且m 是一个虚方法。那么( m ，y ) 在集合 m e m b e r a c c e s s ( p ) 中，表示y 有可能访问m 。 分析过程中必须确定操作访问的类成员，因为类层次结构中不同的类可 能包含了相同名字的成员。而且，多继承可能使得一个给定类型c 的对象具 有多个子对象，因此具有多个成员函数c ：m 。这意味着无论什么时候访问成 员函数m ，都需要确定究竟选择了哪个m 。 假设函数s t a t i c 1 0 0 k u p 能在给定类c 和成员m 情况下确定出选定的成员 所在的基类b ( b 是c 或者c 的一个基类) 。下面讨论如何把变量、声明以 及定义之间适当的关系添加到表中： 定义5 ：假设p 是和表t 关联的一个程序。那么根据程序中成员函数的 访问情况可以把下面的项目添加到表中。 ( m ，y m e m b e r a c c e s s ( p ) ，m d a t a m e m b e r s ( p ) ， i s t a t i c i o o k u p ( t y p e o f ( p ，y ) m ) ( y ，d c t ( x ：m ) ) t ( m ，一) m e m b e r a c c e s s ( p ) ，m n o n v i r t u a i m e t h o d s ( p ) ， z s t a t i c l o o k u p ( t y p e o f ( p ，) ，m ) ( y ，d e f ( x ：m ) ) e t ( m ，y ) m e m b e r a c c e s s ( p ) ，m v i r t u a l m e t h o d s ( p ) ， y 2 8 p p c l a s s p t r v a r s ( p ) x = s t a t i c l o o k u p ( t y p e o f ( 只y ) ，m ) ( 弘d c l ( x ：m ) ) t ( m ，y ) m e m b e r a c c e s s ( p ) ，m v i i 。t u a t m e t h o d s ( p ) ， y 三v ，v c l a s s v a r s ( p ) ， i s t a t i c l o o k u p ( t y p e o f ( p ，y ) ，m ) ( 弘d e f ( x ：) ) t 山东大学硕士学位论文 这四种情况分别是：类型变量y 访问类数据成员，类型变量y 访问非虚 方法x ：m 、指针变量p 访问虚方法( 实际添加到表中的是指针所指向的对象 y ) 以及类型变量y 访问虚方法。 4 3 3 t h i s 指针的表项目 下面将要提出的表构造规则与方法的t h i s 指针有关。对于每个方法 c ：厂( ) ，表中都有一列d e f ( c = = 厂) ，一行+ c ：f 与之对应，其中列用来表示 方法被对象调用的情况，而行用来表示那些通过c ：厂0 的t h i s 指针访问的对 象。虽然概念格的构造过程中始终满足规则，( + c ：f ) 1 t ( d e f ( c ：，) ) ，但是 如果不采取一些预防措施的话，属性d e f ( c ：厂) 和对象c ：厂( ) 可能出现在概 念格的不同节点上( 文献 7 ) 。在这种情况下，我们的方法可以正确地指出 t h i s 指针的类型可以是c ：f 所在类型的基类。 通过约束y ( + c ：厂) t ( d e f ( c ：厂) ) ，按照定义6 添加的表项目可以确保 一个方法的属性和一个方法的t h i s 指针出现在同一个格结点中，这允许在后 面的概念格构造中删除表中方法t h i s 指针对应的行。 i o奄 舅 o ，、 一 霄o ：簧斗： s ，采用直接调用x , f ( y l ，弦) 进行参数传递的方式建模。 这也就可以保守地估计动态调用的潜在的目标。a s s i g n m e n t s ( p ) 还包括隐含 参数项目，比如方法或者函数的t b a s 指针返回了一个类值。 定义7 ：假设p 是个程序。那么类变量或者类指针变量之间的赋值集 合可以定义如下： a s s i g n m e n t s ( p 1 e ( v ，w ) v = wo c c u r si nj p ，v ，w c l a s s v a r s ( p ) ) u ( + p ，m j i 1 ) = wo c c y s i n p ，p c l a s s p t ，。v a t s ( p ) ，、 c l a s s v a r s ( p ) ) u ( 8 p ，+ 9 ) i p = go c c u r s i n p ，p ，g c t a s s p t r v a r s ( p ) ) u ( ( p ，w ) l4 p = w o c c u r si n p ，p c l a s s p t r v a r s ( p ) ，w c l a s s v a t 4 s ( p ) ) u ( 1 ，+ q ) fv = + q o c c u r si n p ，v c l a s s v a r s ( p ) ，g c l a s s p t r v a r s ( p ) u ( 8 p ，4 q ) l4 p = + g o c c u r si np ，p ，q c l a s s p t r v a t s ( p ) 对于图4 1 的p l ，有： 山东大学硕士学位论文 a s s i g n m e n t s ( p 1 ) ! ( + a p ，口) ，( + a p ，6 ，( + a p ，c ) ， s e t a d v i s o r ( p 1 ) ； r e t u r n0 ； ， ( b ) i n tm a i n ( ) c s t r i n gs 2 n a m e ，p 2 n a m e ； c s t r i n gs 2 a d d r , p 2 a d d r ； c s t u d e n t + s 2 = n e wc s t u d e m ( s 2 n a m e ，s 2 a d d r , 8 7 6 5 4 3 2 1 ) ； c p r o f e s s o r + n 2 = n e wc p r o f e s s o r ( p 2 n a r n e ，p r o f e s s o r ，p 2 a d d o ； p 2 h i r e a s s i s t a n t ( s 2 ) ； r e t u r n0 ： ) 图4 4 教授、学生程序示例p 2 ( c ) 图44 的例子表示了学生和教授之间的关系，图4 4 ( a ) 说明了类结构， 类c p e r s 。n 包括姓名、地址以及身份证号码，类c s t u d e n t 和c p r o f e s s 。r 继承 c p e r s 。n 。类c s t u d e n t 具有学号，如果是研究生的话还有课题导师，该类提 供了两个接口，分别用来初始化学生变量和为学生选定导师。类c p m f e 5 8 0 。 3 0 u 东大学硕士学位论文 具有资历和工作地点，并可以雇用一个学生做助手。程序中认为c s t r i n g 为 系统已知类，对其不再进行分析。 图4 4 ( b ) 、( c ) 说明了两个使用图4 4 ( a ) 类结构的程序，在第一个程 序中，创建了一个学生和一个教授实例，而且教授作为学生的导师，第二个 程序创建了另个学生和教授，学生作为教授的助手。程序p z 的原始项目表 如表4 4 - 葛 皇 呈譬 墨 a a 一 f 要 晏 e h 盆 苦 器 罚 等 盘 岩 拦世 三2 童三宝 8 厶 山山u c p e r s o n ：m s n a m e c p e r s o n ：ms a d d r e s s c p e r s o n ：m l i d c s t u d e n t ：c s t u d e m ( ) c s t u d e n t ：s e t a d v i s o r ( ) c s t u d e n t ：m _ l s t u d e n t l d c s t u d e n t ：mp a d v i s o r c p r o f e s s o r ：c p r o f e s s o r 0 c