张雪

摘要：对C程序进行词法，语法、语意分析及差错检测是编译器需要进行的工作中的重要组成部分，该处理工作对于我们进一步处理C 程序至关重要。Ckit系统是使用SML语言编写的一个处理C源程序的前端，它提供了C语言的词法规则和语法规则，能对C源程序进行词法和语法分析并将其转换成抽象语法树，该棵抽象语法树可以使人们对输入的C程序有结构上较为直观的了解。使用该棵语法树，人们还可以实现许多其他相关功能。例如对输入的C程序进行漂亮格式打印。该篇论文详细分析了CKit的内部结构和实现技术，并在该基础上实现了C程序亮格式打印，为大家如何实现C程序的静态分析、程序转换、程序编译提供了重要的思路方法。

关键词：Ckit；Ast；抽象语法树；漂亮格式打印

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）27-0229-04

1 背景

Ckit是一个对C语言程序进行语法分析和类型检查的程序。对Ckit的熟练掌握是实现C程序的静态分析、程序转换、程序编译的重要基础。

Ckit系统是使用SML语言编写的一个处理C源程序的前端，它提供了C语言的词法规则和语法规则，能对C源程序进行词法和语法分析并将其转换成抽象语法树，这棵抽象语法树可以使我们对输入的C程序有结构上较为直观的了解。使用这棵语法树，我们可以实现许多其他相关功能。对输入的C程序进行漂亮格式打印就是其中之一。所谓漂亮格式打印就是将输入的C程序以凸凹有致的交错结构显现出来，有利与我们及其他人的观看，许多C程序的开发环境已提供了这种功能，这为我们在编写C语言程序的过程中检查程序结构提供了方便。本文对Ckit系统进行了详细的分析，并通过调用系统提供的函数，实现了输入程序的漂亮格式打印，通过这个功能的添加扩展了Ckit对C语言的处理能力。

2 Ckit系统详细介绍

2.1 Ckit转换C程序的步骤

我们将C的源程序输入到Ckit系统中，系统的输出为该C源程序的抽象语法树。

其中，粗虚线框内表示的就是整个Ckit系统。我们将C的源程序输入到Ckit系统中，系统的主要输出为简化后的C程序。绿色的虚线框内输出为源程序的漂亮打印。其详细解释如表1所示。

2.2 C的抽象语法（Parser Tree）

分析C程序，生成相应的分析树，我们需要C程序的剖析器（parser）。Ckit程序提供了c.lex和c.grm两个文件。文件c.lex是用来描述C程序的词法规则的。文件c.grm是用来描述C程序的语法规则的，其作用是定义了进行词法分析的关键词、对关键词进行的操作以及最终生成的目标数据格式。定义好这两个文件后，我们还需要利用专门工具ML-LEX 及ML-YACC将其转化为ML的程序文件c.lex.sml及c.grm.sml。当然，SML/NJ为我们提供了方便的工具CM（CompilationandLibraryManager），使我们不必费心去弄清如何利用ML-LEX 及ML-YACC去创建相应的文件。我们只需要在路径ckit-1.0＼ckit＼src下运行SML/MJ然后敲入命令“CM.make（）；”一切就都解决了。

c.grm文件的作用是：

1） 定义了终结符集和非终结符集。

2） 定义最终提取出的数据的格式。

3） 定义对匹配出来的字符的操作：当根据关键词定义提取到匹配的字符后，需要根据不同的关键词匹配对字符进行不同的操作，以生成我们需要的最终数据格式。

c.grm.sml和s.lex.sml模块生成图可以通过图3表示。

得到c.grm.sml和c.lex.sml两个模块文件后，Parser.sml就可以调用这两个模块进行程序格式转化了。

在Parser.sml中，进行格式转化的函数是fun parseFile errState f。它需要两个参数，一个参数是Error.errorState，另一个参数是指定需要处理的C程序文件，输出即为Parse tree。

Parse tree包括externalDecl、qualifier 、storage and specifier、declarator、declaration、expression、operator和statement等结构。

externalDecl用于独立的全局变量、结构、函数等的声明。所有的程序最终都会归结由若干externalDecl组成。

qualifier 和storage定义了可能出现在C数据类型前面的修饰符。

Secifier合并了C语言所有可能的基本类型和构造类型。各构造子分别用来表示C语言中各种不同数据类型。

declarator用来指明变量的名称以及是哪种数据类型的声明。

declaration用于各种变量的声明以及赋值等。

Expression用于表示由运算符、函数调用、常量及变量等构成的表达式。

Operator用于表示各种运算符，

Statement表示组成计算机程序的语句。

2.3 Ckit的抽象语法

Ckit的抽象语法Ast主要由文件ast.sml及ast-sig.sml定义，ast.sml定义如下的数据类型：

Ast，是语法抽象树的最终表示，其是由若干externalDecl构成的。

externalDecl和coreExternalDecl，所构造的值表示全局变量、struct、typedef等与函数定义并列的数据结构，是用于表示全局的声明或定义的主要数据类型。

storageClass表示存储类型AUTO | EXTERN | REGISTER | STATIC | DEFAULT。

binop与unop表示运算符号。

intkind、signednessTag、signedness、fractionality、saturatedness它们用来定义ctype中的构造子Nnmeric。

qualifier表示数据类型是CONST 还是VOLATILE。

label，lable一般与goto连用，标志应该跳转到函数的哪个位置继续执行指令。

member和memberKind（该类型表明了结构、枚举等数据结构的成员）、（该类型用于辅助member类型）。

ctype用来指明变量的数据类型。

intkind （该类型定义了基本的c语言的与数字直接关系的数据类型）。

id该类型用于标志关于程序中一个变量的所有情况。

declStatus用来指明变量变量的状态。

declration用来指明变量的声明及初始化。

statement 与coreStatement表示组成计算机程序的若干条语句

expression、coreExpression、initExpressi on表示由运算符、函数调用、常量及变量等的表达式

3 由ParseTree到Ast的转换

3.1 ParseTree与Ast语法结构的对应关系

图4显示了ParseTree与Ast语法结构的对应关系。

3.2 主要转换函数

1） stateFuns

这个结构定义了处理ParseTree过程中与Ast的数据结构的当前状态有关的若干记录以及相关的操作函数。

2） mungeTyDecr

这个结构对PT.declarator进行处理，获得Ast.ctype的相关构造子，同时，如果变量有名称，还会的到该名称。

3） cnvType

该函数将ParseTree 的数据类型转换为相关的Ast的数据类型。

4） cnvExpression

该函数将ParseTree 的表达式转换为相关的Ast的表达式。

5） cnvStatement

该函数将ParseTree 的语句转换为相关的Ast的语句。

6） cnvExternalDecl

该函数将组成ParseTree 的toplevel数据结构转换为相关的Ast的toplevel数据结构。

3.3 Ast对Parse Tree的优化

Parse Tree是一个简单的未经过过多处理的数据结构，其形式上与C语言的语法结构十分接近。ckit中的函数fun makeAst （sizes： Sizes.sizes， stateInfo： S.stateInfo， errorState ： Error.errorState）可以为输入的Parse Tree数据结构生成Ast，生成的Ast数据结构是对Parse Tree数据结构的优化的结果，其主要表现在：

1） 类型检测：ckit对c程序进行了详尽的ANSIC C类型检测，并产生适当的错误（error）和警告（warning）。如果存在parse errors则错误和警告被抑制。是否进行类型检测以及进行何种类型检测可以由src/variants/ansic/config.sml文件定义的TypeCheckControl structure来控制。

2） 作用域：ckit严格判断了每个变量、结构、联合、枚举类型等数据结构的作用域。

3） pid：为C程序中的每一个变量、函数、结构等赋予了一个唯一的pid（由递增的整数表示）。

4） aid：每个主要语法范畴（major syntactic categories）例如 statements， expressions， and declarations被赋予了唯一的一个aid（由递增的整数表示）。这些索引用来将信息与程序的具体部分对应起来。

5） tid：用来指示typedef、struct、union等定义所处的位置，相当于一个占位符。

6） 类型大小与存储配置（Type Sizes And Memory Layout）：BuildAst可以计算在程序中声明的对象的大小。它也可以将sizeof表达式缩减为一个整数（默认不缩减）。关于这方面的配置由src/variants/ansic/config.sml文件的Sizes structure来控制。

7） 初始化标准化：处理数据的初始化，以便使之与数据的声明类型相匹配。

通过以上所说的各种优化，使得Ast的语法比C的稍有复杂。但应用Ckit系统转化后的C程序拥有与源程序相同的作用但是比源程序更容易理解分析。

4 漂亮格式打印的实现

所谓漂亮格式就是以某c源代码为主，按照一定的缩进方式形成犬牙交错格式的最终c源代码。这不仅使程序漂亮美观，而且增强了程序的可读性。如今，许多开发环境已经集成了这种功能。

Ckit中，该功能的实现是在Ast的基础上进行的。

4.1 OldPrettyPrint

结构OldPrettyPrint是由路径ckit＼src＼parser＼util下的文件old-pp.sml定义的。它是SML/NJ提供的漂亮格式打印的接口的实现。通过这个文件所提供的函数，我们可以很容易地控制组成程序的元素的打印位置。它为继续实现C程序的漂亮格式打印提供了极大的方便。

4.2 PPLib

这个结构内包含的数据结构主要是漂亮格式打印的辅助函数。

1） structure PP声明了结构PP为与ckit的漂亮格式打印接口以及其提供的一些常用函数的声明。dotoStrm这是实现漂亮格式打印最终要使用的函数。

2） ppInt、ppReal与ppString实现int、real、string类型数据的格式转换及打印。

3） separate与ppList实现链表元素的打印，且每个元素之间使用固定字符隔开，打印结果使用”（”和”）”括起来。

4） space与spaces填加1个或n个空格。

5） blockify该函数主要用来标志某一区域，在该区域内所有元素的打印都要缩进n个空格的距离。

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

7） ppGuarded选择性打印括号。

8） ppSymbol、ppId、ppLabel、ppMember与pptidppBinop实现二元运算符的输出

9） ppUnop实现一元运算符的输出

10） isPostFix用来判断一个运算符是前缀运算符还是后缀运算符。

11） ppIdentifier实现变量名称的输出。

12） ppQualifier、ppStorageClass、ppSignedness、ppFractionality、ppSaturatedness和ppIntKind实现相应的变量修饰符的输出。

13） ppStk和ppSpStk，ppStk被ppSpStk调用，ppSpStk被ppDecl0调用，用来辅助其实现变量声明的左侧部分，包括类型和变量名称。

14） ppDecl0与ppCtype。ppDecl0用来实现函数声明的左侧部分的输出，包括类型和变量名称。ppCtype的输出与ppDecl0相比，少了变量名称的输出，仅输出了类型。其主要用在函数声明时没有说明名称仅说明了类型处实现参数类型的输出。

15） ppRefCtype实现struct 、union 、typedef 、enum的具体内容的输出，而不仅仅是类似Ast中，使用tid号代替。

16） ppStmt与blockStmt实现C程序中具体语句的输出，包括复合语句。

17） ppExpr实现C程序中表达式的输出。

18） ppInitExpression被ppDeclaration调用，打印初始化变量的右半部分。

19） ppDeclaration打印C程序中的声明语句。

20） ppExternalDecl打印全局的数据结构。

21） ppAst最终实现漂亮格式打印的函数。该函数通过调用前面的一系列函数重现C程序并以比较漂亮的方式显现出来。

4.3 实验结果

实验结果如图5—图8所示。