（计算机应用技术专业论文）基于程序理解技术的软件复杂性分析技术的研究与应用.pdf

独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：本函丰一日期：上盟旦生亘l 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：叠函垩 导师签名： 摘要 摘要 随着软件规模和复杂性的日益增长，人们对软件的复杂性进行分析和度量 的要求越来越高，因此对软件复杂性分析技术的研究已成为软件工程学中的一 个热点。迄今为止，国内对软件复杂性分析技术的研究尚未成熟，对软件复杂 性的度量和评估的方法也不尽完善，在此基础上，本文提出了基于程序理解技 术的软件复杂性分析技术的研究和应用的课题。 软件复杂性分析技术主要表现在对软件代码进行程序结构分析和关键字识 别，以及在此基础上的软件复杂性分析和度量。其中最关键的问题是如何在分 析代码的过程中，识别并统计可供复杂性度量的数据。针对这一问题，本文提 出了一种基于程序理解技术实现软件复杂性度量的方法。该方法分析和研究了 程序理解技术为软件复杂性度量提供数据方面的问题。在问题研究的基础上， 设计了基于程序理解技术实现软件复杂性度量的模型，并提出了方法研究中要 解决的关键问题以及问题的解决方案，最后本文对该方法的实现给出了相关的 算法。 在对方法进行研究的过程中，本文研究和设计了基于程序控制流的数据遍 历算法、基于抽象语法树的运算符匹配算法和基于抽象语法树的操作数统计算 法，并对抽象语法树所包含的数据信息进行转换、存储、遍历和统计度量。 为了更好的实现本文的研究方法，笔者设计和开发了基于o i n k ( o i n k 是 由k a r lc h e r t 和s c o t tm c p e a k 开发的一款开源的程序理解工具，该工具针对程 序代码进行分析，并应用了多种程序理解技术) 的软件复杂度度量系统，该系 统通过对o i n k 中程序理解技术的运用，实现了度量数据的统计，并在此基础 上完成软件复杂性度量。因此在对该系统设计的过程中对需求分析进行了详细 描述，合理设计了系统的构件图，层次结构模型以及逻辑结构模型，并实现了 系统中复杂性分析的关键算法，数据的采集和存储以及人机交互功能。 为了应用和验证本文提出的基于程序理解技术实现软件复杂性度量的方 法，文章的最后建立了基于o i n k 程序理解平台的软件复杂度度量系统的应用 环境，并详细地设计了应用流程，对随机选取的代码文件进行了复杂度度量测 试。结果分析表明了系统的度量结果和程序复杂性分析结果的一致性，从而证 明了课题研究的方法的合理性和可行性。 关键词程序理解；软件复杂性；复杂度度量；软件维护 北京t q k 大学工学硕士学位论文 a b s t r a c t a b s t r a c t w i t ht h eg r o w i n go ft h es i z ea n dc o m p l e x i t yo fs o t t w a r e ，t h ed e m a n df o r a n a l y z i n ga n dm e a s u r i n gs o t b w a r ec o m p l e x i t yi si m p r o v i n g s o ，t h er e s e a r c ho nt h e s o t t w a r ec o m p l e x i t ya n a l y s i sh a sb e c o m et h ef o c a lp o i n to fs o t t w a r ee n g i n e e r i n g s o f a r , t h ed o m e s t i cs t u d ya b o u tt h ea n a l y s i so fs o t t w a r ec o m p l e x i t yi sn o tm a t u r ey e t , i na d d i t i o n , t h em e a s u r e m e n ta n de v a l u a t i o nm e t h o d so f s o t t w a r ec o m p l e x i t ya l en o t p e r f e c t o nt h i sb a s i s ，t h ep a p e rp r o p o s e st h ep r o g r a ma b o u tt h er e s e a r c ha n d a p p l i c a t i o no ft h es o f t w a r ec o m p l e x i t ya n a l y s i sb a s e do np r o g r a mu n d e r s t a n d i n g t e c h n o l o g y s o t t w a r ec o m p l e x i t ya n a l y s i st e c h n o l o g ym a i n l yr e f l e c t si np r o g r a ms t r u c t u r o a n a l y s i sa n dk e y w o r di d e n t i f i c a t i o no ft h es o t t w a r ec o d e ，a n dt h em e a s u r e m e n ta n d a n a l y s i so ft h es o t t w a r ec o m p l e x i t y t h ek e yp r o b l e mi sh o wt oi d e n t i f ya n dc o u n t t h ed a t af o rt h es o i l - w a r ec o m p l e x i t ym e t r i c sd u r i n gt h ep r o c e s so fc o d ea n a l y s i s t o s o l v et h i sp r o b l e m , t h i sp a p e rp r o p o s e sam e t h o do fc o m p l e t i n gs o t t w a r ec o m p l e x i t y m e t r i c s ，w h i c hi sb a s e do r lt h ep r o g r a mu n d e r s t a n d i n gt e c h n o l o g y t h i sm e t h o d a n a l y z e sa n dr e s e a r c h e st h ep r o b l e m so fp r o v i d i n gd a t af o rs o t t w a r ec o m p l e x i t y m e t r i c sb yp r o g r a mu n d e r s t a n d i n gt e c h n o l o g y , a n db a s e do i lt h ep r o b l e m sr e s e a r c h e d , d e s i g n st h em o d e lo f s o t t w a r ec o m p l e x i t ya n a l y s i st e c h n o l o g yr e a l i z a t i o n t h es t u d y p u tf o r w a r dt h em a i np r o b l e m sa n dt h es o l u t i o nt oi t , a tl a s t , t h i sp a p e rp r o p o s e st h e r e l a t e da l g o r i t h m sf o rt h er e a l i z a t i o no ft h em e t h o d d u r i n gt h ep r o c e s so fs t u d y i n gm e t h o d , t h i sp a p e rr e s e a r c h e sa n dd e s i g n st h e d a t at r a v e r s a la l g o r i t h mb a s e do nt h ep r o g r a mc o n t r o lf l o w , t h eo p e r a t o rm a t c h a l g o r i t h mb a s e do nt h ea b s t r a c ts y n t a xt r e ea n dt h eo p e r a n ds t a t i s t i c sa l g o r i t h mb a s e d o i lt h ea b s t r a c ts y n t a xt r e e b a s e do nt h es t u d ya b o v e ，t h i sm e t h o dc o m p l e t e st h e c o n v e r s i o n , s t o r a g e ，t r a v e r s a la n ds t a t i s t i c a lm e a s u r e m e n to fd a t ai n f o r m a t i o no ft h e a b s t r a c ts y n t a xt r e ea n dt h ep r o g r a mc o n t r o lf l o w i no r d e rt oa c h i e v et h er e s e a r c hm e t h o d sb e t t e ri nt h ep a p e r ，t h ea u t h o rd e s i g n a n di m p l e m e n tt h es o f t w a r ec o m p l e x i t ym e t t l es y s t e mw h i c hi sb a s e do nt h e o i n k ( o i n ki sd e v e l o p e db yk a r lc h e na n ds c o t tm o p e a d , t h i st o o la n a l y z e st h e p r o g r a mc o d e , a n da p p l i e sm a n yk i n d so fp r o g r a mu n d e r s t a n d i n gt e c h n o l o g y ) p r o g r a mu n d e r s t a n d i n gp l a t f o r m t h i ss y s t e mr e a l i z e s t h e m e t r i cd a t as t a t i s t i c s ， b a s e do nt h ea p p l i c a t i o no fp r o g r a mu n d e r s t a n d i n gt e c h n o l o g y ，w h i c hi su s e db y o i n k , a n db a s e do nt h i s ，c o m p l e t e st h es o t t w a r ec o m p l e x i t ym e t r i c 8 d u r i n gt h e - 北京t 业大学工学硕上学位论文 p r o c e s sd e s i g n e d ，t h ea u t h o rg i v e sad e t a i l e dd e s c r i p t i o na b o u tt h es y s t e mn e e d a n a l y s i s ，d e s i g n st h es y s t e mc o m p o n e n td i a g r a m ，h i e r a r c h ym o d e la n dl o g i c a lm o d e l w i mr e a s o n , a n da c c o m p l i s h e st h ek e ya l g o r i t h m so fs o f t w a r ec o m p l e x i t y , d a t a c o l l e c t i o na n ds t o r a g e ，a sw e l la st h eh u m a n - c o m p u t e ri n t e r a c t i o nf u n c t i o n i no r d e rt o a p p l ya n dv e n f yt h em e t h o dt oa c h i e v et h es o f t w a r ec o m p l e x i t y m e t r i c sw h i c hi sb a s e do nt h ep r o g r a mu n d e r s t a n d i n gt e c h n o l o g yp r o p o s e db yt h e p a p e r t h el a s to ft h i sp a p e rs e t su pt h ea p p l i c a t i o nt e s t i n ge n v i r o n m e n td e s i g n st h e a p p l i c a t i o np r o g r a mi nd e t a i l ，a n dm a k e sat e s tf o rm e a s t t r i n gt h ec o d ef i l ew h i c hi s s e l e c t e dr a n d o m l y t h ea n a l y s i sa b o u tt h et e s tr e s u l t ss h o w st h ec o n s i s t e n c yo ft h e s y s t e mt e s t r e s u l t sa n dt h ep r o g r a mc o m p l e x i t ya n a l y s i s r e s u l t s ，p r o v i n gt h e r a t i o n a l i t ya n df e a s i b i l i t yo f t h er e s e a r c h e dm e t h o d k e y w o r d sp r o g r a mu n d e r s t a n d i n g ；s o f t w a r ec o m p l e x i t y ；, c o m p l e x i t ym e t r i c s ； s o f t w a r em a i n t e n a n c 宅 i v 目录 目录 摘要i a b s t r a c t i i i 第l 章绪论1 1 1 选题背景1 1 2 研究现状l 1 3 研究目的2 1 4 主要研究内容3 1 5 论文组织结构4 第2 章程序理解技术及软件复杂性概述5 2 1 程序理解定义5 2 2 程序理解过程分析5 2 3 程序理解相关技术分析6 2 3 1 词法分析：7 2 3 2 语义分析8 2 - 3 3 抽象语法树8 2 3 4 程序控制流程图8 2 3 5 数据流程图1 l 2 4 程序理解存在问题及发展趋势13 2 4 1 程序理解存在的问题1 3 2 4 2 程序理解发展趋势13 2 5 软件复杂性分析与程序理解的关系1 4 2 6 软件复杂性概述1 4 2 6 1 软件复杂性定义1 4 2 6 2 软件复杂性度量的方法1 5 2 6 3 软件复杂性分析的目标15 2 7 本章小节l5 第3 章软件复杂性分析实现的方法的研究1 7 3 1 软件复杂性分析实现方法研究内容l7 3 1 1 软件复杂性分析实现的方法的模型1 7 3 1 2 基于程序控制流的数据遍历算法1 8 3 1 3 基于抽象语法树的运算符匹配算法2 0 3 1 4 基于抽象语法树的操作数统计算法2 2 3 1 5 软件复杂性度量方法的研究2 4 3 2 方法研究中的关键问题2 9 3 2 1 抽象语法树结点的存储问题2 9 3 2 2 抽象语法树的数据信息转化问题3 0 3 2 3 程序控制流结点关系的表示问题3 2 北京工、i k 人学工学顶1 ：学位论文 3 2 4 度量数据的分类及存储问题3 3 3 - 3 基于方法实现的应用模型设计3 4 3 4 基于程序理解技术的工具选择问题3 5 3 5 基于方法研究和实现的技术路线3 6 3 6 软件复杂性分析实现方法的可行性3 6 3 7 本章小节3 7 第4 章基于0 1 n k 的软件复杂性分析方法实现3 9 4 1 基于o i n k 的复杂度度量系统需求分析3 9 4 1 1 分析和研究o i n k 工具结构的需求描述3 9 4 1 2 软件复杂度度量系统的功能需求描述4 0 4 2o i n k 工具的功能结构分析4 4 4 2 1o i n k 程序理解工具概述4 4 4 2 2o i n k 程序理解工具的功能分析4 4 4 2 3o i n k 源代码结构分析4 6 4 3 基于o i n k 的软件复杂度度量系统设计4 7 4 3 1 系统构件图的设计4 7 4 3 2 系统的层次结构模型4 7 4 3 3 系统的逻辑结构模型4 8 4 3 4 复杂度度量操作的序列图一j 5 0 4 4 基于o i n k 的软件复杂性度量方法实现5 0 4 4 1 度量数据搜索算法的实现5 l 4 4 2 度量数据存储的实现5 2 4 4 3 基于o i n k 的l i n ec o u n t 复杂度度量实现算法5 4 4 4 4 基于o i n k 的m c c a b e 复杂度度量实现算法5 5 4 4 5 基于o i n k 的h a l s t e a d 复杂度度量实现算法5 8 4 5 系统的人机交互平台实现6 0 4 6 本章小结6l 第5 章基于o i n k 的软件复杂性分析方法应用6 3 。 5 1 基于w i n d o w s 平台的0 1 n k 环境搭建6 3 5 1 1o 附k 的w i n d o w s 环境平台移植6 3 5 1 2o i n k 在w i n d o w s 环境下的工作机制6 5 。 5 2 软件复杂度度量系统的应用测试6 9 5 2 1 应用测试环境的建立7 0 5 2 2 应用测试流程的设计7 l 5 2 3 应用测试案例的实现7 2 5 3 复杂性分析方法应用解决的问题7 4 5 4 本章小结7 5 结论7 7 参考文献7 9 攻读硕士学位期间发表的学术论文8 3 致谢8 5 i i 第1 章绪论 第1 章绪论 在软件工程领域，软件维护在软件的整个生命周期内占有很大比重，其目 的是在软件交付之后，修改软件的缺陷和提高性能，对软件进行复杂性分析可 以提高软件维护的效率。为提高软件的可维护性本文尝试对软件复杂性分析技 术进行研究。所谓软件复杂性分析是指通过对程序的复杂性进行度量来评估程 序，这样一方面可以降低程序开发时的复杂性，另一方面也降低了程序发生故 障的可能性，从而提高了程序的质量和维护性，因此对软件复杂性分析技术进 行研究具有十分重要的意义。 1 1 选题背景 随着程序理解技术的不断发展，软件复杂性分析技术也随之成为分析和研 究的重点。软件复杂性分析技术能够有效保证软件的开发质量和测试维护质量， 而且软件复杂性分析结果的准确性直接影响软件本身的测试维护工程，特别是 大型软件，例如国防军工航天等软件。随着计算机软件规模逐渐扩大，软件的 复杂性问题越来越突出。近几十年的研究表明，软件复杂性是导致软件错误的 主要原因，当软件复杂性超过某一限度值时，软件中的错误和故障就会急剧上 升，甚至引起软件开发失败。 用于分析和理解程序中的错误和故障的工具相继出现，而且这些工具能够 执行各种测试分析，虽然很多工具分析性能较好，可以生成控制流程图，数据 流图，函数调用图等，但是在国内对软件的复杂性进行有效而全面分析的工具 还是很少，甚至有些工具并没有针对软件复杂性分析的环节。这不能满足当前 一些重要软件系统分析的需要，因此对基于程序理解技术研究软件复杂性分析 技术的研究是非常有意义的。 软件复杂度度量是对软件复杂性的定量分析，是软件复杂性分析和控制的 基础。它从不同的方面反映和评估软件的复杂性，比如程序的控制结构，程序 的长度容量以及程序的物理规模。针对这些不同的方面，分别有如下的度量方 法：l i n ec o u n t 复杂度度量，h a l s t c a d 复杂度度量以及m c c a b e 复杂度度量。 1 2 研究现状 软件的质量保障和维护是软件工程中最为关键的部分，而软件复杂性度量 对于提高软件的质量保障和可维护性十分重要。下面将就国内外对这些技术的 北京t 业大学工学硕士学位论文 研究进行介绍。 就国内而言，目前我国对这种技术的研究还处于起步阶段，研究规模比较 小，参与研究的科技人员也比较少。从技术研究的角度上讲，有些技术还处于 源代码分析的第二阶段，也就是集中式分析阶段。开发人员的分析工作在集成 构建阶段中被取消了，因此隔离了他们与分析工具的关系，这样常会导致不能 及时处理开发人员在程序中引入的错误，降低了程序开发的质量和维护性，从 而影响程序的继续开发。但是，目前国内也有一些比较优秀的工具，比如北京 航空航天大学软件工程研究所开发的s a f e p r oc c + + 。它提供多选窗口单驱动 的用户工作环境，支持若干种测试信息的快速关联分析，能够提供图文并茂的 软件测试结果报告，同时支持静态和动态测试。针对软件复杂性分析，该工具 可支持m o c a b e 复杂度和h a l s t e a d 复杂度度量。总体来看，我国对软件复杂性 分析技术的研究还不成熟。 国外的这种技术的研究已经处于源代码分析技术的第三代，下面将就具有 代表性的工具进行简要介绍：比如k l o c w o r k 公司的源代码分析工具k l o c w o r k i n s i g h t ，它是第一个允许开发人员控制整个分析过程，并且能从集中式分析的 准确性中获益的工具，它能够允许开发人员在他们熟悉的开发环境上进行本地 分析，还可以获得与再集成，验证阶段时做同样分析的一致性和分析精度；除 此之外，还具有代表性的工具是法国t e l e l o g i c 公司的l o g i s c o p e 。它可以评 估软件质量与复杂度；提供代码的直接描述；自动生成软件文档。l o g i s c o p e 提 供了很多方式来可视化文本代码，能够很有效的控制和管理软件复杂度。但是， 国外的研究也存在一定的缺陷，鉴于篇幅限制，这里不进行详细介绍 目前，面向结构化的度量算法能够在一定程度上反映软件开发的复杂程度， 如果能够合理而又稳定地运用这些度量方法去评估软件的复杂度，就会降低软 件发生故障的可能性，并且可以提高软件的可维护性和质量保障。但是，对于 面向对象程序的软件复杂性分析技术还不够成熟，也尚未找到专门分析面向对 象程序的复杂性度量方法，因此对软件复杂性分析技术的研究还需要不断地改 进。 1 3 研究目的 本文的研究对象是软件复杂性分析技术，该技术主要是对软件的复杂性进 行评估和度量，其度量结果从某种程度上可以衡量软件开发的成本和工作量。 软件复杂性分析技术主要通过反映软件开发过程中的复杂性和错误出现率，降 低系统发生故障的可能性来实现提高软件质量和可维护性的目标。本研究从这 一目标出发，提出了基于程序理解技术实现软件复杂性分析技术的方法，旨在 2 第l 章绪论 通过程序理解技术为软件复杂性度量的实现提供必备的数据。在该方法的研究 过程中通过分析程序理解中的相关技术，包括词法分析、语义分析、抽象语法 树以及程序流等技术，设计度量数据的搜集和度量的算法，实现软件复杂性分 析技术的应用。本文在对软件复杂性分析技术的研究过程中要做到对常用软件 复杂度度量算法的实现，并完成对度量数据的采集以及度量结果的存储和报告。 1 4 主要研究内容 本文是对基于程序理解技术的软件复杂性分析技术的研究与应用，旨在通 过程序理解技术实现为软件复杂性分析技术的研究提供必备的度量数据，从而 为度量和评估软件的复杂性提供了可依赖的条件，并能够通过设计一种度量系 统，对本文提出的方法进行应用和验证。其中研究的度量方法主要包括：l i n e c o u n t 复杂度、m c c a b e 复杂度以及h a l s t e a d 复杂度。本研究的主要内容包括以 下几个方面： ( 1 ) 分析和研究程序理解技术及软件复杂性分析基础 。 软件复杂性分析是针对程序源代码来度量程序的结构、长度、规模等方面 的复杂性，因而从某种意义上讲它也属于程序理解的范畴，而且它还是是软件 质量保障和维护工作的一部分。软件复杂性分析技术的实现可以借助程序理解 中的相关技术，例如：对程序的词法分析、语义分析、抽象语法树分析以及程 序流程图的生成等。本文首先从上述几个方面对程序理解技术进行分析和研究， 从而奠定软件复杂性技术研究的技术基础。 ( 2 ) 研究基于程序理解技术的软件复杂性度量方法的设计 基于程序理解技术实现软件复杂性度量的方法旨在解决软件复杂性分析所 依赖的度量数据问题，常规的解决方法是通过分析程序结构和关键字识别来搜 集度量数据。本文提出的方法则是通过程序理解技术来完成度量数据的统计工 作，从而为软件复杂性度量任务提供了便利。该方法的研究工作从研究基础和 研究思路着手，并在此基础上设计方法实现的模型和算法。最后对该方法的实 现做可行性分析。 ( 3 ) 基于程序理解技术的软件复杂性度量方法的实现 对于方法的实现应该在其设计的基础上实现其中的关键算法，并能够通过 设计和开发一款度量系统来体现和运用这种方法，因此本文设计和实现基于 o i n k 程序理解工具的软件复杂度度量系统。该系统通过运用程序理解技术分 析程序代码并结合设计和实现的算法完成度量数据的统计，然后由系统的度量 计算模块完成软件复杂度的度量。 ( 4 ) 基于程序理解技术的软件复杂性度量方法的应用和验证 3 北京工业大学工学硕上学位论文 对于本文实现的方法的应用和验证旨在通过实际的应用测试来验证方法的 合理性和可行性，本文则是通过对设计的系统进行应用测试来完成这一工作， 主要包括：应用环境的搭建、应用测试流程的设计和实行以及对应用测试结果 的分析和验证。 1 5 论文组织结构 第1 章绪论：主要介绍了研究的选题背景，国内外研究现状，以及该论文 的研究目的和主要研究内容，最后确立了文章的组织结构。 第2 章重点对程序理解技术及软件复杂性进行概述。主要包括程序理解的 定义及程序理解过程所采用的技术和方法，在此基础上研究与软件复杂性分析 相关的程序理解技术。除此之外，还对目前程序理解存在的问题及发展趋势进 行分析和预测。在对软件复杂性分析与程序理解的关系进行阐述之后，本部分 还提出了软件复杂性的定义以及复杂性度量常用的度量算法。 第3 章本章主要研究基于程序理解技术实现软件复杂性分析的方法，从以 下几个方面进行研究，包括：该方法研究的主要内容、拟解决的关键问题及解 决方案、方法的研究思路以及方法的可行性分析。 第4 章为完成实现软件复杂性分析的方法，本文对基于o i n k 的软件复杂 度度量系统进行设计，包括对它进行需求分析、系统结构设计。此外，在该系 统中实现本文研究的方法的算法。在此基础上完成了系统的数据采集的与存储 以及人机交互平台的开发。 第5 章为了对设计的系统以及该系统中实现的软件复杂性分析方法进行 应用和验证，本章对该系统进行应用测试，包括测试环境的建立、测试流程的 设计以及具体应用测试的实现，最后对实验的数据进行研究和对比，分析了软 件复杂性分析方法的实现所解决的问题。 4 第2 章程序理解技术及软件复杂性概述 第2 章程序理解技术及软件复杂性概述 程序理解是软件工程学中日益受到关注的一个领域，是软件维护中必不可 少的重要环节。在计算机软件兴起后，程序证明、程序维护和人工智能也逐渐 得到发展，此时人们开始涉足程序理解这一领域。通俗的讲，程序理解是通过 一定的设施和方法来分析一个程序的功能，以及如何实现这些功能的范畴。它 的核心问题并不是改变目标程序，而是对目标程序进行检查。通过对程序理解 的研究可以提高软件的可维护性，因此程序理解对软件维护有很重要的作用， 为了更好的进行软件维护，就要为程序理解提供合适的方法和设施。 2 1 程序理解定义 随着社会对软件需求的不断增长，软件开发和使用量与日俱增，市场上已经 存在许多规模较大，系统较复杂的软件，因此软件维护已成为当前软件产业面 临的重要课题。软件维护是分析、理解、修改、重新确认软件的过程。程序理 解是维护工作的第一步，能否准确、迅速、全面地理解程序是决定维护工作成败 的关键。在对软件进行维护的过程中，软件逆向工程已经成为关键的技术之一。 软件的逆向工程主要包括系统理解、程序理解和文档恢复三个阶段，程序 理解是软件的逆向工程过程中的数据分析阶段，它的数据输入源是程序的源代 码，从源代码上分析程序的抽象信息。因此，程序理解的实现是通过在不同的 抽象级别上建立基本软件的概念模型，包括从程序代码本身到基本应用领域的 模型。 从软件工程的角度上讲，程序理解是软件工程领域里的一个重要部分，软 件工程十分关心如何提高软件开发过程的生产效率和软件产品质量，而程序理 解恰恰是一个从计算机程序中获取知识信息的过程，这些知识信息可以用于程 序排错、增强程序、重用程序以及整理文档等方面，从而为软件维护提供了条 件。 2 2 程序理解过程分析 对于一个程序的理解，可以通过识别和标记代码中的程序片段，在对程序 片段功能的理解基础上建立该程序的抽象层次描述。把这样实现的过程称之为 程序理解过程。程序理解的主要任务是要反映程序的具体功能以及功能的实现 机制。它的任务具体表现在手工代码阅读、程序分析、静态分析、动态分析、 5 北京工业大学工学硕上学位论文 程序流分析、检查程序构造过程的结构关系及识别程序单位和综合程序逻辑。 程序理解过程可分为三个阶段：分析源程序，规范化处理和分析结果【5 1 。 在分析源程序阶段中，将输入的源程序转化为具有程序流信息的中间表示形式； 然后在规范化处理阶段对中间表示形式采用变换法则，进行规范化处理，从而 达到降低理解复杂度的目的；在分析处理结果阶段中的主要任务是识别程序中 包含的语义和知识信息，分析和推理程序开发者的目的。程序理解过程的三个 阶段分别对应着程序理解模型中的三个规范活动：数据收集、知识组织和信息 浏览，其对应关系如图2 1 所示： 程序理解过程三个阶段程序理解模型三个规范活动 图2 1 过程与活动对应关系 f i g u r e2 - 1c o r r e s p o n d i n gr e l a t i o n s h i pb e 4 3 v e 宅nt h ep r o c e s sa n da c t i v i t i e s 在程序理解过程中，可以采用很多理解程序的方式，具体如下：比较传统 的方式，如手工浏览代码、自动化分析方式、静态或动态分析目标系统等。通 过这些方式可以收集和分析系统的可度量数据。其实，贯穿程序理解的过程可 以理解为：其过程是通过在程序源代码中收集大量的原始数据，并提取有效信 息，从而可以构造和浏览程序的高层抽象。 2 3 程序理解相关技术分析 程序理解的任务是建立从问题领域到程序设计领域的映射集，目的是为了 能够便于软件维护，进展和再工程。近几十年国内外的专家对程序理解的方法 进行研究，其主要的技术包括：词法分析、语法分析和程序流分析等技术，同 时从程序设计语言的角度上讲，对程序进行理解的任务包括单个的程序设计结 构，程序被典型地表示成抽象语法树，符号表或普通源文本。关于对源代码进 6 第2 章程序理解技术及软件复杂性概述 行理解和分析的技术流程如图2 - 2 所示： 2 3 1 词法分析 图2 - 2 源代码分析技术流程 f i g u r e2 - 2s o u r cc o d ea n a l y s i st e c h n o l o g yf l o w 词法分析是指把输入的源程序理解为特定语言允许的基本字符流 9 1 ，将代 码转换为一系列的记号，并沿途过滤掉空白或注释，这种记号流的创建过程称 为词法分析。词法规则常通过使用正则表达式来识别记号。 词法分析的基本原理是对逐个读入的源程序的符号，摒弃掉空白和注释， 并根据语言的定义规则，识别出对语言有意义的符号，标记为单词符号，并在 此基础上分析单词符号的属性，把单词符号及其属性填写在符号表中，同时为 了后续能够生成有用的错误报告，在符号表中标记该符号在源代码文本中的位 置【1 2 】。符号表记录了程序中所有单词符号的信息，包括名称、各种属性、所表示 的值、作用域、分配的内存单元数等。当词法分析器识别了一个单词的时候， 第一项工作就是查询符号表。 词法分析在编译结构中，通常作为子例程被语法分析程序调用，每一次调 用返回一个单词，词法分析程序的实现有两种不同的方法：手工编写和机器自 动生成【1 3 】。使用状态转换图是设计词法分析程序的一个好途径。 词法分析是编译过程的第一个阶段，是编译的基础。不同的程序语言有不 同的规则和定义，要根据语言的特点进行词法分析程序的设计。词法分析中的 符号表是一个相当重要的部分，其主要操作包括：填表，查询和更新。 7 北京工业大学t 学硕七学位论文 2 3 2 语义分析 当静态分析工具生成抽象语法树时，同时生成一张符号表，符号表将程序 中的每个标示符与它的类型、声明或定义的指针相关联。抽象语法树和符号表 是执行类型检查的准备条件。一般而言，静态分析工具不会像编译器那样执行 类型检查，但是对于面向对象程序来说，对象的类型至关重要，因为对象的类 型决定着该对象可以操作的成员和方法，因此静态分析工具不得不执行类型检 查。由于编译器会给程序中发现的这些符号赋予一定的含义，符号分析和类型 检查在编译器的领域就被称之为语义分析。完成语义分析之后静态分析和编译 器就区别开来，静态分析会根据自身的需要对抽象语法树执行其它的转换操作， 而编译器则将抽象语法树和符号以及类型信息直接生成一种中间的表示方法。 2 3 3 抽象语法树 从概念角度上讲，语法树是语法结构的图形表示。我们可以根据语法树来 判断一个给定的单词符号是否符合语言的语法规则，因而基于一棵语法树进行 分析是可行的。由于多种原因，在语法树的基础上执行复杂性的分析会有些困 难。这种树中的节点是直接从语法的产生式规则派生而来的，而这些规则引入 一些非终点符号，这种符号的存在只是为了使解析易于进行并且没有歧义，而 不是为了产生更易理解的树。因而，为了进行这种分析，较好的做法是在程序 文本中提取走语法中的细节和句法中的修饰成分。完成这项工作的数据结构称 作抽象语法树。 抽象语法树的叶子结点代表的是非保留字终结符，而中间结点则表示语法 结构。抽象语法树的结点中还可以表示语义关系的连接，比如定义使用链、类型 信息以及符号表。从而，抽象语法树可以包含编译器前端从源代码获取的相关 信息，并且能够表示源程序的语法结构。 抽象语法树是编译器前端的最基本的输出。抽象语法树结点的生成是在词 法分析、语法分析和语义分析的基础上完成的。词法分析为抽象语法树提供了 所必需的符号结点，如常量和名字。语法分析则为抽象语法树提供了含有代表相 应语法结构的中间结点。最后，语义分析经过对名字和操作符的处理，将语法树 转变为一种包括表示类型信息和符号表的标准形式，并将它们连接成树形结构。 2 3 4 程序控制流程图 当函数执行时，许多静态分析算法会探究其可能采取的执行路径，因此大 第2 荦程_ | 予理解技术及软件复杂性概述 多数工具会在抽象语法树或中间表示法上生成一个控制流图。控制流图中的结 点都是一些基本快，指令序列从第一个结点开始顺序连续执行到最后一条指令， 任何指令都不可能跳过。控制流图中的指向代表着基本快之间潜在的控制流路 径，而返回指向则代表着潜在的循环。程序控制流程图表示一个过程内所有基 本块执行的可能流向和被定义为可以连续执行的最大单位或对程序控制的最小 单位，它的特点包括单入口、单出口和中间，没有分支。程序控制流程图可以 显示一个过程内各基本块之间的相互关系、动态执行状态、各基本块对应的语 句表。此外，还有其他辅助信息，如各基本块执行次数、执行时间等。 例如，以下为一个程序片段 i n tm a i n 0 i n tc o u n t ： i n ta ： s c a n f ( “d ，a ) ： i f ( a o ) c o u n t = l ： e l s e c o u n t = 一1 ： r e t u r nc o u n t ： ) 它的程序流程图如图2 3 所示： 9 北京下业大学t 学硕十学位论文 第2 章程序理解技术及软件复杂性概述 图2 - 4 程序控制流程图 f i g u r e2 - 4p r o g r a mc o n t r o lf l o wc h a r t 分析程序的控制结构是对程序进行理解的首要任务，程序的控制结构主要是 指语句可能执行的路径。在此过程中可以通过控制流分析来建立过程内部的控制 层次。从分析的方式上可将控制流分析分为两种：一种是必经点分析方法，另一 种是区间分析方法。这两种方法的相同之处是首先分析程序文本，并将其转化为 某种中间表示，只是基于中间表示而进行的分析方法不同，具体使用哪种方法由 程序理解的任务决定。 2 3 5 数据流程图 数据流分析主要是指对被分析程序在生成数据方面进行计算的行为，它