基于JavaCC的抽象語法樹生成錯誤處理技術研究

王國隆，金大海， 宮云戰

(北京郵電大學 網絡與交換技術國家重點實驗室，北京 100876)

0 引言

為保障計算機軟件質量，應盡早進行軟件測試，而軟件測試的重要手段之一就是靜態測試[1-5]。隨著C++語言標準11/14/17的不斷演進，新標準對C++語法進行了諸多補充和優化，同時也帶來了許多擴充的新特性[6]。隨著C++新標準在市場上大面積的普及應用，對支持C++新標準的靜態測試也顯得尤為重要。

目前存在很多用于C++靜態測試的工具，如Cpplint[7]，PMD[8]，Cppcheck[9]等。在這些靜態測試工具中都必須對代碼解析。抽象語法樹是對代碼的一種重要的中間表示形式，也是一個對代碼進行靜態測試的不可或缺的數據結構，在代碼測試分析領域有著廣泛的應用[10]。

目前存在的很多用于C++語言的詞法語法分析工具，如JavaCC[11]，ANTLR[12]，LEX/YACC[13]等不能完全支持C++新標準的某些特性。而文中采用錯誤處理技術，較好地解決了這個問題，它可以確保對抽象語法樹生成出現錯誤的地方采取對應的策略進行錯誤處理并完成抽象語法樹的創建。在本文中，提出了一個針對抽象語法樹生成的錯誤處理框架，用以解決抽象語法樹生成錯誤問題。

1 相關工作

在詞法語法分析工具方面，彭虎臣[14]以LEX作為詞法分析器，讀入字符串后根據詞法規則，將單詞或者字符轉換為token；采用YACC作為語法分析器，通過在符合BNF范式的語法規則中嵌入語法動作，之后搭建抽象語法樹提取網頁中CSS部分。Liu等[15]采用用戶自定義的語法規則及詞法規則，利用ANTLR來生成相應語法分析器及詞法分析器的代碼。之后，首先把輸入的字符流，通過詞法分析器轉變為由token組成的流，然后利用語法分析器的輸出獲得最后的抽象語法樹進行Scratch語言的特征提取和檢測。黃松等[10]使用純Java代碼編寫的免費編譯工具JavaCC，經過用戶自定義的詞法語法規則文件jjt生成抽象語法樹。肖一飛[16]提出一種基于JavaCC的通用的缺陷檢測預處理方法，通過修改jjt規則文件對不同類型的詞法異常和語法異常進行支持解決。孟春辰[17]提出一種基于JavaCC的中間文件化簡的方式，通過保留一些類型定義信息從而避免了對頭文件中導致靜態分析失敗的復雜語法結構的分析。本文鑒于JavaCC的易用性以及平臺無關性等優勢繼續使用JavaCC作為抽象語法樹的生成工具。

但是，JavaCC也有缺點。JavaCC遇到語法錯誤或者不匹配的語法時，僅僅會報告第一處錯誤并停止分析。也就意味著，對于代碼的抽象語法樹生成錯誤且不完整，所以需要對此進行錯誤處理。

對于錯誤處理方面，羅海麗[18]提出拋棄輸入記號直到某個定界符，JavaCC默認的錯誤處理就是使用了跳過字符到指定符號的方式，但是這種拋棄可能會引入更多的錯誤；郝麗波等[19]提出受到最大重復次數約束的可重試的錯誤處理策略，但是對于JavaCC來說不做出改動每次生成結果都是一樣；Jia等[20]提出了可替換的對輸入做局部修改的錯誤處理策略，但是很難猜測符合意愿的替代方式；曾祥文[21]提出了一種可以回退K個的分析器，使用兩個分析棧，一個棧負責將新單詞壓入棧，另一個棧負責維護K個單詞，相當于對K個單詞的窗口進行修復。由于無法預測出錯的常見形式和替換方式，本文使用跳過符號的方式進行錯誤處理。

現有的詞法語法分析工具對C++新標準支持的不多，一些研究人員是面向C++98標準構造抽象語法樹并進行分析，與他們工作不同的是，本文是面向C++新標準生成抽象語法樹并對生成錯誤進行處理，此方法既可應對不支持或者不匹配的語法片段，也可應對C++日后的語法更新。

2 抽象語法樹生成錯誤分析

2.1 抽象語法樹生成錯誤原因

抽象語法樹(AST,abstract syntax tree)是以樹狀的形式表達源代碼語法結構的一種表現形式[17]，用T=表示，其中：N為樹的節點，表示代碼中的一種語法結構；E為樹的邊，表示代碼中的語法邏輯關系。

抽象語法樹生成過程如圖1所示。

圖1 語法樹生成過程示意圖

源程序經過詞法分析和語法分析生成抽象語法樹。BNF(Backus-Naur Form)是描述編程語言的文法。詞法分析和語法分析[22]根據對應的符合BNF范式的規則文件生成對應的語法樹節點組成語法樹。詞法分析錯誤可以通過在規則文件中添加新token來支持，語法分析則需要針對語法邏輯對規則文件進行修改。現有的規則文件可以較好地支持C++98標準和C++14標準的絕大部分語法和特性，但是針對語法邏輯修改的規則文件不能做到對不斷迭代的C++新標準的完全支持，進而就會產生語法樹生成錯誤。

2.2 語法規則文件不能完全支持的原因分析

語法規則文件不能完全支持C++新標準的原因主要有以下3點：

2.2.1 C++新標準BNF范式無法獲取

官方的C++新標準的BNF范式文檔無法獲取，并且網上存在的新標準BNF范式各有出入，無法確定是否和官方一致。如果范式文檔選擇出現問題，會對后續分析處理產生重大影響。

2.2.2 C++新標準語法結構變化大

C++新標準語法更改中，提出了新的語法結構，新的功能，在新關鍵字的配合之下或不需要新的關鍵字，在原有關鍵字的基礎之上，提出新的結構，完成新的功能。這主要目的是為了更加方便地實現相應的功能。以語法樹中statement節點的語法結構的變化為例，如圖2所示。

圖2 C++新標準語法結構變化示例

標準更新后出現更多的是語法結構的變化，有些結構是在原有結構的基礎之上進行擴展，這種在構建抽象語法樹的時候相對容易進行更改，但是很多結構的更改是在推翻原有結構的基礎上進行重新架構(如圖2)，同時還會糅合其他新的結構進來，層層嵌套。這種在破壞原有結構的基礎上進行的更改在構建抽象語法樹時相對困難。

由于破壞原有的語法結構，所以在修改抽象語法樹規則文件時，也需要對相應結構進行破壞，這樣無法保證在破壞現有結構后仍然可以對原有結構進行支撐，這是較難的問題。對于這種問題，一方面對新的語法盡量修改規則文件進行支撐，無法支撐的語法需要通過錯誤處理技術進行處理。

2.2.3 C++新標準核心庫變更大

C++新標準的庫更樂于使用復雜的嵌套結構和模板類來對相關代碼進行聲明，所以結構變得相對復雜，而之前的C++98的庫更多的是使用直接聲明的方法。例如C++98和C++11核心庫iostream的變化如圖3所示。

圖3 C++新標準核心庫變化示例

可以看出，新標準的庫文件結構變得異常復雜。因此，C++98的庫文件內容更加容易被抽象語法樹支撐。由于測試時，為了獲取到更全面的分析數據，會將全部的頭文件進行展開，以獲取到更多的信息來分析，獲取分析結果。但是目前來說，在極度復雜的庫文件的情況之下，很難做到對頭文件的完全支撐。相反地，用戶所寫源文件的結構相對簡單，不會大量使用復雜的結構，更加容易進行語法的支撐。所以建立抽象語法樹時，構建的主體應為源文件，要做到不丟失源碼信息。

綜上，在對C++新標準的語法邏輯做到最大可能的支撐的基礎上，對于還不支持的會導致語法樹生成錯誤的語法要進行錯誤處理。因為錯誤會導致語法樹生成中斷，錯誤點之后的源代碼不能生成相關的語法樹節點，導致對應源文件的語法樹不完整，從而影響后續靜態分析。所以本文重點討論在語法樹生成中跳過不支持或不匹配的語法片段的錯誤處理技術。

3 針對抽象語法樹生成的錯誤處理框架

對于語法樹生成失敗的源文件，希望通過錯誤處理技術可以繼續生成語法樹并且保證語法樹盡量完整，也由此本文提出了針對抽象語法樹生成的錯誤處理框架，框架設計如圖4所示。

圖4 抽象語法樹生成錯誤處理框架

首先，源代碼經過預處理后生成中間文件。之后是一個迭代的過程，如果中間文件生成抽象語法樹成功，直接結束；如果抽象語法樹生成錯誤，則需要根據報錯行數跳過附近語法片段以此繼續生成抽象語法樹直至成功。

3.1 預處理

中間文件(intermediate file)是在分析C++程序時使用編譯器對源代碼進行預處理后生成的文件，以方便進行后續分析。

先要對C++源文件進行預處理，預處理是通過編譯器進行的，包括一些宏替換，條件編譯以及頭文件展開等操作。正是因為需要上述操作，所以不能使用.cpp文件直接進行處理，需要使用預處理后生成的中間文件.i進一步生成抽象語法樹。

3.2 語法樹生成錯誤處理

中間文件經過詞法和語法規則文件生成抽象語法樹，如果成功生成，當前文件分析完成；如果生成出錯，那么接下來進入語法樹生成錯誤處理流程。

α1α2…αn=w1αiw2

(1)

式中,w1為已經分析并且生成語法樹節點的部分；αi為當前分析的token；w2為當前文件剩余的token流。

假定分析到αi生成語法樹時發生錯誤，因為分析是自上而下的，那就意味著當前已經建立了部分語法樹，并且已經生成的語法樹已經涵蓋了w1，但是語法樹卻無法繼續生成以涵蓋w2。此時，就必須應用錯誤處理技術來繼續生成語法樹。可采取的措施如下：

1)刪除當前tokenαi并繼續分析；

2)于w1和αi之間插進終結符號α，從而把式(1)改寫成式(2)：

α1α2…αn=w1ααiw2

(2)

然后再從αi開始分析；

Lakoff提出的意象圖式（image schema）是人們理解和認知事物的基本結構和組織形式，也是概念范疇內的原型結構[4]。由于人體本身就屬于空間概念范疇，所以基本的意象圖式就是空間圖式，凡是涉及到空間結構的概念都是以意象圖式認知模式儲存在大腦中。at表示空間概念范疇是基于路徑意象圖式基礎的，如圖1：

3)從w1的尾部刪去若干個token后繼續分析。

上述措施可以單獨使用也可以結合使用，其中措施(2)直接添加終結符可能會導致程序不能正常編譯。這里可以結合措施(1)和(3)進行錯誤處理，多次使用措施1并結合措施3進行處理相當于在式(1)中從w1的尾部刪除若干個token并且在w2的首部刪除若干個token，即把式(1)修改為式(3)：

α1…αi-p…αi…αi+qα2…αn=w0Uw3

(3)

式中,

U=αi-p…αi…αi+q

(4)

如果這樣的U存在，就刪除或注釋Uu后繼續分析。

基于以上措施，對于每一個cpp文件，先不考慮源代碼中引用的頭文件，只對純源代碼部分生成抽象語法樹。如果在這個過程中出現異常，解決措施是不考慮報錯行數附近的函數區間，繼續分析其他可以正常生成抽象語法樹的部分。

解決辦法是，從完整的中間文件中分離出源程序部分，根據這部分用戶寫的源代碼生成抽象語法樹，如果發生異常，通過報錯行數和函數區間標識算法略過附近函數區間后重新生成語法樹直至成功。

模塊流程設計如圖5所示。

如圖5所示，新語法錯誤處理模塊可以分為3個部分：1)源程序分離；2)文件內函數區間劃分；3)注釋報錯區間迭代生成抽象語法樹。

3.2.1 源程序分離

在完整的中間文件中，有用戶寫的源代碼部分，也有頭文件展開的部分，這里先不考慮頭文件展開部分，只對源程序生成抽象語法樹。所以，需要從完整的中間文件中得到源程序部分。

中間文件片段以及預期分離效果如圖6所示。

圖6 中間文件片段以及預期分離效果

孟春辰[17]根據“# 行號 文件存放路徑”從后向前遍歷，直到遇到文件后綴.h就結束遍歷。但是對于圖6代碼，在源程序中還插入了一些擴展進來的頭文件部分，之前的算法不能準確截取出源程序部分，所以提出了算法1所示的通用的源程序分離算法。

算法1:源程序分離算法

輸入：源文件名fileName，完整中間文件content；

輸出：只包含源程序部分的中間文件result。

index ← 0

isSourceLine ← false

rightPattern← "#s(d+)s”(.*)" + fileName + "”s(d+)"

falsePattern ←"#s(d+)s”(.*)”s(d+)"

while index < content.size() do

if line matches rightPattern do

index++

isSourceLine ←true

continue

end if

if line matches falsePattern do

isSourceLine ←false

end if

if isSourceLine do

result.add(line)

end if

index++

end while

return result

算法描述：算法從上向下掃描，通過兩種正則表達式進行識別，一種表示含有源文件后綴的文件提示信息，另一種表示普通的文件提示信息，并且通過一個布爾值標識當前行是否加入結果集中，最后返回源程序部分代碼。

3.2.2 文件內區間劃分

對上述中間文件分離出的源程序部分生成語法樹，如果發生錯誤，就需要根據報錯行數注釋相應的區間，所以接下來就需要對中間文件進行區間劃分。

定義1:函數區間：函數區間是文件內用來標識一個函數名稱和范圍的結構，該結構由一個三元組表示，該結構描述記為I={Name,StartLine,EndLine}，其中：

Name：表示該函數區間的函數名稱；

StartLine：表示該函數區間的起始行數；

EndLine：表示該函數區間的終止行數。

文件內區間劃分分為兩部分：第一部分是函數區間的標識，第二部分是函數區間優化。

1)函數區間標識算法:函數區間標識算法通過狀態機來實現，定義11種狀態，利用互相的轉化關系求出函數范圍。狀態機轉化關系如表1所示。

表1 函數區間標識狀態機轉化關系

主要算法是在函數頭結束狀態中遇到{和}的處理邏輯，具體的算法如算法2所示。

算法2: 函數區間標識算法

輸入：文件路徑path；

輸出：函數劃分后起始行結束行的集合list。

switch state do

……

case 7 do

if 3=lastState and 6=lastState then

startLine ←line /*lastState表示當前狀態的上一個狀態*/

end if

if c ='{' then

bracket ←bracket + 1 /*bracket表示大括號的個數*/

end if

if c ='}' then

bracket← bracket - 1

end if

if 0 =bracket then

endLine← line + 1

list.add(startLine, endLine) /*list是保存起始行和結束行的集合*/

end if

……

end switch

算法描述：查看狀態機中的狀態，狀態7表示函數體開始，如果從成員變量初始化列表狀態(狀態3)或者從函數頭結束狀態(狀態6)轉換而來，需要記錄函數開始行數startLine.bracket表示括號個數，當前字符c如果是{符號需要增加括號個數，如果是}需要減少括號個數，如果括號個數減為0，則當前函數結束，記錄相應的結束行數endLine，隨后加入到函數劃分的集合中。

2)函數區間優化算法：對于區間劃分后的文件中，會存在部分沒有在任何區間中的代碼行需要進一步被劃分到現有區間中，區間劃分后剩余部分如圖7所示。

圖7 區間劃分后剩余部分

可以看出，例如“public：”“