Ckit系統(tǒng)分析及應(yīng)用

張雪

摘要：對(duì)C程序進(jìn)行詞法，語(yǔ)法、語(yǔ)意分析及差錯(cuò)檢測(cè)是編譯器需要進(jìn)行的工作中的重要組成部分，該處理工作對(duì)于我們進(jìn)一步處理C 程序至關(guān)重要。Ckit系統(tǒng)是使用SML語(yǔ)言編寫(xiě)的一個(gè)處理C源程序的前端，它提供了C語(yǔ)言的詞法規(guī)則和語(yǔ)法規(guī)則，能對(duì)C源程序進(jìn)行詞法和語(yǔ)法分析并將其轉(zhuǎn)換成抽象語(yǔ)法樹(shù)，該棵抽象語(yǔ)法樹(shù)可以使人們對(duì)輸入的C程序有結(jié)構(gòu)上較為直觀的了解。使用該棵語(yǔ)法樹(shù)，人們還可以實(shí)現(xiàn)許多其他相關(guān)功能。例如對(duì)輸入的C程序進(jìn)行漂亮格式打印。該篇論文詳細(xì)分析了CKit的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)技術(shù)，并在該基礎(chǔ)上實(shí)現(xiàn)了C程序亮格式打印，為大家如何實(shí)現(xiàn)C程序的靜態(tài)分析、程序轉(zhuǎn)換、程序編譯提供了重要的思路方法。

關(guān)鍵詞：Ckit；Ast；抽象語(yǔ)法樹(shù)；漂亮格式打印

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）27-0229-04

1 背景

Ckit是一個(gè)對(duì)C語(yǔ)言程序進(jìn)行語(yǔ)法分析和類型檢查的程序。對(duì)Ckit的熟練掌握是實(shí)現(xiàn)C程序的靜態(tài)分析、程序轉(zhuǎn)換、程序編譯的重要基礎(chǔ)。

Ckit系統(tǒng)是使用SML語(yǔ)言編寫(xiě)的一個(gè)處理C源程序的前端，它提供了C語(yǔ)言的詞法規(guī)則和語(yǔ)法規(guī)則，能對(duì)C源程序進(jìn)行詞法和語(yǔ)法分析并將其轉(zhuǎn)換成抽象語(yǔ)法樹(shù)，這棵抽象語(yǔ)法樹(shù)可以使我們對(duì)輸入的C程序有結(jié)構(gòu)上較為直觀的了解。使用這棵語(yǔ)法樹(shù)，我們可以實(shí)現(xiàn)許多其他相關(guān)功能。對(duì)輸入的C程序進(jìn)行漂亮格式打印就是其中之一。所謂漂亮格式打印就是將輸入的C程序以凸凹有致的交錯(cuò)結(jié)構(gòu)顯現(xiàn)出來(lái)，有利與我們及其他人的觀看，許多C程序的開(kāi)發(fā)環(huán)境已提供了這種功能，這為我們?cè)诰帉?xiě)C語(yǔ)言程序的過(guò)程中檢查程序結(jié)構(gòu)提供了方便。本文對(duì)Ckit系統(tǒng)進(jìn)行了詳細(xì)的分析，并通過(guò)調(diào)用系統(tǒng)提供的函數(shù)，實(shí)現(xiàn)了輸入程序的漂亮格式打印，通過(guò)這個(gè)功能的添加擴(kuò)展了Ckit對(duì)C語(yǔ)言的處理能力。

2 Ckit系統(tǒng)詳細(xì)介紹

2.1 Ckit轉(zhuǎn)換C程序的步驟

我們將C的源程序輸入到Ckit系統(tǒng)中，系統(tǒng)的輸出為該C源程序的抽象語(yǔ)法樹(shù)。

其中，粗虛線框內(nèi)表示的就是整個(gè)Ckit系統(tǒng)。我們將C的源程序輸入到Ckit系統(tǒng)中，系統(tǒng)的主要輸出為簡(jiǎn)化后的C程序。綠色的虛線框內(nèi)輸出為源程序的漂亮打印。其詳細(xì)解釋如表1所示。

2.2 C的抽象語(yǔ)法（Parser Tree）

分析C程序，生成相應(yīng)的分析樹(shù)，我們需要C程序的剖析器（parser）。Ckit程序提供了c.lex和c.grm兩個(gè)文件。文件c.lex是用來(lái)描述C程序的詞法規(guī)則的。文件c.grm是用來(lái)描述C程序的語(yǔ)法規(guī)則的，其作用是定義了進(jìn)行詞法分析的關(guān)鍵詞、對(duì)關(guān)鍵詞進(jìn)行的操作以及最終生成的目標(biāo)數(shù)據(jù)格式。定義好這兩個(gè)文件后，我們還需要利用專門(mén)工具M(jìn)L-LEX 及ML-YACC將其轉(zhuǎn)化為ML的程序文件c.lex.sml及c.grm.sml。當(dāng)然，SML/NJ為我們提供了方便的工具CM（CompilationandLibraryManager），使我們不必費(fèi)心去弄清如何利用ML-LEX 及ML-YACC去創(chuàng)建相應(yīng)的文件。我們只需要在路徑ckit-1.0＼ckit＼src下運(yùn)行SML/MJ然后敲入命令“CM.make（）；”一切就都解決了。

c.grm文件的作用是：

1） 定義了終結(jié)符集和非終結(jié)符集。

2） 定義最終提取出的數(shù)據(jù)的格式。

3） 定義對(duì)匹配出來(lái)的字符的操作：當(dāng)根據(jù)關(guān)鍵詞定義提取到匹配的字符后，需要根據(jù)不同的關(guān)鍵詞匹配對(duì)字符進(jìn)行不同的操作，以生成我們需要的最終數(shù)據(jù)格式。

c.grm.sml和s.lex.sml模塊生成圖可以通過(guò)圖3表示。

得到c.grm.sml和c.lex.sml兩個(gè)模塊文件后，Parser.sml就可以調(diào)用這兩個(gè)模塊進(jìn)行程序格式轉(zhuǎn)化了。

在Parser.sml中，進(jìn)行格式轉(zhuǎn)化的函數(shù)是fun parseFile errState f。它需要兩個(gè)參數(shù)，一個(gè)參數(shù)是Error.errorState，另一個(gè)參數(shù)是指定需要處理的C程序文件，輸出即為Parse tree。

Parse tree包括externalDecl、qualifier 、storage and specifier、declarator、declaration、expression、operator和statement等結(jié)構(gòu)。

externalDecl用于獨(dú)立的全局變量、結(jié)構(gòu)、函數(shù)等的聲明。所有的程序最終都會(huì)歸結(jié)由若干externalDecl組成。

qualifier 和storage定義了可能出現(xiàn)在C數(shù)據(jù)類型前面的修飾符。

Secifier合并了C語(yǔ)言所有可能的基本類型和構(gòu)造類型。各構(gòu)造子分別用來(lái)表示C語(yǔ)言中各種不同數(shù)據(jù)類型。

declarator用來(lái)指明變量的名稱以及是哪種數(shù)據(jù)類型的聲明。

declaration用于各種變量的聲明以及賦值等。

Expression用于表示由運(yùn)算符、函數(shù)調(diào)用、常量及變量等構(gòu)成的表達(dá)式。

Operator用于表示各種運(yùn)算符，

Statement表示組成計(jì)算機(jī)程序的語(yǔ)句。

2.3 Ckit的抽象語(yǔ)法

Ckit的抽象語(yǔ)法Ast主要由文件ast.sml及ast-sig.sml定義，ast.sml定義如下的數(shù)據(jù)類型：

Ast，是語(yǔ)法抽象樹(shù)的最終表示，其是由若干externalDecl構(gòu)成的。

externalDecl和coreExternalDecl，所構(gòu)造的值表示全局變量、struct、typedef等與函數(shù)定義并列的數(shù)據(jù)結(jié)構(gòu)，是用于表示全局的聲明或定義的主要數(shù)據(jù)類型。

storageClass表示存儲(chǔ)類型AUTO | EXTERN | REGISTER | STATIC | DEFAULT。endprint

binop與unop表示運(yùn)算符號(hào)。

intkind、signednessTag、signedness、fractionality、saturatedness它們用來(lái)定義ctype中的構(gòu)造子Nnmeric。

qualifier表示數(shù)據(jù)類型是CONST 還是VOLATILE。

label，lable一般與goto連用，標(biāo)志應(yīng)該跳轉(zhuǎn)到函數(shù)的哪個(gè)位置繼續(xù)執(zhí)行指令。

member和memberKind（該類型表明了結(jié)構(gòu)、枚舉等數(shù)據(jù)結(jié)構(gòu)的成員）、（該類型用于輔助member類型）。

ctype用來(lái)指明變量的數(shù)據(jù)類型。

intkind （該類型定義了基本的c語(yǔ)言的與數(shù)字直接關(guān)系的數(shù)據(jù)類型）。

id該類型用于標(biāo)志關(guān)于程序中一個(gè)變量的所有情況。

declStatus用來(lái)指明變量變量的狀態(tài)。

declration用來(lái)指明變量的聲明及初始化。

statement 與coreStatement表示組成計(jì)算機(jī)程序的若干條語(yǔ)句

expression、coreExpression、initExpressi on表示由運(yùn)算符、函數(shù)調(diào)用、常量及變量等的表達(dá)式

3 由ParseTree到Ast的轉(zhuǎn)換

3.1 ParseTree與Ast語(yǔ)法結(jié)構(gòu)的對(duì)應(yīng)關(guān)系

圖4顯示了ParseTree與Ast語(yǔ)法結(jié)構(gòu)的對(duì)應(yīng)關(guān)系。

3.2 主要轉(zhuǎn)換函數(shù)

1） stateFuns

這個(gè)結(jié)構(gòu)定義了處理ParseTree過(guò)程中與Ast的數(shù)據(jù)結(jié)構(gòu)的當(dāng)前狀態(tài)有關(guān)的若干記錄以及相關(guān)的操作函數(shù)。

2） mungeTyDecr

這個(gè)結(jié)構(gòu)對(duì)PT.declarator進(jìn)行處理，獲得Ast.ctype的相關(guān)構(gòu)造子，同時(shí)，如果變量有名稱，還會(huì)的到該名稱。

3） cnvType

該函數(shù)將ParseTree 的數(shù)據(jù)類型轉(zhuǎn)換為相關(guān)的Ast的數(shù)據(jù)類型。

4） cnvExpression

該函數(shù)將ParseTree 的表達(dá)式轉(zhuǎn)換為相關(guān)的Ast的表達(dá)式。

5） cnvStatement

該函數(shù)將ParseTree 的語(yǔ)句轉(zhuǎn)換為相關(guān)的Ast的語(yǔ)句。

6） cnvExternalDecl

該函數(shù)將組成ParseTree 的toplevel數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換為相關(guān)的Ast的toplevel數(shù)據(jù)結(jié)構(gòu)。

3.3 Ast對(duì)Parse Tree的優(yōu)化

Parse Tree是一個(gè)簡(jiǎn)單的未經(jīng)過(guò)過(guò)多處理的數(shù)據(jù)結(jié)構(gòu)，其形式上與C語(yǔ)言的語(yǔ)法結(jié)構(gòu)十分接近。ckit中的函數(shù)fun makeAst （sizes： Sizes.sizes， stateInfo： S.stateInfo， errorState ： Error.errorState）可以為輸入的Parse Tree數(shù)據(jù)結(jié)構(gòu)生成Ast，生成的Ast數(shù)據(jù)結(jié)構(gòu)是對(duì)Parse Tree數(shù)據(jù)結(jié)構(gòu)的優(yōu)化的結(jié)果，其主要表現(xiàn)在：

1） 類型檢測(cè)：ckit對(duì)c程序進(jìn)行了詳盡的ANSIC C類型檢測(cè)，并產(chǎn)生適當(dāng)?shù)腻e(cuò)誤（error）和警告（warning）。如果存在parse errors則錯(cuò)誤和警告被抑制。是否進(jìn)行類型檢測(cè)以及進(jìn)行何種類型檢測(cè)可以由src/variants/ansic/config.sml文件定義的TypeCheckControl structure來(lái)控制。

2） 作用域：ckit嚴(yán)格判斷了每個(gè)變量、結(jié)構(gòu)、聯(lián)合、枚舉類型等數(shù)據(jù)結(jié)構(gòu)的作用域。

3） pid：為C程序中的每一個(gè)變量、函數(shù)、結(jié)構(gòu)等賦予了一個(gè)唯一的pid（由遞增的整數(shù)表示）。

4） aid：每個(gè)主要語(yǔ)法范疇（major syntactic categories）例如 statements， expressions， and declarations被賦予了唯一的一個(gè)aid（由遞增的整數(shù)表示）。這些索引用來(lái)將信息與程序的具體部分對(duì)應(yīng)起來(lái)。

5） tid：用來(lái)指示typedef、struct、union等定義所處的位置，相當(dāng)于一個(gè)占位符。

6） 類型大小與存儲(chǔ)配置（Type Sizes And Memory Layout）：BuildAst可以計(jì)算在程序中聲明的對(duì)象的大小。它也可以將sizeof表達(dá)式縮減為一個(gè)整數(shù)（默認(rèn)不縮減）。關(guān)于這方面的配置由src/variants/ansic/config.sml文件的Sizes structure來(lái)控制。

7） 初始化標(biāo)準(zhǔn)化：處理數(shù)據(jù)的初始化，以便使之與數(shù)據(jù)的聲明類型相匹配。

通過(guò)以上所說(shuō)的各種優(yōu)化，使得Ast的語(yǔ)法比C的稍有復(fù)雜。但應(yīng)用Ckit系統(tǒng)轉(zhuǎn)化后的C程序擁有與源程序相同的作用但是比源程序更容易理解分析。

4 漂亮格式打印的實(shí)現(xiàn)

所謂漂亮格式就是以某c源代碼為主，按照一定的縮進(jìn)方式形成犬牙交錯(cuò)格式的最終c源代碼。這不僅使程序漂亮美觀，而且增強(qiáng)了程序的可讀性。如今，許多開(kāi)發(fā)環(huán)境已經(jīng)集成了這種功能。

Ckit中，該功能的實(shí)現(xiàn)是在Ast的基礎(chǔ)上進(jìn)行的。

4.1 OldPrettyPrint

結(jié)構(gòu)OldPrettyPrint是由路徑ckit＼src＼parser＼util下的文件old-pp.sml定義的。它是SML/NJ提供的漂亮格式打印的接口的實(shí)現(xiàn)。通過(guò)這個(gè)文件所提供的函數(shù)，我們可以很容易地控制組成程序的元素的打印位置。它為繼續(xù)實(shí)現(xiàn)C程序的漂亮格式打印提供了極大的方便。

4.2 PPLibendprint

這個(gè)結(jié)構(gòu)內(nèi)包含的數(shù)據(jù)結(jié)構(gòu)主要是漂亮格式打印的輔助函數(shù)。

1） structure PP聲明了結(jié)構(gòu)PP為與ckit的漂亮格式打印接口以及其提供的一些常用函數(shù)的聲明。dotoStrm這是實(shí)現(xiàn)漂亮格式打印最終要使用的函數(shù)。

2） ppInt、ppReal與ppString實(shí)現(xiàn)int、real、string類型數(shù)據(jù)的格式轉(zhuǎn)換及打印。

3） separate與ppList實(shí)現(xiàn)鏈表元素的打印，且每個(gè)元素之間使用固定字符隔開(kāi)，打印結(jié)果使用”（”和”）”括起來(lái)。

4） space與spaces填加1個(gè)或n個(gè)空格。

5） blockify該函數(shù)主要用來(lái)標(biāo)志某一區(qū)域，在該區(qū)域內(nèi)所有元素的打印都要縮進(jìn)n個(gè)空格的距離。

6） ppOpt打印option類型的元素。

7） ppGuarded選擇性打印括號(hào)。

8） ppSymbol、ppId、ppLabel、ppMember與pptidppBinop實(shí)現(xiàn)二元運(yùn)算符的輸出

9） ppUnop實(shí)現(xiàn)一元運(yùn)算符的輸出

10） isPostFix用來(lái)判斷一個(gè)運(yùn)算符是前綴運(yùn)算符還是后綴運(yùn)算符。

11） ppIdentifier實(shí)現(xiàn)變量名稱的輸出。

12） ppQualifier、ppStorageClass、ppSignedness、ppFractionality、ppSaturatedness和ppIntKind實(shí)現(xiàn)相應(yīng)的變量修飾符的輸出。

13） ppStk和ppSpStk，ppStk被ppSpStk調(diào)用，ppSpStk被ppDecl0調(diào)用，用來(lái)輔助其實(shí)現(xiàn)變量聲明的左側(cè)部分，包括類型和變量名稱。

14） ppDecl0與ppCtype。ppDecl0用來(lái)實(shí)現(xiàn)函數(shù)聲明的左側(cè)部分的輸出，包括類型和變量名稱。ppCtype的輸出與ppDecl0相比，少了變量名稱的輸出，僅輸出了類型。其主要用在函數(shù)聲明時(shí)沒(méi)有說(shuō)明名稱僅說(shuō)明了類型處實(shí)現(xiàn)參數(shù)類型的輸出。

15） ppRefCtype實(shí)現(xiàn)struct 、union 、typedef 、enum的具體內(nèi)容的輸出，而不僅僅是類似Ast中，使用tid號(hào)代替。

16） ppStmt與blockStmt實(shí)現(xiàn)C程序中具體語(yǔ)句的輸出，包括復(fù)合語(yǔ)句。

17） ppExpr實(shí)現(xiàn)C程序中表達(dá)式的輸出。

18） ppInitExpression被ppDeclaration調(diào)用，打印初始化變量的右半部分。

19） ppDeclaration打印C程序中的聲明語(yǔ)句。

20） ppExternalDecl打印全局的數(shù)據(jù)結(jié)構(gòu)。

21） ppAst最終實(shí)現(xiàn)漂亮格式打印的函數(shù)。該函數(shù)通過(guò)調(diào)用前面的一系列函數(shù)重現(xiàn)C程序并以比較漂亮的方式顯現(xiàn)出來(lái)。

4.3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果如圖5—圖8所示。endprint