基于JavaCC的抽象語法樹生成錯(cuò)誤處理技術(shù)研究

王國隆，金大海， 宮云戰(zhàn)

(北京郵電大學(xué) 網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京 100876)

0 引言

為保障計(jì)算機(jī)軟件質(zhì)量，應(yīng)盡早進(jìn)行軟件測試，而軟件測試的重要手段之一就是靜態(tài)測試[1-5]。隨著C++語言標(biāo)準(zhǔn)11/14/17的不斷演進(jìn)，新標(biāo)準(zhǔn)對C++語法進(jìn)行了諸多補(bǔ)充和優(yōu)化，同時(shí)也帶來了許多擴(kuò)充的新特性[6]。隨著C++新標(biāo)準(zhǔn)在市場上大面積的普及應(yīng)用，對支持C++新標(biāo)準(zhǔn)的靜態(tài)測試也顯得尤為重要。

目前存在很多用于C++靜態(tài)測試的工具，如Cpplint[7]，PMD[8]，Cppcheck[9]等。在這些靜態(tài)測試工具中都必須對代碼解析。抽象語法樹是對代碼的一種重要的中間表示形式，也是一個(gè)對代碼進(jìn)行靜態(tài)測試的不可或缺的數(shù)據(jù)結(jié)構(gòu)，在代碼測試分析領(lǐng)域有著廣泛的應(yīng)用[10]。

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

1 相關(guān)工作

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

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

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

現(xiàn)有的詞法語法分析工具對C++新標(biāo)準(zhǔn)支持的不多，一些研究人員是面向C++98標(biāo)準(zhǔn)構(gòu)造抽象語法樹并進(jìn)行分析，與他們工作不同的是，本文是面向C++新標(biāo)準(zhǔn)生成抽象語法樹并對生成錯(cuò)誤進(jìn)行處理，此方法既可應(yīng)對不支持或者不匹配的語法片段，也可應(yīng)對C++日后的語法更新。

2 抽象語法樹生成錯(cuò)誤分析

2.1 抽象語法樹生成錯(cuò)誤原因

抽象語法樹(AST,abstract syntax tree)是以樹狀的形式表達(dá)源代碼語法結(jié)構(gòu)的一種表現(xiàn)形式[17]，用T=表示，其中：N為樹的節(jié)點(diǎn)，表示代碼中的一種語法結(jié)構(gòu)；E為樹的邊，表示代碼中的語法邏輯關(guān)系。

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

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

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

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

語法規(guī)則文件不能完全支持C++新標(biāo)準(zhǔn)的原因主要有以下3點(diǎn)：

2.2.1 C++新標(biāo)準(zhǔn)BNF范式無法獲取

官方的C++新標(biāo)準(zhǔn)的BNF范式文檔無法獲取，并且網(wǎng)上存在的新標(biāo)準(zhǔn)BNF范式各有出入，無法確定是否和官方一致。如果范式文檔選擇出現(xiàn)問題，會對后續(xù)分析處理產(chǎn)生重大影響。

2.2.2 C++新標(biāo)準(zhǔn)語法結(jié)構(gòu)變化大

C++新標(biāo)準(zhǔn)語法更改中，提出了新的語法結(jié)構(gòu)，新的功能，在新關(guān)鍵字的配合之下或不需要新的關(guān)鍵字，在原有關(guān)鍵字的基礎(chǔ)之上，提出新的結(jié)構(gòu)，完成新的功能。這主要目的是為了更加方便地實(shí)現(xiàn)相應(yīng)的功能。以語法樹中statement節(jié)點(diǎn)的語法結(jié)構(gòu)的變化為例，如圖2所示。

圖2 C++新標(biāo)準(zhǔn)語法結(jié)構(gòu)變化示例

標(biāo)準(zhǔn)更新后出現(xiàn)更多的是語法結(jié)構(gòu)的變化，有些結(jié)構(gòu)是在原有結(jié)構(gòu)的基礎(chǔ)之上進(jìn)行擴(kuò)展，這種在構(gòu)建抽象語法樹的時(shí)候相對容易進(jìn)行更改，但是很多結(jié)構(gòu)的更改是在推翻原有結(jié)構(gòu)的基礎(chǔ)上進(jìn)行重新架構(gòu)(如圖2)，同時(shí)還會糅合其他新的結(jié)構(gòu)進(jìn)來，層層嵌套。這種在破壞原有結(jié)構(gòu)的基礎(chǔ)上進(jìn)行的更改在構(gòu)建抽象語法樹時(shí)相對困難。

由于破壞原有的語法結(jié)構(gòu)，所以在修改抽象語法樹規(guī)則文件時(shí)，也需要對相應(yīng)結(jié)構(gòu)進(jìn)行破壞，這樣無法保證在破壞現(xiàn)有結(jié)構(gòu)后仍然可以對原有結(jié)構(gòu)進(jìn)行支撐，這是較難的問題。對于這種問題，一方面對新的語法盡量修改規(guī)則文件進(jìn)行支撐，無法支撐的語法需要通過錯(cuò)誤處理技術(shù)進(jìn)行處理。

2.2.3 C++新標(biāo)準(zhǔn)核心庫變更大

C++新標(biāo)準(zhǔn)的庫更樂于使用復(fù)雜的嵌套結(jié)構(gòu)和模板類來對相關(guān)代碼進(jìn)行聲明，所以結(jié)構(gòu)變得相對復(fù)雜，而之前的C++98的庫更多的是使用直接聲明的方法。例如C++98和C++11核心庫iostream的變化如圖3所示。

圖3 C++新標(biāo)準(zhǔn)核心庫變化示例

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

綜上，在對C++新標(biāo)準(zhǔn)的語法邏輯做到最大可能的支撐的基礎(chǔ)上，對于還不支持的會導(dǎo)致語法樹生成錯(cuò)誤的語法要進(jìn)行錯(cuò)誤處理。因?yàn)殄e(cuò)誤會導(dǎo)致語法樹生成中斷，錯(cuò)誤點(diǎn)之后的源代碼不能生成相關(guān)的語法樹節(jié)點(diǎn)，導(dǎo)致對應(yīng)源文件的語法樹不完整，從而影響后續(xù)靜態(tài)分析。所以本文重點(diǎn)討論在語法樹生成中跳過不支持或不匹配的語法片段的錯(cuò)誤處理技術(shù)。

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

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

圖4 抽象語法樹生成錯(cuò)誤處理框架

首先，源代碼經(jīng)過預(yù)處理后生成中間文件。之后是一個(gè)迭代的過程，如果中間文件生成抽象語法樹成功，直接結(jié)束；如果抽象語法樹生成錯(cuò)誤，則需要根據(jù)報(bào)錯(cuò)行數(shù)跳過附近語法片段以此繼續(xù)生成抽象語法樹直至成功。

3.1 預(yù)處理

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

先要對C++源文件進(jìn)行預(yù)處理，預(yù)處理是通過編譯器進(jìn)行的，包括一些宏替換，條件編譯以及頭文件展開等操作。正是因?yàn)樾枰鲜霾僮?，所以不能使?cpp文件直接進(jìn)行處理，需要使用預(yù)處理后生成的中間文件.i進(jìn)一步生成抽象語法樹。

3.2 語法樹生成錯(cuò)誤處理

中間文件經(jīng)過詞法和語法規(guī)則文件生成抽象語法樹，如果成功生成，當(dāng)前文件分析完成；如果生成出錯(cuò)，那么接下來進(jìn)入語法樹生成錯(cuò)誤處理流程。

α1α2…αn=w1αiw2

(1)

式中,w1為已經(jīng)分析并且生成語法樹節(jié)點(diǎn)的部分；αi為當(dāng)前分析的token；w2為當(dāng)前文件剩余的token流。

假定分析到αi生成語法樹時(shí)發(fā)生錯(cuò)誤，因?yàn)榉治鍪亲陨隙碌?，那就意味著?dāng)前已經(jīng)建立了部分語法樹，并且已經(jīng)生成的語法樹已經(jīng)涵蓋了w1，但是語法樹卻無法繼續(xù)生成以涵蓋w2。此時(shí)，就必須應(yīng)用錯(cuò)誤處理技術(shù)來繼續(xù)生成語法樹?？刹扇〉拇胧┤缦拢?/p>

1)刪除當(dāng)前tokenαi并繼續(xù)分析；

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

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

(2)

然后再從αi開始分析；

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

3)從w1的尾部刪去若干個(gè)token后繼續(xù)分析。

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

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

(3)

式中,

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

(4)

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

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

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

模塊流程設(shè)計(jì)如圖5所示。

如圖5所示，新語法錯(cuò)誤處理模塊可以分為3個(gè)部分：1)源程序分離；2)文件內(nèi)函數(shù)區(qū)間劃分；3)注釋報(bào)錯(cuò)區(qū)間迭代生成抽象語法樹。

3.2.1 源程序分離

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

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

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

孟春辰[17]根據(jù)“# 行號 文件存放路徑”從后向前遍歷，直到遇到文件后綴.h就結(jié)束遍歷。但是對于圖6代碼，在源程序中還插入了一些擴(kuò)展進(jìn)來的頭文件部分，之前的算法不能準(zhǔn)確截取出源程序部分，所以提出了算法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

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

3.2.2 文件內(nèi)區(qū)間劃分

對上述中間文件分離出的源程序部分生成語法樹，如果發(fā)生錯(cuò)誤，就需要根據(jù)報(bào)錯(cuò)行數(shù)注釋相應(yīng)的區(qū)間，所以接下來就需要對中間文件進(jìn)行區(qū)間劃分。

定義1:函數(shù)區(qū)間：函數(shù)區(qū)間是文件內(nèi)用來標(biāo)識一個(gè)函數(shù)名稱和范圍的結(jié)構(gòu)，該結(jié)構(gòu)由一個(gè)三元組表示，該結(jié)構(gòu)描述記為I={Name,StartLine,EndLine}，其中：

Name：表示該函數(shù)區(qū)間的函數(shù)名稱；

StartLine：表示該函數(shù)區(qū)間的起始行數(shù)；

EndLine：表示該函數(shù)區(qū)間的終止行數(shù)。

文件內(nèi)區(qū)間劃分分為兩部分：第一部分是函數(shù)區(qū)間的標(biāo)識，第二部分是函數(shù)區(qū)間優(yōu)化。

1)函數(shù)區(qū)間標(biāo)識算法:函數(shù)區(qū)間標(biāo)識算法通過狀態(tài)機(jī)來實(shí)現(xiàn)，定義11種狀態(tài)，利用互相的轉(zhuǎn)化關(guān)系求出函數(shù)范圍。狀態(tài)機(jī)轉(zhuǎn)化關(guān)系如表1所示。

表1 函數(shù)區(qū)間標(biāo)識狀態(tài)機(jī)轉(zhuǎn)化關(guān)系

主要算法是在函數(shù)頭結(jié)束狀態(tài)中遇到{和}的處理邏輯，具體的算法如算法2所示。

算法2: 函數(shù)區(qū)間標(biāo)識算法

輸入：文件路徑path；

輸出：函數(shù)劃分后起始行結(jié)束行的集合list。

switch state do

……

case 7 do

if 3=lastState and 6=lastState then

startLine ←line /*lastState表示當(dāng)前狀態(tài)的上一個(gè)狀態(tài)*/

end if

if c ='{' then

bracket ←bracket + 1 /*bracket表示大括號的個(gè)數(shù)*/

end if

if c ='}' then

bracket← bracket - 1

end if

if 0 =bracket then

endLine← line + 1

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

end if

……

end switch

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

2)函數(shù)區(qū)間優(yōu)化算法：對于區(qū)間劃分后的文件中，會存在部分沒有在任何區(qū)間中的代碼行需要進(jìn)一步被劃分到現(xiàn)有區(qū)間中，區(qū)間劃分后剩余部分如圖7所示。

圖7 區(qū)間劃分后剩余部分

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