輕量級靜態分析器構造方法綜述

摘 要：由于對分析對象有嚴格的限制且開發難度大，傳統的重量級靜態分析器在應用中受到限制；輕量級靜態分析器具有易于開發、容錯性好、靈活等特點，能有效解決重量級靜態分析器在應用中遇到的問題。首先分析比較了兩種靜態分析器，詳細介紹了已有的輕量級靜態分析器構造方法；分析了已有方法的優缺點，并指出現存的問題；最后展望了本領域研究的發展趨勢。

關鍵詞：靜態分析； 輕量級靜態分析器； 分等級正則表達式； 模糊分析； 孤立文法； 超集文法

中圖分類號：TP311 文獻標志碼：A 文章編號：1001-3695(2008)08-2245-05

Overview on lightweight static analyzer construction methods

GUO Rong-feng， JIN Mao-zhong， LIU Chao

（Software Engineering Institute， Beihang University， Beijing 100083， China）

Abstract: For the strong constraints on artifacts parsed and being difficult to be developed， that full static analyzer is limited in use practically. Lightweight analyzer is tolerant， flexible and easy to develop， which can solve the problems full static analyzer encountering in application. This paper discussed two kinds of static analyzer and made a comparison between them， then introduced current lightweight static analyzer construction methods in detail. It analyzed those methods detailedly and pointed out existing problems. Finally， it outlined the future direction of the corresponding research.

Key words：static analysis; lightweight static analyzer; hierarchical regular expression; fuzzy parsing; island grammar; superset grammar

0 引言

在不執行程序的情況下對其進行的分析^[1]或基于程序的形式、結構或者文檔評估軟件的過程^[2]稱為靜態分析。靜態分析是軟件白盒測試^[3]、逆向工程^[4]及再工程^[5]、程序分析與理解^[6]等CASE研究的核心支撐技術。隨著軟件工程的成熟與發展，對靜態分析的需求越來越多，并朝著多樣化的方向發展，靜態分析器構造技術成為研究熱點。靜態分析器對源程序進行分析，并根據具體應用提取所關心的程序信息，如函數調用、控制流程、文件依賴關系等。根據對源程序的分析策略，靜態分析器可以分為以下兩類：a)重量級靜態分析器（full static analyzer），類似于編譯器的前端，主要包括詞法分析、語法分析和語義分析三個部分。它使用語法制導分析源程序，特點是語法識別準確，能提供完整、精確的程序信息，但實現難度大。主要可參考的是編譯器構造技術^[7]。b)輕量級靜態分析器（lightweight static analyzer），相對重量級分析器而言的，目前并沒有明確的定義。一般來說，這類分析器并不作精確的全語法分析，只是分析所關心的代碼片斷。其特點是易于實現、容錯性好且非常靈活，但不能保證所提取信息的精確性和完整性。

可以看到，相對輕量級分析器而言，重量級分析器能夠提供完整、精確的程序信息，但是它也存在一定的局限性：

a)實現難度大。重量級分析器需完整的詞法分析、語法分析和語義分析，實現時主要參考編譯器的構造技術。雖然編譯技術已經發展得相當成熟，也有很多通用的語法分析器產生器，如YACC^[8]、ANTLR^[9]，但文法的改寫和消歧仍然是高度專業的軟件開發活動，難以被普通軟件開發者掌握^[10]。對于一些復雜語言，如C++，開發一個重量級分析器幾乎是不可能完成的任務。文獻[11]指出目前流行的C++分析器都不完全符合C++標準^[12]。重量級分析器注重于提取程序信息和進行信息定位，而編譯器前端則注重于生成中間代碼以進行后續分析。這種目的上的差異性使得利用編譯器的前端技術構造重量級分析器成為即使不是不可能，也是非常困難的事情^[13]。

b)重量級分析器對待分析對象有嚴格的限制，它要求待分析對象是能夠通過編譯的。但在實際應用中，待分析對象可能存在語法錯誤（如用于改正錯誤的走查代碼）、可能不完整（如常常缺少頭文件的遺留代碼）、或者不能進行正確配置（如預處理配置）。這些情況都可能導致重量級分析器無法對整個項目進行分析。

c)預處理機制增加了重量級分析器的構造和應用的難度。對于支持預處理機制的語言，如C/C++，重量級分析器需要分析經過預處理后的程序。預處理引進了冗余信息（由宏擴展引起），也導致部分程序信息丟失（由條件編譯引起）。程序員心中的模型建立在未經預處理的程序上，因此，重量級分析得到的程序模型很難與程序員心中的模型相對應，也很難與源程序進行對應。

d)程序中可能包含的方言增加了重量級分析器的構造難度。一些語言由于歷史問題存在很多方言，如C/C++、COBOL。同時，不同的編譯器對語言也有不同程度的擴展，如GCC^[14]和VC都有自己的擴展^[15，16]，基于它們開發的源程序常常不能實現編譯器移植。接受某種方言的重量級分析器可能不能接受其他方言，且方言的搜集本身就是很困難的事情。

由上述分析可知，重量級分析器的構造和應用需要面對一些難以解決的問題。對于需要精確、完整程序信息的軟件測試領域來說，需要重量級分析器收集所需的程序信息。但一些其他的領域，如程序理解、代碼重構^[17]、程序輔助開發環境等，并不需要很細粒度的精確代碼分析，重量級分析器也由于其自身的局限性在這些領域中處處受制。與重量級分析器相反，輕量級分析器更適合應用于類似領域：良好的容錯能力使得語法錯誤、方言不再是問題；支持對未經過預處理的代碼進行分析，也使得靜態分析更加忠于源程序。可以看到，領域專用語言^[18]的盛行、靜態分析需求的多樣化以及重量級靜態分析器自身存在的弱點，使得如何更好更快捷地構造輕量級靜態分析器成為一個非常有價值的研究課題。

1 輕量級分析器構造方法研究現狀

對輕量級分析器構造技術的研究可以追溯到20世紀80年代。為解決重量級分析器開發困難、對分析對象要求嚴格等問題，Steffen提出部分分析的輕量級分析器構造方法，并應用于程序理解工具Cscope。隨著軟件工程的發展與成熟，靜態分析需求越來越趨于多樣性，輕量級分析器構造方法成為研究熱點，研究者提出了多種不同的輕量級分析器構造方法^[20~26]，并將這些輕量級分析器構造方法應用于程序理解、軟件再文檔^[27]、程序改動影響分析^[28]、程序架構恢復^[29]等領域。

相比國外已開展的廣泛研究，國內在這方面的研究還比較缺乏，筆者也沒有檢索到相關論文。國內的靜態分析器構造技術還集中在改造編譯器前端或自主開發重量級分析器上，而開發出的靜態分析器大都達不到真正工業應用的要求。目前已有很多輕量級靜態分析工具如source insight^[30]、source navigator^[31]、Ctags^[32]、Cscope、visual assist^[33]等在軟件開發組織中得到了廣泛應用。

1.1 基于正則表達式的構造方法

目前，已有很多工具和語言支持通過掃描文件來查找匹配特定正則表達式的文本，如grep工具系列（grep、fgrep、egrep、agrep、cgrep）、文本掃描語言Awk^[34]、Lex、Perl、TLex^[22]等。這些工具和語言在不同程度上支持輕量級靜態分析。Linux、UNIX平臺下，grep工具系列被大量用于軟件開發環境；source insight提供了讓用戶編寫正則表達式定制靜態分析器的接口；文獻[35]用Perl和AWK組合開發的輕量級分析器很好地完成了分析任務。

Grep工具系列以指定的模式（正則表達式）搜索文件的每一行，打印出所有匹配該模式的文本行，并給出該文本行所在文件的文件名，但是它們不支持用戶指定在模式被匹配時執行的動作。按行分析以及不支持用戶指定動作限制了grep系列工具在靜態分析中的應用。Perl、Awk和Lex都解決了這個問題，但是它們對訪問與子正則表達式匹配的文本支持不足，此外它們在描述正則表達式集合中各表達式的優先級順序方面缺乏支持^[36]。TLex對正則表達式提供了更多的支持，如上下文相關的正則表達式匹配，并在正則表達式匹配時自動建立分析樹，但不能夠在動作中控制匹配或者回溯。雖然這些工具和語言大都被程序員熟練掌握和廣泛應用，但是它們的分析能力太弱，不能分析底層的語法結構，文獻[33]組合了它們的優點，完成了簡單的靜態分析任務，但這是Ad hoc的方法。

1.2 基于分等級正則表達式的構造方法

由于正則表達式描述能力有限，學者們在以正則表達式為基本匹配模式的基礎上劃分正則表達式的等級，并采用層次詞法分析器（cascade lexer）來增強對遞歸語言結構的分析能力。文獻[37]總結了這種方法的一些共性。多年來，許多學者在這種方法上作了大量的研究，提出了不同的實現方法。

LSME（lexical source model extractor）^[23，36]定義了一種規范語言來描述要提取的程序信息。這種語言以正則表達式為基礎，通過支持分等級正則表達式來增強對語法結構的描述能力；正則表達式的描述不再用傳統的字符，而是用符號（token）；與Lex等工具一樣，LSME可以附加動作到正則表達式，當正則表達式被匹配時，附加的動作被執行，并可以在附加的動作中控制匹配、回溯以及訪問被匹配的文本。LSME接受程序信息描述文件，構造出基于分等級有窮狀態機集合的靜態分析器。靜態分析器掃描源程序、匹配有窮狀態機集合并執行附加的動作，完成對源程序的分析。LSME比較適合于對源程序進行高層次的分析^[38]。

MultiLex^[38]采用與LSME相似的分等級方法；不同的是，它將多個詞法分析器按順序連接，后一個詞法分析器以前一個詞法分析器的輸出為輸入，每個詞法分析器對程序作不同的分析。MultiLex并不構造語法樹，而是針對識別出的語法結構在token流中插入相應的標記，于是一個token要么被輸出為下一個詞法分析器的輸入，要么被相應的標記代替；同時它用計數器記錄遞歸結構的嵌套深度，用棧保存遞歸結構的前綴，以支持對遞歸語法結構的分析。 MultiLex證明基于詞法構造的靜態分析器有能力分析底層的語法結構，并且分析能力與基于語法分析的靜態分析器相當。

文獻[39]認為MultiLex雖然有能力進行底層語法結構的分析，但在實際應用中難度很大。它在MultiLex的基礎上繼續研究，仍然以正則表達式為基礎描述語言結構，把匹配模式（包括正則表達式、等級、動作三部分）根據等級劃分為不同的模式集合。根據等級的高低將模式集合順序應用于對源程序的分析：基于后一個模式集合的分析以前面分析的輸出為輸入；每個模式集合被反復應用于分析，直至達到平衡方才應用下一個等級的模式集合；對正則表達式的匹配采用最短匹配方法^[40]。它用最短匹配以及基于模式等級的迭代式分析模擬了自底向上的語法分析，并在分析過程中建立語法樹。

Revealer^[24]定義了一種XML格式的模式描述規范語言，其元素包括節點、屬性、引用。節點是描述匹配模式的基本單元，它分為正則表達式、字符串、塊三種類型；引用將各節點關聯起來，它分為順序、約束、與、或等幾種類型。節點描述了基本的匹配模式，引用將節點組合成更復雜、能力更強的匹配模式。Revealer以模式規范為輸入，利用Perl的正則表達式處理能力直接對源程序進行分析，不生成單獨的靜態分析器。Revealer適合于分析程序中具有明顯特征的信息，對遞歸語法結構缺乏支持。

RegReg^[25]采用與MultiLex相似的方法，對正則表達式分等級并采用層次詞法分析器，但是RegReg可以選擇正則表達式的匹配方式，支持建立分析樹。不同于MultiLex只為了證明詞法的分析能力，RegReg是一個靜態分析器生成器。

基于分等級正則表達式的靜態分析器構造方法具有靈活、容錯性好、分析速度快的特點，但也存在一些不足：a)沒有可靠的、廣泛應用的分析器產生器，仍然是Ad hoc的方法，并且構造分等級正則表達式模式來描述底層語法結構在實際應用中存在很大難度；b)它無法在一遍分析的情況下分析底層的語法結構，在分析某些需要語義信息的語言結構時顯得力不從心，如函數重載解析、名字查找；c)它分析的精確性稍差。

1.3 基于模糊分析的構造方法

模糊分析策略分為兩種：a)識別具有一定正確度的句子（也就是允許一定的語法錯誤）；b)只分析程序設計語言中所關心的部分，忽略不關心的部分。

對于分析策略a)有兩種實現方法：（a）通過添加錯誤產生式來模擬可能出現的語法錯誤，以增強對錯誤語句的處理能力，并對每個錯誤產生式都標記正確度，依此評估輸入語句的質量。當輸入語句的正確度高于某個限定值時，分析器接受該語句；否則拒絕接收，具體參見文獻[41]。（b）通過增強靜態分析器的錯誤識別和錯誤恢復能力來增強對錯誤語句的處理能力。這一方法類似于編譯器前端的錯誤處理^[7]；不同之處在于不需要報出詳細的錯誤信息。靜態分析器大多采用第二種方法來增強錯誤處理能力。

分析策略b)用錨定符（achor symbol）標記所關心語法元素的開始，靜態分析器保持空閑并拋棄所有token，直到遇到錨定符。在實際開發中，錨定符并不是任何時候都需要。文獻[21]對這種方法進行了詳細的闡述和驗證。Sniff程序設計環境^[20]首先采用這種分析策略，它只分析C++程序中的類、函數、成員函數等高層語法元素的聲明，而不分析函數體。Sniff以后出現了一系列采用這種分析策略的工具，如CTG（class tree generator for C++）、CodeAnalyzer等。

綜上所述，分析策略a)增強了靜態分析器的分析能力，但沒有解決分析器開發難度大的問題，并且枚舉可能出現的錯誤本身就是件很困難的事情；分析策略b)降低了靜態分析器的開發難度，但是它只能分析高層的語言結構或者具有明顯特征的語言結構，在錯誤處理方面也缺乏支持。

1.4 基于孤立文法的構造方法

Deursen等人^[42，43]首先提出孤立文法，Moonen^[26]則進一步說明并給出了形式定義。孤立文法包括島嶼（island）和海水（water）兩部分，它用詳細的產生式表述所關心的語言結構（島嶼），用自由產生式描述余下的語言結構（海水）。其形式定義如下：

c)K(G)>K(G1)，G比G1更復雜。

分析器生成器接收孤立文法描述文件生成分析器，分析器掃描源程序，分析所關心的語言結構，提取相應的程序信息。孤立文法并不要求特殊的語法規范或分析技術，但是選定語法規范和分析技術對孤立文法的能力有所影響。

文獻[42，43]用SDF2^[44]作為孤立文法描述規范，用GLR^[45]分析器產生器生成分析器，用Java對象遍歷生成的語法樹，提取程序信息生成文檔。文獻[46]中采用孤立文法對程序進行影響分析；文獻[26]提供生成分析器的框架MANGROVE，它接收SDF^[47]格式的孤立文法描述文件生成GLR分析器，并配合ASF^[48]描述文件或JJForest^[49]處理語法樹提取相關程序信息。

基于孤立文法的靜態分析器構造方法能夠自動生成靜態分析器，能夠保證靜態分析信息的正確性，能夠保證靜態分析器的分析能力。其缺點是孤立文法的能力受所選分析技術的影響，常用的LL、LR、LALR分析技術限制了孤立文法的自由應用，而GLR分析技術在目前還不是非常成熟，現有的GLR分析器產生器的正確性還沒有得到有效驗證，并且GLR分析器的速度比較慢；當程序中存在語法錯誤時，它可能因為語法錯誤丟失程序信息。

1.5 基于超集文法的構造方法

超集文法并沒有嚴格定義，一般認為：對于文法G0及G0產生的語言L0，如果有文法G1及G1產生的語言L1，且L0L1，則G1是G0的超集。一般說來，靜態分析器的分析對象符合語法規范（由宏擴展或條件編譯引起的語法錯誤除外），并且靜態分析器也無須像編譯器前端那樣對分析對象進行嚴格的語法檢查，因此可以忽略一些語法約束。使用超集文法構造方法能減小開發人員文法改寫的難度，也使得文法更加易于閱讀和理解。文獻[50]首先使用超集文法接收C++一個超集，然后再使用過濾器去掉錯誤的語言結構。

基于超集文法構造靜態分析器降低了文法改寫的難度，也可使用分析器產生器自動生成靜態分析器，但它沒有從根本上解決分析器開發難度的問題，并且在錯誤處理方面缺乏支持。

2 目前存在的問題

表1從正確性、健壯性、分析能力及有無分析器產生器四個方面對上述介紹的輕量級靜態分析器的構造方法進行了對比分析。

表1 各種構造方法的對比分 類正確性健壯性有無產生器分析能力基于正則表達式低好有弱基于分等級正則

表達式中好無中基于模糊分析高好有中基于孤立文法中高好有強基于超集文法中高差有強基于表1對各種方法的分析、對比，可以得到以下結論：

a)基于正則表達式的方法正確性和分析能力均有不足，但其健壯性好，也存在大量輔助自動生成的工具，它適用于對程序進行簡單的分析，如變量引用等。

b)基于分等級表達式的方法沒有通用的分析器產生器，也難以獲得前面提到的幾個分析器生成器，但其健壯性好，也有不錯的正確性。當分析器分析能力要求不高時，用這種方法構造分析器比用后面三種方法構造容易。

c)基于模糊分析的方法分析能力一般，但具有很好的正確性和健壯性，也有輔助自動生成工具。當對分析器能力要求不高時，用這種方法構造分析器比基于分等級表達式構造分析器困難；當對分析器能力要求較高時，文法改寫和錯誤處理給這種方法的應用帶來了困難。

d)基于孤立文法的構造方法正確性、健壯性均較好，也有較好的輔助自動生成的工具ASF+SDF開發環境^[48]，并且開發難度不會隨著分析器能力要求的提高而過度增長。但是ASF+SDF使用起來難度較大，需要開發人員有深厚的相關方面的知識。

e)基于超集文法的方法健壯性有所欠缺，但其分析能力、正確性較好，也有輔助自動生成工具，在一定程度上降低了文法改寫的難度。

通過上述對已有研究的總結并結合筆者的研究實踐，目前的輕量級分析器構造方法存在以下不足：

a)在分析器的開發難度與分析能力上難以找到一個好的平衡點。基于分等級正則表達式能較容易地構造出靜態分析器，但很難描述底層的語言結構。以SDF+GLR為基礎的基于孤立文法的構造技術需要開發人員有深厚的相關知識，其他構造方法或者能力太弱，或者需要文法改寫和錯誤處理。

b)在靜態分析的正確性和開發難度上難以找到一個好的平衡點。分析正確性包括兩方面，即所提取的信息是否正確及是否提取了所有要提取的信息。基于正則表達式和基于分等級正則表達式構造的分析器在這方面有所不足。為了防止因為語法錯誤而造成所提取的信息不正確，在其他構造方法中引入模糊分析也會增加開發難度。

c)缺乏通用的輕量級分析器產生器。現有的分析器產生器注重于編譯器前端的開發，它們生成的詞法分析器能力太弱，生成的語法分析器大多采用LL、LR或LALR等確定性分析方法，不利于輕量級分析器的構造。

3 總結與展望

重量級分析器是目前軟件測試領域使用比較廣泛的分析器，但由于其自身的局限性，在其他領域的應用中面臨很多問題。隨著靜態分析技術的需求日益廣泛，輕量級分析器構造方法成為熱點研究問題。本文對目前已有的輕量級靜態分析器構造方法進行了較為詳細的介紹，并對其進行了分析和總結。展望本領域的發展趨勢，筆者認為未來的輕量級分析器構造應是幾類構造方法的綜合，并根據具體任務和目標選擇不同的構造方法。

a)以基于GLR分析技術的孤立文法為構造方法的主體，緊密結合基于模糊分析、基于超集文法兩種構造方法，是構造健壯有力的靜態分析器的未來方向。從前面的分析可知，基于孤立文法可以較容易地構造分析能力強的分析器；而超集文法可以降低文法改寫的難度；模糊分析可以增強分析器的錯誤處理能力并保證在有語法錯誤的情況下提取信息的正確性。文獻[51]認為：當前的語法分析技術對軟件再工程是有害的，GLR 算法、模塊化分析器生成器、組合分析器生成器或許是未來的解決方案。孤立文法也符合模塊化、組合分析器的要求。GLR分析技術對孤立文法有著非常好的支持，并且計算機硬件的發展使GLR分析算法在執行效率上有了質的飛躍。

b)開發通用的基于分等級正則表達式、現有詞法分析器產生器的靜態分析器產生器是快捷開發輕量級分析器、滿足需求多樣性的未來方向。基于分等級正則表達式可以快速地開發出分析能力稍弱的靜態分析器。這些分析器能快速分析高層次的語言結構或有明顯特征的程序結構，現有的詞法分析器產生器也對這種構造方法有所幫助。因此，基于分等級正則表達式和現有工具的靜態分析器產生器可以快速、便捷地開發出輕量級分析器，有效地滿足靜態分析的需求多樣性。

基于本文的分析和研究，筆者正在進行C++程序分析與理解工具的開發，在已有分析器JLParser^[16]的基礎上采用模糊分析和超集文法相結合的方法進行輕量級靜態分析器的研究和開發工作，并已取得了一定成果，將陸續發表在后續論文中。

參考文獻：

[1]Glossary of terms used in software testing， version 6.2 [EB/OL]. http://www.testingstandards.co.ulc/Gloss62.htm.

[2] IEEE Std 610.12—1990， IEEE standard glossary of software engineering terminology[S]. 1990.

[3]鄭人杰，殷人昆，陶永雷，等.實用軟件工程[M].北京：清華大學出版社，1990.

[4]TILLEY S T. Domain-retargetable reverse engineering[D]. Victoria， Canada: University of Victoria，1995.

[5]GJORWELL D， HAGLUNO S， SANDELL D. Reengineering and reengineering patterns[EB/OL].(2002-02-24).http://www.idt.mdh.se/kurser /cd5130/msg/2002lp3/download/CD5130%20VT0-2%20Reengineering.pdf.

[6]NELSON M L. A survey of reverse engineering and program comprehension [J]. Software Engineering Survey，1996(5):51-62.

[7]AHO A V， SETHI R， ULLMAN J D. Compilers: principles， techniques and tools [M]. Boston: Addison-Wesley，1986.

[8]YACCLEX[EB/OL].http://dinosaur.compilertools.net/.

[9]ANTLR[EB/OL].http://www.antlr.org/.

[10]李虎. GLR分析器自動生成及相關問題研究[D]. 北京：北京航空航天大學，2006.

[11]MALLOY B A， LINDE S A， DUFFY E B， et al. Testing C++ compilers for ISO language conformance [J].Dr Dobbs Journal，2002，27(6): 71-78.

[12]ISO/IEC 14482， ISO C++ standard[S]. 1998.

[13]YANG Fu-qing， MEI Hong， YUAN Wang-hong，et al. Experiences in building C++ front end[J]. ACM SIGPLAN Notices，1998，33(9):95-102.

[14]GCC[EB/OL]. http://gcc.gnu.org/.

[15]尚衛東.C++靜態分析預處理技術及其支持工具的研究與實現[D].北京：北京航空航天大學，2004.

[16]樊平.新型多用途C++靜態分析器的研究與開發[D].北京:北京航空航天大學，2004.

[17]FOWLER M，BECK K，BRANT J， et al．Refactoring：improving the design of existing code[M]. Boston: Addison-Wesley，1999.

[18]DEURSEN A vam， KLINT P. VISSER J. Domain-specific languages: an annotated bibliography [J]. ACM SIGPLAN Notices， 2000， 35(6): 26-36.

[19]STEFFEN J L. Interactive examination of a C program with Cscope[C]//Proc of the USENIX Winter Conference. Berkeley:[s.n.]，1985: 170-175.

[20]BISCHOFFBERGER W R. Sniff: a pragmatic approach to a C++ programming environment[C]//Proc of the USENIX C++ Technology Conference， 1992:67-81.

[21]KOPPLER R. A systematic approach to fuzzy parsing[J]. Software-Practice and Experience，1997，26(6): 637-649.

[22]KEARNS M. TLex[J]. Software-Practice and Experience，1991， 21(8):805-821.

[23]MURPHY G C， NOTKIN D. Lightweight lexical source model extraction[J]. ACM Trans on Software Engineering and Methodology，1996， 5(3):262-292.

[24]PINZGER M， FISCHER M， GALL H， et al. Revealer: a lexical pattern matcher for architecture recovery[C]//Proc of the 9th Working Conference on Reverse Engineering. Washington DC: IEEE Computer Society， 2002:170-178.

[25]LATENDRESSE M. RegReg: a lightweight generator of robust par-sers for irregular languages[C]//Proc of the 10th Working Conference on Reverse Engineering.Washington DC: IEEE Computer Society， 2003:206-215.

[26]MOONEN L. Generating robust parsers using island grammars[C]//Proc of the 8th Working Conference on Reverse Engineering. Wa-shington DC: IEEE Computer Society， 2001:13-22.

[27]WONG K， TILLEY S R， MLLER H A， et al.Storey， structural redocumentation: a case study[J]. IEEE Software， 1995，12(1):46-54.

[28]BOHNER S， ARNOLD R. Software change impact analysis [M]. Los Alamitos: IEEE Computer Society Press， 1996.

[29]JAZAYERI M， RAN A， LINDER F. Software architecture for product families: principles and practice[M]. Boston: Addison-Wesley， 2000.

[30]Source insight[EB/OL]. http://www.sourceinsight.com.

[31]Source navigator[EB/OL]. http://sourcenav.sourceforge.net.

[32]Ctags[EB/OL]. http://ctags.sourceforge.net/.

[33]Visual assist[EB/OL]. http://www.wholetomato.com.

[34]AHO A V， KERNIGHAN B W， WEINBERGER P. Awk: a pattern scanning and processing language[J]. Software-Practice and Experience， 1979，9(4):267-280.

[35]DEURSEN A， KUIPERS T. Rapid system understanding: two COBOL case studies[C]// Proc of the 6th International Workshop on Program Comprehension. Washington DC: IEEE Computer Society， 1998:90-98.

[36]MURPHY G， NOTKIN D. Lightweight source model extraction[C]// Proc of the 3rd ACM SIGSOFT Symposium on Foundations of Software Engineering. New York: ACM Press， 1995:116-127.

[37]COX A， ABOU-ASSALEH T，AI Wei， et al. Lexical source-code transformation[C]// Proc of Software Transformation Systems Workshop at GPCE/OOPSLA， 2004.

[38]COX A， CLARKE C. A comparative evaluation of techniques for syntactic level source code analysis[C]// Proc of the 7th Asia-Pacific Software Engineering Conference. Washington DC: IEEE Computer Society， 2000: 282-289.

[39]COX A， CLARKE C. Syntactic approximation using iterative lexical analysis[C]//Proc of the 11th International Workshop on Program Comprehension. Washington DC: IEEE Computer Society， 2003:282-289.

[40]CLARKE C， CORMACK G. On the use of regular expressions for searching text[J]. ACM Trans on Programming Languages and Systems， 1997，19(3):413-426.

[41]ASVELD P R J. A bibliography on fuzzy automata， grammars and languages [J]. Bulletin of the European Association for Theore-tical Computer Science， 1996(58):187-196.

[42]DEURSEN A， KUIPERS T.Building documentation generators[C]//Proc of IEEE International Conference on Software Maintenance. Washington DC: IEEE Computer Society， 1999:40-49.

[43]DEURSEN A van. Arrangement and method for a documentation gene-ration system: U.S. Patent[P]. 2000.

[44]VISSER E. Syntax definition for language prototyping[D]. Amsterdam: University of Amsterdam， 1997.

[45]VISSER E. Scannerless generalized-LR parsing， P9707[R]. Amsterdam: University of Amsterdam， Programming Research Group， 1997.

[46]MOONEN L. Lightweight impact analysis using island grammars[C]//Proc of the 10th International Workshop on Program Comprehension. Washington DC: IEEE Computer Society， 2002: 219-228.

[47]HEERING J， HENDRIKS P R H. The syntax definition formalism SDF—reference manual [J]. ACM SIGPLAN Notice，1989，24(11):43-75.

[48]BRAND M G J van den， DEURSEN A van， HEERIN J， et al. The ASF+SDF meta-environment: a component-based language development environment[C]//Proc of the 10th International Conference on Compiler Construction. London: Springer-Verlag， 2001:365-370.

[49]KUIPERS T，VISSER J M W. Object-oriented tree traversal with JJForester[C]//Proc of Workshop on Language Descriptions， Tools and Applications. Amsterdam: Centre for Mathematics and Computer Science， 2001:28-52.

[50]WILLINK E D. Meta-compilation for C++[D]. Guildford: University of Surrey， 2001.

[51]BRAND M Q J van den， SELLINK A， VERHOED C. Current parsing techniques in software renovation considered harmful[C]//Proc of the 6th International Workshop on Program Comprehension. Wa-shington DC: IEEE Computer Society， 1998:108-110.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文