宋倩 张峰

（山东科技大学计算机科学与工程学院 青岛 266590）

1 引言

在软件项目的开发过程中，程序流程图（简称为流程图，Flow Process Chart）是软件开发过程中不可或缺的工具。在复杂的程序设计过程中，通常需要先通过流程图来描述算法思路，然后再依据流程图编写出相应的程序代码。此外，在代码分析中，流程图可清晰地展示出程序的结构，用它来辅助分析程序结构远远方便于直接分析源程序本身［1］。因此，为了方便理解，经常需要把源码转换成流程图。现有的一些方法和工具可以把程序源码直接转化成流程图［2］，但是它们得到的流程图都跟源代码紧密相关。由于使用的编程语言或代码功能的实现方式不同，相同流程的代码得到的流程图结构也会不同，这样不便于用户的理解和使用。

针对上述问题，本文提出了一种程序源代码的标准化流程图转化方法，参照ISO 5807：1985标准，对流程图的节点类型和边类型进行了定义，给出了程序流程的三种基本结构：顺序、循环和分支的标准结构；给出了基于特定语言代码的流程图转换为标准化流程图的方法，节点以及结构标准化后生成对应的标准流程图；在转换过程中，为了应对代码冗余等问题，将相邻的无逻辑关系的节点合并，根据标准化的流程图进一步生成主流程图。最后，通过实例具体说明该方法的转化规则。

2 相关工作

从已有的研究工作来看，现有的将程序源代码转换为流程图的工具和方法主要有以下几种。

1）直接分析源代码，生成流程图

AutoFlowchart［3］主要用于对已有的程序进行分析，并为制作项目文档做准备。它生成的流程图支持展开或合拢，缩放和移动，并且可以预设流程图的长宽和纵向横向间距。可以将流程图导出到WORD文档或BMP图像文件中。它支持C，C++，VC++（Visual C++.NET），Delphi（Object Pascal）等语言。

Code Visual to Flowchart［3］可以用于迅速地分析源代码并且在流程图窗口当中显示当前被编辑的代码的图形化描述。它是由一个代码编辑器和一个流程图窗口组成并且支持多种编程语言，诸如C/C++，Java/JavaScript，VB/BASIC/ASP，Delphi/Pas⁃cal，PHP，Power Builder，Perl以及其它语言。

SourceCode to flowchart［3］，一个代码维护与管理软件，它能够快速地分析源代码，并在流程图窗口中显示出目前代码的图示。它具有一个代码编辑器和一个流程图窗口。流程图的引擎很快，同时还可以以多种形式输出流程图。

Visustin［4］，一个支持 42 种编程语言的流程图制作软件。Visustin支持的语言有ABAP，Action⁃Script，Ada，ASP，assembler，BASIC，Batch files，C，C++，C#，Java，Python等。生成的流程图详细，功能很全面，可以对图进行编辑，不足之处是不能向外保存。

2）生成流程图并拓展其他代码分析功能

EasyStructure［3］，从 C 来源自动地生成流程图和资源结构树。EasyStructure从它的分析和结果字符理解源代码。树形浏览以一个可以通过它的结构以及它的原始资源随意地进行浏览、组织的形式来显示资源。可以使用树节点来找到包含的各种不同类型的声明。

Crystal Flow for C［3］，获得一个带有流程图的清晰代码，可以用来校验逻辑功能的正确性，检测错误。导出的流程图为BMP或者JPG格式文件以及用于VISIO的XML文件。它提供代码和注释的自动格式化功能，为功能调用定制相应的形状。利用它可以把自己或别人写的代码格式化，并可以生成直观的流程图、交叉调用图、直观的注释等。

总的来说，通过分析源代码生成流程图的工具和方法，其生成的流程图都跟程序源码紧密相关，即使是相同流程的代码，换一种编程语言或实现方式，对应生成的流程图结构就会不同，对于利用流程图来理解程序的逻辑结构的用户来说是不适用的。

3 程序源代码的标准化流程图转化方法

本文提出的程序源代码的标准化流程图转化方法，在应对由于编程语言或实现方式的不同而导致流程图结构不同的问题方面，对节点类型和结构类型分别制定了统一的转化标准；在标准流程图定义的基础上，给出了标准流程图的映射方法，实现将基于特定语言的流程图转换为标准流程图的方法。在标准化过程中，为了应对代码冗余的问题，将相邻的无逻辑关系的节点合并，借鉴传统的程序依赖图（Program Dependency Graph，PDG）［5-6］的构造思路，生成不包括冗余代码的程序主流程图。最后，为了验证效果，通过实例具体说明该方法的转化规则。

3.1 标准流程图定义

流程图包括算法流程图、数据流程图、程序流程图、系统流程图等。本文提出的标准流程图属于程序流程图，主要用于表示程序中的操作顺序，包括表示实际处理操作的处理符号、根据逻辑条件确定要执行路径的判断符号、表示控制流的流线符号，以及注释符［7～9］。ISO 5807：1985标准中规定了25种流程图符号，包括基本符号和特定符号［10～12］。为了实现流程图的标准化，本文从节点类型、结构类型这两方面进行标准流程图的定义。

3.1.1 节点类型

程序代码经过转换，变成流程图中的节点和边。在标准化流程图的节点、边的基础上，结合流程图结构，本文给出的标准流程图中的节点类型如表1所示。

表1中给出的节点类型分为三类：顺序节点、循环分支节点和组合节点。为了使冗余的代码不对整个流程图结构造成影响，通常会将相邻无逻辑关系的节点合并，即生成组合节点（combine节点），以实现相同流程但不同源码的流程图的标准化。

在根据代码得到的程序流程图中，为了去除冗余的节点，需要将无逻辑关系节点合并。基本思路是：如果两个节点是相邻的，判断两个节点之间是否有逻辑关系，即数据依赖关系和控制依赖关系。若无逻辑关系，则将两个相邻的节点合并在一起。例如图1，a=1和b=1两个相邻节点一一映射后是同一种节点类型，而且两者无任何逻辑关系，因此可以合并成一个“assign”节点；同样将两个节点的顺序交换，也可以合并成一个。

图1 合并同种类型无逻辑关系节点

对于无逻辑关系的不同类型的节点，如图2，int b和a=1两个相邻节点一一映射后是不同的节点类型，两者无任何逻辑关系，因此可以合并成一个“combine”节点。

图2 合并不同类型无逻辑关系节点

3.1.2 结构类型

流程图的基本结构包括：顺序结构、循环结构、分支结构，任何复杂的逻辑都可以通过这三种基本的程序结构来实现［13］。因此，为了实现流程图的标准化，本文给出了标准化流程图中的标准结构类型。

顺序结构是最常用的流程图结构［14］。顺序结构中连接两个节点的边称为顺序执行边（Sequen⁃tial Execution Edge，SEE）。本文给出如下定义。

定义1（顺序执行边）如果存在变量var，从节点v1到v2有边满足：变量var在v1处定义、在v2处引用或存在一条从v1到v2的路径，该路径表示代码执行的顺序。

标准流程图中定义的顺序结构样式如图3所示。

图3 标准化的顺序结构

循环或分支结构中连接loop或control类型的节点到下一节点的边称为控制依赖边（Control De⁃pendency Edge，CDE），给出如下定义。

定义2（控制依赖边）对于loop或control类型节点v1，如果v1条件的取值控制节点v2的执行，则存在从loop或control节点到下一节点的边，称为控制依赖边。

程序中的循环结构，如for循环、while循环、do-while循环，在一定程度上均可实现相同的功能［15］，但是利用现有的工具和方法生成的流程图样式却不相同，不便于用户的理解和使用。为此，本文给出了loop的标准化结构，如图4所示，其中有“yes”和“no”标识的两条边是CDE。

图4 标准化的循环结构

分支结构的执行是依据一定的条件选择执行路径，而不是严格按照语句出现的顺序。四种基本的分支结构包括：if结构、if...else结构、if...else if结构、switch...case结构［16］。图5给出了这四种基本结构对应的control标准化结构。

图5 标准化的分支结构

3.2 特定语言流程图的标准流程图转换方法

将基于特定程序语言生成的流程图转换成标准流程图时，需要将基于特定程序语言的流程图中的节点、边和结构对照标准流程图定义进行转换。

由于在编程过程中代码可能存在没有使用到的变量，这种冗余会使流程图的可读性降低［17～18］。以图6中的代码为例，本文给定一段求和代码，其中包含了部分冗余代码，图6是代码段对应生成的程序依赖关系图。为了应对这些代码冗余的问题，结合传统的程序依赖图［5～6］，需要进一步生成主流程图，从而去除冗余的节点。

3.2.1 节点和边的标准化

定义（映射）两个非空集合A与B间存在着对应关系f，而且对于A中的每一个元素x，B中总有唯一的一个元素y与它对应，这种对应为从A到B的映射，记作 f：A→B［11］。

将程序代码转换成流程图并不需要体现具体的代码语句，因此需要将节点和边一一映射转换为标准流程图中的节点和边。将程序代码转换成对应的流程图，参照3.1.1每个节点内的文本给出其节点类型。边根据类型定义3.1.2相应转换成顺序执行边和控制依赖边。

3.2.2 结构的标准化

对于两段代码，如果它们使用了不同类型的循环结构或者相同循环结构的不同形式，则流程图中的循环结构也可能不同［19］。例如有的循环结构在生成的流程图中只体现判断条件语句的节点，初始化语句和控制条件语句自动省略，而有的循环则一句对应生成一个节点，需要将不同类型或相同结构不同形式的循环结构转变为标准结构。这时标准流程图代表判断条件语句的节点统一映射为loop类型，按照3.1.2循环结构标准化转化规则，将按照程序源码生成的流程图中代表初始化语句和控制条件语句的两个节点删除，如图7。

图7 循环结构标准化过程

同样的，分支结构中if结构、if...else结构、if...else if结构、switch...case结构，无论条件的多少，都统一转换成3.1.2分支结构的标准化形式。

3.2.3 主流程图的生成

结合传统的PDG，把输出程序结果的语句转换成流程图节点时进行输出标记，在程序流程图生成以后，从流程图中的输出节点开始深度遍历图，进而得到一个最大连通图，不在最大连通图的图节点将被删除掉，最终得到的程序流程图称为主流程图。

图8展示了图6中求和代码的程序依赖关系图转换成其对应的主数据流图的生成结果。

图8 生成的主数据流图

主数据流图对应的代码段如下，此时的代码段去除了冗余代码，最终生成的主流程图见图9。

图9 最终的主流程图

3.3 实例

下面通过一个实例说明特定语言流程图转换为标准流程图的方法。用Java实现求n的阶乘这一算法，分别用的是while和for循环结构，源代码和利用现有工具生成的流程图样式见表2。

表2 求n的阶乘代码和对应的流程图

在两者生成的流程图中可以看出，for循环中5节点的控制语句只体现了i＜=n这一句，i=1和i++这两句自动省略了，而while循环中由于这三句是分开写的，所以都体现了出来，且一句代表一个节点。因此循环结构标准化时，将while循环结构的流程图代表i=1和i++这两个语句的节点删除，边集e根据删除的两个节点和依赖关系进行相应的改变，这就是流程图的结构标准化。

表3是用标准化后的循环结构求n的阶乘的流程图和进行节点和边一一映射后的流程图样式。

表3 原流程图和映射后流程图

4 结语

本文提出了一种从源程序代码到其流程图的标准转化方法，在标准流程图定义的基础上，给出了标准流程图的映射方法，并通过实例具体说明该方法的转化规则。

本文研究的方法还有后续可以继续完善的地方，下一步将从以下几个方面进行深入研究。

第一，由于标准化后的流程图节点不受具体代码语句或使用的编程语言的约束，因此可以考虑继续深入研究基于流程图的跨程序语言代码相似度的检测。

第二，方法对于检测控制结构级的代码冗余和错误还有上升空间，可以继续优化流程图的标准转换。

第三，对于将程序源代码转化成流程图的工作，有的实验系统现在还只是提供了对应的接口，用于集成到其他系统中，后续工作可以将系统实现为一个有友好用户界面的工具，既可以单独使用也可以提供服务集成其他软件使用［20］。