没有合适的资源?快使用搜索试试~ 我知道了~
编程语言-C语言代码分析与函数时间复杂度计算的研究.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 81 浏览量
2022-06-24
16:00:13
上传
评论
收藏 965KB PDF 举报
温馨提示
试读
56页
编程语言-C语言代码分析与函数时间复杂度计算的研究.pdf
资源推荐
资源详情
资源评论
ABSTRACT
The existing C language compiler or code analysis software are mostly
concentrated in testing the correctness of the encoding process and the accuracy of the
structure of C program code , but the automatically testing of the information
contained in the code, such as keywords information and time efficiency level of
determination has not been implemented.
Through static analysis process, this paper analyzed the lexical and grammatical
form of the C language code under ANSI C standard, accomplished the resolving and
storage of information of C language program in XML tree storage structure, then
designed, implemented, and verified the algorithm model of the time complexity
calculated automatically.
The experimental results show that the keywords information in the C program
code can be extracted and summarized well, meanwhile, the time efficiency of C
program depends greatly on the time complexity of the intrinsic functions. The higher
the overall time complexity of functions, the less run-time efficiency. Compared to
the traditional method of C language analysis, this algorithm focuses more on
analyzing and calculating the time complexity of C language, which can judge the
time efficiency quickly and accurately.
This research may help the C developer to analyze the C language program more
simplicity, more conveniently, more directly. The C program can be analyzed before
running, so that developer can make pre-correcting, which means the workload of
reading the code and the learning costs will be greatly reduced, and focus on other
more important work.
KEY WORDS:Tree Structure, C Code Analysis, Calculating The Complexity, XML
目 录
第一章 绪论 .................................................................................................................. 1
1.1 自动化代码分析的发展概况 .......................................................................... 1
1.2 C 代码静态分析的国内外研究现状 ............................................................... 3
1.3 C 代码分析研究的意义和应用前景 ............................................................... 4
1.4 本文的研究内容及结构安排 .......................................................................... 4
第二章 相关理论及技术介绍 ...................................................................................... 6
2.1 词法分析与 Lex 简介 ...................................................................................... 6
2.2 语法分析与 Yacc 简介 .................................................................................... 7
2.3 Windows 平台下的 Parser Generator ............................................................... 8
2.4 XML 树状结构存储方式简述 ......................................................................... 8
2.5 TinyXML 简介 ................................................................................................ 10
2.6 JNI 简介 .......................................................................................................... 11
2.7 本章小结 ........................................................................................................ 11
第三章 相关功能及算法的分析与设计 .................................................................... 12
3.1 C 程序代码的结构 ......................................................................................... 13
3.2 代码解析的分析设计 .................................................................................... 14
3.2.1 代码的词法分析 .................................................................................. 15
3.2.2 代码的语法分析 .................................................................................. 16
3.3 信息存储的分析设计 .................................................................................... 17
3.4 时间复杂度计算算法的分析设计 ................................................................ 18
3.5 显示功能的分析设计 .................................................................................... 22
3.6 整体结构的整合 ............................................................................................ 23
3.7 本章小结 ........................................................................................................ 25
第四章 C 代码分析平台的实现 ................................................................................ 26
4.1 代码分析功能的实现 .................................................................................... 26
4.1.1 C 代码分析综述 ................................................................................... 26
4.1.2 Lex&Yacc 文件的编写 ......................................................................... 26
4.1.3 Lex&Yacc 整合 ..................................................................................... 32
4.2 XML 文件信息存储的实现 ........................................................................... 32
4.3 时间复杂度自动化计算的实现 .................................................................... 34
4.3.1 符号说明 .............................................................................................. 34
4.3.2 算法实现 .............................................................................................. 34
4.3.3 算法补充说明 ...................................................................................... 36
4.4 前台可视化显示的实现 ................................................................................ 36
4.5 本章小结 ........................................................................................................ 40
第五章 实验验证及数据分析 .................................................................................... 41
5.1 实验设计原理 ................................................................................................ 41
5.2 复杂度计算算法准确性实验 ........................................................................ 41
5.3 算法应用实验 ................................................................................................ 45
5.4 信息提取统计实验 ........................................................................................ 47
5.5 本章小结 ........................................................................................................ 49
第六章 总结与展望 .................................................................................................... 50
6.1 总结 ................................................................................................................ 50
6.2 展望 ................................................................................................................ 51
参考文献 ...................................................................................................................... 52
发表论文和参加科研情况说明 .................................................................................. 55
致 谢 ...................................................................................................................... 56
第一章 绪论
1
第一章 绪论
在现代计算机应用与软件开发的发展过程中,C 语言无疑扮演了一个很重要
的角色。作为一种通用的、过程式的编程语言,C 语言广泛用于各种应用软件与
系统的开发。它具有高效、灵活、功能丰富、表达力强和较高的可移植性等特点,
在程序员中备受青睐,是使用最广泛的编程语言
[1]
。
随着信息化和计算机技术在各专业领域的广泛应用,基础而又通用的 C 语
言编程技术已经成为广大现代化专业人才的必备技能,对于 C 语言的学习则是
其必须经历的阶段。而阅读和分析已开发完成的 C 语言程序则是一种便捷高效
的学习方式。
同时,在软件开发和应用中,也需要对所编写 C 程序在运行效率、内部结
构优良性等各个方面进行实时判定与横向比较。在此过程中就需要对相关 C 程
序进行专业化地分析和计算。
基于以上的现实需求,本文进行 C 语言程序相关的分析研究方向的讨论。C
语言分析与检验的算法研究与实现可以更好地搭建利于开发者和学习者进行阅
读和分析代码的平台,其技术性、理论性、可研究性和现实意义都是非常有潜力
的。
1.1 自动化代码分析的发展概况
自动化代码分析
[2]
可分成两大类基本类型:静态分析和动态分析。静态类型
的分析器检查源代码或者目标代码,不需要真正执行代码。动态类型则需要运行
代码,在运行过程中检查代码效果。本文的研究方向是基于静态代码分析现有技
术之上进行的。
程序静态分析(Program Static Analysis)是指在不运行代码的方式下,通过
词法分析、语法分析、控制流、数据流分析等技术对程序代码进行扫描,验证代
码是否满足规范性、安全性、可靠性、可维护性等指标的一种代码分析技术
[3]
。
它可以帮助软件开发人员、质量保证人员查找代码中存在的结构性错误、安全漏
洞等问题,从而保证软件的整体质量。还可以用于帮助软件开发人员快速理解文
档残缺的大规模软件系统以及系统业务逻辑抽取等系统文档化等领域。 如开发
20 年以上的金融核心 COBOL 系统,动辄上千万行代码的系统规模。对于理解
这样规模的系统,基于程序静态分析
[4]
的辅助理解工具就能发挥积极作用。
第一章 绪论
2
程序静态分析是与程序动态分析相对应的代码分析技术,它通过对代码的自
动扫描发现隐含的程序问题,主要具有以下特点:
1、不实际执行程序。动态分析是通过在真实或模拟环境中执行程序进行分
析的方法,多用于性能测试、功能测试、内存泄漏测试等方面。与之相反,静态
分析不运行代码只是通过对代码的静态扫描对程序进行分析。
2、执行速度快、效率高。目前成熟的代码静态分析工具每秒可扫描上万行
代码,相对于动态分析,具有检测速度快、效率高的特点。
3、误报率较高。代码静态分析是通过对程序扫描找到匹配某种规则模式的
代码从而发现代码中存在的问题,例如可以定位 strcpy()这样可能存在漏洞的函
数,这样有时会造成将一些正确代码定位为缺陷的问题,因此静态分析有时存在
误报率较高的缺陷,可结合动态分析方法进行修正。
常用的静态分析技术如下:
1、词法分析
[4]
:从左至右一个字符一个字符的读入源程序,对构成源程序
的字符流进行扫描,通过使用正则表达式匹配方法将源代码转换为等价的符号
(Token) 流,生成相关符号列表,Lex 为常用词法分析工具。
2、语法分析
[4]
:判断源程序结构上是否正确,通过使用上下文无关语法将
相关符号整理为语法树, Yacc 为常用工具。
3、抽象语法树分析:将程序组织成树形结构,树中相关节点代表了程序中
的相关代码,目前已有 Javacc/ Antlra 等抽象语法树生成工具。
4、语义分析:对结构上正确的源程序进行上下文有关性质的审查。
5、控制流分析:生成有向控制流图,用节点表示基本代码块,节点间的有
向边代表控制流路径,反向边表示可能存在的循环;还可生成函数调用关系图,
表示函数间的嵌套关系。
6、数据流分析:对控制流图进行遍历,记录变量的初始化点和引用点,保
存相切片关数据信息。
7、污点分析:基于数据流图判断源代码中哪些变量可能受到攻击,是验证
程序输入、识别代码表达缺陷的关键。
8、无效代码分析,根据控制流图可分析孤立的节点部分为无效代码。
现有的 C 语言程序代码分析工具基本上均为以上技术的应用。其实对于静
态分析代码而言,分析出普遍的编程错误和编码规则
[3]
或风格的违反,相对 Lint
时代已经有了长足的进步。IDE 的内建分析器、第三方工具和插件让我们可以在
开发过程中发现和定位并修改大量的这些错误。与此同时,这个世界变得更加互
联互通、更加复杂、也更加危险。面对新的潜在错误和威胁,今天运行着的代码
分析软件必须变得更加健壮和强大。
剩余55页未读,继续阅读
资源评论
programhh
- 粉丝: 8
- 资源: 3838
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 1040g0cg310ravpiu6ibg5pg00tsipsln3ju2d0g 2
- 基于Python的SAR图像去噪CNN-NLM设计源码
- redhat6升级到redhat7,过程redhat6.x-> redhat6.10->rehat7.9 主版本最高版本
- 基于Django的流程引擎设计源码
- 基于Node.js的Express框架与MySQL的后台管理系统设计源码
- 基于Java的Flink流批一体数据处理快速集成开发框架设计源码
- FirstFilterOrderCompare
- Screenshot_2024-03-28-19-17-25-020_com.ss.android.lark.jpg
- 基于Java的车辆违章信息查询系统设计源码
- wqeAFSDADWDAESD
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功