基于語法和語義結(jié)合的源代碼精確搜索方法

顧逸圣,曾國蓀

(1.同濟大學 計算機科學及技術(shù)系,上海 200092; 2.嵌入式系統(tǒng)與服務(wù)計算教育部重點實驗室,上海 200092) (*通信作者電子郵箱qswy929@163.com)

基于語法和語義結(jié)合的源代碼精確搜索方法

顧逸圣1,2*,曾國蓀1

(1.同濟大學 計算機科學及技術(shù)系,上海 200092; 2.嵌入式系統(tǒng)與服務(wù)計算教育部重點實驗室,上海 200092) (*通信作者電子郵箱qswy929@163.com)

針對在編寫軟件、復(fù)用源代碼的過程中僅依靠關(guān)鍵詞無法精準搜索到適用源代碼的問題,提出一種將語法和語義結(jié)合的源代碼精準搜索方法。首先依據(jù)源代碼語法語義的客觀和唯一性,增加語法結(jié)構(gòu)和“輸入/輸出”語義作為用戶錄入請求的一部分,并規(guī)范了具體的請求格式;然后在此基礎(chǔ)上分別設(shè)計源代碼語法匹配算法、“輸入/輸出”語義匹配算法、關(guān)鍵詞兼容匹配，以及源代碼搜索結(jié)果可信度計算算法;最后綜合上述算法實現(xiàn)對源代碼的精準搜索。測試結(jié)果表明:與單純的關(guān)鍵詞搜索相比,提出的方法對搜索的平均排序倒數(shù)(MRR)有超過62%的提升,有助于實現(xiàn)源代碼的精準搜索。

軟件編寫;源代碼復(fù)用;語法語義;匹配搜索

0 引言

在信息化時代,社會運作的方方面面都離不開軟件。在軟件編寫的過程中,大量的源代碼無疑是一筆筆寶貴的“財富”。為了盡可能利用這些“財富”,有人試圖將源代碼看作普通的文本,借助通用搜索引擎的技術(shù),建立基于關(guān)鍵詞的源代碼搜索引擎。這種方法技術(shù)成熟,實施成本低,但是基于關(guān)鍵詞的搜索方法最大的問題是結(jié)果不精確,這個問題在目前的源代碼搜索引擎中普遍存在:返回的結(jié)果中往往混雜著聲明、類定義等,造成用戶選擇困難。為此,學者們利用例如語法、語義等其他多種信息,開展開源代碼搜索,以提高搜索精度。

在基于源代碼語法的搜索方面:Bajracharya等[1]將源代碼搜索從基于關(guān)鍵詞的全文搜索變?yōu)榛谠创a結(jié)構(gòu)的搜索,支持“細節(jié)搜索”,并將其分為“Components”“Component Use”等五類。Farah等[2]對源代碼搜索引擎Open Hub深入研究，總結(jié)出其本質(zhì)就是將搜索需求按函數(shù)、結(jié)構(gòu)體、類、接口等進行分類。以上方法對搜索內(nèi)容進行類別細分,但只是簡單根據(jù)代碼的組成并沒有實質(zhì)涉及語法的研究。Paul等[3]則進一步通過定義一系列的通配符,對C語言的語法集進行抽象形成代碼模式自動機(Code Pattern Automaton, CPA),通過解釋器進行匹配,充分展示了利用語法進行抽象搜索的可行性,然而此方法接收的通配符描述過于復(fù)雜,難以推廣。在基于源代碼語義的搜索方面:Hill等[4]提出的“自然語言源碼定位”可應(yīng)用于海量數(shù)據(jù),將源代碼中的變量名稱進行語義猜測,構(gòu)建一個包含海量源碼變量使用關(guān)系與詞素拓展集的數(shù)據(jù)庫。胡翔等[5]將Hill的方法運用于源代碼搜索,并結(jié)合傳統(tǒng)的程序分析技術(shù),提出一種海量源碼分析的新方法。孟驍[6]通過以語義網(wǎng)絡(luò)為文本關(guān)鍵字建立近義詞索引的方法,改善了代碼搜索問題中近義詞無法被關(guān)鍵字匹配的問題。上述方法增加了源代碼搜索輸入的容錯度,但是只是對其中某些元素的釋義,并沒有提取出源代碼蘊涵的功能語義。劉石等[7]利用“超鏈接引導(dǎo)的主題搜索”(Hyperlink-Induced Topic Search, HITS)算法分析技術(shù)對Java語言的代碼模型進行二次周游,從而實現(xiàn)了對搜索應(yīng)用程序編程接口(Application Programming Interface, API)實現(xiàn)代碼和調(diào)用代碼的區(qū)分、并從搜索結(jié)果摘要等方面進行了優(yōu)化。Keivanloo等[8]利用本體描述語言(Ontology Web Language, OWL)對面向?qū)ο蟮木幊陶Z言的各個屬性進行語義分析并建模,解決了搜索到的源代碼存在外部依賴關(guān)系從而不完整的問題。Stolee等[9-10]則提出了一種全新的基于“輸入/輸出”的源代碼搜索方式，編寫輕量級的需求描述作為輸入和期望的輸出并對其分析,將程序的語義與描述其行為的約束進行映射；因為其分析過程的復(fù)雜性,目前該方法還只是停留在理論階段。

可見,借助于源代碼的語法或語義信息,搜索源代碼的方式能夠更加豐富,有助提高搜索的準確率。然而,縱觀上述研究,目前的研究多數(shù)只針對語法、語義的其中一個方面展開?，F(xiàn)階段將語法與語義相結(jié)合,共同運用于源代碼的搜索的工作現(xiàn)階段開展較少。本文擬將函數(shù)作為源代碼搜索的粒度,提取并利用函數(shù)源代碼的語法結(jié)構(gòu)和“輸入/輸出”語義信息進行搜索，通過語法和語義相結(jié)合的手段探索豐富源代碼搜索錄入形式、提高搜索精準度的途徑。

1 源代碼語法和語義的客觀性

源代碼是一段按照某種程序設(shè)計語言規(guī)范編寫的形式化文本,因此反映了該語言的特征。記源代碼L為三元組:L=(T,G,S)。其中:T是整個源代碼的文本;G是文本的語法規(guī)則;S是文本的語義規(guī)則。本章以C語言為例,說明源代碼的語法和語義的客觀性和唯一性。

1.1 語法和語義的客觀性

自然語言中,為了確保某個區(qū)域內(nèi)個體間信息交換的順暢進行,對于用來交流、接收和傳遞信息的字符串,必須遵守相同的一組規(guī)則[11],如漢語規(guī)則、英語規(guī)則等。類似地,為了使計算機能夠識別輸入的源代碼字符串,必須同樣對源代碼字符串的組成制定規(guī)則,這都屬于語法的范疇。

源代碼的語法是指有一組規(guī)則,用其能夠形成和產(chǎn)生一個計算機程序。這組規(guī)則中包括了單詞符號的形成規(guī)則,以及如何從單詞符號形成表達式、語句、函數(shù)等語言規(guī)則。設(shè)s是程序設(shè)計語言源代碼中的某一句,則語法的客觀性體現(xiàn)在:?s((s∈T) ? ?!f(x)∧(f(s)∈G)),其中f(x)是一個從單詞符號串x到語言規(guī)則的映射。即每一條語句都能找到它對應(yīng)的語言規(guī)則。映射f實際中可以采用巴科斯范式(Backus-Naur Form, BNF)等形式表現(xiàn)。很難想象,僅僅幾十條BNF規(guī)則就可以描述所有C語言源代碼的語法。如C語言的賦值語句就可以表示為以下的BNF,通過它就能客觀確定所有賦值語句的操作。

〈assignment_exp〉 ::=〈conditional_exp〉 | 〈unary_exp〉

〈assignment_operator〉〈assignment_exp〉;

〈assignment_operator〉 ::=′=′ | ′*=′ | ′/=′ | ′%=′ | ′+=′ | ′-=′| ′lt;lt;=′ | ′gt;gt;=′ | ′amp;=′ | ′^=′ | ′|=′

源代碼的語義是指能夠用其定義源代碼的功能和意義的一組規(guī)則[12]。無論是源代碼執(zhí)行前還是執(zhí)行后的語義,都可以歸類在操作語義、指稱語義、公理語義之中。語義的客觀性可以從源代碼的功能、正確性等方面體現(xiàn)。例如對整型變量Y執(zhí)行“Y=5”這條賦值語句就可用操作語義“〈Y:=5,σ〉→σ′”表示,其中:σ表示的是狀態(tài)函數(shù),σ′表示執(zhí)行完賦值命令后的終態(tài)。執(zhí)行1到100整數(shù)求和的操作的語義正確性可以借助以下公理:“P:=0;I:=1 {P=0∧I=1} (while(I=101) doP:=P+I;I:=I+1)”驗證。

1.2 語法和語義的唯一性

每個人在世上都是唯一的個體,在思想、性格、行為等方面的不同造就了其個性。由于個性差異對于同一件事不同人有全然不同的處理方式:到達同一個目的地會選擇不同的出行方式;面對同樣的題目能夠?qū)懗霾煌奈恼碌?。為實現(xiàn)相同的功能,不同的程序員會有全然不同的編寫源代碼的方式。因為每條語句都可能有區(qū)別,源代碼這種近乎的唯一性也會傳遞到其中蘊涵的語法和語義的信息中,成為其相互區(qū)分的特征。如果認為不同的人很容易寫出兩段格式、變量、算法都一樣的源代碼,那就無異于忽略了人的個性因素。

1.3 語法和語義在源代碼搜索中的用途

源代碼語法和語義的客觀性和唯一性對于源代碼的搜索有很大的幫助。假設(shè)T1、T2是兩段源代碼文本,G°S(X)是對任意源代碼文本串X進行語法和語義分析后的結(jié)果,那么有:G°S(T1)=G°S(T2)→T1=T2。換而言之,對任意的源代碼都可以分析其蘊涵的語法和語義信息;通過這兩方面的信息,也可以唯一確定所需的源代碼，因而通過語法和語義信息來搜索源代碼理論上是可行的。本文的目的就是設(shè)計一種切實可行的方法以表達和分析這些信息,為搜索作鋪墊。特別說明的是,本文中的源代碼指的是“函數(shù)片段”,即一段完整的函數(shù)源代碼。

2 用戶搜索錄入需求的描述

2.1 用戶搜索請求表達的困難性

雖然源代碼的語法和語義具有客觀性與唯一性,但正如人往往很難僅依靠語言或者文字表達自己的需求,同樣,對于某時某刻需要什么樣的源代碼,搜索者也是很難完全清楚地描述。在描述時,由于交互方式的局限,關(guān)鍵詞是一種為數(shù)不多的對文本信息的檢索手段,因此現(xiàn)今用戶采取錄入關(guān)鍵詞的方式提交搜索請求。單純的關(guān)鍵詞無法對問題精準描述,卻又沒有找到比之更簡單有效的方法,這正是目前用戶表達搜索請求的困難之處。

2.2 關(guān)鍵詞搜索情況的特性分析

傳統(tǒng)的利用關(guān)鍵詞對所需源代碼進行搜索,依靠的是關(guān)鍵詞中對語法和語義信息的部分表達,是模糊不完整的。用戶既不能準確地歸結(jié)出與所需源代碼密切相關(guān)的關(guān)鍵詞,依靠關(guān)鍵詞也多半不能獲取相關(guān)的源代碼。例如K={k1,k2,…,kn} 是在搜索某一源代碼時的一組關(guān)鍵詞,Rs為對應(yīng)的結(jié)果,Re為用戶期望的結(jié)果,C為閾值常量,則?K((Input(K)?|Rs|)∧(|Rs|∩|Re|lt;C)),且只是在不區(qū)分輸入順序的情況下返回n個關(guān)鍵詞的并集,這便暴露了傳統(tǒng)關(guān)鍵詞搜索的不精確性。進而,如果能在搜索時考慮到關(guān)鍵詞出現(xiàn)的位置及順序,以區(qū)分關(guān)鍵詞的重要程度,結(jié)合客觀的語法和語義,那么這種改進后的搜索將能大幅提升搜索的精準度。

2.3 語法和語義搜索請求的表達法

僅憑關(guān)鍵詞搜索源代碼依然難以表達用戶需求，搜索往往不精確,應(yīng)當增加一些請求表達的方式,以便用戶提供盡可能多的信息。本文提出一種將語法、語義、關(guān)鍵詞三者結(jié)合用于源代碼的搜索的方法。其中,關(guān)鍵詞搜索的形式用戶經(jīng)常接觸,不需要另行設(shè)計,而用戶對語法和語義的搜索表達形式則需特別交代。

源代碼的語法信息包括多種,本文選擇結(jié)構(gòu)信息用以描述源代碼語法。其中,諸如抽象語法樹信息雖是在源代碼語法分析階段一一對應(yīng)生成,表示的結(jié)構(gòu)信息完備且不存在二義性,但是圖的結(jié)構(gòu)使其注定不滿足方便用戶錄入的要求。因而本文采取一種折中的方法,僅將源代碼中分支和循環(huán)結(jié)構(gòu)的描述作為用戶錄入的語法請求表達。用戶的請求可以分為兩種情形。第一種情形下用戶清楚所需函數(shù)源代碼的語法結(jié)構(gòu)及順序,此時定義符號“c:()”表示一個分支結(jié)構(gòu),“l(fā):()”表示一個循環(huán)結(jié)構(gòu)。用戶錄入這兩個符號的先后及嵌套順序就代表了源代碼中分支和循環(huán)的組成:如請求“l(fā):(c:())”就表示先出現(xiàn)循環(huán)并且其中嵌套一個分支,“l(fā):()c:()”表示先循環(huán),后跟隨一個分支。第二種情形下用戶只能提供每種結(jié)構(gòu)出現(xiàn)的數(shù)目,則可以分別錄入分支、循環(huán)等結(jié)構(gòu)的數(shù)目,來搜索所需的源代碼。這種以分支和循環(huán)結(jié)構(gòu)作為源代碼語法特征的方式,雖然不如語法樹那樣完備,比如無法表示代碼中的遞歸結(jié)構(gòu),但通過確定這兩種結(jié)構(gòu)的數(shù)目或者出現(xiàn)的順序及嵌套關(guān)系,都能輔助過濾過大量無關(guān)代碼,是一種利用語法信息提高搜索精準度的可行之策。

同樣,源代碼的語義信息有多種,本文將代碼的“輸入/輸出”功能語義作為讓用戶錄入的語義信息。對函數(shù)參數(shù)表中的參數(shù)以及返回的參數(shù)的讀/寫通常反映了函數(shù)源代碼的功能,所以本文中將這些參數(shù)視為源代碼的“輸入/輸出”。在錄入請求的階段,用戶使用文本串對“輸入/輸出”的參數(shù)類型和名稱進行描述。定義語義請求為“itype1iname1,itype2iname2,…;otype oname”的形式,其中分號以左為函數(shù)接收的參數(shù)表,以右為函數(shù)的返回參數(shù)。type是“輸入/輸出”的參數(shù)類型,name是“輸入/輸出”參數(shù)名稱。特別地,當參數(shù)為空時,規(guī)定type和name均為void。這樣定義語義請求,形式上直觀全面地表達了“輸入/輸出”語義,用戶操作時錄入的難度也較低。不過參數(shù)的順序和數(shù)目是“輸入/輸出”語義重要特征,因而用戶在搜索錄入時要注意盡量精確描述請求中的每個參數(shù)及它們的次序,這些都可作為語義匹配的依據(jù)。

2.4 用戶搜索錄入需求操作界面

根據(jù)2.3節(jié)的討論,可以設(shè)計出圖1中的界面,等待用戶輸入源代碼搜索請求。按提示錄入了對所需源代碼的描述后,三個輸入框中的文本分別記作kquery、squery和ioquery,它們就構(gòu)成了用戶的請求表達語句，記作query。下一步的工作就將針對用戶在此提交的各項請求表達,分析源代碼中的對應(yīng)的信息,并按特定方法進行匹配。

圖1 搜索請求錄入界面

3 源代碼語法和語義的分析

3.1 語法結(jié)構(gòu)信息分析算法

在2.3節(jié)中明確了用戶通過“c:()”“l(fā):()”兩種符號的組合表示源代碼的語法結(jié)構(gòu)請求,那么在分析目標源代碼結(jié)構(gòu)時,一種自然而然的思想,就是分析其中表示結(jié)構(gòu)信息的保留字標志,將一段函數(shù)源代碼中分支和循環(huán)結(jié)構(gòu)信息的出現(xiàn)關(guān)系同樣利用上述兩種符號表達,形成語法結(jié)構(gòu)串。這樣在匹配時通過分別統(tǒng)計每一種符號出現(xiàn)的總數(shù),以及符號的先后順序、嵌套關(guān)系,比較所有的特征是否相符,就能夠判定用戶請求是否與當前源代碼相匹配。以分析對象是一段C語言的函數(shù)源代碼文件(用變量one_src_file)為例,算法1描述了對其進行語法結(jié)構(gòu)分析的整個過程。

算法1 語法結(jié)構(gòu)信息分析匹配算法syntaxStructMatch。

輸入 語法信息搜索錄入squery, 一段函數(shù)的源代碼文件one_src_file。

輸出 源代碼文件是否語法結(jié)構(gòu)匹配True/False。

syntaxStructMatch(squery,one_src_file)

{ if (isEmpty(squery))

return True;

//請求為空時直接返回“匹配”

condition←{"if","else","case",…};

//分支結(jié)構(gòu)保留字

loop←{"for","do","while",…};

//循環(huán)結(jié)構(gòu)保留字

nest←{"{","}",…};

//結(jié)構(gòu)嵌套保留字

text←readSourceCode(one_src_file);

struct←geneStructString(text,condition,loop,nest);

//構(gòu)造用3.3節(jié)兩種符號表達的語法結(jié)構(gòu)串

if (squery=struct)

//源代碼文件與用戶語法搜索需求相同

return True;

//語法結(jié)構(gòu)匹配

if (sameCount(squery,struct))

//錄入的分支、循環(huán)的數(shù)目與目標相同

return True;

//近似認為語法結(jié)構(gòu)匹配

else

return False;

//語法結(jié)構(gòu)不匹配

}

執(zhí)行算法1后,假設(shè)用戶錄入為“l(fā):(l:())”,則有且僅有雙重循環(huán)結(jié)構(gòu)的源代碼的分析結(jié)果為“l(fā):(l:())”,即與搜索匹配。若錄入的只是查找含有“2個循環(huán)”的源代碼,除了雙重循環(huán)的源代碼,單獨循環(huán)兩次的源代碼也會被判定為匹配,這在實際應(yīng)用過程中可能是合理的。

3.2 “輸入/輸出”語義信息分析算法

算法2 “輸入/輸出”的語義信息分析匹配算法inoutMatch。

輸入 語義信息搜索錄入ioquery, 一段函數(shù)的源代碼文件one_src_file。

輸出 函數(shù)名Fname，參數(shù)名Pname, 匹配度degree。

inoutMatch(ioquery,one_src_file)。

{line←readDefineLine(one_src_file);

//讀取函數(shù)定義行

Fname←wordSegment(line);

//分詞后的函數(shù)名

text←readSourceCode(one_src_file);

〈Itype,Iname,otype,oname〉←getParaInfo(line,text);

//獲取函數(shù)“輸入/輸出”參數(shù)的類型和名稱

if (isEmpty(ioquery))

degree←0;

//輸入請求為空,degree為0

else

{inout←geneInoutString(Itype,Iname,otype,oname);

//構(gòu)造同3.3節(jié)用戶語義請求形式的語義串

//計算匹配度

}

Pname←Iname+{oname};

returnFname,Pname,degree;

}

例如,用戶語義請求錄入為“int a, float b; int c”,而某段源代碼的語義串經(jīng)過分析為“byte a, float b; int c”,那么cioquery=cinout=3,u=2(float b和int c),n=3(a、b和c),t=2(float和int),degree為5/9。

3.3 關(guān)鍵詞匹配及可信度計算

算法2返回的源代碼三方面的語義信息,將會在關(guān)鍵詞匹配和代碼可信度計算中再次用到。本節(jié)引入3個匹配得分變量:fscore是錄入的關(guān)鍵詞和源代碼函數(shù)名的匹配得分,通過找出分詞后的用戶關(guān)鍵詞和函數(shù)名中的公共單詞,將這些單詞在兩者中的出現(xiàn)位次作為向量每一維的值,構(gòu)造成兩個向量,計算相似度而得。類似地,pscore是錄入的關(guān)鍵詞和源代碼參數(shù)名的匹配得分,利用分詞后的用戶關(guān)鍵詞、“輸入/輸出”參數(shù)名和兩者的公共單詞,構(gòu)造兩個向量,計算相似度而得。score則是總的可信度得分,由fscore、pscore、傳統(tǒng)的“詞頻-逆文檔頻率”(Term Frequency-Inverse Document Frequency, TF-IDF)關(guān)鍵詞全文匹配度[13]和之前求得的語義匹配度degree,四者的加權(quán)和構(gòu)成。這是一種將多方面的有效信息充分合理利用的手段。以一個源代碼文件one_src_file為對象,將關(guān)鍵詞匹配及可信度計算的過程在算法3中展現(xiàn)。

算法3 可信度計算算法trustedScore。

輸入 錄入的關(guān)鍵詞請求kquery、one_src_file、Fname、Pname、degree。

輸出one_src_file的可信度score。

trustedScore(kquery,one_src_file,Fname,Pname,degree)

{ if (isEmpty(kquery))

//關(guān)鍵詞搜索請求為空

{fscore←0,pscore←0;}

else

{Words←wordSegment(kquery);

//析取出多個關(guān)鍵詞

Fwords←{f|f∈Words∩Fname};

//求關(guān)鍵詞和函數(shù)名中公共及匹配的單詞集合

Pwords←{p|p∈Words∩Pname};

//求關(guān)鍵詞和參數(shù)名中公共及匹配的單詞集合

if (|Fwords|=1)

else

fscore←findSimilarity(Words,Fname,Fwords);

//根據(jù)錄入關(guān)鍵詞和源代碼函數(shù)名計算匹配得分

if (|Pwords|=1)

else

pscore←findSimilarity(Words,Pname,Pwords);

//根據(jù)錄入關(guān)鍵詞和函數(shù)參數(shù)名計算匹配得分

}

score←a1*fscore+a2*pscore+

a3*tf_idf(Words,one_scr_file)+a4*degree;

// tf_idf():計算傳統(tǒng)的關(guān)鍵詞全文匹配度

returnscore;

}

4 語法和語義結(jié)合的精確搜索算法

4.1 搜索匹配原理及過程

源代碼搜索的最終目的是滿足用戶需求,既然用戶在搜索時已經(jīng)提供了語法、語義和關(guān)鍵詞三方面的請求,那就應(yīng)該充分利用這些信息,匹配用戶的請求。整個源代碼精準搜索的過程如下:1)提取和過濾用戶的搜索請求,進行預(yù)處理,分別形成對應(yīng)的規(guī)范格式。2)進行語法精確匹配:源代碼語法結(jié)構(gòu)信息可以精確獲取,因此可以精確匹配用戶的語法要求,只有當源代碼的語法結(jié)構(gòu)完全符合用戶搜索時提供的語法要求,這樣的源代碼才是有效的,特別用戶搜索時提供的語法要求為“空”時,則認為任何源代碼都是有效的。如果語法匹配失敗,則此次源代碼搜索失敗、結(jié)束。3)進行語義近似匹配:正如3.2節(jié)所述,源代碼的語義信息很難精確獲取,所以只能用語義匹配度來近似。本文通過分析源代碼隱含的輸入、輸出變量特征,比較匹配用戶搜索時提供的輸入、輸出請求,顯然匹配度高對應(yīng)的源代碼更符合用戶要求。4)進行關(guān)鍵字匹配,獲得本次搜索源代碼的可信度分值,為大量搜索結(jié)果排序提高了依據(jù)。關(guān)鍵字匹配過程一方面利用第2)～3)步的語法、語義匹配的結(jié)果,提高了搜索的精度,另一方面也可兼容傳統(tǒng)搜索引擎的方法。5)重復(fù)第2)～4)步,直至搜索了規(guī)定個數(shù)的源代碼文件,可信度高的源代碼文件排在前面。

4.2 搜索算法

用戶通過圖1界面錄入了請求表達式后,根據(jù)4.1節(jié)的匹配原理,利用算法4“搜索精化算法”,即可更精確地返回滿足用戶需求的函數(shù)源代碼。特別地,該算法能夠根據(jù)給定的值設(shè)置限制搜索的代碼數(shù)量,以防搜索時間過長。

算法4 搜索精化算法searchRefine。

輸入 用戶錄入搜索請求query, 待搜索的源代碼庫src_code_database, 限制搜索的代碼個數(shù)n_max。

輸出 符合條件的函數(shù)源代碼文件集合Ok_files。

searchRefine(query,src_code_database,n_max)

{Rfiles←?,Rscores←?;

//記錄待排序文件及得分的有序集

searchCount←0;

//已搜索的次數(shù)

kquery←getKquery(query);

//獲取預(yù)處理后的關(guān)鍵詞

squery←getSquery(query);

//獲取錄入的語法請求表達式

ioquery←getIOquery(query);

//獲取錄入的語義請求表達式

if (isEmpty(query))

//用戶請求全空

{Ok_files←random(src_code_database,n_max);

//隨機返回若干文件

returnOk_files;

}

while (one_src_file←nextFile(src_code_database) and

searchCount≤n_max)

{ if (syntaxStructMatch(squery,one_src_file))

//算法1 語法結(jié)構(gòu)分析匹配

{ 〈Fname,Pname,degree〉

←inoutMatch(ioquery,one_src_file);

//算法2 語義信息分析匹配

Rscores←Rscores+{trustedScore(kquery,one_src_file,

Fname,Pname,degree)};

//算法3 可信度計算

Rfiles←Rfiles+{one_src_file};

//記錄對應(yīng)的文件

}

searchCount←searchCount+1;

}

Ok_files←sortByScore(Rfiles,Rscores);

//根據(jù)可信度的降序,返回結(jié)果文件集合

returnOk_files;

}

5 搜索測試及分析

5.1 測試環(huán)境

關(guān)于測試的硬件環(huán)境,使用的計算機的CPU為2.7 GHz Intel Core i5,內(nèi)存為8 GB。在軟件方面,進行測試前編寫了Java程序,接收用戶的語法、語義和關(guān)鍵詞請求,將用戶的關(guān)鍵詞請求轉(zhuǎn)發(fā)到SearchCode源代碼搜索引擎,把前100項結(jié)果對應(yīng)的源文件保存到本地,按函數(shù)為粒度拆分后進一步調(diào)用算法4的Java實現(xiàn)版本進行搜索排序,并在最后以函數(shù)為粒度返回結(jié)果。

5.2 測試用例

本文將搜索表1中常見的5種算法的C語言代碼作為測試的用例。測試分為兩組:第一組在SearchCode引擎中錄入表1的關(guān)鍵詞部分進行搜索;第二組使用5.1節(jié)編寫的程序,除了利用相同的關(guān)鍵詞,同時加入每個算法用例可能包含的語法結(jié)構(gòu)和“輸入/輸出”語義的描述信息。程序中進行可信度計算時的權(quán)值(a1,a2,a3,a4)=(0.3, 0.15, 0.25, 0.3),根據(jù)每一項的重要程度按經(jīng)驗設(shè)置；限制搜索的代碼個數(shù)n_max設(shè)置為100。對于兩組的返回結(jié)果,通過統(tǒng)計首條與搜索請求相關(guān)結(jié)果的排名,并對5次搜索的平均排序倒數(shù)(Mean Reciprocal Rank, MRR)[14]進行計算,來衡量搜索的精準程度。

表1 搜索測試用例

5.3 結(jié)果分析

圖2為各個用例的搜索測試結(jié)果?？梢钥闯鱿鄬τ诘谝唤M,第二組中有4個用例的首條相關(guān)結(jié)果的排名更靠前,一個用例排名持平。分別記兩組的MRR為MRR1和MRR2,通過圖2的排名計算可得MRR1=0.378 5,MRR2=0.616 7。測試中本文算法對該指標有超過62%的提升。

圖2 搜索測試的排名結(jié)果

進一步以用例1為例,列出第二組測試中返回的前10項函數(shù)結(jié)果、對應(yīng)的可信度,以及在SearchCode中的原始排名(通過在其搜索頁面錄入關(guān)鍵詞,并篩選C語言源代碼后獲得),見表2。

經(jīng)過統(tǒng)計,排名前10的結(jié)果中只有4條結(jié)果同樣在SearchCode中排在前十,其余都是原先排名靠后的結(jié)果。但通過分析這些結(jié)果的源代碼發(fā)現(xiàn),它們又的確都是和用戶搜索需求高度匹配的,反而是在原始排名的前十項中包含了與請求無關(guān)的信息。究其原因,不外乎是在SearchCode引擎中單單錄入關(guān)鍵詞不能利用到源代碼蘊含的語法和語義信息,導(dǎo)致搜索的不精準,而本文結(jié)合了源代碼語法和語義的方法則改善了這一問題。測試結(jié)果說明:利用了源代碼語法、語義信息搜索得到的結(jié)果更準確可信。

表2 第二組測試中用例1的詳細結(jié)果

6 結(jié)語

當前,每天都會產(chǎn)生無數(shù)的源代碼,人們對搜索源代碼的需求愈發(fā)渴望，然而目前基于單純關(guān)鍵詞的搜索卻無法達到精準搜索。本文提出了一種基于語法和語義結(jié)合的源代碼精確搜索方法。該方法通過利用源代碼本身的語法和語義信息,接收經(jīng)過設(shè)計的用戶語法結(jié)構(gòu)信息、“輸入/輸出”語義信息及關(guān)鍵詞搜索請求表達式,分別提出了相應(yīng)的算法將用戶的請求與源代碼進行匹配、計算可信度,并最終按可信度排序。對于相同的測試對象,將本文方法與單純的關(guān)鍵詞搜索比較,MRR指標提升顯著,且排名靠前的那些源代碼確為所需,以此驗證了方法的可行性。當然,源代碼的語法和語義信息類型有很多,本文對于源代碼其他方面的語法語義尚未充分發(fā)掘。下一步的研究工作將是對源代碼中相關(guān)更深層次的信息的挖掘和利用。

References)

[1] BAJRACHARYA S, NGO T, LINSTEAD E, et al. Sourcerer: a search engine for open source code supporting structure-based search [C]// OOPSLA 2006: Companion To the 21st ACM SIGPLAN Symposium on Object-Oriented Programming Systems, Languages, and Applications. New York: ACM, 2006: 681-682.

[2] FARAH G, TEJADA J S, CORREAL D. OpenHub: a scalable architecture for the analysis of software quality attributes [C]// MSR 2014: Proceedings of the 11th Working Conference on Mining Software Repositories. New York: ACM, 2014: 420-423.

[3] PAUL S, PRAKASH A. A framework for source code search using program patterns[J]. IEEE Transactions on Software Engineering, 1994, 20(6): 463-475.

[4] HILL E, POLLOCK L, VIJAY-SHANKER K. Improving source code search with natural language phrasal representations of method signatures [C]// ASE 2011: Proceedings of the 2011 26th IEEE/ACM International Conference on Automated Software Engineering. Washington, DC: IEEE Computer Society, 2011: 524-527.

[5] 胡翔, 舒禮蓮. 基于語義網(wǎng)絡(luò)的海量源代碼搜索引擎[J]. 計算機與現(xiàn)代化, 2014, 30(7): 19-23. (HU X, SHU L L. Search engine of massive source code based on semantic network[J]. Computer and Modernization, 2014, 30(7): 19-23.)

[6] 孟驍. 基于語義網(wǎng)絡(luò)的智能搜索引擎研究[D]. 長春: 東北師范大學, 2011. (MENG X. Research of intelligent search engine based on semantic Web[D]. Changchun: Northeast Normal University, 2011.)

[7] 劉石, 李合, 王嘯吟, 等. 基于語法與語義分析的代碼搜索結(jié)果優(yōu)化[J]. 計算機科學, 2009, 32(8): 165-168. (LIU S, LI H, WANG X Y, et al. Enhancement of code search results using syntax and semantic analysis[J]. Computer Science, 2009, 32(8): 165-168.)

[8] KEIVANLOO I, ROOSTAPOUR L, SCHUGERL P, et al. SE-CodeSearch: a scalable semantic Web-based source code search infrastructure [C]// ICSM 2010: Proceedings of the 2010 26th IEEE International Conference on Software Maintenance. Piscataway, NJ: IEEE, 2010: 1-5.

[9] STOLEE K T, ELBAUM S, DOBOS D. Solving the search for source code[J]. ACM Transactions on Software Engineering and Methodology, 2014, 23(3): 26-26.

[10] STOLEE K T, ELBAUM S, DWYER M B, et al. Code search with input/output queries: generalizing, ranking, and assessment[J]. Journal of Systems and Software, 2016, 116(6): 35-48.

[11] 滿海霞, 梁雅夢. 喬姆斯基層級與自然語言語法——從短語結(jié)構(gòu)語法到非轉(zhuǎn)換語法[J]. 外國語文, 2015, 31(3): 84-89. (MAN H X, LIANG Y M. Chomsky hierarchy and natural language grammars: from phrase structure grammar to non-transformational grammar[J]. Foreign Language and Literature, 2015, 31(3): 84-89.)

[12] 陳火旺. 程序設(shè)計語言編譯原理[M]. 北京: 國防工業(yè)出版社, 2000. (CHEN H W. Programming Language and Compile Principles[M]. Beijing: National Defense Industry Press, 2000.)

[13] RAJESHWARKAR A, NAGORI M. Optimizing search results using Wikipedia based ESS and enhanced TF-IDF approach[J]. International Journal of Computer Applications, 2016, 144(12): 23-28.

[14] FREITAS A, OLIVEIRA J G, ORIAIN S, et al. Querying linked data using semantic relatedness: a vocabulary independent approach [C]// NLDB 2011: Proceedings of the 16th International Conference on Application of Natural Language to Information Systems. Berlin: Springer, 2011: 40-51.

Accuratesearchmethodforsourcecodebycombiningsyntacticandsemanticqueries

GU Yisheng1,2*, ZENG Guosun1

(1.DepartmentofComputerScienceandTechnology,TongjiUniversity,Shanghai200092,China;2.EmbeddedSystemandServiceComputingKeyLaboratoryofMinistryofEducation,Shanghai200092,China)

In the process of programming and source code reuse, since simple keyword-based code search often leads to inaccurate results, an accurate search method for source code was proposed. Firstly, according to the objectivity and uniqueness of syntax and semantics, the syntactic structure and semantics of I/O of a function in source code were considered as part of a query. Such query should be submitted following a regularized format. Secondly, the syntactic structure, semantics of I/O, keyword-compatible match algorithms along with the reliability calculation algorithm were designed. Finally, the accurate search method by combining syntactic and semantic queries was realized by using the above algorithms. The test result shows that the proposed method can improve Mean Reciprocal Rank (MRR) by more than 62% compared with the common keyword-based search method, and it is effective in improving the accuracy of source code search.

software programming; source code reuse; syntax and semantics; matching search

2017- 04- 21;

2017- 06- 09。

上海市優(yōu)秀學科帶頭人計劃項目(10XD1404400);同濟大學實驗教改項目(0800104214)。

顧逸圣(1992—),男,上海人,碩士研究生,主要研究方向:軟件工程、代碼搜索; 曾國蓀(1964—),男,江西吉安人,教授,博士,博士生導(dǎo)師,主要研究方向:并行計算、可信軟件、信息安全。

1001- 9081(2017)10- 2958- 06

10.11772/j.issn.1001- 9081.2017.10.2958

TP311.1

A

This work is partially supported by the Program of Shanghai Subject Chief Scientist (10XD1404400), the Experimental Teaching Reform Project of Tongji University (0800104214).

GUYisheng, born in 1992, M. S. candidate. His research interests include software engineering, source code search.

ZENGGuosun, born in 1964, Ph. D., professor. His research interests include parallel computing, trusted computing, information security.