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

顧逸圣,曾國(guó)蓀

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

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

顧逸圣1,2*,曾國(guó)蓀1

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

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

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

0 引言

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

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

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

1 源代碼語(yǔ)法和語(yǔ)義的客觀性

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

1.1 語(yǔ)法和語(yǔ)義的客觀性

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

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

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

〈assignment_operator〉〈assignment_exp〉;

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

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

1.2 語(yǔ)法和語(yǔ)義的唯一性

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

1.3 語(yǔ)法和語(yǔ)義在源代碼搜索中的用途

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

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

2.1 用戶搜索請(qǐng)求表達(dá)的困難性

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

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

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

2.3 語(yǔ)法和語(yǔ)義搜索請(qǐng)求的表達(dá)法

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

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

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

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

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

圖1 搜索請(qǐng)求錄入界面

3 源代碼語(yǔ)法和語(yǔ)義的分析

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

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

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

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

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

syntaxStructMatch(squery,one_src_file)

{ if (isEmpty(squery))

return True;

//請(qǐng)求為空時(shí)直接返回“匹配”

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é)兩種符號(hào)表達(dá)的語(yǔ)法結(jié)構(gòu)串

if (squery=struct)

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

return True;

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

if (sameCount(squery,struct))

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

return True;

//近似認(rèn)為語(yǔ)法結(jié)構(gòu)匹配

else

return False;

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

}

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

3.2 “輸入/輸出”語(yǔ)義信息分析算法

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

輸入 語(yǔ)義信息搜索錄入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;

//輸入請(qǐng)求為空,degree為0

else

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

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

//計(jì)算匹配度

}

Pname←Iname+{oname};

returnFname,Pname,degree;

}

例如,用戶語(yǔ)義請(qǐng)求錄入為“int a, float b; int c”,而某段源代碼的語(yǔ)義串經(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)鍵詞匹配及可信度計(jì)算

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

算法3 可信度計(jì)算算法trustedScore。

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

輸出one_src_file的可信度score。

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

{ if (isEmpty(kquery))

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

{fscore←0,pscore←0;}

else

{Words←wordSegment(kquery);

//析取出多個(gè)關(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ù)名計(jì)算匹配得分

if (|Pwords|=1)

else

pscore←findSimilarity(Words,Pname,Pwords);

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

}

score←a1*fscore+a2*pscore+

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

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

returnscore;

}

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

4.1 搜索匹配原理及過程

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

4.2 搜索算法

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

算法4 搜索精化算法searchRefine。

輸入 用戶錄入搜索請(qǐng)求query, 待搜索的源代碼庫(kù)src_code_database, 限制搜索的代碼個(gè)數(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);

//獲取錄入的語(yǔ)法請(qǐng)求表達(dá)式

ioquery←getIOquery(query);

//獲取錄入的語(yǔ)義請(qǐng)求表達(dá)式

if (isEmpty(query))

//用戶請(qǐng)求全空

{Ok_files←random(src_code_database,n_max);

//隨機(jī)返回若干文件

returnOk_files;

}

while (one_src_file←nextFile(src_code_database) and

searchCount≤n_max)

{ if (syntaxStructMatch(squery,one_src_file))

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

{ 〈Fname,Pname,degree〉

←inoutMatch(ioquery,one_src_file);

//算法2 語(yǔ)義信息分析匹配

Rscores←Rscores+{trustedScore(kquery,one_src_file,

Fname,Pname,degree)};

//算法3 可信度計(jì)算

Rfiles←Rfiles+{one_src_file};

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

}

searchCount←searchCount+1;

}

Ok_files←sortByScore(Rfiles,Rscores);

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

returnOk_files;

}

5 搜索測(cè)試及分析

5.1 測(cè)試環(huán)境

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

5.2 測(cè)試用例

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

表1 搜索測(cè)試用例

5.3 結(jié)果分析

圖2為各個(gè)用例的搜索測(cè)試結(jié)果。可以看出相對(duì)于第一組,第二組中有4個(gè)用例的首條相關(guān)結(jié)果的排名更靠前,一個(gè)用例排名持平。分別記兩組的MRR為MRR1和MRR2,通過圖2的排名計(jì)算可得MRR1=0.378 5,MRR2=0.616 7。測(cè)試中本文算法對(duì)該指標(biāo)有超過62%的提升。

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

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

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

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

6 結(jié)語(yǔ)

當(dāng)前,每天都會(huì)產(chǎn)生無(wú)數(shù)的源代碼,人們對(duì)搜索源代碼的需求愈發(fā)渴望，然而目前基于單純關(guān)鍵詞的搜索卻無(wú)法達(dá)到精準(zhǔn)搜索。本文提出了一種基于語(yǔ)法和語(yǔ)義結(jié)合的源代碼精確搜索方法。該方法通過利用源代碼本身的語(yǔ)法和語(yǔ)義信息,接收經(jīng)過設(shè)計(jì)的用戶語(yǔ)法結(jié)構(gòu)信息、“輸入/輸出”語(yǔ)義信息及關(guān)鍵詞搜索請(qǐng)求表達(dá)式,分別提出了相應(yīng)的算法將用戶的請(qǐng)求與源代碼進(jìn)行匹配、計(jì)算可信度,并最終按可信度排序。對(duì)于相同的測(cè)試對(duì)象,將本文方法與單純的關(guān)鍵詞搜索比較,MRR指標(biāo)提升顯著,且排名靠前的那些源代碼確為所需,以此驗(yàn)證了方法的可行性。當(dāng)然,源代碼的語(yǔ)法和語(yǔ)義信息類型有很多,本文對(duì)于源代碼其他方面的語(yǔ)法語(yǔ)義尚未充分發(fā)掘。下一步的研究工作將是對(duì)源代碼中相關(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] 胡翔, 舒禮蓮. 基于語(yǔ)義網(wǎng)絡(luò)的海量源代碼搜索引擎[J]. 計(jì)算機(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] 孟驍. 基于語(yǔ)義網(wǎng)絡(luò)的智能搜索引擎研究[D]. 長(zhǎng)春: 東北師范大學(xué), 2011. (MENG X. Research of intelligent search engine based on semantic Web[D]. Changchun: Northeast Normal University, 2011.)

[7] 劉石, 李合, 王嘯吟, 等. 基于語(yǔ)法與語(yǔ)義分析的代碼搜索結(jié)果優(yōu)化[J]. 計(jì)算機(jī)科學(xué), 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] 滿海霞, 梁雅夢(mèng). 喬姆斯基層級(jí)與自然語(yǔ)言語(yǔ)法——從短語(yǔ)結(jié)構(gòu)語(yǔ)法到非轉(zhuǎn)換語(yǔ)法[J]. 外國(guó)語(yǔ)文, 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è)計(jì)語(yǔ)言編譯原理[M]. 北京: 國(guó)防工業(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)秀學(xué)科帶頭人計(jì)劃項(xiàng)目(10XD1404400);同濟(jì)大學(xué)實(shí)驗(yàn)教改項(xiàng)目(0800104214)。

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

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.