基于文法產(chǎn)生式優(yōu)化的設(shè)計(jì)模式識(shí)別方法

肖卓宇，何 锫，楊鑫維，楊邦平，陳俊旭，胡振濤

(1. 中南林業(yè)科技大學(xué)涉外學(xué)院 長(zhǎng)沙 410200; 2. 廣州大學(xué)計(jì)算機(jī)科學(xué)與教育軟件學(xué)院 廣州 510006; 3. 長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院 長(zhǎng)沙 410114; 4. 北京大學(xué)高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室 北京 海淀區(qū) 100871)

基于文法產(chǎn)生式優(yōu)化的設(shè)計(jì)模式識(shí)別方法

肖卓宇1，何 锫2,3,4，楊鑫維1，楊邦平1，陳俊旭1，胡振濤1

(1. 中南林業(yè)科技大學(xué)涉外學(xué)院 長(zhǎng)沙 410200; 2. 廣州大學(xué)計(jì)算機(jī)科學(xué)與教育軟件學(xué)院 廣州 510006; 3. 長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院 長(zhǎng)沙 410114; 4. 北京大學(xué)高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室 北京 海淀區(qū) 100871)

以精確的設(shè)計(jì)模式檢測(cè)結(jié)果為目標(biāo)，為解決設(shè)計(jì)模式識(shí)別的變體問(wèn)題，提出一種基于文法產(chǎn)生式優(yōu)化的設(shè)計(jì)模式識(shí)別方法，旨在使用可視化文法產(chǎn)生式描述設(shè)計(jì)模式參與者角色的屬性與聯(lián)系，并通過(guò)增加文法產(chǎn)生式描述的特征信息來(lái)識(shí)別重疊的設(shè)計(jì)模式及參與者角色間的附加關(guān)系。實(shí)驗(yàn)結(jié)果表明，該方法減少了設(shè)計(jì)模式識(shí)別的假陽(yáng)性結(jié)果與假陰性結(jié)果，通過(guò)與主流方法的F-score評(píng)估指標(biāo)比較，顯示出該方法的優(yōu)勢(shì)。

設(shè)計(jì)模式檢測(cè); 文法產(chǎn)生式; 模式共享; 變體; 可視化

設(shè)計(jì)模式恢復(fù)有助于軟件的維護(hù)與程序的理解，常用于軟件系統(tǒng)的重構(gòu)[1]。當(dāng)前眾多研究在設(shè)計(jì)模式識(shí)別方面做出了重要貢獻(xiàn)[2-3]。文獻(xiàn)[4]提出將設(shè)計(jì)模式抽取的結(jié)果分類，并形成Clue、EDP等微結(jié)構(gòu)。文獻(xiàn)[5]通過(guò)分類學(xué)習(xí)來(lái)提升設(shè)計(jì)模式識(shí)別效果。文獻(xiàn)[6]以子圖同構(gòu)的形式檢測(cè)設(shè)計(jì)模式。文獻(xiàn)[7]使用DSL方法以圖形的形式檢測(cè)設(shè)計(jì)模式。文獻(xiàn)[8]通過(guò)注釋對(duì)設(shè)計(jì)模式變體問(wèn)題進(jìn)行研究。文獻(xiàn)[9]采用多階段逐步篩選設(shè)計(jì)模式候選參與者集的方法來(lái)檢測(cè)設(shè)計(jì)模式實(shí)例。文獻(xiàn)[10]給出了多種影響設(shè)計(jì)模式檢測(cè)精確率的原因，并提出了融合精確度與召回率的F-score指標(biāo)。文獻(xiàn)[11]對(duì)設(shè)計(jì)模式參與者角色間附加關(guān)系等導(dǎo)致的模式變體問(wèn)題進(jìn)行了初步研究。

總而言之，傳統(tǒng)方法存在4類問(wèn)題：

1) 設(shè)計(jì)模式識(shí)別在評(píng)估指標(biāo)選擇上沒(méi)有同時(shí)兼顧假陽(yáng)性與假陰性結(jié)果，以至于不能反應(yīng)出真實(shí)的識(shí)別效果。

2) 評(píng)估結(jié)果僅單獨(dú)分析比較召回率或精確率，缺乏一個(gè)綜合的評(píng)估指標(biāo)。

3) 對(duì)附加關(guān)系及參與者角色共享設(shè)計(jì)模式導(dǎo)致的變體問(wèn)題缺乏深入研究，導(dǎo)致不精確結(jié)果產(chǎn)生。

4) 不能識(shí)別復(fù)雜多層類之間的設(shè)計(jì)模式實(shí)例。

為此，本文提出一種基于文法產(chǎn)生式優(yōu)化的設(shè)計(jì)模式識(shí)別方法，主要思路是將抽取后的信息通過(guò)文獻(xiàn)[12]給出的可視化語(yǔ)言及文獻(xiàn)[13]提出的文法以產(chǎn)生式的形式進(jìn)行描述，并依據(jù)文獻(xiàn)[14]中提出的47種特征信息進(jìn)行表示。之后，增加文法產(chǎn)生式解決設(shè)計(jì)模式參與者角色共享設(shè)計(jì)模式實(shí)例及其附加關(guān)系導(dǎo)致的變體問(wèn)題。最后，通過(guò)Jhotdraw等4個(gè)開(kāi)源系統(tǒng)進(jìn)行了實(shí)驗(yàn)設(shè)計(jì)與評(píng)估。

1 模式實(shí)例識(shí)別步驟

設(shè)計(jì)模式實(shí)例識(shí)別的5個(gè)步驟：

1) 抽取軟件系統(tǒng)相關(guān)信息；

2) 以可視化文法的形式表示抽取結(jié)果；

3) 將產(chǎn)生式表示為文獻(xiàn)[14]給出的特征形式；

4) 增加可視化文法產(chǎn)生式識(shí)別設(shè)計(jì)模式變體；

5) 通過(guò)工具Sparx Enterprise Architect(EA)[8]進(jìn)行設(shè)計(jì)模式檢測(cè)；

2 可視化文法表示設(shè)計(jì)模式實(shí)例

文獻(xiàn)[12]通過(guò)可視化文法表示設(shè)計(jì)模式參與者角色間的屬性及關(guān)系。如圖1a中Proxy模式的Subject、RealSubject、 Proxy類 及 關(guān)系實(shí)體Dependency、Inheritance可表示為可視化圖形，而可視化圖形的屬性可通過(guò)連接點(diǎn)聯(lián)系。

圖1 Proxy模式

圖1b比圖1a更加側(cè)重參與者角色屬性之間的聯(lián)系，圓角矩形表示設(shè)計(jì)模式參與者角色，如RoleA、RoleB等，圓角矩形中的連接區(qū)域用數(shù)字進(jìn)行編號(hào)，此外，圓角矩形周邊的空心小圓圈表示角色屬性的連接點(diǎn)，也用數(shù)字進(jìn)行編號(hào)，參與者角色之間通過(guò)連接點(diǎn)銜接。如圖1b中RoleC與繼承關(guān)系實(shí)體間通過(guò)角色RoleC的屬性區(qū)域1及連接點(diǎn)1在屬性c處聯(lián)系，而角色屬性d表示RoleC與Dependency關(guān)系之間通過(guò)角色RoleC的屬性區(qū)域1及連接點(diǎn)2進(jìn)行聯(lián)系。表1給出了圖1b中參與者角色的屬性表。

文獻(xiàn)[13]依據(jù)文獻(xiàn)[12]提出的可視化文法將圖1b表示為字符串形式，其實(shí)質(zhì)是通過(guò)定義約束來(lái)交替參與者角色及其屬性，從而挖掘角色間的關(guān)系。

表1 參與者角色屬性表

定義1中m和n表示參與者角色的編號(hào)，Connecti,j表示角色Role[m]的連接點(diǎn)或?qū)傩詤^(qū)域i與角色Role[n] 的連接點(diǎn)或?qū)傩詤^(qū)域j之間的聯(lián)系，k表示參與者角色間不同關(guān)系的編號(hào)。

圖1b中角色RoleC的屬性區(qū)域1與Inheritance關(guān)系實(shí)體的連接點(diǎn)1存在聯(lián)系，可表示為：

此外，角色RoleB的屬性區(qū)域1與Inheritance實(shí)體的連接點(diǎn)1也存在聯(lián)系。依據(jù)定義1，為了避免與式(1)的Connect1,1符號(hào)沖突，式(2)中的k值取2，有：

定義2表示角色Role[m]與角色Role[n]的連接點(diǎn)或角色屬性區(qū)域間各種聯(lián)系組成的關(guān)系實(shí)體集。

依據(jù)定義1，圖1b可表示為：

圖1b中圓角矩形表示模式的參與者角色，如RoleA、RoleB、RoleC，每個(gè)圓角矩形中有相應(yīng)的數(shù)字表示角色的屬性區(qū)域，而其周邊的小圓圈表示參與角色屬性區(qū)域與關(guān)系實(shí)體間的連接點(diǎn)，用數(shù)字標(biāo)處連接，可表示為Connect1,2。此外，為了區(qū)分已經(jīng)存在的Connect1,2，RoleB角色的屬性區(qū)域1與注連接點(diǎn)區(qū)分。式(3)中RoleA角色的屬性區(qū)域1與Inheritance實(shí)體的圓形連接點(diǎn)2在表1中的角色屬性a Dependency關(guān)系實(shí)體的連接點(diǎn)2在表1的角色屬性b處相連，可用表示。

依據(jù)定義1與定義2，在文獻(xiàn)[13]提出的文法基礎(chǔ)上進(jìn)行改進(jìn)，旨在實(shí)現(xiàn)文法產(chǎn)生式終結(jié)符與非終結(jié)符角色的替換。為此，Proxy模式可表示為：

式(4)描述了Proxy模式，式(5)～式(7)使用Δ規(guī)則[12]依次將參與者扮演的角色通過(guò)產(chǎn)生式左右兩側(cè)的非終結(jié)符與終結(jié)符替換出來(lái)。如式(7)中Role角色扮演了Proxy模式中的Proxy角色，Role角色的屬性i也對(duì)應(yīng)了Proxy角色的屬性i。

圖2中Proxy模式的Subject、RealSubject、Proxy角色通過(guò)Δ規(guī)則及式(5)～式(7)依次被扮演的角色替換出來(lái)，詳見(jiàn)步驟2)～步驟4)，而矩形點(diǎn)線框表示替換后的結(jié)果，最終，經(jīng)歷步驟5)之后，一個(gè)標(biāo)準(zhǔn)的Proxy模式被識(shí)別出來(lái)。

圖2 Proxy模式檢測(cè)流程圖

3 設(shè)計(jì)模式實(shí)例變體檢測(cè)

式(4)～式(7)在一定程度上解決了參與者在設(shè)計(jì)模式中的角色扮演問(wèn)題，但沒(méi)有考慮設(shè)計(jì)模式參與角色共享及設(shè)計(jì)模式角色間附加關(guān)系導(dǎo)致的設(shè)計(jì)模式變體問(wèn)題，這將導(dǎo)致模式檢測(cè)時(shí)產(chǎn)生大量假陽(yáng)性與假陰性結(jié)果[11]。傳統(tǒng)的方法較少考慮變體問(wèn)題，即使一部分方法關(guān)注了變體，但僅單方面考慮變體結(jié)果的假陰性問(wèn)題或假陽(yáng)性問(wèn)題，缺乏將二者結(jié)合進(jìn)行深入的研究與分析，導(dǎo)致了不精確的檢測(cè)結(jié)果出現(xiàn)。

為解決這個(gè)問(wèn)題，本文研究兼顧設(shè)計(jì)模式變體的假陽(yáng)性與假陰性結(jié)果檢測(cè)，對(duì)文獻(xiàn)[13]提出的文法進(jìn)行改進(jìn)，并表示為文獻(xiàn)[14]中給定的47種特征，通過(guò)工具Sparx Enterprise Architect(EA)[8]實(shí)現(xiàn)設(shè)計(jì)模式實(shí)例識(shí)別。表2描述了文獻(xiàn)[14]中部分重要特征。

表2 特征類型表

3.1 設(shè)計(jì)模式假陰性結(jié)果檢測(cè)

傳統(tǒng)方法檢測(cè)設(shè)計(jì)模式時(shí)，圖3不能識(shí)別為Proxy模式，究其原因發(fā)現(xiàn)，傳統(tǒng)方法要求Proxy模式中AbstractRealSubject類的方法Request需能被Proxy類的Request方法委托實(shí)現(xiàn)，而Abstract-RealSubject在圖3a中是一個(gè)抽象類，其方法Request需調(diào)用其子類RealSubject1或RealSubject2的方法Request實(shí)現(xiàn)。事實(shí)上這是一個(gè)典型的Proxy模式變體，因?yàn)镻roxy類中的方法Request最終還是能夠通過(guò)調(diào)用AbstractRealSubject子類中的方法實(shí)現(xiàn)的，屬于Proxy模式的變體，這是一個(gè)典型的假陰性結(jié)果。

除此之外，圖3a點(diǎn)線框中的3個(gè)類RealSubject1、RealSubject2、AbstractRealSubject及其關(guān)系也是一個(gè)Composite模式，但傳統(tǒng)的方法也不能識(shí)別，也屬于一個(gè)典型的假陰性結(jié)果。對(duì)圖3a進(jìn)一步研究發(fā)現(xiàn)，AbstractRealSubject這個(gè)類參與者角色被Proxy與Composite兩種設(shè)計(jì)模式共享，即扮演了Proxy模式中的RealSubject角色，又扮演了Composite模式中的Component角色。

傳統(tǒng)檢測(cè)方法很難識(shí)別涉及復(fù)雜多層重疊的設(shè)計(jì)模式。為檢測(cè)圖3a中的Proxy變體及Composite與Proxy與的重疊問(wèn)題，通過(guò)在第2節(jié)提出的文法基礎(chǔ)上增加產(chǎn)生式實(shí)現(xiàn)。

圖3 Proxy模式變體

式(8)中ShareRole表示參與多個(gè)設(shè)計(jì)模式實(shí)例的共享角色，Design_Pattern表示被識(shí)別出的設(shè)計(jì)模式；式(9)中Design_Pattern這個(gè)非終結(jié)符可被23種標(biāo)準(zhǔn)的GOF設(shè)計(jì)模式終結(jié)符替換。式(11)～式(13)通過(guò)Δ規(guī)則依次實(shí)現(xiàn)對(duì)Proxy模式的角色替換。

表3 設(shè)計(jì)模式實(shí)例角色扮演對(duì)應(yīng)表

表3描述了具體的映射關(guān)系，Proxy、Subject、AbstractRealSubject依次扮演了Proxy模式中的Proxy、Subject、Real Subject角色，其中加邊框與灰色底紋的AbstractRealSubject類除扮演了Proxy模式的RealSubject角色外，還扮演了Composite模式中的Component角色，而字體加粗部分表示被扮演的設(shè)計(jì)模式角色。

首先通過(guò)產(chǎn)生式識(shí)別出圖4中圓角矩形虛線框中的Proxy模式，見(jiàn)步驟2)。此外，式(14)中共享角色ShareRole再次作為非終結(jié)符起點(diǎn)對(duì)可能存在關(guān)聯(lián)的角色及關(guān)系繼續(xù)進(jìn)行遍歷，最終，式(15)～式(17)通過(guò)Δ規(guī)則依次實(shí)現(xiàn)對(duì)Composite模式角色替換，表2中AbstractRealSubject、RealSubject1、RealSubject2依 次扮演了 Composite模 式的Component，Composite，Leaf角色。最終圖4中點(diǎn)線矩形框中的Composite被識(shí)別出來(lái)，見(jiàn)步驟3)。

圖4 重疊設(shè)計(jì)模式識(shí)別流程圖

表4 Proxy特征表示

依據(jù)表2給出的特征，表4描述了Proxy模式文法產(chǎn)生式(8)～式(12)的具體實(shí)現(xiàn)。第1行GetAllClass表示Proxy模式中存在Proxy, AbstractRealSubject, Real-Subject1,RealSubject2共4個(gè)類角色，第2行表示Subject角色是接口，第3、4行描述了Proxy與Subject，AbstractRealSubject與RealSubject兩組角色間存在泛化關(guān)系，第5行限定Proxy與AbstractRealSubject不能存在關(guān)聯(lián)關(guān)系，第6行描述了Proxy的request方法與RealSubject的request方法通過(guò)委托實(shí)現(xiàn)，第7行表示角色Proxy、Subject及RealSubject中有同名方法request。

3.2 設(shè)計(jì)模式假陽(yáng)性結(jié)果檢測(cè)

傳統(tǒng)方法檢測(cè)設(shè)計(jì)模式時(shí)，圖5易被錯(cuò)誤的識(shí)別為Proxy模式，這是一個(gè)典型的假陽(yáng)性結(jié)果，因?yàn)闃?biāo)準(zhǔn)Proxy模式中的Proxy類和Subject不存在聚合關(guān)系，這是一類典型的附加關(guān)系[11]。

規(guī)則1：Proxy類不能與Subject類存在聚合關(guān)系。

為檢測(cè)圖5中的Proxy模式的假陽(yáng)性問(wèn)題，仍需對(duì)第2節(jié)文法進(jìn)行優(yōu)化，旨在通過(guò)增加產(chǎn)生式來(lái)檢測(cè)規(guī)則1。為此增加一個(gè)附加關(guān)系檢測(cè)標(biāo)記access，若設(shè)計(jì)模式識(shí)別過(guò)程中發(fā)現(xiàn)了規(guī)則1描述的附加關(guān)系，則access值取1，以便后續(xù)階段檢測(cè)過(guò)程中忽略該關(guān)系的搜尋，從而避免假陽(yáng)性結(jié)果。Tagging表示附加關(guān)系是否關(guān)聯(lián)其他參與者角色的屬性，初值設(shè)為0。

圖5 Proxy模式變體

此外，引入文獻(xiàn)[12]提出的Γ規(guī)則對(duì)產(chǎn)生式進(jìn)行約束，式(20)中Role′角色的access標(biāo)志為1，表示Proxy角色存在附加關(guān)系A(chǔ)ggregation，故后續(xù)遍歷將不再檢測(cè)該關(guān)系。相反，若access值設(shè)為0，則式(20)中的Tagging不用標(biāo)記，這表示違反了規(guī)則1的約束。

文法產(chǎn)生式(18)～式(22)依據(jù)表2的特征描述表示為表5，其中表5的第1行～第7行描述了一個(gè)標(biāo)準(zhǔn)的Proxy模式，而第8行是與標(biāo)準(zhǔn)的Proxy模式相比發(fā)生了變化的特征，即Proxy與Subject類之間存在附加的聚合關(guān)系。此外，第1行GetAllClass表示Proxy模式中存在Proxy、Abstract- RealSubject等類，第2行表示Subject角色是接口，第3,4行描述了Proxy與Subject、RealSubject與Subject兩組角色間存在泛化關(guān)系，第5行限定Proxy與RealSubject不能存在關(guān)聯(lián)關(guān)系，第6行描述了Proxy的request方法與RealSubject的request方法通過(guò)委托實(shí)現(xiàn)，第7行表示角色Proxy、Subject、RealSubject中有同名方法request。

表5 Proxy假陽(yáng)性變體特征表示

4 實(shí)驗(yàn)與結(jié)果分析

為評(píng)估基于文法產(chǎn)生式優(yōu)化的設(shè)計(jì)模式識(shí)別方法有效性，選用JavaAWT等4個(gè)開(kāi)源系統(tǒng)展開(kāi)實(shí)驗(yàn)。評(píng)估通過(guò)真陽(yáng)性、假陽(yáng)性、假陰性結(jié)果來(lái)關(guān)注精確率與召回率，并通過(guò)F-score指標(biāo)進(jìn)行了比較試驗(yàn)。

1) 真陽(yáng)性TP: 正確的模式識(shí)別為正確；

2) 假陽(yáng)性FP: 錯(cuò)誤的模式識(shí)別為正確；

3) 假陰性FN: 正確的模式識(shí)別為錯(cuò)誤；

執(zhí)行實(shí)驗(yàn)的操作系統(tǒng)采用WINDOW8，CPU為INTEL Core4 E3-1230 V2 3.3 GHz，內(nèi)存16 GB。

式中，P為精確率；R為召回率。

表6中第一列字段表示設(shè)計(jì)模式類型，依據(jù)GOF原則分為了結(jié)構(gòu)型(structure,S)，行為型(behavior, B)，創(chuàng)建型(creation,C)3類[1]，此外，(not analysed , NA)表示該模式在系統(tǒng)中未發(fā)現(xiàn)。通過(guò)分析表6中4個(gè)系統(tǒng)的TP、FP、FN值，發(fā)現(xiàn)了幾個(gè)明顯的問(wèn)題。

1) 結(jié)構(gòu)型模式S相對(duì)行為型模式B與創(chuàng)建型模式C更容易產(chǎn)生假陽(yáng)性與假陰性結(jié)果。深入研究后發(fā)現(xiàn)，一方面行為型模式與創(chuàng)建型模式在4個(gè)開(kāi)源系統(tǒng)中使用的數(shù)量與頻率相對(duì)結(jié)構(gòu)型模式低。另一方面由于行為型模式在執(zhí)行時(shí)對(duì)復(fù)雜的控制流幾乎無(wú)法跟蹤，而創(chuàng)建型模式側(cè)重抽象實(shí)例化，并涉及了委托等復(fù)雜的關(guān)系，故行為型與創(chuàng)建型模式產(chǎn)生變體的幾率相對(duì)結(jié)構(gòu)型模式要小。

2) 4個(gè)開(kāi)源系統(tǒng)的檢測(cè)結(jié)果表明，Singleton是創(chuàng)建型模式中較易產(chǎn)生變體的模式，在javaAWT 5.0中甚至同時(shí)出現(xiàn)了假陽(yáng)性結(jié)果FP與假陰性結(jié)果FN。究其原因發(fā)現(xiàn)Singleton模式僅保證系統(tǒng)中的一個(gè)類只有一個(gè)實(shí)例，這樣的簡(jiǎn)單結(jié)構(gòu)易于擴(kuò)展，故容易產(chǎn)生變體。為此，文獻(xiàn)[11]分析了Singleton模式的8種變體。后續(xù)工作中將通過(guò)增加文法產(chǎn)生式并結(jié)合特征結(jié)構(gòu)進(jìn)一步改進(jìn)現(xiàn)有工作。

3) composite、adapter、state等模式相對(duì)容易識(shí)別出假陽(yáng)性與假陰性結(jié)果，在深入分析后發(fā)現(xiàn)，composite與decorator模式、state與stategy模式、adapter與command模式容易發(fā)生重疊。表7描述了JavaAWT 5.0與Dom4j 1.6.1系統(tǒng)識(shí)別后的模式重疊結(jié)果。為此，后續(xù)工作中將考慮將composite與decorator模式、state與stategy模式、adapter與command模式組合成3組進(jìn)行檢測(cè)試驗(yàn)，并通過(guò)復(fù)雜大類圖分割法等優(yōu)化方法避免消極的模式共享。

表6 4類開(kāi)源系統(tǒng)設(shè)計(jì)模式識(shí)別表

表7 JavaAWT 5.0與Dom4j 1.6.1系統(tǒng)重疊模式檢測(cè)表

如：Peterson從召回率與精確率兩個(gè)角度出發(fā)提出一種綜合的評(píng)估指標(biāo)F-score：

式中，權(quán)值W取2.8。F-score值越大則表明設(shè)計(jì)模式檢測(cè)效果越好，為此，將本文方法與文獻(xiàn)[2,6-9]的識(shí)別方法通過(guò)Jhotdraw進(jìn)行了F-score指標(biāo)比較實(shí)驗(yàn)，表8結(jié)果說(shuō)明了本文方法值得進(jìn)一步深入研究。

表8 Jhotdraw開(kāi)源系統(tǒng)中的F-score指標(biāo)值對(duì)比

5 結(jié) 束 語(yǔ)

本文對(duì)設(shè)計(jì)模式實(shí)例識(shí)別的精確性問(wèn)題進(jìn)行了研究，提出一種基于文法產(chǎn)生式優(yōu)化的設(shè)計(jì)模式識(shí)別方法，該方法通過(guò)逆向工程工具抽取特征信息，在文獻(xiàn)[12]提出的可視化語(yǔ)言基礎(chǔ)上結(jié)合文獻(xiàn)[13]的文法，以文獻(xiàn)[14]給出的特征信息對(duì)設(shè)計(jì)模式實(shí)例進(jìn)行了描述，并通過(guò)增加文法產(chǎn)生式優(yōu)化了識(shí)別結(jié)果。實(shí)踐結(jié)果表明新方法具有較好精確率，解決了模式實(shí)例檢測(cè)結(jié)果的假陽(yáng)性及假陰性問(wèn)題。

[1] KACZOR O, GUEHENEUC Y G, HAMEL S. Identification of design motifs with pattern matching algorithms[J]. Information and Software Technology, 2010, 52(2): 152-168.

[2] AMPATZOGLOU A, CHARALAMPIDOU S, STAMELOS I. Research state of the art on GoF design patterns: a mapping study[J]. Journal of Systems and Software, 2013, 86(7): 1945-1964.

[3] YU D, ZHANG Y, CHEN Z. A comprehensive approach to the recovery of design pattern instances based on sub-patterns and method signatures[J]. Journal of Systems and Software, 2015, 88(5): 1-16.

[4] FONTANA F A, MAGGIONI S, RAIBULET C. Design patterns: a survey on their micro-structures[J]. Journal of Software: Evolution and Process, 2013, 25(1): 27-52.

[5] ZANONI M, FONTANA F A, STELLA F. On applying machine learning techniques for design pattern detection[J]. Journal of Systems and Software, 2015, 88(5): 102-117.

[6] DONG J, ZHAO J, SUN Y. A matrix based approach to recovering design patterns[J]. IEEE Transactions on Systems, Man and Cybernatics, 2009, 39(6): 1271-1282.

[7] BERNARDI M L, CIMITILE M, DI LUCCA G.. Design pattern detection using a DSL-driven graph matching approach[J]. Journal of Software: Evolution and Process, 2014, 26(12): 1233-1266.

[8] RASOOL G, PHILIPPOW I. Design pattern recovery based on annotations[J]. International Journal of Advances in Engineering Software, 2010, 41(4): 519-526.

[9] GUEHENEUC Y G, ANTONIOL G. DeMIMA: a multilayered approach for design pattern identification[J]. IEEE Transactions on Software Engineering, 2008, 34(5): 667-684.

[10] PETTERSON N, LOWE W, NIVRE J. Evaluation of accuracy in design pattern occurrence detection[J]. IEEE Transactions on Software Engineering, 2010, 36(4): 575-590.

[11] STENCEL K, WEGRZYNOWICZ P. Implementation variants of the singleton design pattern[C]//On the Move to Meaningful Internet Systems: OTM 2008 Workshops. Berlin Heidelberg: Springer, 2008: 396-406.

[12] COSTAGLIOLA G, DE LUCIA A, OREFICE S, et al. A classification framework to support the design of visual languages[J]. Journal of Visual Languages and Computing, 2002, 13(6): 573-600.

[13] COSTAGLIOLA G, DE LUCIA A, OREFICE S, et al. A parsing methodology for the implementation of visual systems[J]. IEEE Transactions on Software Engineering, 1997, 23(12): 777-799.

[14] RASOOL G, MADER P. A customizable approach to design patterns recognition based on feature types[J]. Arabian Journal for Science and Engineering, 2014, 39(12): 8851-8873.

編 輯 稅 紅

An Optimization Method for Design Pattern Identification Based on the Grammar Production

XIAO Zhuo-yu1, HE Pei2,3,4, YANG Xin-wei1, YANG Bang-ping1, CHEN Jun-xu1, and HU Zhen-tao1

(1. Swan College, Central South University of Forestry and Technology Changsha 410200; 2. School of Computer Science & Education Software, Guangzhou University Guangzhou 510006; 3. School of Computer and Communication Engineering, Changsha University of Science and Technology Changsha 410114; 4. Key Laboratory of High Confidence Software Technologies of Ministry of Education, Peking University Haidian Beijing 100871)

Aiming at obtaining the accurate detection results of design pattern, an optimization method for design pattern identification based on the grammar production is presented for solving the variant problem of design pattern. The method focuses on role attributes of participants and relationships of design pattern instances by visual grammar production, and identifies the overlapping patterns and the additional relations between the participant roles by adding the feature information of grammar production. Experiment results show that the proposed method can reduce the false positive results and the false negative results. F-score index comparison with other well-known algorithms indicates the effectiveness and merits of the proposed method.

design pattern detection; grammar production; pattern sharing; variant; visualization

TP311

A

10.3969/j.issn.1001-0548.2017.03.015

2015 ? 12 ? 28；

2016 ? 05 ? 26

國(guó)家自然科學(xué)基金(61170199)；湖南省大學(xué)生研究性學(xué)習(xí)和創(chuàng)新性實(shí)驗(yàn)計(jì)劃(湘教通[2015]84號(hào)197)；湖南省教學(xué)改革資助項(xiàng)目(湘教通[2016]400號(hào)1068)；廣東省自然科學(xué)基金(2015A030313501)；廣東省普通高校創(chuàng)新團(tuán)隊(duì)建設(shè)項(xiàng)目(2015KCXTD014)；湖南省教育廳重點(diǎn)基金項(xiàng)目(11A004)

肖卓宇(1979 ? )，男，副教授，主要從事程序理解、逆向工程、演化計(jì)算等方面的研究.