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

2、如何實現(xiàn)c程序的靜態(tài)分析、程序轉(zhuǎn)換、程序編譯提供了重要的思路方法。關(guān)鍵詞：ckit；ast；抽象語法樹；漂亮格式打印：tp311 ：a ：1009-3044（2017）27-0229-041 背景ckit是一個對c語言程序進行語法分析和類型檢查的程序。對ckit的熟練掌握是實現(xiàn)c程序的靜態(tài)分析、程序轉(zhuǎn)換、程序編譯的重要基礎(chǔ)。ckit系統(tǒng)是使用sml語言編寫的一個處理c源程序的前端，它提供了c語言的詞法規(guī)則和語法規(guī)則，能對c源程序進行詞法和語法分析并將其轉(zhuǎn)換成抽象語法樹，這棵抽象語法樹可以使我們對輸入的c程序有結(jié)構(gòu)上較為直觀的了解。使用這棵語法樹，我們可以實現(xiàn)許多其他相關(guān)功能。對輸入的c程序進行

3、漂亮格式打印就是其中之一。所謂漂亮格式打印就是將輸入的c程序以凸凹有致的交錯結(jié)構(gòu)顯現(xiàn)出來，有利與我們及其他人的觀看，許多c程序的開發(fā)環(huán)境已提供了這種功能，這為我們在編寫c語言程序的過程中檢查程序結(jié)構(gòu)提供了方便。本文對ckit系統(tǒng)進行了詳細的分析，并通過調(diào)用系統(tǒng)提供的函數(shù)，實現(xiàn)了輸入程序的漂亮格式打印，通過這個功能的添加擴展了ckit對c語言的處理能力。2 ckit系統(tǒng)詳細介紹2.1 ckit轉(zhuǎn)換c程序的步驟我們將c的源程序輸入到ckit系統(tǒng)中，系統(tǒng)的輸出為該c源程序的抽象語法樹。其中，粗虛線框內(nèi)表示的就是整個ckit系統(tǒng)。我們將c的源程序輸入到ckit系統(tǒng)中，系統(tǒng)的主要輸出為簡化后的c程序。綠

4、色的虛線框內(nèi)輸出為源程序的漂亮打印。其詳細解釋如表1所示。2.2 c的抽象語法（parser tree）分析c程序，生成相應(yīng)的分析樹，我們需要c程序的剖析器（parser）。ckit程序提供了c.lex和c.grm兩個文件。文件c.lex是用來描述c程序的詞法規(guī)則的。文件c.grm是用來描述c程序的語法規(guī)則的，其作用是定義了進行詞法分析的關(guān)鍵詞、對關(guān)鍵詞進行的操作以及最終生成的目標數(shù)據(jù)格式。定義好這兩個文件后，我們還需要利用專門工具ml-lex 及ml-yacc將其轉(zhuǎn)化為ml的程序文件c.lex.sml及c.grm.sml。當然，sml/nj為我們提供了方便的工具cm（compilationa

5、ndlibrarymanager），使我們不必費心去弄清如何利用ml-lex 及ml-yacc去創(chuàng)建相應(yīng)的文件。我們只需要在路徑ckit-1.0ckitsrc下運行sml/mj然后敲入命令“cm.make（）；”一切就都解決了。c.grm文件的作用是：1） 定義了終結(jié)符集和非終結(jié)符集。2） 定義最終提取出的數(shù)據(jù)的格式。3） 定義對匹配出來的字符的操作：當根據(jù)關(guān)鍵詞定義提取到匹配的字符后，需要根據(jù)不同的關(guān)鍵詞匹配對字符進行不同的操作，以生成我們需要的最終數(shù)據(jù)格式。c.grm.sml和s.lex.sml模塊生成圖可以通過圖3表示。得到c.grm.sml和c.lex.sml兩個模塊文件后，parse

6、r.sml就可以調(diào)用這兩個模塊進行程序格式轉(zhuǎn)化了。在parser.sml中，進行格式轉(zhuǎn)化的函數(shù)是fun parsefile errstate f。它需要兩個參數(shù)，一個參數(shù)是error.errorstate，另一個參數(shù)是指定需要處理的c程序文件，輸出即為parse tree。parse tree包括externaldecl、qualifier 、storage and specifier、declarator、declaration、expression、operator和statement等結(jié)構(gòu)。externaldecl用于獨立的全局變量、結(jié)構(gòu)、函數(shù)等的聲明。所有的程序最終都會歸結(jié)由若干ext

7、ernaldecl組成。qualifier 和storage定義了可能出現(xiàn)在c數(shù)據(jù)類型前面的修飾符。secifier合并了c語言所有可能的基本類型和構(gòu)造類型。各構(gòu)造子分別用來表示c語言中各種不同數(shù)據(jù)類型。declarator用來指明變量的名稱以及是哪種數(shù)據(jù)類型的聲明。declaration用于各種變量的聲明以及賦值等。expression用于表示由運算符、函數(shù)調(diào)用、常量及變量等構(gòu)成的表達式。operator用于表示各種運算符，statement表示組成計算機程序的語句。2.3 ckit的抽象語法ckit的抽象語法ast主要由文件ast.sml及ast-sig.sml定義，ast.sml定義如下

8、的數(shù)據(jù)類型：ast，是語法抽象樹的最終表示，其是由若干externaldecl構(gòu)成的。externaldecl和coreexternaldecl，所構(gòu)造的值表示全局變量、struct、typedef等與函數(shù)定義并列的數(shù)據(jù)結(jié)構(gòu)，是用于表示全局的聲明或定義的主要數(shù)據(jù)類型。storageclass表示存儲類型auto | extern | register | static | default。endprintbinop與unop表示運算符號。intkind、signednesstag、signedness、fractionality、saturatedness它們用來定義ctype中的構(gòu)造子nnm

9、eric。qualifier表示數(shù)據(jù)類型是const 還是volatile。label，lable一般與goto連用，標志應(yīng)該跳轉(zhuǎn)到函數(shù)的哪個位置繼續(xù)執(zhí)行指令。member和memberkind（該類型表明了結(jié)構(gòu)、枚舉等數(shù)據(jù)結(jié)構(gòu)的成員）、（該類型用于輔助member類型）。ctype用來指明變量的數(shù)據(jù)類型。intkind （該類型定義了基本的c語言的與數(shù)字直接關(guān)系的數(shù)據(jù)類型）。id該類型用于標志關(guān)于程序中一個變量的所有情況。declstatus用來指明變量變量的狀態(tài)。declration用來指明變量的聲明及初始化。statement 與corestatement表示組成計算機程序的若干條語句e

10、xpression、coreexpression、initexpressi on表示由運算符、函數(shù)調(diào)用、常量及變量等的表達式3 由parsetree到ast的轉(zhuǎn)換3.1 parsetree與ast語法結(jié)構(gòu)的對應(yīng)關(guān)系圖4顯示了parsetree與ast語法結(jié)構(gòu)的對應(yīng)關(guān)系。3.2 主要轉(zhuǎn)換函數(shù)1） statefuns這個結(jié)構(gòu)定義了處理parsetree過程中與ast的數(shù)據(jù)結(jié)構(gòu)的當前狀態(tài)有關(guān)的若干記錄以及相關(guān)的操作函數(shù)。2） mungetydecr這個結(jié)構(gòu)對pt.declarator進行處理，獲得ast.ctype的相關(guān)構(gòu)造子，同時，如果變量有名稱，還會的到該名稱。3） cnvtype該函數(shù)將par

11、setree 的數(shù)據(jù)類型轉(zhuǎn)換為相關(guān)的ast的數(shù)據(jù)類型。4） cnvexpression該函數(shù)將parsetree 的表達式轉(zhuǎn)換為相關(guān)的ast的表達式。5） cnvstatement該函數(shù)將parsetree 的語句轉(zhuǎn)換為相關(guān)的ast的語句。6） cnvexternaldecl該函數(shù)將組成parsetree 的toplevel數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換為相關(guān)的ast的toplevel數(shù)據(jù)結(jié)構(gòu)。3.3 ast對parse tree的優(yōu)化parse tree是一個簡單的未經(jīng)過過多處理的數(shù)據(jù)結(jié)構(gòu)，其形式上與c語言的語法結(jié)構(gòu)十分接近。ckit中的函數(shù)fun makeast （sizes： sizes.sizes， s

12、tateinfo： s.stateinfo， errorstate ： error.errorstate）可以為輸入的parse tree數(shù)據(jù)結(jié)構(gòu)生成ast，生成的ast數(shù)據(jù)結(jié)構(gòu)是對parse tree數(shù)據(jù)結(jié)構(gòu)的優(yōu)化的結(jié)果，其主要表現(xiàn)在：1） 類型檢測：ckit對c程序進行了詳盡的ansic c類型檢測，并產(chǎn)生適當?shù)腻e誤（error）和警告（warning）。如果存在parse errors則錯誤和警告被抑制。是否進行類型檢測以及進行何種類型檢測可以由src/variants/ansic/config.sml文件定義的typecheckcontrol structure來控制。2） 作用域：c

13、kit嚴格判斷了每個變量、結(jié)構(gòu)、聯(lián)合、枚舉類型等數(shù)據(jù)結(jié)構(gòu)的作用域。3） pid：為c程序中的每一個變量、函數(shù)、結(jié)構(gòu)等賦予了一個唯一的pid（由遞增的整數(shù)表示）。4） aid：每個主要語法范疇（major syntactic categories）例如 statements， expressions， and declarations被賦予了唯一的一個aid（由遞增的整數(shù)表示）。這些索引用來將信息與程序的具體部分對應(yīng)起來。5） tid：用來指示typedef、struct、union等定義所處的位置，相當于一個占位符。6） 類型大小與存儲配置（type sizes and memory layo

14、ut）：buildast可以計算在程序中聲明的對象的大小。它也可以將sizeof表達式縮減為一個整數(shù)（默認不縮減）。關(guān)于這方面的配置由src/variants/ansic/config.sml文件的sizes structure來控制。7） 初始化標準化：處理數(shù)據(jù)的初始化，以便使之與數(shù)據(jù)的聲明類型相匹配。通過以上所說的各種優(yōu)化，使得ast的語法比c的稍有復(fù)雜。但應(yīng)用ckit系統(tǒng)轉(zhuǎn)化后的c程序擁有與源程序相同的作用但是比源程序更容易理解分析。4 漂亮格式打印的實現(xiàn)所謂漂亮格式就是以某c源代碼為主，按照一定的縮進方式形成犬牙交錯格式的最終c源代碼。這不僅使程序漂亮美觀，而且增強了程序的可讀性。如今

15、，許多開發(fā)環(huán)境已經(jīng)集成了這種功能。ckit中，該功能的實現(xiàn)是在ast的基礎(chǔ)上進行的。4.1 oldprettyprint結(jié)構(gòu)oldprettyprint是由路徑ckitsrcparserutil下的文件old-pp.sml定義的。它是sml/nj提供的漂亮格式打印的接口的實現(xiàn)。通過這個文件所提供的函數(shù)，我們可以很容易地控制組成程序的元素的打印位置。它為繼續(xù)實現(xiàn)c程序的漂亮格式打印提供了極大的方便。4.2 pplibendprint這個結(jié)構(gòu)內(nèi)包含的數(shù)據(jù)結(jié)構(gòu)主要是漂亮格式打印的輔助函數(shù)。1） structure pp聲明了結(jié)構(gòu)pp為與ckit的漂亮格式打印接口以及其提供的一些常用函數(shù)的聲明。dot

16、ostrm這是實現(xiàn)漂亮格式打印最終要使用的函數(shù)。2） ppint、ppreal與ppstring實現(xiàn)int、real、string類型數(shù)據(jù)的格式轉(zhuǎn)換及打印。3） separate與pplist實現(xiàn)鏈表元素的打印，且每個元素之間使用固定字符隔開，打印結(jié)果使用”（”和”）”括起來。4） space與spaces填加1個或n個空格。5） blockify該函數(shù)主要用來標志某一區(qū)域，在該區(qū)域內(nèi)所有元素的打印都要縮進n個空格的距離。6） ppopt打印option類型的元素。7） ppguarded選擇性打印括號。8） ppsymbol、ppid、pplabel、ppmember與pptidppbino

17、p實現(xiàn)二元運算符的輸出9） ppunop實現(xiàn)一元運算符的輸出10） ispostfix用來判斷一個運算符是前綴運算符還是后綴運算符。11） ppidentifier實現(xiàn)變量名稱的輸出。12） ppqualifier、ppstorageclass、ppsignedness、ppfractionality、ppsaturatedness和ppintkind實現(xiàn)相應(yīng)的變量修飾符的輸出。13） ppstk和ppspstk，ppstk被ppspstk調(diào)用，ppspstk被ppdecl0調(diào)用，用來輔助其實現(xiàn)變量聲明的左側(cè)部分，包括類型和變量名稱。14） ppdecl0與ppctype。ppdecl0用來實現(xiàn)函數(shù)聲明的左側(cè)部分的輸出，包括類型和變量名稱。ppctype的輸出與ppdecl0相比，少了變量名稱的輸出，僅輸出了類型。其主要用在函數(shù)聲明時沒有說明名稱僅說明了類型處實現(xiàn)參數(shù)類型的輸出。15） pprefctype實現(xiàn)struct 、union 、typedef 、enum的具體內(nèi)容的輸出，而不僅僅是類似ast中，使用tid號代替。16） ppstmt與blockstmt實現(xiàn)c程序中具體語句的輸出，包括復(fù)合語句。17） ppexpr實現(xiàn)c程序中表達式的輸出。18） ppinitexpression被ppdeclaration調(diào)用，打印初始化變量的右半部分。19） ppd