一种形式化上下无关文法关系驱动的设计模式检测方法

工程科学学报，第38卷，第10期：1499-1508,2016年10月 Chinese Journal of Engineering,Vol.38,No.10:1499-1508,October 2016 D0l:10.13374/j.issn2095-9389.2016.10.020:http://journals..ustb.edu.cn 一种形式化上下无关文法关系驱动的设计模式检测 方法 肖卓宇四，何锫23)，余波”，黎妍)，杨鑫维” 1)中南林业科技大学涉外学院，长沙4102002)广州大学计算机科学与教有软件学院，广州510006 3)北京大学高可信软件技术教有部重点实验室，北京1008714)长沙理工大学计算机与通信工程学院，长沙410114 5)湖南省高速公路管理局，长沙410209 区通信作者，E-mail:xzyx0770@126.com 摘要针对设计模式识别结果的假阴性问题与重叠问题，为提高设计模式实例恢复的精确性，提出一种形式化上下无关文 法关系驱动的设计模式检测方法.依据设计模式实例中的参与者属性及其关系，以形式化可视化语言描述模式实例的识别 文法.在此基础上，改进该文法检测设计模式实例参与者间的附加关系，并识别共享实例的模式.实验结果表明，新方法不仅 减少了模式实例的假阴性结果，还解决了模式实例识别的重叠问题，与其他检测方法的精确度、召回率及Fsco指标比较， 新方法取得了较好的效果 关键词模式识别：设计模式：检测：形式化文法 分类号TP311 An approach for design pattern detection based on the formal context-free grammar relation driver XIA0Zhuo3u回，HEPe2s,,YUBo》,lYam》,YANG Xin-ei 1)Swan College,Central South University of Forestry and Technology,Changsha 410200,China 2)School of Computer Science&Education Software,Guangzhou University,Guangzhou 510006,China 3)Key Laboratory of High Confidence Software Technologies of the Ministry of Education,Peking University,Beijing 100871,China 4)School of Computer and Communication Engineering,Changsha University of Science and Technology,Changsha 410114,China 5)Hunan Highway Administration Bureau,Changsha 410209,China Corresponding author,E-mail:xzyxzy0770@126.com ABSTRACT Aiming at the false negative problem and the overlap problem in pattern instance detection,in order to improve the ac- curacy of the design pattern recovery,this article introduces an approach for design pattern detection based on the formal context-free grammar relation driver.Focusing on the attribute and relationship of classes in pattem instances,the formal grammar of pattern in- stance identification is established using the visual language,and an improved formalism grammar is presented for identifying the addi- tional relationships and the sharing problem of design pattern instances.Experimental results show that,compared with other well- known algorithms by precision,recall and F-score,the proposed method can reduce the false negative results and the overlap problem in pattern instance detection,indicating the effectiveness of the proposed method. KEY WORDS pattern recognition:design patterns:detection;formal grammars 收稿日期：2015-12-25 基金项目：国家自然科学基金资助项目(61170199)：湖南省大学生研究性学习和创新性实验计划资助项目（湘教通2015]84号197）：湖南省 教学改革研究立项资助项目（湘教通[2016]400号1068）：广东省自然科学基金资助项目(2015A030313501):湖南省教有厅重点资助项目 (11A004):广东省普通高校创新团队建设资助项目(2015 KCXTD014):中南林业科技大学教学改革研究资助项目(ZNLJG2016一A067)

工程科学学报，第 38 卷，第 10 期: 1499--1508，2016 年 10 月 Chinese Journal of Engineering，Vol． 38，No． 10: 1499--1508，October 2016 DOI: 10． 13374 /j． issn2095--9389． 2016． 10． 020; http: / /journals． ustb． edu． cn 一种形式化上下无关文法关系驱动的设计模式检测 方法 肖卓宇1) ，何 锫2，3，4) ，余 波1) ，黎 妍5) ，杨鑫维1) 1) 中南林业科技大学涉外学院，长沙 410200 2) 广州大学计算机科学与教育软件学院，广州 510006 3) 北京大学高可信软件技术教育部重点实验室，北京 100871 4) 长沙理工大学计算机与通信工程学院，长沙 410114 5) 湖南省高速公路管理局，长沙 410209  通信作者，E-mail: xzyxzy0770@ 126． com 收稿日期: 2015--12--25 基金项目: 国家自然科学基金资助项目( 61170199) ; 湖南省大学生研究性学习和创新性实验计划资助项目( 湘教通［2015］84 号 197) ; 湖南省 教学改革研究立项资助项目( 湘教通［2016］400 号 1068) ; 广东省自然科学基金资助项目( 2015A030313501) ; 湖南省教育厅重点资助项目 ( 11A004) ; 广东省普通高校创新团队建设资助项目( 2015KCXTD014) ; 中南林业科技大学教学改革研究资助项目( ZNLJG2016--A067) 摘 要 针对设计模式识别结果的假阴性问题与重叠问题，为提高设计模式实例恢复的精确性，提出一种形式化上下无关文 法关系驱动的设计模式检测方法． 依据设计模式实例中的参与者属性及其关系，以形式化可视化语言描述模式实例的识别 文法． 在此基础上，改进该文法检测设计模式实例参与者间的附加关系，并识别共享实例的模式． 实验结果表明，新方法不仅 减少了模式实例的假阴性结果，还解决了模式实例识别的重叠问题，与其他检测方法的精确度、召回率及 F-score 指标比较， 新方法取得了较好的效果． 关键词 模式识别; 设计模式; 检测; 形式化文法 分类号 TP311 An approach for design pattern detection based on the formal context-free grammar relation driver XIAO Zhuo-yu1)  ，HE Pei2，3，4) ，YU Bo1) ，LI Yan5) ，YANG Xin-wei1) 1) Swan College，Central South University of Forestry and Technology，Changsha 410200，China 2) School of Computer Science ＆ Education Software，Guangzhou University，Guangzhou 510006，China 3) Key Laboratory of High Confidence Software Technologies of the Ministry of Education，Peking University，Beijing 100871，China 4) School of Computer and Communication Engineering，Changsha University of Science and Technology，Changsha 410114，China 5) Hunan Highway Administration Bureau，Changsha 410209，China  Corresponding author，E-mail: xzyxzy0770@ 126． com ABSTＲACT Aiming at the false negative problem and the overlap problem in pattern instance detection，in order to improve the ac￾curacy of the design pattern recovery，this article introduces an approach for design pattern detection based on the formal context-free grammar relation driver． Focusing on the attribute and relationship of classes in pattern instances，the formal grammar of pattern in￾stance identification is established using the visual language，and an improved formalism grammar is presented for identifying the addi￾tional relationships and the sharing problem of design pattern instances． Experimental results show that，compared with other well￾known algorithms by precision，recall and F-score，the proposed method can reduce the false negative results and the overlap problem in pattern instance detection，indicating the effectiveness of the proposed method． KEY WOＲDS pattern recognition; design patterns; detection; formal grammars

·1500. 工程科学学报，第38卷，第10期 设计模式封装了解决重复设计问题的有效方 的形式化文法(additional relationships formal grammars, 案”：而设计模式识别有利于软件系统的理解与维护， ARFGS),从而进一步避免设计模式实例识别过程中 并为重构软件项目提供了支持.目前国内外研究人员 出现的假阴性结果，再进一步扩展与优化ARFGS文 在设计模式检测的工具、方法、技术等方面做了大量的 法，解决了参与者共享实例而导致设计模式实例识别 研究工作.文献56]中提出一种基于子模式及 的重叠问题，并通过六个开源项目对本研究方法的识 方法签名的设计模式实例恢复方法，其思路是将设计 别效果进行了评估实验 模式中的类参与者以图形结点的形式表示出来，并将 1基于可视化符号的模式实例结构分析 图形结点间的关系表示为子图，最终通过子图匹配来 识别设计模式实例.Fontana等7-将设计模式参与者 文献21]提出了可视化语言的概念，可视化语言 信息及其关系分类成不同的micro-structures结构，从 由一组可视化字符符号与句型符号组成，是一种具有 而对设计模式实例进行恢复，文献D-11]使用机器学 关系类型名及句型属性的图形化对象，每个图形化的 习对特征信息进行训练，并通过各种聚类方法提高设 对象都具有其相关的属性，并且符号类型名可以通过 计模式识别的精度.文献02-13]引入子图同构的思 基于字符串的可视化符号来定义，而句型属性表示可 想，以邻接矩阵的形式来识别类关系图之间的相似性， 视化符号间的关系.每个可视化符号S,的属性可进行 从而挖掘设计模式实例.文献4]提出对设计模式中 编号，其值表示为S.attrtibute[n],S,表示第i个可视 主要角色的特征属性进行注释，一定程度上提高了设 化符号，n表示符号的属性数n∈{1,2，…，N}.句型 计模式实例的精确率.文献5]通过语义分析对设计 属性表示为可视化符号彼此联系的连接区域或连 模式中的结构型与行为型模式进行检测，依据模式命 接点. 名的原则，将参与者映射到实例中的主要角色，并加以 图1中，Composite模式中Component、Leaf、Com- 注释，从而减少假阴性结果.文献6]使用抽象的形 posite类及Inheritance、Aggregation等关系皆可表示为 式化语言来表示设计模式，其文法描述和代码过于分 不同的图形符号，而连接点作为句型属性对应两个不 离，以至于模式实例很难被自动识别.文献7]提出 同的端点符号.图2在图1基础上强调了句型属性. 一种自适应特征信息分类的设计模式恢复方法，该方 其中圆角矩形表示CLASS类型符号，ClassA、ClassB等 法对特征信息共享而导致的设计模式实例重叠问题缺 表示符号名，其相应的连接区域在圆角矩形中用数字 乏考虑.Gueheneuc和Antoniol提出依据源码抽取 1标注，空心圆点表示句型属性的连接点，用1、2等数 类关系的不同表示形式，使用不同的参数值来比较设 字表示，连接区域通过连接点联系起来.例如：图2中 计模式实例指标，该方法采用多阶段过滤，从而缩小搜 ClassB与Inheritance符号之间存在一个连接区域I及 索空间，进而减少了设计模式检测的复杂度.Petters- 空心连接点1，符号属性a表示描述了二者间的连接 son等网在评估真阳性(true positives)、假阳性(false 关系点，而符号属性b描述了Inheritance符号中连接 positives)、假阴性(false negatives)等参数指标的基础 点2与ClassA中连接区域1的连接关系点.表l描述 上提出一种更精确的设计模式实例评估指标F-score. 了图2中各个符号的属性列表.其中Symbol,表示第i 文献20]对设计模式角色间存在的附加关系进行了 个符号名，Attrtibute门表示符号的第j个属性. 分析，并制定了附加关系检测规则. Component 综上所述，现有设计模式实例恢复方法存在以下 主要问题：(1)设计模式实例恢复由于算法过于抽象， +….0 导致识别的召回率、精确度等结果不够理想：(2)对设 计模式实例参与者之间存在的附加关系缺乏考虑，从 Leaf Composile -children 而导致大量假阴性结果出现：(3)在识别设计模式实 for g in children HOperalion +Operalion 例过程中，未考虑到一个参与者可能同时参与了多个 中，4 g.Operation( 设计模式实例，从而导致设计模式实例识别的重叠问 题.为此，提出一种形式化上下无关文法关系驱动的 图1 Composite模式 Fig.1 Composite pattern 设计模式检测方法，旨在将软件项目中的主要特征抽 取后，将其结果表示为文献21]中描述的可视化字符 文献22]将图形表示为一个文本句子，通过交替 符号及关系句型符号等，并结合文献22]中提出的形 符号及属性来定义符号间的关系.在此基础上，笔者 式化上下无关文法描述了参与者符号间存在的关系， 对其符号及其关系以形式化文法的形式进行了扩展. 同时在文献20]制定的基于设计模式角色的附加关 定义1 SymbolA,Connect,,SymbolB. 系检测规则基础上，改进一种致力于发现该附加关系 Connect,表示符号SymbolA的连接区域或连接点

工程科学学报，第 38 卷，第 10 期 设计模式封装了解决重复设计问题的有效方 案［1］; 而设计模式识别有利于软件系统的理解与维护， 并为重构软件项目提供了支持． 目前国内外研究人员 在设计模式检测的工具、方法、技术等方面做了大量的 研究工作［2--4］． 文献［5--6］中提出一种基于子模式及 方法签名的设计模式实例恢复方法，其思路是将设计 模式中的类参与者以图形结点的形式表示出来，并将 图形结点间的关系表示为子图，最终通过子图匹配来 识别设计模式实例． Fontana 等［7--8］将设计模式参与者 信息及其关系分类成不同的 micro-structures 结构，从 而对设计模式实例进行恢复，文献［9--11］使用机器学 习对特征信息进行训练 ，并通过各种聚类方法提高设 计模式识别的精度． 文献［12--13］引入子图同构的思 想，以邻接矩阵的形式来识别类关系图之间的相似性， 从而挖掘设计模式实例． 文献［14］提出对设计模式中 主要角色的特征属性进行注释，一定程度上提高了设 计模式实例的精确率． 文献［15］通过语义分析对设计 模式中的结构型与行为型模式进行检测，依据模式命 名的原则，将参与者映射到实例中的主要角色，并加以 注释，从而减少假阴性结果． 文献［16］使用抽象的形 式化语言来表示设计模式，其文法描述和代码过于分 离，以至于模式实例很难被自动识别． 文献［17］提出 一种自适应特征信息分类的设计模式恢复方法，该方 法对特征信息共享而导致的设计模式实例重叠问题缺 乏考虑． Guéhéneuc 和 Antoniol［18］提出依据源码抽取 类关系的不同表示形式，使用不同的参数值来比较设 计模式实例指标，该方法采用多阶段过滤，从而缩小搜 索空间，进而减少了设计模式检测的复杂度． Petters￾son 等［19］在评估真阳性( true positives) 、假阳性( false positives) 、假阴性( false negatives) 等参数指标的基础 上提出一种更精确的设计模式实例评估指标 F-score． 文献［20］对设计模式角色间存在的附加关系进行了 分析，并制定了附加关系检测规则． 综上所述，现有设计模式实例恢复方法存在以下 主要问题: ( 1) 设计模式实例恢复由于算法过于抽象， 导致识别的召回率、精确度等结果不够理想; ( 2) 对设 计模式实例参与者之间存在的附加关系缺乏考虑，从 而导致大量假阴性结果出现; ( 3) 在识别设计模式实 例过程中，未考虑到一个参与者可能同时参与了多个 设计模式实例，从而导致设计模式实例识别的重叠问 题． 为此，提出一种形式化上下无关文法关系驱动的 设计模式检测方法，旨在将软件项目中的主要特征抽 取后，将其结果表示为文献［21］中描述的可视化字符 符号及关系句型符号等，并结合文献［22］中提出的形 式化上下无关文法描述了参与者符号间存在的关系， 同时在文献［20］制定的基于设计模式角色的附加关 系检测规则基础上，改进一种致力于发现该附加关系 的形式化文法( additional relationships formal grammars， AＲFGS) ，从而进一步避免设计模式实例识别过程中 出现的假阴性结果，再进一步扩展与优化 AＲFGS 文 法，解决了参与者共享实例而导致设计模式实例识别 的重叠问题，并通过六个开源项目对本研究方法的识 别效果进行了评估实验． 1 基于可视化符号的模式实例结构分析 文献［21］提出了可视化语言的概念，可视化语言 由一组可视化字符符号与句型符号组成，是一种具有 关系类型名及句型属性的图形化对象，每个图形化的 对象都具有其相关的属性，并且符号类型名可以通过 基于字符串的可视化符号来定义，而句型属性表示可 视化符号间的关系． 每个可视化符号 Si的属性可进行 编号，其值表示为 Si ． attrtibute［n］，Si表示第 i 个可视 化符号，n 表示符号的属性数 n∈{ 1，2，…，N} ． 句型 属性表示为可视化符号彼此联系的连接区域或连 接点． 图 1 中，Composite 模 式 中 Component、Leaf、Com￾posite 类及 Inheritance、Aggregation 等关系皆可表示为 不同的图形符号，而连接点作为句型属性对应两个不 同的端点符号． 图 2 在图 1 基础上强调了句型属性． 其中圆角矩形表示 CLASS 类型符号，ClassA、ClassB 等 表示符号名，其相应的连接区域在圆角矩形中用数字 1 标注，空心圆点表示句型属性的连接点，用 1、2 等数 字表示，连接区域通过连接点联系起来． 例如: 图 2 中 ClassB 与 Inheritance 符号之间存在一个连接区域 1 及 空心连接点 1，符号属性 a 表示描述了二者间的连接 关系点，而符号属性 b 描述了 Inheritance 符号中连接 点 2 与 ClassA 中连接区域 1 的连接关系点． 表 1 描述 了图 2 中各个符号的属性列表． 其中 Symboli表示第 i 个符号名，Attrtibute［j］表示符号的第 j 个属性． 图 1 Composite 模式 Fig． 1 Composite pattern 文献［22］将图形表示为一个文本句子，通过交替 符号及属性来定义符号间的关系． 在此基础上，笔者 对其符号及其关系以形式化文法的形式进行了扩展． 定义 1 SymbolA，Connecti，j ，SymbolB． Connecti，j表示符号SymbolA的连接区域或连接点 · 0051 ·

肖卓宇等：一种形式化上下无关文法关系驱动的设计模式检测方法 ·1501· Connect,表示符号SymbolA的连接区域或连接点 i和SymbolB的连接区域或连接点j之间不存在联系， n表示不同符号间的关系，ne{1,2,…,N}.依据上述 定义，图2的Composite模式可描述为： ClassA Connect2 Inheritance Connect ClassB Connect2 ClassB ClassC Inheritance Connect ClassC Connect Aggregation. (4) 图2 Composite模式句型属性 图2中ClassA符号表示为圆角矩形，而圆角矩形 Fig.2 Syntactic attributes of Composite pattern 内的1表示该符号的连接区域，连接区域附近的空心 表1符号属性表 圆点2表示该符号的连接点，依据定义1，式(4)中 Table 1 Symbol attribute table ClassA符号的连接区域1与表1中符号属性点b]处 Symbol Attrtibute [1] Attrtibute 的连接点2表示为Connect,2,可与Inheritance符号进 ClassA Le] 行连接，同理，Inheritance符号通过Connect.!连接符号 ClassB H ClassB.考虑到不只ClassB符号与Inheritance存在联 ClassC 回 C 系，依据定义2，ClassC与nheritance的联系表示为 Aggregation [d山 Le] Connect.2,而ClassC与ClassA之间除继承关系外还存 Inheritance a 0] 在聚合关系.符号ClassC与符号Aggregation之间通过 Inheritance 时 ] Connect.,表示，并在表I中的ClassC符号属性点[d 处进行连接 i与SymbolB的连接区域或连接点j存在联系.例如： 基于上述定义，引入一种类似于上下文无关文法 图2中ClassA与ClassB符号的关系可表示为 的形式化语法.该语法通过产生式来交替终结符符号 ClassA Connect.2 Inheritance Connect ClassB.(1) 与非终结符符号，并结合文献22]中提出的符号属性 式中Connect,2表示符号ClassA的连接区域1与符号 来描述类图.图2中的Composite设计模式可描述 Inheritance的连接点2存在联系，而Inheritance的连接 如下： 点1与ClassB的连接区域l通过Connect.!连接.值得 Composite_pattern-Component Connect.2 Inheritance 注意的是符号与符号的连接存在多样性，如ClassC的 Connect Leaf Connecti Inheritance 连接区域I不仅与符号Inheritance的连接点1有联 Connect.Composite Connect Aggregation.(5) 系，同时也与Aggregation符号的连接点1存在联系，为 Component→CLASS△：{Component,,=CLASS,}. 解决这个问题，给出定义2. (6) 定义2 SymbolA Connect SymbolB Leaf=CLASS△：{Lead,=CLASS,}. (7) 定义2中Connect,的指数上标n用来区分符号间 Composite→CLASS△：{Composite,=CLASS:}.(8) 不同的关系.例如：ClassC符号与Inheritance符号可表 式(5)给出了Composite模式的形式化语法实现， 示为 式中非终结符Component,.Leaf和Composite符号通过 ClassC Connect Inheritance. (2) Inheritance、Aggregation等终结符进行了可视化字符串 ClassC符号不仅与Inheritance符号存在关系，也 的连接.式(6)~式(8)中，△规则用来关联产生式左 与Aggregation符号有关联，见下式： 侧的非终结符与右侧终结符的初始化属性值，例如：式 ClassC Connecti.Aggregation. (3) (6)中符号Component的属性i关联了CLASS属性i 式中Connect..,表示ClassC符号的连接区域1与Ag- 的值.使用基于上下无关文法的产生式允许扩展经典 gregation符号的连接点1存在联系.这样能够处理与 的LR分析技术及一些经典的自动文法生成工具，克 式(2)的冲突.为了表示符号之间的关系集合，给出定 服了文献22]中提出的可视化文法低效性问题.事实 义3. 上，本研究提出的基于形式化上下无关文法关系驱动 定义3 SymbolA{Connect}SymbolB 的方法集合了表1中不同符号存储的属性值.图3描 定义3表示符号SymbolA的连接区域或连接点i 述了Composite模式实例的识别过程.通过式(5)~ 与SymbolB连接区域或连接点j之间存在多种关系的 (8)的定义，使用△规则来将产生式左侧的非终结符 集合，n表示符号间关系数n∈{1,2，…，N}. 与右侧终结符进行映射，并给出符合规范的输入符号 定义4 SymbolA Connect?,SymbolB. 及句型属性

肖卓宇等: 一种形式化上下无关文法关系驱动的设计模式检测方法 图 2 Composite 模式句型属性 Fig． 2 Syntactic attributes of Composite pattern 表 1 符号属性表 Table 1 Symbol attribute table Symboli Attrtibute［1］ Attrtibute［2］ ClassA ［b］ ［e］ ClassB ［a］ ClassC ［c］ ［d］ Aggregation ［d］ ［e］ Inheritance ［a］ ［b］ Inheritance ［c］ ［b］ i 与 SymbolB 的连接区域或连接点 j 存在联系． 例如: 图 2 中 ClassA 与 ClassB 符号的关系可表示为 ClassA Connect1，2 Inheritance Connect1，1 ClassB． ( 1) 式中 Connect1，2表示符号 ClassA 的连接区域 1 与符号 Inheritance 的连接点 2 存在联系，而 Inheritance 的连接 点 1 与 ClassB 的连接区域 1 通过 Connect1，1连接． 值得 注意的是符号与符号的连接存在多样性，如 ClassC 的 连接区域 1 不仅与符号 Inheritance 的连接点 1 有联 系，同时也与 Aggregation 符号的连接点 1 存在联系，为 解决这个问题，给出定义 2． 定义 2 SymbolA Connectn i，j SymbolB． 定义 2 中 Connectn i，j的指数上标 n 用来区分符号间 不同的关系． 例如: ClassC 符号与 Inheritance 符号可表 示为 ClassC Connect1，1 Inheritance． ( 2) ClassC 符号不仅与 Inheritance 符号存在关系，也 与 Aggregation 符号有关联，见下式: ClassC Connect2 1，1 Aggregation． ( 3) 式中 Connect2 1，1 表示 ClassC 符号的连接区域 1 与 Ag￾gregation 符号的连接点 1 存在联系． 这样能够处理与 式( 2) 的冲突． 为了表示符号之间的关系集合，给出定 义 3． 定义 3 SymbolA { Connectn i，j } SymbolB． 定义 3 表示符号 SymbolA 的连接区域或连接点 i 与 SymbolB 连接区域或连接点 j 之间存在多种关系的 集合，n 表示符号间关系数 n∈{ 1，2，…，N} ． 定义 4 SymbolA  Connectn i，j SymbolB． Connectn i，j表示符号 SymbolA 的连接区域或连接点 i 和 SymbolB 的连接区域或连接点 j 之间不存在联系， n 表示不同符号间的关系，n∈{ 1，2，…，N} ． 依据上述 定义，图 2 的 Composite 模式可描述为: ClassA Connect1，2 Inheritance Connect1，1 ClassB Connect2 1，2 Inheritance Connect1，1 ClassC Connect2 1，1 Aggregation． ( 4) 图 2 中 ClassA 符号表示为圆角矩形，而圆角矩形 内的 1 表示该符号的连接区域，连接区域附近的空心 圆点 2 表示该符号的连接点，依据定义 1，式( 4) 中 ClassA 符号的连接区域 1 与表 1 中符号属性点［b］处 的连接点 2 表示为 Connect1，2，可与 Inheritance 符号进 行连接，同理，Inheritance 符号通过 Connect1，1连接符号 ClassB． 考虑到不只 ClassB 符号与 Inheritance 存在联 系，依 据 定 义 2，ClassC 与 Inheritance 的 联 系 表 示 为 Connect2 1，2，而 ClassC 与 ClassA 之间除继承关系外还存 在聚合关系． 符号 ClassC 与符号 Aggregation 之间通过 Connect2 1，1表示，并在表 1 中的 ClassC 符号属性点［d］ 处进行连接． 基于上述定义，引入一种类似于上下文无关文法 的形式化语法． 该语法通过产生式来交替终结符符号 与非终结符符号，并结合文献［22］中提出的符号属性 来描 述 类 图． 图 2 中 的 Composite 设 计 模 式 可 描 述 如下: Composite_patternComponent Connect1，2 Inheritance Connect1，1 Leaf Connect2 1，2 Inheritance Connect1，1 Composite Connect2 1，1 Aggregation． ( 5) Component CLASS Δ: { Componenti = CLASSi} ． ( 6) LeafCLASS Δ: { Leafi = CLASSi} ． ( 7) Composite CLASS Δ: { Compositei = CLASSi} ． ( 8) 式( 5) 给出了 Composite 模式的形式化语法实现， 式中非终结符 Component、Leaf 和 Composite 符号通过 Inheritance、Aggregation 等终结符进行了可视化字符串 的连接． 式( 6) ～ 式( 8) 中，Δ 规则用来关联产生式左 侧的非终结符与右侧终结符的初始化属性值，例如: 式 ( 6) 中符号 Component 的属性 i 关联了 CLASS 属性 i 的值． 使用基于上下无关文法的产生式允许扩展经典 的 LＲ 分析技术及一些经典的自动文法生成工具，克 服了文献［22］中提出的可视化文法低效性问题． 事实 上，本研究提出的基于形式化上下无关文法关系驱动 的方法集合了表 1 中不同符号存储的属性值． 图 3 描 述了 Composite 模式实例的识别过程． 通过式( 5) ～ ( 8) 的定义，使用 Δ 规则来将产生式左侧的非终结符 与右侧终结符进行映射，并给出符合规范的输入符号 及句型属性． · 1051 ·

·1502· 工程科学学报，第38卷，第10期 softset 公式6 Component +Get_order( +. produet softcomposite pmdnet softcomposite +Get_order() +Get_order() +Get_order0 +Getorder) Composite +0 +0 +0 +0 paltern 步醉 步豫B} 步骤E 一=三========= Component 公式5) 7八 sollcomposite Leaf Leal Composite +Get_order() +0 步骤D 公式8 图3 Composite模式识别步骤 Fig.3 Recognition step for Composite patter 图3的步骤A中，虚线框表示要通过产生式处理 Component 的符号，语法分析器开始搜寻充当Component角色的 CLASS符号.因此，依据△规则，并应用式(6)，CLASS +Operalion( +, 符号被替换为非终结符Component,步骤B描述了替 换后的结果.然后，语法分析器通过Connect1.2搜寻连 Composile -children 接Component符号的Inheritance符号.同理，使用式 Association for g in children (7),步骤B中虚线框对应的CLASS符号替换为非终 十，，} 十， g.Operation() 结符Leaf,再使用式(8)，步骤C中虚线框对应的 Inheritance CLASS符号替换为非终结符Composite,步骤D阶段之 图4 Composite模式附加关系 后，应用式(5)搜寻各符号属性间的关系，并发现了一 Fig.4 Additional relationships of Composite pattern 个完整的Composite模式实例，见步骤E. 2设计模式参与者符号间的附加关系 通过增加产生式规则来提升识别附加关系的能力.依 据式(11)与式(12)，如符号间关系满足附加关系标 第1节中，形式化文法一定程度上描述了符号间 的关系，但对其附加关系缺乏考虑m,为解决这个问 准，则Composite模式实例识别时，其附加关系标志ac- cess将被标记为1，表示已访问，从而在后续识别过程 题，提出一种检测类符号间附加关系的形式化文法 中不再考虑该符号关系的检索.为此，将式(9)中关联 (additional relationships formal grammars,ARFGS), 其他属性的CLASS符号标识为Tagging,并跟踪已被文 文法涉及符号间关系处理的机制，并能在文献22]基 法分析的符号，Tagging初值设置为0. 础上构建更为严谨的文法.ARFGS制定了符号间附加 Composite_pattern→ 关系的形式化文法，从而避免设计模式检测时假阴性 实例被识别后导致的结果误差.图4中虚线为Com- Component Connect.2 Inheritance Connect. posite模式符号间的附加关系，为识别附加关系制定下 Leaf Connect.2 Inheritance {Connect Tagging} 述2条规则. Composite Connect,Connect}Aggregation. 规则1Leaf与Composite类之间不存在继承(In- (9) heritance).关系. Component =CLASS A:{Component,=CLASS,}. 规则2Leaf与Composite类之间不存在关联(As- (10) sociate)关系. Leaf Leaf Connect.2 Inheritance Connect. 为执行检测规则1与规则2，ARFGS形式化文法 CLASS△：{Lead,=Leaf}

工程科学学报，第 38 卷，第 10 期 图 3 Composite 模式识别步骤 Fig． 3 Ｒecognition step for Composite pattern 图 3 的步骤 A 中，虚线框表示要通过产生式处理 的符号，语法分析器开始搜寻充当 Component 角色的 CLASS 符号． 因此，依据 Δ 规则，并应用式( 6) ，CLASS 符号被替换为非终结符 Component，步骤 B 描述了替 换后的结果． 然后，语法分析器通过 Connect1，2搜寻连 接 Component 符号的 Inheritance 符号． 同理，使用式 ( 7) ，步骤 B 中虚线框对应的 CLASS 符号替换为非终 结符 Leaf，再 使 用 式 ( 8 ) ，步 骤 C 中 虚 线 框 对 应 的 CLASS 符号替换为非终结符 Composite，步骤 D 阶段之 后，应用式( 5) 搜寻各符号属性间的关系，并发现了一 个完整的 Composite 模式实例，见步骤 E． 2 设计模式参与者符号间的附加关系 第 1 节中，形式化文法一定程度上描述了符号间 的关系，但对其附加关系缺乏考虑［20］． 为解决这个问 题，提出一种检测类符号间附加关系的形式化文法 ( additional relationships formal grammars，AＲFGS) ，该 文法涉及符号间关系处理的机制，并能在文献［22］基 础上构建更为严谨的文法． AＲFGS 制定了符号间附加 关系的形式化文法，从而避免设计模式检测时假阴性 实例被识别后导致的结果误差． 图 4 中虚线为 Com￾posite 模式符号间的附加关系，为识别附加关系制定下 述 2 条规则． 规则 1 Leaf 与 Composite 类之间不存在继承( In￾heritance) 关系． 规则2 Leaf 与 Composite 类之间不存在关联( As￾sociate) 关系． 为执行检测规则 1 与规则 2，AＲFGS 形式化文法 图 4 Composite 模式附加关系 Fig． 4 Additional relationships of Composite pattern 通过增加产生式规则来提升识别附加关系的能力． 依 据式( 11) 与式( 12) ，如符号间关系满足附加关系标 准，则 Composite 模式实例识别时，其附加关系标志 ac￾cess 将被标记为 1，表示已访问，从而在后续识别过程 中不再考虑该符号关系的检索． 为此，将式( 9) 中关联 其他属性的 CLASS 符号标识为 Tagging，并跟踪已被文 法分析的符号，Tagging 初值设置为 0． Composite_pattern Component Connect1，2 Inheritance Connect1，1 Leaf Connect2 1，2 Inheritance{ Connect1，1， Tagging} Composite { Connect1，1，Connect3 1，2 } Aggregation． ( 9) Component CLASS Δ: { Componenti = CLASSi} ． ( 10) Leaf Leaf' Connect1，2 Inheritance Connect1，1 CLASS Δ: { Leaf1 = Leaf'1 } · 2051 ·

肖卓字等：一种形式化上下无关文法关系驱动的设计模式检测方法 ·1503· T:((CLASS CLASS;=CLASSCLASS=1)). 图6中两个Composite模式实例共享了类符号 (11) CLASSA与CLASSB,但如文法开始符号选定为 Leaf =Leaf Connect.2 Association Connect. CLASSC,通过第2节中定义的产生式搜寻CLASSA与 CLASS△：{Leaf=Leaf} CLASSB符号及其三者之间的关系，左侧虚线框中的 T:((CLASS CLASS;=CLASS CLASS=1)). Composite模式实例1将被识别出来，这样的方法并没 (12) 有考虑到CLASSA与CLASSB符号是可以共享的.事 Leaf→CLASS△：{Leaf=CLASS,}. (13) 实上，如果开始符号选定的不是CLASSC而是 Composite→CLASS△：{Composite.=CLASS,}. CLASSC',再次通过第2节中定义的产生式搜寻 (14) CLASSA与CLASSB符号及其三者之间的关系，则最终 本研究在文献21]提出的下规则上，引入新的终 被识别出来的是右侧虚线框中的Composite模式实 结符符号描述上述产生式.式(Il)描述Leaf符号的 例2. 属性1与Leaf符号的属性1在识别过程中存在映射 Composile 关系，并具有相同的值.另一个新的符号CLASS被引 Composite CLASSA 模式实例2 模式实例1 入，它继承了CLASS符号属性1的值，其附加关系标 十 志access置为I,所有的CLASS联系Leaf需通过一个 nheritance关系.相似的产生式(12)中CLASS符号的 CLASSC CLASSB CLASSC dre 附加关系标志access也设置为l,所有的CLASS联系 +Operation() 0 Leaf需通过一个Association关系，避免下次识别过程 0 再次检测该附加关系，从而很大程度上减低了假阴性 图6 Composite模式重叠 结果.如access属性值为0，则产生式(9)中的Tagging Fig.6 Overlapped composite pattern 无需标记，这意味着违反规则1和规则2定义的附加 关系检测规则. CLASS符号及其关系的共享不限于相同设计模式 以图5为例，该图是Jhotdraw开源系统中的类关 实例的重叠，同样也适用于不同设计模式实例的重叠 系图，依据产生式(9)~式(14)，该实例不能被识别为 图7是JhotDraw系统中的类关系图.其Composite模 Composite模式，因为Composite Figure类中的方法draw 式与Decorator模式存在重叠，Composite模式实例与 (g)被Figure类的方法draw(g)代理，这是一个典型的 Decorator模式实例共享了类符号Abstract Figure、Com- 附加关系，违反了规则2，依据式(9)，Figure类不能被 posite Figure和Decorator Figure.但如果开始符号选定 Composite模式中的Leaf类替换. 为Border Decorator,通过第2节中定义的产生式搜寻 AbstractFigure Scroll Decorator、Abstract Figure、Composite Figure和 Decorator Figure符号及其关系，外侧虚线框中的Deco- CompositeFigure.draw(g) rator模式实例将被识别出来，但这样的做法并没有考 虑到Abstract Figure、Composite Figure和Decorator Fig-- Figure CompositeFigure -children ure是可以共享的，其直接结果将导致内侧虚线框中的 +draw(in g) Composite模式实例不能被识别. 十 +.…0 解决上述问题首先需确定选择哪个CLASS符号 图5类图违反规则2 作为开始符号，并依据文法对收索结果依次进行记录 Fig.5 Class diagram violating negative Rule 2 该方法要求每个CLASS符号都至少有一次被选定为 产生式的开始符号，当一个类参与者担任多个设计模 3识别重叠的设计模式实例 式实例的起始符至少一次时，可解决符号共享导致的 在识别设计模式实例过程中，一个类可能参与多 实例重叠问题.图6中CLASSA类共享了两个Com- 个设计模式实例，可理解为类参与者由于共享模式实 posite模式实例，可以考虑作为起始符两次.为了不影 例而导致的实例重叠问题.这类问题产生原因是因为 响文中1、2节得出的结果，上述问题将扩展ARFGS形 通过随机搜寻类图中的CLASS符号作为文法的开始 式化文法来解决.为此，引入递归思想来解决共享问 符号，当匹配到某种设计模式实例时，即认为识别成 题，并通过指定下述文法的产生式来解决 功，而忽略了CLASS符号的共享问题，这样的方法不 CompositePattern Components. (15) 能保证所有模式实例识别的成功. Components -Components Connect.2 Inheritance

肖卓宇等: 一种形式化上下无关文法关系驱动的设计模式检测方法 Γ: { ( CLASS' : CLASS'1 = CLASS1 ; CLASS'access = 1) } ． ( 11) Leaf Leaf Connect1，2 Association Connect1，1 CLASS Δ: { Leaf1 = Leaf'1 } Γ: { ( CLASS' : CLASS'1 = CLASS1 ; CLASS'access = 1) } ． ( 12) Leaf CLASS Δ: { Leafi = CLASSi} ． ( 13) Composite CLASS Δ: { Compositei = CLASSi} ． ( 14) 本研究在文献［21］提出的 Γ 规则上，引入新的终 结符符号描述上述产生式． 式( 11) 描述 Leaf 符号的 属性 1 与 Leaf'符号的属性 1 在识别过程中存在映射 关系，并具有相同的值． 另一个新的符号 CLASS'被引 入，它继承了 CLASS 符号属性 1 的值，其附加关系标 志 access 置为 1，所有的 CLASS 联系 Leaf 需通过一个 Inheritance 关系． 相似的产生式( 12) 中 CLASS'符号的 附加关系标志 access 也设置为 1，所有的 CLASS 联系 Leaf 需通过一个 Association 关系，避免下次识别过程 再次检测该附加关系，从而很大程度上减低了假阴性 结果． 如 access 属性值为 0，则产生式( 9) 中的 Tagging 无需标记，这意味着违反规则 1 和规则 2 定义的附加 关系检测规则． 以图 5 为例，该图是 Jhotdraw 开源系统中的类关 系图，依据产生式( 9) ～ 式( 14) ，该实例不能被识别为 Composite 模式，因为 Composite Figure 类中的方法 draw ( g) 被 Figure 类的方法 draw( g) 代理，这是一个典型的 附加关系，违反了规则 2，依据式( 9) ，Figure 类不能被 Composite 模式中的 Leaf 类替换． 图 5 类图违反规则 2 Fig． 5 Class diagram violating negative Ｒule 2 3 识别重叠的设计模式实例 在识别设计模式实例过程中，一个类可能参与多 个设计模式实例，可理解为类参与者由于共享模式实 例而导致的实例重叠问题． 这类问题产生原因是因为 通过随机搜寻类图中的 CLASS 符号作为文法的开始 符号，当匹配到某种设计模式实例时，即认为识别成 功，而忽略了 CLASS 符号的共享问题，这样的方法不 能保证所有模式实例识别的成功． 图 6 中 两 个 Composite 模 式 实 例 共 享 了 类 符 号 CLASSA 与 CLASSB，但 如 文 法 开 始 符 号 选 定 为 CLASSC，通过第 2 节中定义的产生式搜寻 CLASSA 与 CLASSB 符号及其三者之间的关系，左侧虚线框中的 Composite 模式实例 1 将被识别出来，这样的方法并没 有考虑到 CLASSA 与 CLASSB 符号是可以共享的． 事 实 上，如 果 开 始 符 号 选 定 的 不 是 CLASSC 而 是 CLASSC’，再 次 通 过 第 2 节中定义的产生式搜寻 CLASSA 与 CLASSB 符号及其三者之间的关系，则最终 被识别 出 来 的 是 右 侧 虚 线 框 中 的 Composite 模 式 实 例 2． 图 6 Composite 模式重叠 Fig． 6 Overlapped composite pattern CLASS 符号及其关系的共享不限于相同设计模式 实例的重叠，同样也适用于不同设计模式实例的重叠． 图 7 是 JhotDraw 系统中的类关系图． 其 Composite 模 式与 Decorator 模式存在重叠，Composite 模式实例与 Decorator 模式实例共享了类符号 Abstract Figure、Com￾posite Figure 和 Decorator Figure． 但如果开始符号选定 为 Border Decorator，通过第 2 节中定义的产生式搜寻 Scroll Decorator、Abstract Figure、Composite Figure 和 Decorator Figure 符号及其关系，外侧虚线框中的 Deco￾rator 模式实例将被识别出来，但这样的做法并没有考 虑到 Abstract Figure、Composite Figure 和 Decorator Fig￾ure 是可以共享的，其直接结果将导致内侧虚线框中的 Composite 模式实例不能被识别． 解决上述问题首先需确定选择哪个 CLASS 符号 作为开始符号，并依据文法对收索结果依次进行记录． 该方法要求每个 CLASS 符号都至少有一次被选定为 产生式的开始符号，当一个类参与者担任多个设计模 式实例的起始符至少一次时，可解决符号共享导致的 实例重叠问题． 图 6 中 CLASSA 类共享了两个 Com￾posite 模式实例，可以考虑作为起始符两次． 为了不影 响文中 1、2 节得出的结果，上述问题将扩展 AＲFGS 形 式化文法来解决． 为此，引入递归思想来解决共享问 题，并通过指定下述文法的产生式来解决． CompositePattern Components． ( 15) Components Components Connect1，2 Inheritance · 3051 ·

·1504. 工程科学学报，第38卷，第10期 存在继承关系的Leaf符号，结合图6，并依据式(17)， AhstractFigure Composite模式 Component与Leaf的继承关系不存在重叠.式(21)与 式(22)目的是避免CLASS符号间引入Inheritance与 +Operalion() +,, Association附加关系. 图8描述了存在重叠的Composite模式实例识别 Cm叮ositeFigure DecoralorFigure rhi dre 过程，图中有三个重叠的Composite模式实例，其中 CLASSA可替换为Component,CLASSB可替换为Com- +Operation() +Operation( +0 +0 posite,而CLASSC、CLASSC和CLASSC"可替换为Leaf, 依据式(15)~式(24)，识别过程的起始符定义为 BorderDecoralor ScrollDecoralor CLASSA,而被识别出的Composite模式实例用虚线框 I Decoralor模式 表示.步骤A、步骤B和步骤C依次识别出Composite +.0 十.0 模式实例1、Composite模式实例2和Composite模式实 例3，而在步骤D全部3个Composite模式实例皆被成 图7 Composite模式与Decorator模式重叠 功检测出来 Fig.7 Overlapping between Composite and Decorator pattem 4 设计模式实例识别步骤 Connecti.Composites A:{Components,=Components,}. (16) 设计模式实例识别包括五个主要步骤，见图9. Components Component Connect2 Inheritance Connect. 步骤1通过逆向工程工具E.T.切抽取特征 Composites A:{Components,Component,)(17) 信息. Component Component'Connect.2 Aggregation Connect. 步骤2在步骤1基础上对可视化符号进行 CLASS△：{Component,=Componenti} 分析. T:((CLASS CLASS=CLASS )) (18) 步骤3在步骤2基础上，形式化描述设计模式 Component→CLASS△：{Component,=CLASS,}. 实例 (19) 步骤4对步骤3结果进行优化，制定设计模式 Component -Components Connect2 Inheritance Connect 参与者间的附加关系检测规则. Leaf△：{Components,=Components,}.(20) 步骤5进一步恢复重叠的设计模式实例. Composites =Composites'Connect.Inheritance 5 实验设计与评估 {Connect.l,Tagging}Leaf△：{Composites,= Composites,} 为评估本研究的有效性，选用JhotDraw等六个开 T:{(CLASS:CLASS =Leaf :CLASS=1)}.(21) 源系统进行了设计模式实例识别实验.表2展示了这 Composites-Composites Connect.Association 些开源系统的特征参数，执行实验的操作系统采用 (ConnectTagging)Leaf WINDOW7,CPU为INTEL Core2G6302.7GHz,内存8G. △：{Composites,=Composites,} 表2开源系统特征参数 T:((CLASS CLASS,Leaf CLASS=1)). Table 2 Characteristic parameters of the open source system (22) 开源项目名称 类的数目 千行代码的数目 Composite→CLASS△：{Composite1=CLASS,}. JhotDraw 6.0bl 300 g (23) Dom4j1.6.1 179 18 Leaf→CLASS△：{Leaf=CLASS}.(24) Junit v3.8 56 式(15)考虑了一个类符号可以参与多个模式实 Apache ant vl.6.2 79566 895 例识别的问题，式(16)~式(20)通过对开始符号引入 Quick UML2001 8792 203 递归的思想来担任多个Composite模式实例的Compo- JavaAWT 5.0 345 56 nenl及Composite角色.式(16)与式(17)允许Compo-- nenl作为一个开始符号遍历所有可能存在继承关系的 5.1 指标评估实验 Composite符号.式(18)与式(19)描述了能与Compos-. 实验评估采用精确度Precision(P)、召回率Recall ite符号之间存在Aggregation关系的CLASS符号.式 (R)、正确性Accuracy(A)、F-score等指标.值得注意 (20)描述了Component作为一个开始符遍历所有可能 的是当待识别系统规模较大时，假阳性FP(false posi--

工程科学学报，第 38 卷，第 10 期 图 7 Composite 模式与 Decorator 模式重叠 Fig． 7 Overlapping between Composite and Decorator pattern Connect1，1 Composites Δ: { Components1 = Components1 } ． ( 16) Components Component Connect1，2 Inheritance Connect1，1 Composites Δ: { Components1 = Component1 } ． ( 17) Component Component' Connect1，2 Aggregation Connect1，1 CLASS Δ: { Component1 = Component'1 } Γ: { ( CLASS' : CLASS'1 = CLASS1 ) } ． ( 18) Component CLASS Δ: { Component1 = CLASS1 } ． ( 19) Component Components Connect1，2 Inheritance Connect1，1 Leaf Δ: { Components1 = Components1 } ． ( 20) Composites Composites' Connect1，1 Inheritance { Connect2 1，1， Tagging} Leaf Δ: { Composites1 = Composites'1 } Γ: { ( CLASS: CLASS1 = Leaf1 ; CLASSaccess = 1) } ． ( 21) Composites Composites Connect1，1 Association { Connect2 1，1， Tagging} Leaf Δ: { Composites1 = Composites1 } Γ: { ( CLASS : CLASS1 = Leaf1 ; CLASSaccess = 1) } ． ( 22) Composite CLASS Δ: { Composite1 = CLASS1 } ． ( 23) Leaf CLASS Δ: { Leaf1 = CLASS1 } ． ( 24) 式( 15) 考虑了一个类符号可以参与多个模式实 例识别的问题，式( 16) ～ 式( 20) 通过对开始符号引入 递归的思想来担任多个 Composite 模式实例的 Compo￾nent 及 Composite 角色． 式( 16) 与式( 17) 允许 Compo￾nent 作为一个开始符号遍历所有可能存在继承关系的 Composite 符号． 式( 18) 与式( 19) 描述了能与 Compos￾ite 符号之间存在 Aggregation 关系的 CLASS 符号． 式 ( 20) 描述了 Component 作为一个开始符遍历所有可能 存在继承关系的 Leaf 符号，结合图 6，并依据式( 17) ， Component 与 Leaf 的继承关系不存在重叠． 式( 21) 与 式( 22) 目的是避免 CLASS 符号间引入 Inheritance 与 Association 附加关系． 图 8 描述了存在重叠的 Composite 模式实例识别 过程，图中 有 三 个 重 叠 的 Composite 模 式 实 例，其 中 CLASSA 可替换为 Component，CLASSB 可替换为 Com￾posite，而 CLASSC、CLASSC'和 CLASSC″可替换为 Leaf， 依据式( 15 ) ～ 式 ( 24 ) ，识别过程的起始符定义为 CLASSA，而被识别出的 Composite 模式实例用虚线框 表示． 步骤 A、步骤 B 和步骤 C 依次识别出 Composite 模式实例 1、Composite 模式实例 2 和 Composite 模式实 例 3，而在步骤 D 全部 3 个 Composite 模式实例皆被成 功检测出来． 4 设计模式实例识别步骤 设计模式实例识别包括五个主要步骤，见图 9． 步骤 1 通 过 逆 向 工 程 工 具 F． T． ［17］ 抽取 特 征 信息． 步骤 2 在 步 骤 1 基础上对可视化符号进行 分析． 步骤 3 在步骤 2 基础上，形式化描述设计模式 实例． 步骤 4 对步骤 3 结果进行优化，制定设计模式 参与者间的附加关系检测规则． 步骤 5 进一步恢复重叠的设计模式实例． 5 实验设计与评估 为评估本研究的有效性，选用 JhotDraw 等六个开 源系统进行了设计模式实例识别实验． 表 2 展示了这 些开源系统的特征参数，执行实验的操作系统采用 WINDOW7，CPU 为 INTEL Core2 G630 2. 7 GHz，内存8 G． 表 2 开源系统特征参数 Table 2 Characteristic parameters of the open source system 开源项目名称 类的数目 千行代码的数目 JhotDraw 6. 0b1 300 19 Dom4j 1. 6. 1 179 18 Junit v3. 8 56 4 Apache ant v1. 6. 2 79566 895 Quick UML2001 8792 203 JavaAWT 5. 0 345 56 5. 1 指标评估实验 实验评估采用精确度 Precision ( P) 、召回率 Ｒecall ( Ｒ) 、正确性 Accuracy ( A) 、F-score 等指标． 值得注意 的是当待识别系统规模较大时，假阳性 FP ( false posi- · 4051 ·

肖卓字等：一种形式化上下无关文法关系驱动的设计模式检测方法 ·1505· Composite模式实例1 CLASSC" Composite模式实例l .0 (omposite模式实例2 CLASSA CLASSA +Operation( +Operation( 十。……} CLASSC CLASSB CLASSC' CLASSC CLASSB CLASSC' +Operation( t.0 …0 t0 t0 步骤A 步骤B Composite模式实例1 Composite模式实例l omi式实例3 CLASSA Composite模式实例2 Composite模式实例3 +Operation) Composite 十.0 模式实例2 A CLASSR CLASSC 步骤D hildren +Operation() 十 步骤C 图8重叠的Composite模式识别过程 Fig.8 Recognition process of overlapped Composite pattern 形式化 制定模式 式(25)中P表示精确度，式(26)中R表示召回率，式 源码 可视化语言 描述设计 实例的 恢复重叠 抽取 表示信总 模式实例 (27)中A表示正确性. 模式实伤例 附加关系 检测规则 依据表3，JhotDraw6.Obl中State、Template、Visi- 图9设计模式实例识别流程 tor、Singleton和Adapter五个模式存在假阴性FN,从而 Fig.9 Design pattern instance identification flow chart 导致召回率R与正确性A受到影响.表3 Apache ant vl.6.2系统中State、Singleton、Factory method、Bridge、 tive)、假阴性FN(false negative)的识别结果容易出现 Visitor和Adapter六个模式存在假阴性FN.表4中 偏差.此外，精确度和召回率指标之间的关系确定了 Junit3.8仅有Adapter一个模式存在假阴性FN. 方法的实用与否，而精确度和召回率在进行设计模式 检测时依赖于四个重要指标，即真阳性(true positive, Apache ant vl.6.2中Factory method、Bridge和Visitor TP)、假阳性(false positive,FP)、真阴性(true negative, 模式也存在假阴性FN(false negative).表5中Quick UML2OOl系统的State与Adapter模式存在假阴性FN, TN)和假阴性(false negative,FN). Java AWT5.0中只有Decorator模式不存在假阴性 (1)真阳性TP:表示正确实例识别为正确. FN. (2)假阳性FP:表示错误实例识别为正确. 综合表3~表5数据分析发现以下两个显著的 (3)真阴性TN:表示错误实例识别为错误. (4)假阴性FN:表示正确实例识别为错误 问题 (1)六个测试系统中，State模式的假阴性结果FN TP P=TP+FP (25) 在其中四个开源系统都存在，由于另外两个测试系统 TP Junit3.8和Apache ant vl.6.2未识别到State模式实 R=TP+FN (26) 例.统计发现，在已识别出State模式实例存在假阴性 TP +TN 结果FN的概率为lOO%.State模式在表3 JhotDraw A=TP+FP +TN+FN (27) 6.0b1与Do4j1.6.1系统的召▣率R分别为80%与

肖卓宇等: 一种形式化上下无关文法关系驱动的设计模式检测方法 图 8 重叠的 Composite 模式识别过程 Fig． 8 Ｒecognition process of overlapped Composite pattern 图 9 设计模式实例识别流程 Fig． 9 Design pattern instance identification flow chart tive) 、假阴性 FN ( false negative) 的识别结果容易出现 偏差． 此外，精确度和召回率指标之间的关系确定了 方法的实用与否，而精确度和召回率在进行设计模式 检测时依赖于四个重要指标，即真阳性( true positive， TP) 、假阳性( false positive，FP) 、真阴性( true negative， TN) 和假阴性( false negative，FN) ． ( 1) 真阳性 TP: 表示正确实例识别为正确． ( 2) 假阳性 FP: 表示错误实例识别为正确． ( 3) 真阴性 TN: 表示错误实例识别为错误． ( 4) 假阴性 FN: 表示正确实例识别为错误． P = TP TP + FP． ( 25) Ｒ = TP TP + FN． ( 26) A = TP + TN TP + FP + TN + FN ( 27) 式( 25) 中 P 表示精确度，式( 26) 中 Ｒ 表示召回率，式 ( 27) 中 A 表示正确性． 依据表 3，JhotDraw 6. 0b1 中 State、Template、Visi￾tor、Singleton 和 Adapter 五个模式存在假阴性 FN，从而 导致召回率 Ｒ 与正确性 A 受到影响． 表 3 Apache ant v1. 6. 2 系统中 State、Singleton、Factory method、Bridge、 Visitor 和 Adapter 六个模式存在假阴性 FN． 表 4 中 Junit 3. 8 仅 有 Adapter 一个模式存在假阴性 FN． Apache ant v1. 6. 2 中 Factory method、Bridge 和 Visitor 模式也存在假阴性 FN( false negative) ． 表 5 中 Quick UML2001 系统的 State 与 Adapter 模式存在假阴性 FN， Java AWT 5. 0 中 只 有 Decorator 模式不存在假阴性 FN． 综合表 3 ～ 表 5 数据分析发现以下两个显著的 问题． ( 1) 六个测试系统中，State 模式的假阴性结果 FN 在其中四个开源系统都存在，由于另外两个测试系统 Junit 3. 8 和 Apache ant v1. 6. 2 未识别到 State 模式实 例． 统计发现，在已识别出 State 模式实例存在假阴性 结果 FN 的概率为 100% ． State 模式在表 3 JhotDraw 6. 0b1 与 Dom4j 1. 6. 1 系统的召回率 Ｒ 分别为 80% 与 · 5051 ·

·1506· 工程科学学报，第38卷，第10期 表3 Jhot Draw6.0b1与Dom4j1.6.1设计模式实例识别结果 Table3 Identification results of design pattems in Jhot Draw 6.0bl and Dom4j 1.6.1 JhotDraw 6.0bl Dom4j1.6.1 设计模式名 TP FP TN FN P/%R/%A/% TP TN FN P/%R/%A/% Composite 28 0 0 0 100 100 100 0 0 0 100100 100 State 4 0 0 100 80 80 30 0 0 2 100 93.8 93.8 Template 125 0 0 2 100 98.498.4 41 0 0 0 100 100 100 Decorator 28 0 0 0 100 100 100 11 0 0 0100 100 100 Singleton 6 0 0 100 85.7 85.7 32 0 0 4 100 88.9 88.9 Factory method 45 0 0 0 100 100 100 53 0 0 1 100 98.1 98.1 Bridge 一 41 0 0 100 95.3 95.3 Visitor 0 0 100 80 80 0 0 100 92.392.3 Adapter 35 0 0 3 100 92.1 92.1 65 0 2 100 97.0 97.0 Prototype 0 0 100 100 100 6 0 100 100 100 平均统计 100 92.492.4 100 96.596.5 注：二”表示该模式在系统中不存在 表4 Junit v3.8与Apache ant vl..6.2设计模式实例识别结果 Table 4 Identification results of design pattems in Junit v3.8 and Apache ant v1.6.2 Junit 3.8 Apache ant v1.6.2 设计模式名 TP FP TN FN P/% R/%A/% TP P TN FN P/%R/%A/% Composite 4 0 0 0 100 100 100 11 0 0 0 100 100 100 State Template 2 0 0 0 100 100 100 6 0 0 0 100100 100 Decorator 6 0 0 0 100 100 100 14 0 0 0 100 100 100 Singleton 一 一 7 0 0 2 100 77.8 77.8 Factory method 4 0 0 0 100 100 100 38 0 0 0 100 100 100 Bridge 157 0 0 3 100 98.198.1 Visitor Adapter 0 0 2 100 93.3 93.3 145 0 100 97.3 97.3 Prototype 平均统计 100 98.398.3 100 96.296.2 注：一”表示该模式在系统中不存在 表5 Quick UML20O1与Java AWT5.0设计模式实例识别结果 Table 5 Identification results of design patterns in Quick UML2001 and Java AWT 5.0 Quick UML2001 Java AWT 5.0 设计模式名 TP FP TN FN P/S R/S A/ TP FP TN FN P/%R/%A/% Composite 1080 0 2100 98.198.1 State 13 0 0 100 86.786.7 1340 0 12 100 91.8 91.8 Template 5 0 0 0 100 100 100 290 0 0 6 100 98.0 98.0 Decorator 一 69 0 0 0 100 100 100 Singleton 1 0 0 0 100 100 100 135 0 0 11 100 92.5 92.5 Factory method 55 0 0 2 100 96.5 96.5 Bridge 162 0 0 10 100 94.2 94.2 Visitor 13 0 0 2 100 86.7 86.7 Adapter 82 0 0 100 72.7 72.7 394 0 15 100 96.3 96.3 Prototype 6 0 0 100 85.785.7 平均统计 10090.090.0 10094.794.7 注：二”表示该模式在系统中不存在

工程科学学报，第 38 卷，第 10 期 表 3 Jhot Draw 6. 0b1 与 Dom4j 1. 6. 1 设计模式实例识别结果 Table 3 Identification results of design patterns in Jhot Draw 6. 0b1 and Dom4j 1. 6. 1 设计模式名 JhotDraw 6. 0b1 Dom4j 1. 6. 1 TP FP TN FN P /% Ｒ /% A /% TP FP TN FN P /% Ｒ /% A /% Composite 28 0 0 0 100 100 100 57 0 0 0 100 100 100 State 4 0 0 1 100 80 80 30 0 0 2 100 93. 8 93. 8 Template 125 0 0 2 100 98. 4 98. 4 41 0 0 0 100 100 100 Decorator 28 0 0 0 100 100 100 11 0 0 0 100 100 100 Singleton 6 0 0 1 100 85. 7 85. 7 32 0 0 4 100 88. 9 88. 9 Factory method 45 0 0 0 100 100 100 53 0 0 1 100 98. 1 98. 1 Bridge ——————— 41 0 0 2 100 95. 3 95. 3 Visitor 4 0 0 1 100 80 80 12 0 0 1 100 92. 3 92. 3 Adapter 35 0 0 3 100 92. 1 92. 1 65 0 0 2 100 97. 0 97. 0 Prototype 3 0 0 0 100 100 100 16 0 0 0 100 100 100 平均统计 100 92. 4 92. 4 100 96. 5 96. 5 注: “—”表示该模式在系统中不存在． 表 4 Junit v3. 8 与 Apache ant v1. 6. 2 设计模式实例识别结果 Table 4 Identification results of design patterns in Junit v3. 8 and Apache ant v1. 6. 2 设计模式名 Junit 3. 8 Apache ant v1. 6. 2 TP FP TN FN P /% Ｒ /% A /% TP FP TN FN P /% Ｒ /% A /% Composite 4 0 0 0 100 100 100 11 0 0 0 100 100 100 State —————————————— Template 2 0 0 0 100 100 100 6 0 0 0 100 100 100 Decorator 6 0 0 0 100 100 100 14 0 0 0 100 100 100 Singleton ——————— 7 0 0 2 100 77. 8 77. 8 Factory method 4 0 0 0 100 100 100 38 0 0 0 100 100 100 Bridge ——————— 157 0 0 3 100 98. 1 98. 1 Visitor —————————————— Adapter 28 0 0 2 100 93. 3 93. 3 145 0 0 4 100 97. 3 97. 3 Prototype —————————————— 平均统计 100 98. 3 98. 3 100 96. 2 96. 2 注: “—”表示该模式在系统中不存在． 表 5 Quick UML2001 与 Java AWT 5. 0 设计模式实例识别结果 Table 5 Identification results of design patterns in Quick UML2001 and Java AWT 5. 0 设计模式名 Quick UML2001 Java AWT 5. 0 TP FP TN FN P /% Ｒ /% A /% TP FP TN FN P /% Ｒ /% A /% Composite ——————— 108 0 0 2 100 98. 1 98. 1 State 13 0 0 2 100 86. 7 86. 7 134 0 0 12 100 91. 8 91. 8 Template 5 0 0 0 100 100 100 290 0 0 6 100 98. 0 98. 0 Decorator ——————— 69 0 0 0 100 100 100 Singleton 1 0 0 0 100 100 100 135 0 0 11 100 92. 5 92. 5 Factory method ——————— 55 0 0 2 100 96. 5 96. 5 Bridge ——————— 162 0 0 10 100 94. 2 94. 2 Visitor ——————— 13 0 0 2 100 86. 7 86. 7 Adapter 82 0 0 3 100 72. 7 72. 7 394 0 0 15 100 96. 3 96. 3 Prototype 6 0 0 1 100 85. 7 85. 7 ——————— 平均统计 100 90. 0 90. 0 100 94. 7 94. 7 注: “—”表示该模式在系统中不存在． · 6051 ·

肖卓宇等：一种形式化上下无关文法关系驱动的设计模式检测方法 ·1507· 93.8%,准确率A分别为80%和93.8%.State模式在 表6描述了上述六个测试系统中模式实例重叠的 表5中Quick UML2001与Java AWT5.0系统中的召 统计结果，其中JH表示JhotDraw6.0bl,D0表示 回率R分别为86.7%和91.8%，准确率A分别为 Dom4jl.6.l,JU表示Junit v3.8,AP表示Apache ant 6.7%和91.8%.Adapter模式在表3 ThotDraw6.0b1 vl.6.2,OU表示Quick UML2001,JA表示Java AWT 与Dom4j1.6.1系统的召回率R分别为92.1%和 5.0,最后一列统计了六个测试系统中十个不同设计模 97%,准确率A分别为92.1%和97%，Adapter模式在 式实例发生重叠的总数.由此可见，六个测试系统总 表4中Junit3.8和Apache ant vl.6.2系统中的召回率 共识别的Adapter实例数为28，Bridge实例数为21， R分别为93.3%和97.3%，准确率A分别为93.3%和 Composite实例数为l9,Decorator模式实例数为l0,这 97.3%.Adapter模式在表5中Quick UML2001与Java 四种设计模式共享实例的情况较多，而深层次思考后， AWT5.0系统中的召回率R分别为72.7%和93.3%， 发现上述4种模式具备一个共同的特点，即都为结构 准确率A分别为72.7%和93.3%.而导致出现该问 型模式. 题的原因是State和Strategy模式以及Adapter模式和 Gamma等0将设计模式分为结构型、行为型和创 Command模式等众多模式存在实例重叠，并且相同设 建型三类.分析三者特点发现行为型模式存在难以跟 计模式实例之间也存在实例重叠问题.虽然，第3节 踪的复杂控制流，而创建型模式存在委托等难以复制 提出的方法一定程度上解决了设计模式实例的重叠问 的关系，以至于很难被共享，可理解为很难发生设计模 题，见表6，但对涉及代理等复杂关系的模式实例重叠 式实例识别中的重叠问题，而结构型模式涉及如何组 问题仍不能100%避免假阴性结果，在后续工作中将 合类及对象，以获得更大的结构，并采用继承机制来组 继续完善ARFGS文法，并通过演化计算等对识别效果 合接口或实现，这样的特点使其结构具有更大的灵活 进行优化. 性，也更容易共享模式实例.依据表6的统计结果分 表6六个测试系统设计模式重叠实例统计表 析，图10中结构型设计模式实例重叠占据了主导地 Table 6 Design pattern instance overlap statistics in six systems 位，达到了93% 设计模式实例重叠数 行为型5%创建型2% 设计模式名 JH DO JU AP QU JA统计 Composite 7 0 2 0 9 19 State 0 0 0 0 0 1 Template 0 0 0 0 0 1 Decorator 0 1 3 2 0 10 Singleton 2 10 0 0 1 4 结构型93% Factory method 0000 0 0 0 图10三类模式重叠实例识别所占比例 Bridge 0 3 0 7 1 11 21 Fig.10 Proportion of three types of pattern overlapping instances Visitor 0 0 0 0 0 5.2 F-score指标比较实验 Adapter 2 2 9 0 14 28 文献9]提出了融合精确率P与召回率R的F- Prototype 0 0 0 0 0 0 0 score指标. (2)Singleton模式的假阴性结果FN在四个开源 (1+W2)×P×R F-score (28) W2×P+R 系统都存在，由于Junit3.8软件系统中未识别到Sin- gleton模式实例，而Quick UML2001中Singleton模式 式中，W为权值，其值给定为2.8，F-score值与设计模 式实例恢复的效果成正比.为检验本研究提出的方 的FN值为0.统计发现，Singleton模式存在假阴性结 法，结合表3中JhotDraw系统的平均精确度P与平均 果FN的概率为80%.表3中Singleton模式在Jhol- Draw6.0bl系统的召回率R与准确率A皆为85.7%， 召回率R进行了实验 在Dom4j1.6.1系统的召回率R与准确率A皆为 除所提新方法外，还与参考文献[4,12-13,15， 88.9%,表4中Singleton模式在Apache ant vI.6.2系 18]中提出的检测方法进行比较.由表7的F-score值 统的召回率R和准确率A皆为77.8%，表5中Single- 可知，本文方法取得了较好的效果. ton模式在Java AWT5.0系统的召回率R与准确率A 6结论 皆为92.5%.分析原因后发现Singleton模式自身结构 比较简单，且存在自循环而导致很难被正确识别出来. 文中提出一种形式化上下无关文法关系驱动的设

肖卓宇等: 一种形式化上下无关文法关系驱动的设计模式检测方法 93. 8% ，准确率 A 分别为 80% 和 93. 8% ． State 模式在 表 5 中 Quick UML2001 与 Java AWT 5. 0 系统中的召 回率 Ｒ 分 别 为 86. 7% 和 91. 8% ，准 确 率 A 分 别 为 6. 7% 和 91. 8% ． Adapter 模式在表 3 JhotDraw 6. 0b1 与 Dom4j 1. 6. 1 系 统 的 召 回 率 Ｒ 分 别 为 92. 1% 和 97% ，准确率 A 分别为 92. 1% 和 97% ，Adapter 模式在 表 4 中 Junit 3. 8 和 Apache ant v1. 6. 2 系统中的召回率 Ｒ 分别为 93. 3% 和 97. 3% ，准确率 A 分别为 93. 3% 和 97. 3% ． Adapter 模式在表 5 中 Quick UML2001 与 Java AWT 5. 0 系统中的召回率 Ｒ 分别为 72. 7% 和 93. 3% ， 准确率 A 分别为 72. 7% 和 93. 3% ． 而导致出现该问 题的原因是 State 和 Strategy 模式以及 Adapter 模式和 Command 模式等众多模式存在实例重叠，并且相同设 计模式实例之间也存在实例重叠问题． 虽然，第 3 节 提出的方法一定程度上解决了设计模式实例的重叠问 题，见表 6，但对涉及代理等复杂关系的模式实例重叠 问题仍不能 100% 避免假阴性结果，在后续工作中将 继续完善 AＲFGS 文法，并通过演化计算等对识别效果 进行优化． 表 6 六个测试系统设计模式重叠实例统计表 Table 6 Design pattern instance overlap statistics in six systems 设计模式名 设计模式实例重叠数 JH DO JU AP QU JA 统计 Composite 1 7 0 2 0 9 19 State 0 0 0 0 0 1 1 Template 0 1 0 0 0 0 1 Decorator 0 1 3 2 0 4 10 Singleton 2 1 0 0 0 1 4 Factory method 0 0 0 0 0 0 0 Bridge 0 3 0 7 1 11 21 Visitor 0 0 0 0 0 0 0 Adapter 2 2 1 9 0 14 28 Prototype 0 0 0 0 0 0 0 ( 2) Singleton 模式的假阴性结果 FN 在四个开源 系统都存在，由于 Junit 3. 8 软件系统中未识别到 Sin￾gleton 模式实例，而 Quick UML2001 中 Singleton 模式 的 FN 值为 0． 统计发现，Singleton 模式存在假阴性结 果 FN 的概率为 80% ． 表 3 中 Singleton 模式在 Jhot￾Draw 6. 0b1 系统的召回率 Ｒ 与准确率 A 皆为 85. 7% ， 在 Dom4j 1. 6. 1 系 统 的 召 回 率 Ｒ 与 准 确 率 A 皆 为 88. 9% ，表 4 中 Singleton 模式在 Apache ant v1. 6. 2 系 统的召回率 Ｒ 和准确率 A 皆为 77. 8% ，表 5 中 Single￾ton 模式在 Java AWT 5. 0 系统的召回率 Ｒ 与准确率 A 皆为 92. 5% ． 分析原因后发现 Singleton 模式自身结构 比较简单，且存在自循环而导致很难被正确识别出来． 表 6 描述了上述六个测试系统中模式实例重叠的 统计 结 果，其 中 JH 表 示 JhotDraw 6. 0b1，DO 表 示 Dom4j 1. 6. 1，JU 表示 Junit v3. 8，AP 表示 Apache ant v1. 6. 2，QU 表 示 Quick UML2001，JA 表 示 Java AWT 5. 0，最后一列统计了六个测试系统中十个不同设计模 式实例发生重叠的总数． 由此可见，六个测试系统总 共识别的 Adapter 实例数为 28，Bridge 实例数为 21， Composite 实例数为 19，Decorator 模式实例数为 10，这 四种设计模式共享实例的情况较多，而深层次思考后， 发现上述 4 种模式具备一个共同的特点，即都为结构 型模式． Gamma 等［1］将设计模式分为结构型、行为型和创 建型三类． 分析三者特点发现行为型模式存在难以跟 踪的复杂控制流，而创建型模式存在委托等难以复制 的关系，以至于很难被共享，可理解为很难发生设计模 式实例识别中的重叠问题，而结构型模式涉及如何组 合类及对象，以获得更大的结构，并采用继承机制来组 合接口或实现，这样的特点使其结构具有更大的灵活 性，也更容易共享模式实例． 依据表 6 的统计结果分 析，图 10 中结构型设计模式实例重叠占据了主导地 位，达到了 93% ． 图 10 三类模式重叠实例识别所占比例 Fig． 10 Proportion of three types of pattern overlapping instances 5. 2 F-score 指标比较实验 文献［19］提出了融合精确率 P 与召回率 Ｒ 的 F￾score 指标． F-score = ( 1 + W2 ) × P × Ｒ W2 × P + Ｒ ． ( 28) 式中，W 为权值，其值给定为 2. 8，F-score 值与设计模 式实例恢复的效果成正比． 为检验本研究提出的方 法，结合表 3 中 JhotDraw 系统的平均精确度 P 与平均 召回率 Ｒ 进行了实验． 除所提新方法外，还与参考 文 献［4，12--13，15， 18］中提出的检测方法进行比较． 由表 7 的 F-score 值 可知，本文方法取得了较好的效果． 6 结论 文中提出一种形式化上下无关文法关系驱动的设 · 7051 ·

·1508· 工程科学学报，第38卷，第10期 表7 F-score值比较 on their micro-structures.J Soficare Erol Process,2013,25(1): Table7 F-score value comparison 3 识别技术平均精确度/%平均召回率/%F-score/% 8]Fontana F A,Maggioni S,Raibulet C.Understanding the rele- vance of micro-structures for design pattems detection.ISyst Sofi- 笔者工作 100 91.57 92.45 ae,2011,84(12):2334 文献) 94 62 64.48 9]Zanoni M,Fontana FA,Stella F.On applying machine learning 文献02] 91 67 69.06 techniques for design pattern detection.J Syst Software,2015, 文献3] 68 82 80.13 103:102 文献05] 94 2 [10]Alhusain S,Coupland S,John R,et al.Towards machine learn- 73.96 ing based design pattem recognition //2013 13th UK Workshop 文献08] 39 100 84.97 on Computational Intelligence (UKCI).Guildford,2013:244 [11]Chihada A,Jalili S,Hasheminejad S M H,et al.Source code 计模式检测方法，通过逆向工程工具将源代码中的特 and design conformance,design pattern detection from source 征信息进行抽取，之后以文献21]中提出的可视化形 code by classification approach.Appl Soft Comput,2015,26: 式对抽取信息进行表示与分析，并结合文献22]中描 357 述的文法，以形式化文法描述了符号间存在的关系，接 12] Dong J,Zhao Y J,Sun Y T.A matrix based approach to recove- 着在文献20]制定的设计模式参与者间附加关系检 ring design patterns.IEEE Trans Syst Man Cybern Part A,2009. 39(6):1271 测规则的基础上，改进该文法以发现附加关系，并优化 [13]Bernardi M L,Cimitile M,Lucca G D.Design pattern detection ARFGS文法进一步避免了模式实例参与者共享实例 using a DSLriven graph matching approach.Sofucare Erol 的问题.由实验结果可见，由于综合考虑了设计模式 Process,2014,26(12):1233 角色间的附加关系与实例共享问题，本研究在避免设 041 Sabo M,Porubiin J.Preserving design patters using source code 计模式实例识别的假阴性结果与重叠问题方面取得了 annotations.J Comput Sci Control Syst,2009(1):53 较好的效果，使得模式实例识别的精确度显著提高 05] Rasool G.Philippow I,Mader P.Design pattem recovery based on annotations.Adr Eng Softuare,2010,41 (4)519 16] Garlan D,Monroe R,Wile D.Acme:an architecture deseription 参考文献 interchange language //CASCON First Decade High Impact Pa- Gamma E,Helm R,Johnson R,et al.Design Pattern:Elements pers.Riverton,2010:159 of Reusable Object-Oriented Software.Pearson Education India, 17] Rasool G,Mader P.A customizable approach to design patterns 1995 recognition based on feature types.Arab Sci Eng,2014,39 2]Ampatzoglou A,Frantzeskou G,Stamelos I.A methodology to as- (12):8851 sess the impact of design patterns on software quality.Inf Sofiuare [18]Gueheneuc Y G,Antoniol G.DeMIMA:a multilayered approach Technol,2012,54(4):331 for design pattern identification.IEEE Trans Softcare Eng, B] Ampatzoglou A,Michou O,Stamelos I.Building and mining a re- 2008,34(5):667 pository of design pattern instances:practical and research bene- 19] Pettersson N,Lowe W,Nivre J.Evaluation of accuracy in design fits.Entertain Comput,2013,4(2):131 pattern occurrence detection.IEEE Trans Software Eng,2010, 4]Ampatzoglou A.Charalampidou S,Stamelos I.Research state of 36(4):575 the art on GoF design patterns:a mapping study.Syst Sofucare, 120]Xiao Z Y,He P,Li Y.Study on additional relationships based 2013,86(7):1945 on design patterns'roles.Appl Res Comput,2015,32 (7): [5]Yu D J,Zhang Y Y,Chen Z L.A comprehensive approach to the 2042 recovery of design pattern instances based on subpatterns and (肖卓宇，何锫，黎妍.基于设计模式角色的附加关系检测 method signatures.J Syst Software,2015,103:1 研究.计算机应用研究，2015,32(7)：2042) [6]Yu D J,Zhang Y Y,Ge J L,et al.From subpatterns to pat- 21]Costagliola G,Delucia A,Orefice S,et al.A classification terns:an approach to the detection of structural design pattern in- framework to support the design of visual languages.J Visual stances by subgraph mining and merging /2013 IEEE 37th An- Lang Comput,2002,13(6):573 nual Computer Sofiware and Applications Conference (COMP- D2]Costagliola G,De Lucia A,Orefice S,et al.A parsing method- SAC).Kyoto,2013:579 ology for the implementation of visual systems.IEEE Trans Soft- [7]Fontana F A,Maggioni S,Raibulet C.Design pattemns:a survey ware Eng,1997,23(12):777

工程科学学报，第 38 卷，第 10 期 表 7 F-score 值比较 Table 7 F-score value comparison 识别技术 平均精确度/% 平均召回率/% F-score /% 笔者工作 100 91. 57 92. 45 文献［4］ 94 62 64. 48 文献［12］ 91 67 69. 06 文献［13］ 68 82 80. 13 文献［15］ 94 72 73. 96 文献［18］ 39 100 84. 97 计模式检测方法，通过逆向工程工具将源代码中的特 征信息进行抽取，之后以文献［21］中提出的可视化形 式对抽取信息进行表示与分析，并结合文献［22］中描 述的文法，以形式化文法描述了符号间存在的关系，接 着在文献［20］制定的设计模式参与者间附加关系检 测规则的基础上，改进该文法以发现附加关系，并优化 AＲFGS 文法进一步避免了模式实例参与者共享实例 的问题． 由实验结果可见，由于综合考虑了设计模式 角色间的附加关系与实例共享问题，本研究在避免设 计模式实例识别的假阴性结果与重叠问题方面取得了 较好的效果，使得模式实例识别的精确度显著提高． 参 考 文 献 ［1］ Gamma E，Helm Ｒ，Johnson Ｒ，et al． Design Pattern: Elements of Ｒeusable Object-Oriented Software． Pearson Education India， 1995 ［2］ Ampatzoglou A，Frantzeskou G，Stamelos I． A methodology to as￾sess the impact of design patterns on software quality． Inf Software Technol，2012，54( 4) : 331 ［3］ Ampatzoglou A，Michou O，Stamelos I． Building and mining a re￾pository of design pattern instances: practical and research bene￾fits． Entertain Comput，2013，4( 2) : 131 ［4］ Ampatzoglou A，Charalampidou S，Stamelos I． Ｒesearch state of the art on GoF design patterns: a mapping study． J Syst Software， 2013，86( 7) : 1945 ［5］ Yu D J，Zhang Y Y，Chen Z L． A comprehensive approach to the recovery of design pattern instances based on sub-patterns and method signatures． J Syst Software，2015，103: 1 ［6］ Yu D J，Zhang Y Y，Ge J L，et al． From sub-patterns to pat￾terns: an approach to the detection of structural design pattern in￾stances by subgraph mining and merging / / 2013 IEEE 37th An￾nual Computer Software and Applications Conference ( COMP￾SAC) ． Kyoto，2013: 579 ［7］ Fontana F A，Maggioni S，Ｒaibulet C． Design patterns: a survey on their micro-structures． J Software Evol Process，2013，25( 1) : 27 ［8］ Fontana F A，Maggioni S，Ｒaibulet C． Understanding the rele￾vance of micro-structures for design patterns detection． J Syst Soft￾ware，2011，84( 12) : 2334 ［9］ Zanoni M，Fontana F A，Stella F． On applying machine learning techniques for design pattern detection． J Syst Software，2015， 103: 102 ［10］ Alhusain S，Coupland S，John Ｒ，et al． Towards machine learn￾ing based design pattern recognition / / 2013 13th UK Workshop on Computational Intelligence ( UKCI) ． Guildford，2013: 244 ［11］ Chihada A，Jalili S，Hasheminejad S M H，et al． Source code and design conformance，design pattern detection from source code by classification approach． Appl Soft Comput，2015，26: 357 ［12］ Dong J，Zhao Y J，Sun Y T． A matrix based approach to recove￾ring design patterns． IEEE Trans Syst Man Cybern Part A，2009， 39( 6) : 1271 ［13］ Bernardi M L，Cimitile M，Lucca G D． Design pattern detection using a DSL-driven graph matching approach． J Software Evol Process，2014，26( 12) : 1233 ［14］ Sabo M，Porubn J． Preserving design patterns using source code annotations． J Comput Sci Control Syst，2009( 1) : 53 ［15］ Ｒasool G，Philippow I，Mder P． Design pattern recovery based on annotations． Adv Eng Software，2010，41( 4) : 519 ［16］ Garlan D，Monroe Ｒ，Wile D． Acme: an architecture description interchange language / / CASCON First Decade High Impact Pa￾pers． Ｒiverton，2010: 159 ［17］ Ｒasool G，Mder P． A customizable approach to design patterns recognition based on feature types． Arab J Sci Eng，2014，39 ( 12) : 8851 ［18］ Guéhéneuc Y G，Antoniol G． DeMIMA: a multilayered approach for design pattern identification． IEEE Trans Software Eng， 2008，34( 5) : 667 ［19］ Pettersson N，Lwe W，Nivre J． Evaluation of accuracy in design pattern occurrence detection． IEEE Trans Software Eng，2010， 36( 4) : 575 ［20］ Xiao Z Y，He P，Li Y． Study on additional relationships based on design patterns’roles． Appl Ｒes Comput，2015，32 ( 7 ) : 2042 ( 肖卓宇，何锫，黎妍． 基于设计模式角色的附加关系检测 研究． 计算机应用研究，2015，32( 7) : 2042) ［21］ Costagliola G，Delucia A，Orefice S，et al． A classification framework to support the design of visual languages． J Visual Lang Comput，2002，13( 6) : 573 ［22］ Costagliola G，De Lucia A，Orefice S，et al． A parsing method￾ology for the implementation of visual systems． IEEE Trans Soft￾ware Eng，1997，23( 12) : 777 · 8051 ·