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语言词法语法分析工具。但是,这些方法或多或少都存在一些缺陷。具体分析如下。……
