基于抽象語法樹的軟件語義分析方法研究.pdf

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

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

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

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