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

工程科学学报，第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 ·