基于抽象語(yǔ)法樹(shù)的軟件語(yǔ)義分析方法研究.pdf

1、隨著計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展，軟件質(zhì)量面臨著新的任務(wù)和考驗(yàn)，軟件語(yǔ)義分析作為一種提高軟件質(zhì)量的重要手段受到了社會(huì)的廣泛關(guān)注。但是，目前主要的軟件語(yǔ)義分析方法普遍存在著時(shí)間復(fù)雜度高、結(jié)果不準(zhǔn)確的問(wèn)題。論文提出了一種重建抽象語(yǔ)法樹(shù)的算法，在很大程度上減少了抽象語(yǔ)法樹(shù)的節(jié)點(diǎn)個(gè)數(shù)；然后，在該抽象語(yǔ)法樹(shù)的基礎(chǔ)上，提出了一種系統(tǒng)依賴(lài)圖的優(yōu)化算法，有效地降低了系統(tǒng)依賴(lài)圖的規(guī)模；最后，論文基于簡(jiǎn)化的系統(tǒng)依賴(lài)圖的可達(dá)性算法計(jì)算程序的切片，完成整個(gè)軟件的語(yǔ)義分

2、析。論文提到的軟件語(yǔ)義方法對(duì)提高軟件語(yǔ)義分析的速率和準(zhǔn)確率具有很重要的意義。
　　論文首先對(duì)GCC（GNU Compiler Collection，GNU編譯器集合）產(chǎn)生的抽象語(yǔ)法節(jié)點(diǎn)的結(jié)構(gòu)以及每部分的含義進(jìn)行了簡(jiǎn)單介紹。針對(duì)GCC編譯器產(chǎn)生的抽象語(yǔ)法樹(shù)節(jié)點(diǎn)結(jié)構(gòu)混亂，冗余節(jié)點(diǎn)多的問(wèn)題，論文提出了一種基于 GCC標(biāo)準(zhǔn)化文件的抽象語(yǔ)法樹(shù)重建算法，通過(guò)對(duì)GCC產(chǎn)生的抽象語(yǔ)法樹(shù)進(jìn)行節(jié)點(diǎn)規(guī)范化、刪除冗余節(jié)點(diǎn)等操作后，生成只包含有用節(jié)點(diǎn)的GC

3、C標(biāo)準(zhǔn)化文件，基于該文件重建程序的抽象語(yǔ)法樹(shù)，有效地減小了抽象語(yǔ)法樹(shù)的節(jié)點(diǎn)規(guī)模。其次，論文提出了一種基于控制依賴(lài)圖構(gòu)建程序控制流圖的算法，打破了傳統(tǒng)系統(tǒng)依賴(lài)圖中先建立控制流圖，再建立控制依賴(lài)圖的常規(guī)流程。如果用戶(hù)只需要控制依賴(lài)關(guān)系，則可省略后續(xù)部分的操作，給軟件語(yǔ)義分析帶來(lái)了良好的靈活性。再次，在該抽象語(yǔ)法樹(shù)的基礎(chǔ)上，提出了一種基于依賴(lài)圖等價(jià)代換的SSDG（simplified system dependence graph，簡(jiǎn)化的系統(tǒng)

4、依賴(lài)圖）構(gòu)建算法，采用依賴(lài)圖等價(jià)代換的思想，用程序依賴(lài)圖代替系統(tǒng)依賴(lài)圖，有效地降低了構(gòu)建系統(tǒng)依賴(lài)圖的復(fù)雜度。最后，論文采用基于SSDG可達(dá)性算法計(jì)算程序的動(dòng)態(tài)切片，通過(guò)將程序執(zhí)行過(guò)程分解為循環(huán)和非循環(huán)的兩種情況，有效地避免了圖的可達(dá)性算法中無(wú)法正確標(biāo)記循環(huán)邊的缺陷，并且圖的可達(dá)性算法能夠有效地避免數(shù)據(jù)流方程算法中因反復(fù)迭代造成的時(shí)間復(fù)雜度高的缺陷。
　　論文采用VS2010仿真平臺(tái)對(duì)文中提到算法進(jìn)行模擬實(shí)現(xiàn)，實(shí)驗(yàn)證明，論文提到的軟