C语言词法语法分析工具CParser的设计与实现
2014-04-29杨劭君苏小红王甜甜马培军
杨劭君 苏小红 王甜甜 马培军
摘要：程序分析技术包括控制流分析、数据流分析、别名分析、程序切片和程序插桩等技术，在程序理解，代码重构、代码优化和软件自动化调试等方面有着重要的应用，而词法分析和语法分析技术是程序分析技术的基础。本文设计与实现了一个轻量级的C语言词法语法分析工具CParser，通过词法分析、预处理和语法分析三个步骤，实现了根据源代码建立相应的抽象语法树的功能。工具使用简单方便，而且能够完整支持C99标准，可用于克隆代码检测、软件错误定位等后续研究工作。
关键词：词法分析；语法分析；抽象语法树；编译原理
中图分类号：TP311 文献标识号：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 引言
程序分析技术可以分为静态分析技术和动态分析技术两大类，具体来说则包括控制流分析、数据流分析、别名分析、程序切片和程序插桩等诸多技术[1]，并在程序理解，代码重构、代码优化和软件自动化调试等方面有着重要的应用。
程序分析技术中，词法分析和语法分析是其实现基础。具体地，词法分析是对程序的源代码进行分析，并从中提取词法单元（Token）的过程。语法分析则是按照编程语言的语法规则，对词法分析得到的Token串进行深度解析，并建立抽象语法树的过程。
目前针对C语言的研究工作，大多都使用GCC或者基于LLVM[2]的Clang来分析源代码，还有一些则使用一些其它较为简单的C语言词法语法分析工具。但是，这些方法或多或少都存在一些缺陷。具体分析如下。
GCC和Clang都是完整的C、C++语言的编译器，而C语言的词法语法分析，仅仅用到了这些工具的很小一部分功能。而且，GCC并未提供方便的接口来提取根据源文件建立的抽象语法树，需要使用者能够解析GCC的AST中间文件，这一过程难度较大，尤其是其中包含了很多冗余信息，造成了很大不便。Clang则更为庞大、复杂，同时缺少相关的文档和示例，学习和使用都较为困难，需要经过较长时间的摸索和尝试。
而一些其他的C语言词法语法分析工具，则未能完整支持必要的C语言标准，也未能很好地支持宏定义、头文件引入和类型声明等特性，而是只能解析部分比较简单的C语言程序。
因此，本文使用C#语言设计了一个C语言词法语法分析工具CParser，采用Visual Studio 2012 集成开发环境提供管理运行，主要实现了C99 （ISO/IEC 9899：1999）标准的全部特性，包括完整的预处理功能，以及对引入头文件和类型声明的支持，已足够用于常见的C语言程序分析。
1 词法语法分析工具的整体设计
本文的目标是实现简单易用的C语言的词法语法分析工具，以C语言源文件作为输入，以相应的抽象语法树作为输出。具体地，采用了如图1所示的架构，其中主要包括词法分析、预处理、语法分析、符号表和错误处理五大模块。
其基本原理是：首先输入需要分析的C语言源程序，由词法分析模块对其进行词法分析，生成Token串。然后由预处理模块对Token串执行预处理，解析并处理其中的预处理指令。最后由语法分析模块根据预处理后的结果建立抽象语法树，再将其返回给用户。各个模块之间使用符号表交换必要的数据，如果任何模块出现了错误，则统一由错误处理模块向用户提交报告。
图1 词法语法分析工具框架图
Fig.1 Frame diagram of lexical and syntax analysis tool
2 词法语法分析工具的具体实现
2.1 词法分析的实现
要实现C语言的词法分析，首先需要定义C语言的基本组成单元的实现模式，用于之后的文本匹配。通常使用正则表达式来进行模式定义，本文定义了8个模式，分别是注释（匹配单行或多行注释）、标识符（匹配C语言的关键字和合法的标识符）、数字常量（匹配整数、浮点数和科学记数法）、字符常量（匹配C语言的字符常量）、字符串常量（匹配C语言的字符串常量）、符号（匹配C语言的运算符和分隔符）、换行符和空白。
词法分析的原理，就是按照一定顺序扫描给出的C语言源代码，不断的将读入的源代码与预先定义的模式进行匹配。如果匹配成功，就表示成功地找到了一个Token，接下来继续匹配剩余的源代码直至到达文件结尾，源代码即可成功转换为Token串。如果匹配失败，则直接终止扫描，并向错误处理模块报告错误信息。
模式的匹配过程，是建立可以识别模式的自动机，来判断源代码与哪个模式相匹配。这样虽然需要消耗一些时间来建立自动机，但自动机只需建立一次，就可以在O（n）的时间复杂度内完成源代码的扫描，其中n为源代码的长度。自动机的建立程是利用Thompson 算法[3]，即将模式转换为与其等价的不确定有穷自动机（Nondeterministic Finite Automata， NFA），再利用子集构造法[4]，构造出与NFA等价的确定有穷自动机（Deterministic Finite Automata， DFA），由此而实现稳定高效的模式匹配。
在得到与源代码对应的Token串之后，会将其中表示注释和空白的Token删去，因为这些内容仅用于帮助开发者理解程序，在程序分析时并不会起到任何作用。而表示换行符的Token却必须保留，因为C语言的预处理指令是以换行符为结尾的，在接下来的预处理过程中即将会用到这一信息。
2.2 预处理的实现
C语言的预处理指令，主要包括文件包含指令（#include），宏定义指令（#define和#undef）、条件编译指令（#if、#ifdef、#ifndef、#elif、#else和#endif），以及一些辅助指令（#line、#error和#pragma）。这些预处理指令的执行，都是由预处理模块完成的。
预处理模块的功能就是遍历词法分析得到的Token串，找到并执行其中的预处理指令。执行完毕的预处理指令，即会从Token串中移除。下面介绍这些预处理指令的具体实现。
（1）文件包含指令，用于将指定文件的内容包含到当前源文件中。
如果指令中包含的文件名形式是 “fileName”，就会在当前文件路径中搜索该文件名；如果形式是
（2）宏定义指令，用于定义或取消定义指定名称的宏。
对于#define命令，则将定义的宏的名称、内容和当前位置记录下来；对于#undef宏，亦同样会将宏的名称和当前位置记录下来。宏的替换过程将在最后来进行研究和处理。
一个宏的作用范围是从#define的位置开始，到相应的#undef位置结束，在该范围外，这个宏则不存在。而按照内容的不同，可以将宏分为对象宏（无参数）和函数宏（有参数）两类。
（3）条件编译指令，用于根据条件，选择某些代码进行编译，而忽略另外一些代码。
首先需要找到#if、#elif、#else、#endif这些指令间的对应关系（因条件编译允许相互嵌套），然后按从上到下的顺序依次计算指令中的条件，只有第一个结果不为0的指令所对应的Token串会被保留，其余的Token都将被删去。
在计算相应条件时，需要将条件中的所有宏展开，再将所有标识符替换为整数0，最后就是计算这个仅由整数和整数运算符组成的表达式的结果即可。
（4）辅助指令，提供一些辅助功能，这些指令对词法语法分析过程均不产生影响，
经过以上步骤，Token串中的预处理指令已经全部移除，接下去就是执行宏替换，也就是依次遍历Token串中的每个Token，假设当前遍历到第i个Token，若：
① 该Token的类型不是标识符，或者标识符不是已定义的宏名称，还或者当前位置不在宏的作用范围内，那么跳过当前Token。
②该Token对应的宏是对象宏，则将对象宏的内容替换该Token，下次仍需从位置i重新开始遍历。
③该Token对应的宏是函数宏，则从位置i+1开始搜索实参，再使用函数宏的内容替换该Token和实参，而下次仍需从位置i遍历。在使用实参替换形参之前，还需要对实参进行一次宏替换。
需要注意的是，如果在替换宏M时，将一个标识符D插入到了Token串，那么其后D是不会再被宏M替换的。因为上述的宏替换过程，同一个标识符可能会经历多次扫描，随之就需要保证不会出现无限的宏替换。
例如，对于以下代码：
#define a a+b
a；
宏替换的结果是a+b；，宏a只会被替换一次，而不会出现无限替换的情况。
2.3 语法分析的实现
基于上述工作，其后就要开展语法分析研究。这里同样需要定义一系列规则，这些规则使用上下文无关文法，描述了C语言的语法。语法分析就是根据这些规则，构造出LALR[5]语法分析表，再利用这个表格，尝试将预处理得到的Token串与规则进行匹配。如果匹配成功，就可以将Token串归约为节点，并最终形成抽象语法树。如果匹配失败，说明出现了语法错误，同样会终止匹配，并向错误处理模块报告错误信息。
语法分析部分的规则定义非常复杂，本文共定义了220条规则，描述了63种抽象语法结构。每种抽象语法结构都对应一种抽象语法树节点，可以分为声明、语句、表达式和类型四大类。这四类结构相互嵌套，就可以描述任意复杂的C语言源代码。
所有的抽象语法树节点都继承自SyntaxNode类，对其定义如下：
class SyntaxNode {
SyntaxKind Kind；
SourceRange Range；
IList
}
所有节点都具有节点类型、对应的源文件位置，以及子节点这些属性。不同类型的节点，具体包含的子节点数是不同的，例如IfStatement类表示if语句，可能包含Condition（条件表达式）、TrueStatements（条件为真时要执行语句）和FalseStatements（条件为假时要执行的语句）三个子节点。而BinaryExpression类表示二元表达式，却只会包含Left（左操作数）和Right（右操作数）两个子节点。
本文使用的抽象语法树，还实现了一个较为少见却很实用的功能，能够将抽象语法树反向生成相应的C语言源代码。该功能有利于程序对源代码进行修改，即首先通过词法语法分析，建立源代码的抽象语法树。再用程序修改抽象语法树，由于抽象语法树中包含源代码的所有结构信息，因此程序的操作会极为便捷。最后再反向生成相应的C语言源代码，进而实现源代码的修改。
2.4 用户界面的设计和实现
本文基于CParser工具，实现了一个语法树建立与展示的程序，具体如图2所示。点击分析按钮，选择要分析的C语言源代码，就会对源代码进行词法语法分析，建立相应的抽象语法树，并在界面右边显示出来。
界面左边列出了被分析的源文件、包含的头文件以及诊断信息（分析时产生的错误信息），界面右边是相应的抽象语法树。选择一个抽象语法树节点，与其对应的源代码会高亮显示，便于根据抽象语法树找到相应的源代码。图2左侧高亮的if语句块，对应的抽象语法树即如图3所示，每一个椭圆表示一个抽象语法树节点，其中的文字是节点的类型，第二行加粗的文本是该节点附加的属性。
可以看到，抽象语法树中只包括了源代码的抽象结构，源代码的很多不影响程序结构的细节信息（空白、注释、花括号等分隔符）都已移除，而关键信息（如变量名、常量等）则全部保留下来。
if语句的条件表达式，语句块内的fprintf函数和exit函数调用，很容易就能够在抽象语法树中找到相应的节点，关键的变量名称、函数名称等信息也全部保存在节点属性中。将图3所示的抽象语法树显示在界面上，即如图2右边所示，而且同样也是以树状结构来实现可视显示的。
图2 语法树建立与展示程序的界面
Fig.2 Interface of syntax tree build and display program
图3 条件语句的抽象语法树
Fig.3 Abstract syntax tree of condition statement
3 结束语
本文实现了一个C语言词法语法分析工具CParser。该工具首先使用DFA实现Token的匹配，继而完整地实现了预处理过程，最后基于LALR语法分析技术将Token串建立为抽象语法树。
本文成果的优势在于能够完整地支持C99标准，而且无需复杂的配置，使用简单，开发效率高，且只要给出即将分析的源代码，就能够自动建立抽象语法树。本文设计的C语言词法语法分析工具CParser是一种非常实用的轻量级的C语言分析工具，并且对于克隆代码检测、软件错误定位等后续研究工作具有良好的适用性。
参考文献
[1] 梅宏，王千祥，张路等.软件分析技术进展[J].计算机学报，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.
