楊劭君 蘇小紅 王甜甜 馬培軍

摘要：程序分析技術(shù)包括控制流分析、數(shù)據(jù)流分析、別名分析、程序切片和程序插樁等技術(shù)，在程序理解，代碼重構(gòu)、代碼優(yōu)化和軟件自動(dòng)化調(diào)試等方面有著重要的應(yīng)用，而詞法分析和語(yǔ)法分析技術(shù)是程序分析技術(shù)的基礎(chǔ)。本文設(shè)計(jì)與實(shí)現(xiàn)了一個(gè)輕量級(jí)的C語(yǔ)言詞法語(yǔ)法分析工具CParser，通過(guò)詞法分析、預(yù)處理和語(yǔ)法分析三個(gè)步驟，實(shí)現(xiàn)了根據(jù)源代碼建立相應(yīng)的抽象語(yǔ)法樹(shù)的功能。工具使用簡(jiǎn)單方便，而且能夠完整支持C99標(biāo)準(zhǔn)，可用于克隆代碼檢測(cè)、軟件錯(cuò)誤定位等后續(xù)研究工作。

關(guān)鍵詞：詞法分析；語(yǔ)法分析；抽象語(yǔ)法樹(shù)；編譯原理

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)號(hào)：A 文章編號(hào)：2095-2163（2014）05-

Design and Implementation of Lexical and Syntax Analysis Tool CParser for C Language

YANG Shaojun， SU Xiaohong， WANG Tiantian， MA Peijun

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin， 150001， China）

Abstract：Program analysis techniques contains control flow analysis， data flow analysis， alias analysis， program slicing techniques and program instrumentation， and has important applications in program comprehension， code refactoring， code optimization， automated software debugging and other aspects， and the lexical analysis and syntax analysis technology is the basis for program analysis techniques. This paper designs and implements a new C language syntax analysis tool named CParser， through three steps which are lexical analysis， preprocessing and syntax analysis to achieve the establishment of the abstract syntax tree based on the source code. This tool is easy to use， and can fully support the C99 standard， furtherly can be used to code clone detection and fault localization.

Keywords：Lexical Analysis； Syntax Analysis； Abstract Syntax Tree； Compiler Principles

0 引言

程序分析技術(shù)可以分為靜態(tài)分析技術(shù)和動(dòng)態(tài)分析技術(shù)兩大類(lèi)，具體來(lái)說(shuō)則包括控制流分析、數(shù)據(jù)流分析、別名分析、程序切片和程序插樁等諸多技術(shù)[1]，并在程序理解，代碼重構(gòu)、代碼優(yōu)化和軟件自動(dòng)化調(diào)試等方面有著重要的應(yīng)用。

程序分析技術(shù)中，詞法分析和語(yǔ)法分析是其實(shí)現(xiàn)基礎(chǔ)。具體地，詞法分析是對(duì)程序的源代碼進(jìn)行分析，并從中提取詞法單元（Token）的過(guò)程。語(yǔ)法分析則是按照編程語(yǔ)言的語(yǔ)法規(guī)則，對(duì)詞法分析得到的Token串進(jìn)行深度解析，并建立抽象語(yǔ)法樹(shù)的過(guò)程。

目前針對(duì)C語(yǔ)言的研究工作，大多都使用GCC或者基于LLVM[2]的Clang來(lái)分析源代碼，還有一些則使用一些其它較為簡(jiǎn)單的C語(yǔ)言詞法語(yǔ)法分析工具。但是，這些方法或多或少都存在一些缺陷。具體分析如下。

GCC和Clang都是完整的C、C++語(yǔ)言的編譯器，而C語(yǔ)言的詞法語(yǔ)法分析，僅僅用到了這些工具的很小一部分功能。而且，GCC并未提供方便的接口來(lái)提取根據(jù)源文件建立的抽象語(yǔ)法樹(shù)，需要使用者能夠解析GCC的AST中間文件，這一過(guò)程難度較大，尤其是其中包含了很多冗余信息，造成了很大不便。Clang則更為龐大、復(fù)雜，同時(shí)缺少相關(guān)的文檔和示例，學(xué)習(xí)和使用都較為困難，需要經(jīng)過(guò)較長(zhǎng)時(shí)間的摸索和嘗試。

而一些其他的C語(yǔ)言詞法語(yǔ)法分析工具，則未能完整支持必要的C語(yǔ)言標(biāo)準(zhǔn)，也未能很好地支持宏定義、頭文件引入和類(lèi)型聲明等特性，而是只能解析部分比較簡(jiǎn)單的C語(yǔ)言程序。

因此，本文使用C#語(yǔ)言設(shè)計(jì)了一個(gè)C語(yǔ)言詞法語(yǔ)法分析工具CParser，采用Visual Studio 2012 集成開(kāi)發(fā)環(huán)境提供管理運(yùn)行，主要實(shí)現(xiàn)了C99 （ISO/IEC 9899：1999）標(biāo)準(zhǔn)的全部特性，包括完整的預(yù)處理功能，以及對(duì)引入頭文件和類(lèi)型聲明的支持，已足夠用于常見(jiàn)的C語(yǔ)言程序分析。

1 詞法語(yǔ)法分析工具的整體設(shè)計(jì)

本文的目標(biāo)是實(shí)現(xiàn)簡(jiǎn)單易用的C語(yǔ)言的詞法語(yǔ)法分析工具，以C語(yǔ)言源文件作為輸入，以相應(yīng)的抽象語(yǔ)法樹(shù)作為輸出。具體地，采用了如圖1所示的架構(gòu)，其中主要包括詞法分析、預(yù)處理、語(yǔ)法分析、符號(hào)表和錯(cuò)誤處理五大模塊。

其基本原理是：首先輸入需要分析的C語(yǔ)言源程序，由詞法分析模塊對(duì)其進(jìn)行詞法分析，生成Token串。然后由預(yù)處理模塊對(duì)Token串執(zhí)行預(yù)處理，解析并處理其中的預(yù)處理指令。最后由語(yǔ)法分析模塊根據(jù)預(yù)處理后的結(jié)果建立抽象語(yǔ)法樹(shù)，再將其返回給用戶。各個(gè)模塊之間使用符號(hào)表交換必要的數(shù)據(jù)，如果任何模塊出現(xiàn)了錯(cuò)誤，則統(tǒng)一由錯(cuò)誤處理模塊向用戶提交報(bào)告。

圖1 詞法語(yǔ)法分析工具框架圖

Fig.1 Frame diagram of lexical and syntax analysis tool

2 詞法語(yǔ)法分析工具的具體實(shí)現(xiàn)

2.1 詞法分析的實(shí)現(xiàn)

要實(shí)現(xiàn)C語(yǔ)言的詞法分析，首先需要定義C語(yǔ)言的基本組成單元的實(shí)現(xiàn)模式，用于之后的文本匹配。通常使用正則表達(dá)式來(lái)進(jìn)行模式定義，本文定義了8個(gè)模式，分別是注釋?zhuān)ㄆヅ鋯涡谢蚨嘈凶⑨專(zhuān)?biāo)識(shí)符（匹配C語(yǔ)言的關(guān)鍵字和合法的標(biāo)識(shí)符）、數(shù)字常量（匹配整數(shù)、浮點(diǎn)數(shù)和科學(xué)記數(shù)法）、字符常量（匹配C語(yǔ)言的字符常量）、字符串常量（匹配C語(yǔ)言的字符串常量）、符號(hào)（匹配C語(yǔ)言的運(yùn)算符和分隔符）、換行符和空白。

詞法分析的原理，就是按照一定順序掃描給出的C語(yǔ)言源代碼，不斷的將讀入的源代碼與預(yù)先定義的模式進(jìn)行匹配。如果匹配成功，就表示成功地找到了一個(gè)Token，接下來(lái)繼續(xù)匹配剩余的源代碼直至到達(dá)文件結(jié)尾，源代碼即可成功轉(zhuǎn)換為T(mén)oken串。如果匹配失敗，則直接終止掃描，并向錯(cuò)誤處理模塊報(bào)告錯(cuò)誤信息。

模式的匹配過(guò)程，是建立可以識(shí)別模式的自動(dòng)機(jī)，來(lái)判斷源代碼與哪個(gè)模式相匹配。這樣雖然需要消耗一些時(shí)間來(lái)建立自動(dòng)機(jī)，但自動(dòng)機(jī)只需建立一次，就可以在O（n）的時(shí)間復(fù)雜度內(nèi)完成源代碼的掃描，其中n為源代碼的長(zhǎng)度。自動(dòng)機(jī)的建立程是利用Thompson 算法[3]，即將模式轉(zhuǎn)換為與其等價(jià)的不確定有窮自動(dòng)機(jī)（Nondeterministic Finite Automata， NFA），再利用子集構(gòu)造法[4]，構(gòu)造出與NFA等價(jià)的確定有窮自動(dòng)機(jī)（Deterministic Finite Automata， DFA），由此而實(shí)現(xiàn)穩(wěn)定高效的模式匹配。

在得到與源代碼對(duì)應(yīng)的Token串之后，會(huì)將其中表示注釋和空白的Token刪去，因?yàn)檫@些內(nèi)容僅用于幫助開(kāi)發(fā)者理解程序，在程序分析時(shí)并不會(huì)起到任何作用。而表示換行符的Token卻必須保留，因?yàn)镃語(yǔ)言的預(yù)處理指令是以換行符為結(jié)尾的，在接下來(lái)的預(yù)處理過(guò)程中即將會(huì)用到這一信息。

2.2 預(yù)處理的實(shí)現(xiàn)

C語(yǔ)言的預(yù)處理指令，主要包括文件包含指令（#include），宏定義指令（#define和#undef）、條件編譯指令（#if、#ifdef、#ifndef、#elif、#else和#endif），以及一些輔助指令（#line、#error和#pragma）。這些預(yù)處理指令的執(zhí)行，都是由預(yù)處理模塊完成的。

預(yù)處理模塊的功能就是遍歷詞法分析得到的Token串，找到并執(zhí)行其中的預(yù)處理指令。執(zhí)行完畢的預(yù)處理指令，即會(huì)從Token串中移除。下面介紹這些預(yù)處理指令的具體實(shí)現(xiàn)。

（1）文件包含指令，用于將指定文件的內(nèi)容包含到當(dāng)前源文件中。

如果指令中包含的文件名形式是 “fileName”，就會(huì)在當(dāng)前文件路徑中搜索該文件名；如果形式是，則會(huì)在用戶指定的標(biāo)準(zhǔn)頭文件目錄中搜索該文件名，失敗后還要在當(dāng)前文件路徑中再次搜索。如果搜索成功，即讀取文件的內(nèi)容，利用詞法分析模塊對(duì)其進(jìn)行詞法分析，并將得到的Token串插入到當(dāng)前Token串中。

（2）宏定義指令，用于定義或取消定義指定名稱的宏。

對(duì)于#define命令，則將定義的宏的名稱、內(nèi)容和當(dāng)前位置記錄下來(lái)；對(duì)于#undef宏，亦同樣會(huì)將宏的名稱和當(dāng)前位置記錄下來(lái)。宏的替換過(guò)程將在最后來(lái)進(jìn)行研究和處理。

一個(gè)宏的作用范圍是從#define的位置開(kāi)始，到相應(yīng)的#undef位置結(jié)束，在該范圍外，這個(gè)宏則不存在。而按照內(nèi)容的不同，可以將宏分為對(duì)象宏（無(wú)參數(shù)）和函數(shù)宏（有參數(shù)）兩類(lèi)。

（3）條件編譯指令，用于根據(jù)條件，選擇某些代碼進(jìn)行編譯，而忽略另外一些代碼。

首先需要找到#if、#elif、#else、#endif這些指令間的對(duì)應(yīng)關(guān)系（因條件編譯允許相互嵌套），然后按從上到下的順序依次計(jì)算指令中的條件，只有第一個(gè)結(jié)果不為0的指令所對(duì)應(yīng)的Token串會(huì)被保留，其余的Token都將被刪去。

在計(jì)算相應(yīng)條件時(shí)，需要將條件中的所有宏展開(kāi)，再將所有標(biāo)識(shí)符替換為整數(shù)0，最后就是計(jì)算這個(gè)僅由整數(shù)和整數(shù)運(yùn)算符組成的表達(dá)式的結(jié)果即可。

（4）輔助指令，提供一些輔助功能，這些指令對(duì)詞法語(yǔ)法分析過(guò)程均不產(chǎn)生影響，

經(jīng)過(guò)以上步驟，Token串中的預(yù)處理指令已經(jīng)全部移除，接下去就是執(zhí)行宏替換，也就是依次遍歷Token串中的每個(gè)Token，假設(shè)當(dāng)前遍歷到第i個(gè)Token，若：

① 該Token的類(lèi)型不是標(biāo)識(shí)符，或者標(biāo)識(shí)符不是已定義的宏名稱，還或者當(dāng)前位置不在宏的作用范圍內(nèi)，那么跳過(guò)當(dāng)前Token。

②該Token對(duì)應(yīng)的宏是對(duì)象宏，則將對(duì)象宏的內(nèi)容替換該Token，下次仍需從位置i重新開(kāi)始遍歷。

③該Token對(duì)應(yīng)的宏是函數(shù)宏，則從位置i+1開(kāi)始搜索實(shí)參，再使用函數(shù)宏的內(nèi)容替換該Token和實(shí)參，而下次仍需從位置i遍歷。在使用實(shí)參替換形參之前，還需要對(duì)實(shí)參進(jìn)行一次宏替換。

需要注意的是，如果在替換宏M時(shí)，將一個(gè)標(biāo)識(shí)符D插入到了Token串，那么其后D是不會(huì)再被宏M替換的。因?yàn)樯鲜龅暮晏鎿Q過(guò)程，同一個(gè)標(biāo)識(shí)符可能會(huì)經(jīng)歷多次掃描，隨之就需要保證不會(huì)出現(xiàn)無(wú)限的宏替換。

例如，對(duì)于以下代碼：

#define a a+b

a；

宏替換的結(jié)果是a+b；，宏a只會(huì)被替換一次，而不會(huì)出現(xiàn)無(wú)限替換的情況。

2.3 語(yǔ)法分析的實(shí)現(xiàn)

基于上述工作，其后就要開(kāi)展語(yǔ)法分析研究。這里同樣需要定義一系列規(guī)則，這些規(guī)則使用上下文無(wú)關(guān)文法，描述了C語(yǔ)言的語(yǔ)法。語(yǔ)法分析就是根據(jù)這些規(guī)則，構(gòu)造出LALR[5]語(yǔ)法分析表，再利用這個(gè)表格，嘗試將預(yù)處理得到的Token串與規(guī)則進(jìn)行匹配。如果匹配成功，就可以將Token串歸約為節(jié)點(diǎn)，并最終形成抽象語(yǔ)法樹(shù)。如果匹配失敗，說(shuō)明出現(xiàn)了語(yǔ)法錯(cuò)誤，同樣會(huì)終止匹配，并向錯(cuò)誤處理模塊報(bào)告錯(cuò)誤信息。

語(yǔ)法分析部分的規(guī)則定義非常復(fù)雜，本文共定義了220條規(guī)則，描述了63種抽象語(yǔ)法結(jié)構(gòu)。每種抽象語(yǔ)法結(jié)構(gòu)都對(duì)應(yīng)一種抽象語(yǔ)法樹(shù)節(jié)點(diǎn)，可以分為聲明、語(yǔ)句、表達(dá)式和類(lèi)型四大類(lèi)。這四類(lèi)結(jié)構(gòu)相互嵌套，就可以描述任意復(fù)雜的C語(yǔ)言源代碼。

所有的抽象語(yǔ)法樹(shù)節(jié)點(diǎn)都繼承自SyntaxNode類(lèi)，對(duì)其定義如下：

class SyntaxNode {

SyntaxKind Kind；

SourceRange Range；

IList ChildNodes；

}

所有節(jié)點(diǎn)都具有節(jié)點(diǎn)類(lèi)型、對(duì)應(yīng)的源文件位置，以及子節(jié)點(diǎn)這些屬性。不同類(lèi)型的節(jié)點(diǎn)，具體包含的子節(jié)點(diǎn)數(shù)是不同的，例如IfStatement類(lèi)表示if語(yǔ)句，可能包含Condition（條件表達(dá)式）、TrueStatements（條件為真時(shí)要執(zhí)行語(yǔ)句）和FalseStatements（條件為假時(shí)要執(zhí)行的語(yǔ)句）三個(gè)子節(jié)點(diǎn)。而B(niǎo)inaryExpression類(lèi)表示二元表達(dá)式，卻只會(huì)包含Left（左操作數(shù)）和Right（右操作數(shù)）兩個(gè)子節(jié)點(diǎn)。

本文使用的抽象語(yǔ)法樹(shù)，還實(shí)現(xiàn)了一個(gè)較為少見(jiàn)卻很實(shí)用的功能，能夠?qū)⒊橄笳Z(yǔ)法樹(shù)反向生成相應(yīng)的C語(yǔ)言源代碼。該功能有利于程序?qū)υ创a進(jìn)行修改，即首先通過(guò)詞法語(yǔ)法分析，建立源代碼的抽象語(yǔ)法樹(shù)。再用程序修改抽象語(yǔ)法樹(shù)，由于抽象語(yǔ)法樹(shù)中包含源代碼的所有結(jié)構(gòu)信息，因此程序的操作會(huì)極為便捷。最后再反向生成相應(yīng)的C語(yǔ)言源代碼，進(jìn)而實(shí)現(xiàn)源代碼的修改。

2.4 用戶界面的設(shè)計(jì)和實(shí)現(xiàn)

本文基于CParser工具，實(shí)現(xiàn)了一個(gè)語(yǔ)法樹(shù)建立與展示的程序，具體如圖2所示。點(diǎn)擊分析按鈕，選擇要分析的C語(yǔ)言源代碼，就會(huì)對(duì)源代碼進(jìn)行詞法語(yǔ)法分析，建立相應(yīng)的抽象語(yǔ)法樹(shù)，并在界面右邊顯示出來(lái)。

界面左邊列出了被分析的源文件、包含的頭文件以及診斷信息（分析時(shí)產(chǎn)生的錯(cuò)誤信息），界面右邊是相應(yīng)的抽象語(yǔ)法樹(shù)。選擇一個(gè)抽象語(yǔ)法樹(shù)節(jié)點(diǎn)，與其對(duì)應(yīng)的源代碼會(huì)高亮顯示，便于根據(jù)抽象語(yǔ)法樹(shù)找到相應(yīng)的源代碼。圖2左側(cè)高亮的if語(yǔ)句塊，對(duì)應(yīng)的抽象語(yǔ)法樹(shù)即如圖3所示，每一個(gè)橢圓表示一個(gè)抽象語(yǔ)法樹(shù)節(jié)點(diǎn)，其中的文字是節(jié)點(diǎn)的類(lèi)型，第二行加粗的文本是該節(jié)點(diǎn)附加的屬性。

可以看到，抽象語(yǔ)法樹(shù)中只包括了源代碼的抽象結(jié)構(gòu)，源代碼的很多不影響程序結(jié)構(gòu)的細(xì)節(jié)信息（空白、注釋、花括號(hào)等分隔符）都已移除，而關(guān)鍵信息（如變量名、常量等）則全部保留下來(lái)。

if語(yǔ)句的條件表達(dá)式，語(yǔ)句塊內(nèi)的fprintf函數(shù)和exit函數(shù)調(diào)用，很容易就能夠在抽象語(yǔ)法樹(shù)中找到相應(yīng)的節(jié)點(diǎn)，關(guān)鍵的變量名稱、函數(shù)名稱等信息也全部保存在節(jié)點(diǎn)屬性中。將圖3所示的抽象語(yǔ)法樹(shù)顯示在界面上，即如圖2右邊所示，而且同樣也是以樹(shù)狀結(jié)構(gòu)來(lái)實(shí)現(xiàn)可視顯示的。

圖2 語(yǔ)法樹(shù)建立與展示程序的界面

Fig.2 Interface of syntax tree build and display program

圖3 條件語(yǔ)句的抽象語(yǔ)法樹(shù)

Fig.3 Abstract syntax tree of condition statement

3 結(jié)束語(yǔ)

本文實(shí)現(xiàn)了一個(gè)C語(yǔ)言詞法語(yǔ)法分析工具CParser。該工具首先使用DFA實(shí)現(xiàn)Token的匹配，繼而完整地實(shí)現(xiàn)了預(yù)處理過(guò)程，最后基于LALR語(yǔ)法分析技術(shù)將Token串建立為抽象語(yǔ)法樹(shù)。

本文成果的優(yōu)勢(shì)在于能夠完整地支持C99標(biāo)準(zhǔn)，而且無(wú)需復(fù)雜的配置，使用簡(jiǎn)單，開(kāi)發(fā)效率高，且只要給出即將分析的源代碼，就能夠自動(dòng)建立抽象語(yǔ)法樹(shù)。本文設(shè)計(jì)的C語(yǔ)言詞法語(yǔ)法分析工具CParser是一種非常實(shí)用的輕量級(jí)的C語(yǔ)言分析工具，并且對(duì)于克隆代碼檢測(cè)、軟件錯(cuò)誤定位等后續(xù)研究工作具有良好的適用性。

參考文獻(xiàn)

[1] 梅宏，王千祥，張路等.軟件分析技術(shù)進(jìn)展[J].計(jì)算機(jī)學(xué)報(bào)，2009，32（9）：1697-1710. DOI：10.3724/SP.J.1016.2009.01697.

[2] LATTNER C， ADVE V. LLVM： A compilation framework for lifelong program analysis & transformation[C]//Code Generation and Optimization， 2004. CGO 2004. International Symposium on. IEEE， 2004： 75-86.

[3] CHANG C H， PAIGE R. From regular expressions to dfa's using compressed nfa's[C]//Combinatorial Pattern Matching. Springer Berlin Heidelberg， 1992： 90-110.

[4] RABIN M O， SCOTT D. Finite automata and their decision problems[J]. IBM journal of research and development， 1959， 3（2）： 114-125.

[5] De REMER F L. Practical translators for LR （k） languages[D]. Massachusetts Institute of Technology， 1969.