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

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

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

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

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