【文章內(nèi)容簡介】 圖中標(biāo)識了JSE的兩個主要邏輯層：靜態(tài)分析層和應(yīng)用層。靜態(tài)分析層主要負責(zé)Java源程序的預(yù)處理和靜態(tài)分析，生成PAT樹和源程序文本對象；應(yīng)用層主要實現(xiàn)了基于PAT樹的符號執(zhí)行功能，此外還實現(xiàn)了PAT樹和Java源程序文本的可視化功能。各種功能各司其職，互相協(xié)作，保證符號執(zhí)行系統(tǒng)功能完善、結(jié)構(gòu)清晰，并具有良好的可維護性。 JSE系統(tǒng)模塊框架圖靜態(tài)分析層分析源程序，得到程序的一個中間形式程序靜態(tài)分析樹。雖然由源程序直接實現(xiàn)應(yīng)用層的功能是可行的，甚至更高效，但是使用中間形式，可以實現(xiàn)分析程序與符號執(zhí)行應(yīng)用的邏輯獨立性，能夠比較容易的實現(xiàn)面向不同應(yīng)用和不同語言的符號執(zhí)行系統(tǒng)。在不改變符號執(zhí)行前端－代碼分析程序的情況下為新的應(yīng)用構(gòu)造一個新的應(yīng)用框架。同樣對于一個新的語言，在不改變已有應(yīng)用框架的情況下，為新的語言構(gòu)造一個分析該語言的分析程序，就可以構(gòu)造出新語言的符號執(zhí)行系統(tǒng)。使用中間形式的主要缺點是：中間形式的生成相比不使用中間形式的應(yīng)用在效率上會有所降低，這是因為中間形式需要再一次的處理才能生成符號執(zhí)行所需目標(biāo)結(jié)構(gòu)。程序的中間形式常見的是樹形表示。樹形表示是一種最常見的表示方式，它最大的優(yōu)點就是能夠反映出程序的自然層次結(jié)構(gòu)，而且能夠滿足應(yīng)用的需求。程序分析樹在程序分析和提取符號執(zhí)行有效信息之間建立了一個清晰的接口。＋＋WXYZ應(yīng)用層主要實現(xiàn)符號執(zhí)行和可視化這兩個方面的功能，它的實現(xiàn)是基于程序分析樹及其遍歷算法組成的數(shù)據(jù)結(jié)構(gòu)框架的。結(jié)構(gòu)化顯示程序元素的功能主要通過遍歷程序分析樹，提取出相關(guān)的信息，然后通過圖形用戶接口顯示。符號執(zhí)行功能首先提取符號執(zhí)行有效信息，然后進行相關(guān)的處理。 原型系統(tǒng)JSE執(zhí)行模型符號執(zhí)行系統(tǒng)JSE的主要任務(wù)是符號執(zhí)行Java源程序，并實現(xiàn)可視化功能。下面對設(shè)計的模塊作總體性的介紹：1. 靜態(tài)分析模塊在原型系統(tǒng)中，采用開源項目eclipse的JDT(Java Development Tool)對Java源程序進行靜態(tài)分析，靜態(tài)分析的主要功能包括詞法分析和改進的語法分析。詞法分析是將Java慣用的詞法如關(guān)鍵字、專用符號、注釋、標(biāo)識符、數(shù)字等終結(jié)符劃分出來作為語法分析的輸入；語法分析的任務(wù)是對詞法分析的結(jié)果進行語義分析，產(chǎn)生抽象語法樹。進一步地產(chǎn)生類結(jié)構(gòu)信息表、函數(shù)、語句列表等。語法分析是識別程序結(jié)構(gòu)的過程，通常采用遞歸下降法，具體做法是將語法規(guī)則的每一項都寫成一個處理函數(shù)，分析過程中采用向前看一個語言單元，判斷所處的狀態(tài)并調(diào)用相應(yīng)的處理函數(shù)。JSE的語法分析經(jīng)過改進，加入了針對符號執(zhí)行系統(tǒng)的PAT樹語法，并在抽象語法樹的基礎(chǔ)上，使用Java的合成模式，生成了針對符號執(zhí)行的程序靜態(tài)分析樹。此外，靜態(tài)分析模塊還使用JDT生成的文本對象，實現(xiàn)了對代碼文本副本的輔助操作功能。2. 符號執(zhí)行模塊符號執(zhí)行模塊是應(yīng)用層的主要功能模塊，也是原型系統(tǒng)的核心模塊。符號執(zhí)行模塊的輸入是PAT樹，核心方法是PAT樹的遍歷方法，輸出的符號執(zhí)行結(jié)果。符號執(zhí)行的主要流程是：首先遍歷根據(jù)程序生成PAT樹，生成變量列表；然后使用路徑控制模塊控制模擬程序執(zhí)行的執(zhí)行路徑，每當(dāng)遇到分支時，與用戶進行交互，根據(jù)用戶的選擇從而選擇執(zhí)行的路徑，并且記錄路徑選擇條件；每當(dāng)執(zhí)行到需要符號執(zhí)行的語句時，就對相應(yīng)的變量進行符號計算，然后更新變量列表，將符號計算結(jié)果輸入變量列表。符號執(zhí)行模塊包括四個子模塊：(1) PAT樹遍歷功能模塊。針對基于Java的合成模式構(gòu)造的PAT樹，采用訪問者模式設(shè)計PAT樹的遍歷功能。該遍歷功能能夠遍歷Java語言的各種語法結(jié)構(gòu)，如類文件、包聲明、import聲明、類聲明、類結(jié)構(gòu)體、變量聲明、類的方法、if結(jié)構(gòu)、while結(jié)構(gòu)、賦值語句和中綴表達式等結(jié)構(gòu)。(2) 變量列表相關(guān)功能模塊。變量列表主要內(nèi)容包括變量名和變量的符號值。首先，遍歷PAT樹，初始化符號執(zhí)行的變量列表，變量的符號值初始化為變量名；在符號計算過程中，每次計算到一個變量就在變量列表中查找相應(yīng)的變量；每次符號計算完成后，查找需更新變量，更新相關(guān)變量。(3) 符號計算模塊。符號計算模塊是該原型系統(tǒng)的核心模塊之一，該模塊實現(xiàn)了中綴表達式中變量值的符號替換。當(dāng)符號執(zhí)行系統(tǒng)處理賦值語句的中綴表達時，系統(tǒng)根據(jù)PAT樹遍歷方法遍歷中綴表達式，每次遍歷到一個變量，查找變量列表，用變量的符號值替換變量，最后就得到了符號計算的結(jié)果。(4) 路徑控制模塊。路徑控制模塊也是該原型系統(tǒng)的核心模塊之一，該模塊實現(xiàn)了在符號執(zhí)行系統(tǒng)模擬程序執(zhí)行過程中選擇執(zhí)行路徑的功能。Java程序中存在分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)，因此程序執(zhí)行路徑不是簡單的順序結(jié)構(gòu)。當(dāng)符號執(zhí)行分支結(jié)構(gòu)時，使用PAT樹的相應(yīng)的遍歷方法，符號執(zhí)行系統(tǒng)提示用戶輸入執(zhí)行分支選擇，然后系統(tǒng)根據(jù)輸入執(zhí)行用戶選擇的路徑。同樣，當(dāng)符號執(zhí)行循環(huán)結(jié)構(gòu)時，使用PAT樹處理循環(huán)的遍歷方法，符號執(zhí)行系統(tǒng)提示輸入執(zhí)行次數(shù)，用戶輸入后系統(tǒng)根據(jù)輸入次數(shù)循環(huán)執(zhí)行相應(yīng)的語句。3. 可視化模塊可視化模塊屬于原型系統(tǒng)的應(yīng)用層?？梢暬K分為三個子模塊：源程序文本顯示模塊、PAT樹可視化模塊和符號執(zhí)行結(jié)果可視化模塊。(1) 源程序文本可視化模塊：使用已生成的文本對象和文本控件，可視化源程序，并實現(xiàn)代碼高亮和代碼定位等功能；(2) PAT樹可視化模塊：根據(jù)已生成的PAT樹和PAT樹的遍歷方法，使用樹狀控件，實現(xiàn)一個可視化的樹型結(jié)構(gòu)；(3) 符號執(zhí)行結(jié)果可視化模塊：符號執(zhí)行結(jié)果包括變量的符號值和路徑選擇條件，可以使用文本控件，實現(xiàn)符號執(zhí)行結(jié)果的可視化。 小結(jié)本章主要介紹了JSE的體系結(jié)構(gòu)和工作流程。為了使符號執(zhí)行系統(tǒng)具有良好的健壯性和可維護性，JSE采用了分層的構(gòu)架。系統(tǒng)的四個功能模塊（文件管理模塊、程序靜態(tài)分析模塊、可視化組件、符號執(zhí)行組件）分布在三個邏輯層（基礎(chǔ)層、中間層和應(yīng)用層）中。在描述了符號執(zhí)行系統(tǒng)基礎(chǔ)構(gòu)架之后，介紹了各模塊的調(diào)用關(guān)系。最后，從用戶的角度介紹了JSE中程序靜態(tài)分析和符號執(zhí)行的工作流程，以及如何完成各種不同的功能。通過此章的介紹可以看出，該系統(tǒng)在結(jié)構(gòu)上遵循了符號執(zhí)行系統(tǒng)可擴展性和健壯性的設(shè)計原則。不過要真正進行較好的符號執(zhí)行，還需要各個模塊的細節(jié)設(shè)計和實現(xiàn)。其中程序信息的有效組織和符號執(zhí)行的機制是JSE的重點和難點。3 Java程序靜態(tài)分析技術(shù)程序靜態(tài)分析[39]是符號執(zhí)行的基礎(chǔ)，也是一個實現(xiàn)的難點。程序靜態(tài)分析的主要功能包括構(gòu)造程序靜態(tài)分析樹和實現(xiàn)程序靜態(tài)分析樹的遍歷這兩個部分。本章主要集中研究與符號執(zhí)行緊密聯(lián)系的程序靜態(tài)分析的要點，具體來說就是如何構(gòu)造一種與程序?qū)?yīng)的數(shù)據(jù)結(jié)構(gòu)，如何設(shè)計針對這個數(shù)據(jù)結(jié)構(gòu)的靈活高效的遍歷方法。而程序靜態(tài)分析樹的實現(xiàn)借鑒了現(xiàn)有的編譯技術(shù)，因此它的實現(xiàn)只作必要的介紹。從根本上說，Java源代碼只是一些普通的文本文件。對一個Java 源代碼文件進行編輯最直觀的方法，就是采用文本掃描工具。然而在實際運用中，它有很大的局限性。//Example 類package example 。public class Example{int foo = 1。public int getFoo( ){return foo。} public int getFoo(int foo){ return foo + this. Foo。 }}在對以上代碼做解釋時，就會發(fā)現(xiàn)一個單純的掃描程序很難區(qū)分方法getFoo（） 與getFoo（int foo）方法中傳入的實例變量foo。類似的，也很難區(qū)分同一個getFoo（int foo）方法中實例變量foo 與本地引用this. foo 所表示的不同含義。程序靜態(tài)分析樹能準(zhǔn)確、形象地描述了程序的邏輯機構(gòu)，具有較強的描述能力。在這個例子中，它會考慮“foo”引用的上下文，將不同方法體中“foo”引用表示成程序靜態(tài)分析樹中不同的節(jié)點，易于客戶端識別它們。如果采用程序靜態(tài)分析樹PAT(Program Analysis Tree)作為中間表示形式，對程序進行靜態(tài)分析后的輸出，是依據(jù)某種文法生成的在內(nèi)存中具有統(tǒng)一結(jié)構(gòu)的程序靜態(tài)分析樹，從而能很好地實現(xiàn)軟件復(fù)用。并且針對Java 源代碼的編輯操作（例如在Example 類中對本地引用foo 的重命名操作）只需要遍歷這一個由對象構(gòu)成的樹型層次結(jié)構(gòu)，因此使用程序靜態(tài)分析樹也非常的方便。對于面向?qū)ο蟮南到y(tǒng)，有些源代碼的語法成分是我們不關(guān)心的，而有些是我們要重點關(guān)注的，因此在對Java 源代碼的語法分析過程中沒有必要去生成一棵完整的抽象語法樹。在抽象語法樹中去掉那些不必要的信息，從而可獲得更有效的源程序中間表示，這種經(jīng)變換后的語法樹就是程序靜態(tài)分析樹。要建立一個程序靜態(tài)分析樹，必須以程序靜態(tài)分析樹的文法為前提。文法是決定怎樣將語言的元素組合起來的規(guī)則的集合。給定一個編程語言Java 之后，就可以根據(jù)Java 語言的特點定義出程序靜態(tài)分析樹的文法。Java語言有多種結(jié)構(gòu)，限于篇幅，主要文法示例如下：文法1. CompilationUni t= ( PackageDeclaration ) ? ( ImportDeclaration ) * ( TypeDeclaration ) * EOF ；文法2. PackageDeclaration = “package” Name “?！?；文法3. ImportDeclaration =“import”Name(“.”“*”)?“?！?；文法4. TypeDeclaration = ( ClassDeclaration | InterfaceDeclaration | “?！?) ；文法5. IfStatement = “if”“(“Expression”)”Statement (“else”Statement)?；文法6. WhileStatement = “while” “ ( “Expression” ) ” Statement。其中：CompilationUnit：一個編譯單元，對應(yīng)一個類文件；PackageDeclaration：包聲明；ImportDeclaration：一個引用聲明；TypeDeclaration：類型聲明，即聲明主體；ClassDeclaration：類聲明，即類的主體；InterfaceDeclaration：接口主體，即接口主體；IfStatement：if機構(gòu)主體；WhileStatement：while結(jié)構(gòu)主體；Expression：表達式；Statement：語句。 PAT樹的構(gòu)造1. 程序靜態(tài)分析樹的結(jié)點程序分析樹的每一個節(jié)點是一個類的對象，代表一個類型的語句. 基于Java 語言的程序靜態(tài)分析樹文法中包含了86 條文法規(guī)則，規(guī)則的左部出現(xiàn)的符號稱為非終結(jié)符號，對應(yīng)為程序靜態(tài)分析樹的復(fù)合節(jié)點；規(guī)則中不屬于非終結(jié)符號集合的符號稱為終結(jié)符號，對應(yīng)的是樹葉節(jié)點，因此在我們設(shè)計的解釋器中，節(jié)點類包含了這86 條規(guī)則對應(yīng)的基本類。CompilationUnit等基本類都繼承于ASTNode類， ASTNode類定義了setParent( )和addChild( )等基本操作。2. 程序靜態(tài)分析樹的構(gòu)造在構(gòu)造程序靜態(tài)分析樹的過程中，使用了已有的詞法分析和語法分析工具JDT，構(gòu)造PAT樹則采用了Java合成(Composite)模式[40]。合成模式利用整體和部分的關(guān)系將對象組織到樹結(jié)構(gòu)中，使得客戶端把一個個單獨的成分對象和由它們復(fù)合而成的對象同等對待。設(shè)計采用的程序靜態(tài)分析樹樹是一個有向樹結(jié)構(gòu)，一個節(jié)點對象既持有對所有子對象的引用，又持有對其父對象的引用。其構(gòu)造的過程在后面有詳細的描述。在程序分析樹的構(gòu)造過程中，涉及到解釋器(Interpreter)模式。通常方法是設(shè)計一個解釋器，客戶端可以使用這個解釋器來解釋Java 源代碼。解釋器在掃描Java 源代碼的過程中，通過匹配從而去創(chuàng)建一個個節(jié)點類對應(yīng)的對象。 PAT樹的構(gòu)造方法詞法分析器的任務(wù)是從左至右逐個字符地對源程序進行掃描，產(chǎn)生一個個的單詞符號。單詞符號是一個程序語言的基本，包括：關(guān)鍵字、標(biāo)識符、常數(shù)運算符、界符等，掃描操作返回值是一個整型變量，用于判斷哪一個節(jié)點類對象需要創(chuàng)建。語法分析是解釋過程的核心部分，它的任務(wù)是在詞法分析識別出單詞符號串的基礎(chǔ)上，建立一棵與輸入串相匹配的語法分析樹。每個節(jié)點類都對應(yīng)一個調(diào)用方法，用于創(chuàng)建這個節(jié)點類的對象。例如：根節(jié)點類CompilationUnit 對應(yīng)了方法CompilationUnit( )， 類PackageDeclaration對應(yīng)了方法PackageDeclaration( )。這些方法之間的互相調(diào)用，依據(jù)PAT樹的文法規(guī)則來予以確認。，給出一個Java類Test，它只有一個方法main( )，并且根據(jù)這個程序構(gòu)造對應(yīng)的PAT樹。這個程序計算兩個整數(shù)的商和余數(shù)。其中m是被除數(shù)，n是除數(shù)，r是余數(shù)，q是商。下面針對main()為例來闡述程序靜態(tài)分析樹的創(chuàng)建過程。解釋器的掃描過程是從第一行第一列開始，從上往下從左至右進行掃描的。如何將子樹的節(jié)點依據(jù)父子關(guān)系連成一個子樹？本文采用“自下而上”語法分析方法，即從語法樹的末端開始，步步向上“歸約” ，直至根節(jié)點。自下而上分析法是一種“移進、歸約”法。這種方法是利用一個寄存節(jié)點的先進后出棧，首先把某個分枝的末端節(jié)點進棧，當(dāng)棧頂形成某個產(chǎn)生式的一個候選式時，把棧頂?shù)倪@一部分歸約成該文法規(guī)則的左部符號。package test。public class Test{void main(int m, int n){ int q=0, r=m。 while(r=n){ r=rn。 q=q+1。 }} } main()函數(shù)代碼文法CompilationUnit = ( PackageDeclaration ) ? ( ImportDeclaration ) * ( TypeDeclaration ) * EOF 表明CompilationUnit 對象是根節(jié)點。文法規(guī)則的右