（计算机软件与理论专业论文）面向对象程序等价转换技术的研究与应用.pdf

摘要 摘要 程序的等价转换技术在程序的分析评价中有着广泛的应用前景。由于目前程 序分析评价主要停留在程序输出结果的比较阶段，未深入到程序的结构层次分析， 以发现程序之间存在的语义差异。另外，在已有相关方面的研究中，程序分析评 价的目标语言仅限于函数式语言或命令式语言，尚未涉及到面向对象语言的等价 转换研究。 本文研究基于面向对象程序的等价转换技术及其在程序分析评价中的应用。 程序的等价转换技术是以程序语义等价性为理论基础，程序语义的等价性包括执 行语义等价、结构语义等价和似结构语义等价。具有等价似结构语义的源程序之 间可以作相互转换。 由于使用面向对象语言设计的程序具有明显的层次性，在对这类程序进行等 价转换时，分以下三个层次进行：程序级等价转换、类级等价转换和方法级等价 转换。程序级等价转换主要是针对程序中类之间存在继承关系而进行的程序标准 化处理过程，通过对继承关系的消除，可以显式地表达每个类所包含的所有信息。 类级等价转换主要是针对每个类中的成员方法之间的相互调用关系进行的程序标 准化处理过程，通过对调用关系的消除，可以直观表达每个成员方法中所包含的 所有信息，同时，还需要消除类中存在的冗余方法，简化类的构成。方法级等价 转换主要是针对程序在语句表达上的多样化而进行的程序标准化处理过程，通过 对程序中的语句进行赋值标准化、表达式标准化和控制结构标准化来消除每个方 法中语句表达的多样化问题。 在面向对象程序等价转换技术的基础上，提出了一个j a 、，a 程序自动测评系 统的框架，并实现了系统原型。在该系统中，使用a n t l r w o r k s 构造一个以 a s t 为中间代码的j a v a 语言解析器。在a s t 基础上，对程序结构进行分析，并 引入c & k 和m o o d 等著名的面向对象的度量体系对程序进行度量，并生成用于 分析程序的各种图形表示。然后按程序级保留语义的等价转换、类级保留语义的 等价转换和方法级保留语义的等价转换共三个层次对程序进行保留语义的等价转 换，最终生成在语义上可以比较的程序依赖图，应用相关算法实现对程序的比较 与评价。 广东【。业大学t 学硕士学位论文 关键词：面向对象；等价转换；语义等价；程序标准化；程序比较 i i a b s t r a c t p r o g r a me q u i v a l e n c e t r a n s f o r m a t i o n t e c h n o l o g yh a s e x t e n s i v e a p p l i c a t i o n p r o s p e c t si np r o g r a ma n a l y s i sa n da s s e s s m e n tt e c h n o l o g y n o w a d a y s ，t h ep r o g r a m a n a l y s i st e c h n o l o g ym a i n l yc o n c e n t r a t e so nc o m p a r i s o no fp r o g r a mo u t p u t s i tc a n t f i n do u ts e m a n t i cd i f f e r e n c e st h r o u g ha n a l y s i n gs t r u c t u r e so fp r o g r a m s a tp r e s e n t ， r e s e a r c hr e s u h sm a d eo fw h i c ht a r g e tl a n g u a g ei sf i m c t i o n a ll a n g u a g eo ri n j u n c t i v e l a n g u a g e h o w e v e r , t h e r ea r e f e wr e s e a r c ho ne q u i v a l a n c et r a n s f o r m a t i o nf o r o b j e c t - o r i e n t e dl a n g u a g e i nt h et h e s i s ，w ed or e s e a r c hi np r o g r a me q u i v a l e n c et r a n s f o r m a t i o nt e c h n o l o g y a n di t sa p p l i c a t i o ni np r o g r a ma n a l y s i sa n da s s e s s m e n t s e m a n t i ce q u i v a l e n c eo f p r o g r a mi st h e o r e t i c a lf o u n d a t i o no fp r o g r a me q u i v a l e n c et r a n s f o r m a t i o nt e c h n o l o g y s e m a n t i ce q u i v a l e n c eo fp r o g r a mc o n t a i n se x e c u t i o ns e m a n t i ce q u i v a l e n c e ，s t r u c t u r e s e m a n t i c e q u i v a l e n c ea n ds i m i l a r s t r u c t u r es e m a n t i c e q u i v a l e n c e i ft h es i m i l a r s t r u c t u r es e m a n t i c so ft w os o u r c ep r o g r a ma r ee q u i v a l e n t , o n es o u r c ep r o g r a mc a nb e t r a n s f o r m e di n t oa n o t h e rs o u r c ep r o g r a m d u et oo b v i o u sh i e r a r c h yo fo b j e c t o r i e n t e dp r o g r a m , t h e r ea r et h r e el e v e l s e q u i v a l e n c et r a n s f o r m a t i o n , w h i c hc o n t a i n sp r o g r a ml e v e le q u i v a l e n c et r a n s f o r m a t i o n , c l a s sl e v e le q u i v a l e n c et r a n s f o r m a t i o na n df i m c t i o nl e v e le q u i v a l e n c et r a n s f o r m a t i o n ， f o ro b j e c t - o r i e n t e dp r o g r a m p r o g r a ml e v e le q u i v a l e n c et r a n s f o r m a t i o ni su s e dt os h o w a l lt h ei n f o r m a t i o nw h i c he x i s t e di ne a c hc l a s st h r o u g he l i m i n a t i n gi n h e r i t a n c er e l a t i o n b e t w e e na l lc l a s s e si nt h ep r o g r a m c l a s sl e v e le q u i v a l e n c et r a n s f o r m a t i o ni su s e dt o s h o wa l lt h ei n f o r m a t i o nw h i c he x i s t e di ne a c hf u n c t i o nt h r o u g he l i m i n a t i n gm e t h o d c a l l sb e t w e e na l lm e t h o d si ne a c hc l a s s m e a n w h i l e ，t h es t r u c t u r e so fa l lc l a s sa r e s i m p l i f i e d b y e l i m i n a t i n g r e d u n d a n tm e t h o d s f u n c t i o n l e v e l e q u i v a l e n c e t r a n s f o r m a t i o ni su s e dt oe l i m i n a t i n gt h ed i v e r s i f i c a t i o no fs e n t e n c ee x p r e s s i o nt h r o u g h s t a n d a r d i z i n ga s s i g n m e n t s ，e x p r e s s i o n sa n dc o n t r o ls t r u c t u r e s b a s e do no b j e c t o r i e n t e dp r o g r a me q u i v a l e n c et r a n s f o r m a t i o nt e c h n o l o g y , w e p r o p o s e an e wf r a m e w o r ko fj a v ap o r g r a ma u t o m a t i ca s s e s s m e n ts y s t e m , a n d i m p l e m e n tt h ep r o t o t y p e i nt h es y s t e m , w eu s ea n t l r w o r k t oc o n s t r u c taj a v a p a r s e r ，w h i c hi sa b l et og e n e r a t ea b s t r a c ts y n t a xt r e ea si n t e r m e d i a t el a n g u a g e a tt h e i i i 查；：些奎兰三兰堡圭兰篁堡圣 a n a l y s i so fp r o g r a ms t m c t i 。w em a k eu s eo fc & ka n dm o o ds o n 、v a r em e t r i c st o c o m p u t ea n dv i s u a l i z et h em e t r i c si n f o r m a t i o no f p r o g r a m s ，a n dg e n e r a t es e v e r a lg r a p h e x p r e s s i o no f p r o g r a m s a te q u i v a l e n c et r a n s f o r m a t i o no f p r o g r a m , w ep r o p o s ean e w m e t h o dw h i c hi m p l e m e n t ss e m a n t i c a l l yp r e s e r v i n ge q u i v a l e n c et r a n s f o r m a t i o nb yt h r e e l e v e l st h a ta l et r a n s f o r m a t i o na tp r o g r a ml e v e ls e p e r a t e l y , t r a n s f o r m a t i o na tc l a s sl e v e l ， t r a n s f o r m a t i o na tm e t h o dl e v e l a f t e r e q u i v a l e n c et r a n s f o r m a t i o n , t h ep r o g r a m d e p e n d a n c eg r a p h sa r ec o n s t r u c t e da n dt h ec o m p a r i s o na n da s s e s s m e n ta l g o r i t h mi s a p p l yt oi d e n t i l y i n gt h es e m a n t i cd i f f e r e n c e so tt w op r o g r a m sa n dg i v i n ga l la n a l y s i s a n da s s e s s m e n tr e p o r t k e y w o r d s ： s t a n d a r d i z a t i o n , e q u i v a l e n c et r a n s f o r m a t i o n , s e m a n t i ce q u i v a l e n c e ，p r o g r a m p r o g r a mc o m p a r i s o n , a s s e s s m e n t i v 广东一1 - 业大学1 ：学硕士学位论文 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 论文作者签字： 指导教师签字： 2 0 0 8 年5 月1 2 日 郴 第一章绪论 1 1 本文研究背景 第一章绪论 随着计算机技术的飞速发展和在社会中各个领域的广泛应用，使得人们原有 的生活方式发生了巨大的变化。就教育领域而言，将计算机应用于教育测量和测 评的全过程，即计算机辅助测评( c o m p u t e r a s s i s t e d a s s e s s m e n t ) ，已经成为一种 不可阻挡的发展趋势。如何将计算机应用于准确地测评人的知识技能水平已成为 研究热点。 尤其是近年来，我国高等教育的规模持续扩大，其中学生规模的增长速度已 经远远超过了教职工规模的增长速度，这种不协调的发展趋势势必会影响到高等 教育的质量。特别是针对计算机专业的学生来说，上机实践的能力非常重要，由 于学生过多，而教师数量又非常有限，因此，学生在上机实践方面得到的指导非 常有限。针对程序设计的课程来说，初学编程的学生特别需要教师进行一对一的 指导，来提高编程能力。由于学生数量与教师数量的比例严重失调，这种针对学 生进行一对一的辅导是不现实的。因此，开发一个能够缓解教师工作，帮助学生 提高编程能力的程序自动分析评价系统是非常必要的。若有了这样一个系统，学 生就可以根据系统的提示，来发现所编写程序的错误，尤其是能够编译通过但结 果错误的程序，并尝试自己解决问题。这样不仅可以提高学生学习编程的兴趣， 同时还可以大大降低教师的工作量，又不影响教育质量。 除此之外，计算机自动测评技术还可以应用到信息产业领域。尤其是近年来， 侵犯知识产权的案件屡屡发生，特别是软件的版权问题不断浮现，这个局面对软 件行业的健康发展提出严重的挑战。然而，怎样才能准确地判定一个软件产品是 否侵权还是一个备受争议的问题，还没有一个有效的解决方案，因此，侵权判定 主要是通过软件专家通过个人的经验来完成的。计算机自动测评技术为软件相似 性的判别提供相应的技术支持。在我国，这方面的相关研究更是方兴未艾，仍然 是一个需要大量投入的新兴领域。 广东f ：业大学1 一学硕十学位论文 1 1 1 程序测评技术现状 程序测评是对一个程序进行分析，根据一定的标准对程序中存在的错误进行 定位，并反馈分析结果。 我院正在使用的数据结构作业系统则是一个能够对程序进行测评的程序作业 的环境。该系统内嵌了一个编译器，可以通过检查输出结果来判断程序的正误， 但对于能够编译通过但却存在语义错误的程序则无能为力。 c m a r k e r u 是一个c 语言的测评软件，它仅仅是通过对程序的结构和输出 结果的分析来判定程序的准确性。但并不能通过测评程序与模板程序的对比来发 现测评程序中存在的语义错误，因此，不具备较大的实用价值。 类似地，g e n e r i ca u t o m a t e dm a r k i n qe n v i r o d s e n t 圜，a no n l i n e p r o g r a m m i n ga s s e s s m e n tt o o l 【3 】，o n l i n ej u d g e 嗍，a s a p 【5 1 等测评工具 也是通过分析程序结构和匹配程序的输出结果来实现程序测评，根本无法定位程 序中存在的语义错误。 东南大学计算机科学与工程系研制了一种c 源程序分析及理解的辅助工具 c a a t ，其主要通过对源程序的逐级抽象理解来对没有注释的反编译源代码 进行添加注释、格式化显示，分析显示各类变量的使用情况，提供对宏、变量、 结构和联合等定义说明的查询显示，另外可输出模块调用关系及源程序中的函数 调用关系图【6 。 在文献 7 中，提出了程序对等结构，等价结构和程序结构规范化的概念，以 及确定对等结构的方法和比较确定等价结构的规则。设计的测评目标语言是c 语 言的子集，没有指针，不允许递归。 在文献 8 】中，提出基于转换的程序分析技术。在其开发的a n a l y s e c 系统原型 中，同样是以c 语言的一个子集作为目标语言，所不同的是，在原有的程序自动 测评系统的基础上，扩展了交互函数到内部函数的转换规则以及递归的转换规则， 具有更大通用性。 值得一提的是，国立新加坡大学计算机学院的s o n g w e nx u 等研制出 s i p l e s i i 9 ，1 川系统来分析学生程序，通过将学生程序与模板程序做标准化转 换，并生成种名为面向对象程序依赖关系图( a o p d g ) 的结构，然后两个程序的 a o p d g 进行对比，以此来定位程序中存在的错误。这样极大的提高的测评软件的 2 第章绪论 智能性。 阔1 - i s i p l e s - i i 系统的工作流程 f i g u r ei - 1p r o c e d u r eo fd i a g n o s i si ns i p l e s - i is y s t e m 但是s i p l e s i i 系统是针对s m a l l t a l k 语言的，而s m a l l t a l k 在我国并 不普及，而且s i p l e s i i 系统只能分析内部函数( i n t r a p r o c e d u r e ) ，不能 对交互函数( i n t e r - p r o c e d u r e ) 和类的层次结构( c l a s sh i e r a r c h y ) 进行 分析。 e x p r e s s o “1 能够识别出j a v a 编程的常见错误( 分类成语法错误、语义错 误、逻辑错误) ，具有较一般编译器高的分析查错功能，能为产生有用的错误信息 并提供修改代码的建议。但是该系统的语义分析查错能力不强，只能分析出少量 语义错误。 1 1 2 程序转换技术现状 在编译技术中，将源代码翻译成中间代码i 他】、抽象语法树，以及代码优化等， 普遍使用了程序转换技术。这里所指的程序变换，都是以不改变程序的语义为前 提的，称为保留语义的程序转换【l o 】。 在实际应用中，按照不同的需要存在多种程序转换。 i ) 将程序的一种源码表达形式转换成该程序的另一种源码表达形式，目的是 为了消除程序中语句表达的多样化问题【1 3 j ，为实现程序的对比分析以及排错提供 了方便。 例如，a n a l y s e c 系统 8 】首先通过对模板程序和学生程序进行一系列的标准化 转换，其中包括l 每时变量标准化，各种表达式的标准化和控制结构的标准化。这 样就消除了诸多程序中存在的保留语义的变化，为实现程序的测评，准备定位学 广东j ：业大学t 学硕十学位论文 生程序中存在的语义错误提供了可能。 2 ) 将一种语言程序转换成另一种语言程序，特别是将低级语言程序转换成为 高级语言程序，以帮助程序理解，解决遗产代码的问题。 2 0 0 3 年中国科学院计算技术研究所对c o b o l 到j a v a 源代码翻译进行了相关研 究，开发了c o b o l 2 j a v a 转换器【】。该转换器针对c o b o l 和j a 、，a 之间的不同点分 别定义了转换策略，其中包括数据类型的转换，控制结构的转换等相关问题，并 实现了将遗产代码成功的移植到目标平台，并保持原有的功能不变。 3 ) 通过在原有程序中加入相应的安全检查代码，转换之后的程序健壮性会更 好。 例如，在诸多的程序设计语言中都加入了t r y c a t c h 语句，该语句就是 为了防止程序在运行过程中发生异常而设计的。这样的语句不会增加程序实现的 主要功能，但确可以极大的提高程序的安全性。 1 1 3 其他相关技术现状 软件度量技术在程序的分析中也起着至关重要的作用。近年来，随着面向对 象语言的不断盛行，软件度量技术的研究重点逐渐由传统软件度量技术的研究转 向面向对象软件度量技术的研究。其中比较著名的有c & k 度量体系和m o o d 度量体系1 1 6 , 1 7 1 。 c & k 度量体系是由c h i d a m b e r 和k e m e r e r 所提出了一系列用于面向对象软件 系统的度量标准。该度量体系侧重于对系统中存在的每个类的相关属性进行度量。 其中包括六个度量准则： 1 每个类的方法加权和( w e i g h t e dm e t h o d sp e rc l a s s ，简称1 v m c ) 2 继承树的深度( d e p t ho fi n h e r i t a n c et r e e ，d i t ) 3 子类数( n u m b e ro fc h i l d r e n ，n o c ) 4 对象类之间的耦合度( c o u p l i n gb e t w e e no b j e c tc l a s s e s ，c b o ) 5 类响应度( r e s p o n s ef o rc l a s s ，r f c ) 6 内聚缺乏度( l a c ko fc o h e s i o nm e t r i c ，l c o m ) m o o d 度量是另一个著名的度量体系，由b r i t o 和a b r e u 所提出，它从封装 性、继承性、耦合性和多态性四个方面给出了面向对象软件的六个度量准则，分 别是： 4 第一章绪论 1 方法隐藏因子m h f 2 属性隐藏因子a h f 3 方法继承因子m f 4 属性继承因子m f 5 耦合因子c f 6 多态因子p f 该度量体系主要侧重于对整个面向对象软件系统进行度量。 不过，总体上来说，面向对象的软件度量还不够成熟，缺乏相应的理论基础， 尚难以成为软件度量的标准。 i 2 本文研究点 本文主要研究面向对象程序的保留语义的等价转换准则，并将其应用到j a v a 程序的自动测评系统中。 尽管已经有不少人在程序分析评价等相关技术方面做了不少工作，但是大多 使用比较实际输出与标准输出的方法来判断程序的正误，但是这种方法在大多数 情况下，并不能检测出程序中存在的语义错误，因此，实用价值不高。 国立新加坡大学的s i p l e s i i 系统【1 0 1 对在语义层次上分析评价程序进行 了尝试，而且有一定效果。但是s i p l e s i i 系统是针对s m a l l t a l k 语言的， 而s m a l l t a l k 语言的教学在我国的大学教育中并不普及，而且s i p l e s i i 系 统只能分析内部函数( i n t r a p r o c e d u r e ) ，不能对交互函数 ( i n t e r p r o c e d u r e ) 和类的层次结构( c l a s sh i e r a r c h y ) 进行分析。 我们实验室设计的a n a l y s e c 系统原型，参照了s i p l e s i i 系统的设计思 想，并通过内联扩展的方式解决了交互函数的分析问题。由于该系统原型是以c 语言为目标语言，因此，并没有任何涉及砸向对象语言程序的分析问题。 j a v a 程序自动测评系统是以j a v a 语言为目标语言的程序测评系统，在系统 架构的设计上参照了a n a l y s e c 8 】的结构，并完善了类层次结构的转换规则，解决 了面向对象语言程序的对比分析问题。 1 2 1 程序解析器的构造 利用a n t l r w o r k 编写j a v a 语言的a n t l r 元语割1 8 1 ，并使用a n t l r w o r k 生成 广东t 业大学丁：学硕士学位论文 j a v a 语言的解析器：同时构造j a v a 程序抽象语法树解析器程序。为程序的进一 步分析做铺垫。 1 2 2 面向对象程序信息提取 针对j a v a 语言的特点设计特定的数据结构一代码信息树( c i t ) 1 1 9 1 ，用于 存储通过扫描获得的源程序的信息。 提取的目的主要是为了对程序进行结构分析做准备，从源程序的a s t 中需要 收集以下信息：类与类之间的关系，类与其成员之间的关系，类的成员变量与成 员函数之间的关系，以及成员函数与成员函数之间的关系。最后利用这些信息生 成程序的代码信息树。c i t 为以后程序的分析和等价转换以及在程序的分析和转 换的过程中生成的各种图形表示提供了必要的信息。 1 2 3 面向对象程序度量 本文主要采用c & k 和m o o d 度量技术对程序中的相关属性给出相应的度量值， 并利用类层次图、类构造图直观的反应程序的结构信息。本文着重研究类之问继 承关系和类与其成员之间关系的度量以及可视化。 1 2 4 面向对象程序的等价转换 j a v a 语言是一种比较纯洁的面向对象语言，任何j a v a 程序都需要用类来构 成，这样就决定了j a v a 程序具有明显的层次性。一个j a v a 文件有多个类构成， 一个类由多个成员方法和成员变量构成，一个成员函数又是由多个语句所构成。 基于上述的分析，可以对j a v a 程序进行三个层次的等价转换，即程序级保 留语义的等价转换，类级保留语义的等价转换和方法级保留语义的等价转换。 程序级的等价转换主要是针对程序中类之问存在继承关系而进行的标准化 处理过程，通过对继承关系的消除，可以显示地表达每个类所包含的所有信息， 便于对程序做进一步分析。 类级的等价转换主要是针对每个类中的成员方法之间的相互调用进行的标 准化处理过程，通过对调用关系的消除，可以显示地表达每个成员方法中所包含 的所有信息，同时，还需要消除类中存在的冗余方法，简化类的构成，便于对程 序做迸一步分析。 方法级的等价转换主要是针对程序在表达上的多样化而进行的标准化处理 6 第章绪论 过程，通过对程序中的语句进行赋值标准化、表达式标准化和控制结构标准化来 消除每个方法中语句表达的多样化问题。 1 3 课题目标 通过对以上相关理论的分析，本人计划实现对j a v a 语言程序分析评价的软 件系统，即j a v a 程序自动测评系统，并结合数据结构作业系统以辅助学生的上 机编程练习。j a v a 程序自动测评系统具备了程序分析及其可视化、程序转换及 其可视化、程序分析评价等功能。课题的目标为“面向对象程序等价转换技术的 研究与应用”。 7 广东i - 业大学i ：学硕士学位论文 第二章等价转换技术概述 本章将简要介绍针对面向对象程序的等价转换技术所包括的主要内容，其中 包括程序等价性的定义、等价转换技术已有的工作基础和程序等价转换的处理过 程。 2 1 程序的等价性 程序的等价性主要是指程序语义的等价性，它为程序的转换提供理论依据和 实现方法。语义等价性分为以下三种：执行语义的等价性、结构语义的等价性和 似结构语义的等价性1 。 定义1 ( 执行语义的等价) ：设s o u r c e l 和s o u r c e 2 是两个源程序，若存 在完全相同的输入输出数组对集 ( i n p u t - g r o u p ，o u p u t - g r o u p ) ，使得 e x e c - s e m ( s o u r c e l ) ( i n p u t - g r o u p ) = o u t p u t - g r o u p e x e c - s e r n ( s o u r c e 2 ) ( i n p u t - g r o u p ) = o u t p u t - g r o u p 则称s o u r c e l 和s o u r c e 2 在 ( i n p u t g r o u p ，o u t p u t - g m u 上具有等价的执行语 义。 执行语义的等价性实际上定义了在值这一层次上最为基础的等价性。其他语 义等价的定义也是建立执行语义等价性基础上的。 定义2 ( 结构语义的等价) ：设s o u r c e l 和s o u r c e 2 是两个源程序，若 s o u r c e l 和s o u r c e 2 具有相同的抽象语法树，即 s t r u - s e m ( s o u r c e l ) = s y n t a x t r e e s t r u - s e m ( s o u r c e 2 ) = s y n t a x - t r e e 则称s o u r c e l 和s o u r c e 2 具有等价的结构语义。 定义3 ( 1 1 ；i 结构语义的等价) ：设s o u r c e l 和s o u r c e 2 是用同一种语言p l 编写的两个源程序，同属一个结构语义映射且其执行语义等价，即 e x e c s e m ( s t r u - s e m ( s o u r c e l ) ) = e x e c s e m ( s t r u s e m ( s o u r c e 2 ) ) 则称s o u r c e l 和s o u r c e 2 具有等价的似结构语义。 显然，具有等价的似结构语义的源程序之间是可以相互转换的，由此可以将 8 第二章等价转换技术概述 一个源程序转换成与其似结构语义等价的另一个代码表达上更为合适的源程序， 以满足其他的需要。本文所研究的是基于似结构语义等价性来研究源程序的等价 转换方法及其在程序对比分析中的应用。 上述三个关于程序等价性之问的关系如图2 1 所示。 2 2 已有的工作基础 图2 - 1 等价性关系图 f i g u r e2 - 1r e l a t i o ng r a p ho f e q u i v a l a n c e 目前尚没有办法严格证明“从程序结构的等价性来判定程序是否等价”的完备 性。但是从编程经验可以得到这样的结论，对于使用了相同算法的程序，整体结 构是大致相同的，至于由语法灵活应用引起的结构上的差异，已有相应的解决办 法。 在文献 7 d p ，对程序作业自动测评进行了研究，提出了程序对等结构，等价 结构和程序结构规范化的概念，以及确定对等结构的方法和比较确定等价结构的 规则。在该系统中，采用源代码特征提取及比较的方案，将学生程序与存储在试 题库中的模板程序集依次比较，然后根据基于相似度概念的评分规则得出对学生 程序完成程度和质量的测评结果。在学生程序与模板程序比较前需要对二者进行 一系列信息提取和结构转换工作。输入源程序后通过语法分析主要建立起对程序 控制结构的信息树，称作扩展语法树( e s t ) ；在e s t 的基础上通过对数据流向 的分析，建立起扩展流图( e f g ) 作为过渡；在e f g 基础上通过对程序基本块的 划分，对各子块的控制和数据依赖关系分析，以及使用一些规范化规则等技术， 广东t 业大学工学硕+ 学位论文 得到了程序特征属性图( p f s g ) 。之后的程序评价过程是基于程序对等结构和程 序等价结构的概念，对学生程序和模板程序的p f s g 进行的。该系统设计的测评 目标语言是c 语言的子集，没有指针，不允许递归，不支持函数调用的测评。 在文献 8 】中，提出基于转换的程序分析技术，对程序的转换规则进行了扩展， 并在程序的对比方面做了相关研究。在其开发的a n a l y s e c 系统原型中，使用 a n t l r 构造一个以抽象语法树为中间代码的c 语言分析器。在结构层次上， a n a l y s e c 基于程序的抽象语法树，应用传统的软件度量对程序进行分析和可视 化，并提出将数据结构的使用列为程序度量的元素之一，实现程序的结构相似性 分析。在语义层次上，应用编译器的转换技术和内联扩展技术等代码优化相关技 术，对程序进行标准化转换、控制流分析和数据流分析，形成可以在语义上进行 比较的程序依赖图，最终通过程序划分、比较，实现程序的分析评价。但a n a l y s e c 同样是以c 语言的一个子集作为目标语言，所不同的是，在原有的程序自动测评 系统的基础上，扩展了交互函数到内部函数的转换规则以及递归的转换规则，并 将s e q u e n c e c o n g r u e n c e 算法 2 q 应用到程序的对比中，提高了程序语义等价性判 别的准确性。 2 3 等价转换的处理过程 在上面所提到的工作中，主要是集中在命令式语言口2 】的等价转换的研究，其 目标语言是c 语言的一个子集。本文研究的重点是面向对象程序等价转换的研究， 其目标语言是j a v a 语言的一个子集。面向对象程序等价转换的处理过程如图2 - i 所示。 处理过程主要包括三个主要部分：抽象语法树的生成、结构分析和等价转换。 1 0 第二章等价转换技术概述 源程序 上 程序解析器 上 抽象吾法树 1 l 结构分析 上 等价转换 上 i 另一抽象语法树 图2 - l 面向对象程序等价转换的处理过程 f i g u r e2 - 1s t e po f e q u i v a l e n c et r a n s f o r m a t i o nf o ro b j e c t - o r i e n t e dp r o g r a m 2 3 1 抽象语法树的生成 在编译技术中，抽象语法树是一种非常重要的程序中间代码，是对程序进行 后续分析的基础。针对j a v a 语言的特点，构造j a v a 程序解析器，其主要包括三 个部分：词法分析器、语法分析器和语法树分析器。词法分析器用于将输入的程 序代码，转换成单词符号序列。词法分析器一般可以识别出关键字、标识符、常 数、运算符和分界符等单词符号，并将这些符号信息填入不同的符号表。语法分 析器用于检查有词法分析器生成的符号序列是否构成合法的语句。语法树解析器 用于这些合法的程序语句转化成抽象语法树的表达形式并可视化。针对生成的抽 象语法树，从中抽取相关的程序信息，并将其存入代码信息树中，为后续的程序 结构分析做铺垫。 2 3 2 结构分析 广东i 业大学j ：学硕十学位论文 在抽象语法树的基础上，采用著名的m o o d 度量体系、c & k 度量体系和一些传 统的度量体系对j a v a 程序进行度量并分析其结构特性。对j a v a 程序的结构分析 与度量可以分为三个层次进行，分别是程序级结构分析、类级结构分析和方法级 结构分析。在程序级结构分析中，根据代码信息树，构造j a v a 程序的类层次图， 对程序中各个类之间的关系进行分析并用m o o d 度量体系对程序进行度量。在类级 结构分析中，根据代码信息树构造每个类的类构造图，对每个类结构进行分析， 并采用c & k 度量体系对每个类进行度量。在方法级结构分析中，根据代码信息树， 构造每个函数的程序依赖图，并采用传统的度量体系( 例如环形复杂度理论) 每 个类中的每个成员方法进行分析和度量。对程序结构进行分析的目的，是为下一 步的等价转换做准备，有关结构分析的具体内容将在第三章详细论述。 2 3 3 等价转换 与结构分析相似，对程序进行等价转换也需要分三个层次进行，分别是程序 级等价转换、类级等价转换和方法级等价转换。在程序级等价转换中，根据生成 的类层次图，确定各个类之间的继承关系，并应用相应算法消除各个类之问的继 承关系，并保持每个类所包含的原有信息不变。在类级等价转换中，根据每个类 的类构造图，应用内联扩展技术消除方法之间调用关系，并保持方法原有功能不 变。在方法级等价转换中，根据抽象语法树，应用语句标准化规则实现方法内语 句的标准化转换。同时，在每个方法的程序依赖图的基础上，实现前向替换和消 除死代码的优化转换。有关等价转换的具体内容将在第四章详细介绍。 第三章程序结构分析 第三章程序结构分析 3 1 面向对象程序的特性 目前，支持面向对象程序设计的语言已经成为程序开发的主流。从本质上讲， 面向对象程序设计就是对抽象数据类烈的抽象原则的一个应用。在面向对象程序 设计中，类似抽象数据类型集合的共同性被抽取出来，并置于一个新的类型中。 作为面向对象的语言，必须支持3 个关键语言特性：封装性、继承性和多态性圈。 3 1 1 封装性 在面向对象程序中，封装是将数据类型和一系列相关操作同时装入一个对象 中。封装是一种信息隐蔽技术。用户只能见到对象封装界面上的信息，对象内部 的信息对用户是隐蔽的。在面向对象语言中，其封装性是通过“类”和“对象” 的概念实现的。类的作用主要有两种：一是方法作为对象的描述机制，刻画一组 对象的公共属性和行为；二是作为程序的基本单位，它又是支持模块化设计的设 施【2 2 】。 3 1 2 继承性 继承是描述类之间相似性的一个重要机制。面向对象的方法按照子类与父类 的关系，把若干个类组成一个层次结构的软件系统，在这种层次系统中，下层的 子类通常具有与父类相同的属性和行为，但是，在子类中允许对继承的某些特征 和方法重新定义，也就是说，下层的特征将屏蔽上层的同名特征。 3 1 3 多态性 同一消息可以根据发送消息对象的不同采用多种不同的行为方式，这就是多 态的概念。一个行为的多种形态从外界看来具有相同的行为名称( t g 即相同的消息 名) ，因此外界看到的只是一种行为。具体应该执行哪种形态由对象自己根据接收 到消息里的相关参数决定。 广东工业大学工学硕士学位论文 3 2 面向对象软件度量 软件度量是一种用于定量测量软件质量的方法。传统的、著名的软件度量方 法有m e c a b e 结构复杂性度量、h a l s t e a d 软件科学、l o c 语句行度量和w o o d w a r d 度量等【2 m 6 i ，这些度量方法都是针对传统的软件开发过程。但随着面向对象技术 的广泛应用，而面向对象软件系统的程序结构与传统软件系统的程序结构有显著 区别，传统度量方法已不再适用于面向对象的某些概念。面向对象软件度量方法 是一种专门针对面向对软件而设计的软件质量的度量方法。其中有一部分所涉及 到的度量标准是从传统的设计方法中获得的，而另外一部分是专门针对面向对象 软件开发的。本节所介绍的一些面向对象软件度量系统是对面向对象程序进行结 构层次等价转换的理论依据。下面对一些著名的面向对象软件度量体系做详细阐 述。 3 2 1c & k 度量 1 9 9 4 年，c h i d a m b e r 和k e m e r e r 提出了一系列用于面向对象软件系统的度量 标准，我们将之简称为c & k 度型1 5 1 。c i ( 度量体系的建立是源于由b u n g e 所提出 的并由y a n d 和w e b e r 在随后应用于面向对象系统的一套“实体论原理”。在“实 体论原理”中，世界被看成是由真是个体组成的，真实个体具有一组有限数量的 属性。真实个体及其属性共同构成一个对象。类则是具有相同属性的一组对象， 方法是对对象的操作，它被定义为类声明的一个组成部分。 c h i d a m b e r 和k e m e r e r 利用上述提到的这些概念定义了一系列度量准则，下 面将这些度量准则介绍如下： 1 每个类的方法加权和( w e i g h t e dm e t h o d sp e rc l a s s ，简称w m c ) 定义这个度量准则的目的是为了与传统度量中的复杂性相关联。对于含有方 法m 【，m 2 ，m | | 的类c ，对各方法分别用“复杂性”c ，c ：一c 进行加权，则 该度量准则的计算公式为式( 3 1 ) ： h w m c = yc f ( 3 1 ) 百 其中方法复杂性度量可以采用传统的方法进行度量，例如，可以应用m c c a b e 结构复杂性度量系统中每个类的每一个方法。 2 继承树的深度( d e p t ho fi n h e r i t a n c