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

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

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

中圖分類號：TP311 文獻(xiàn)標(biāo)識號：A 文章編號：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ù)和動態(tài)分析技術(shù)兩大類，具體來說則包括控制流分析、數(shù)據(jù)流分析、別名分析、程序切片和程序插樁等諸多技術(shù)[1]，并在程序理解，代碼重構(gòu)、代碼優(yōu)化和軟件自動化調(diào)試等方面有著重要的應(yīng)用。

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

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

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

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

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

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

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

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

圖1 詞法語法分析工具框架圖

Fig.1 Frame diagram of lexical and syntax analysis tool

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

需要注意的是，如果在替換宏M時，將一個標(biāo)識符D插入到了Token串，那么其后D是不會再被宏M替換的。因為上述的宏替換過程，同一個標(biāo)識符可能會經(jīng)歷多次掃描，隨之就需要保證不會出現(xiàn)無限的宏替換。

例如，對于以下代碼：

#define a a+b

a；

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

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

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

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

所有的抽象語法樹節(jié)點(diǎn)都繼承自SyntaxNode類，對其定義如下：

class SyntaxNode {

SyntaxKind Kind；

SourceRange Range；

IList ChildNodes；

}

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

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

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

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

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

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

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

圖2 語法樹建立與展示程序的界面

Fig.2 Interface of syntax tree build and display program

圖3 條件語句的抽象語法樹

Fig.3 Abstract syntax tree of condition statement

3 結(jié)束語

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

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

參考文獻(xiàn)

[1] 梅宏，王千祥，張路等.軟件分析技術(shù)進(jìn)展[J].計算機(jī)學(xué)報，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.