程序控制流图自动生成的算法

《程序控制流图自动生成的算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、总第244期计算机与数字工程Vo1．38No．22010年第2期Computer&DigitalEngineering28程序控制流图自动生成的算法张雁D林英(西南林学院计算机科学系”昆明650224)(云南大学软件学院昆明650091)摘要运用程序控制流图，可以方便地度量程序的逻辑复杂度，确定软件测试中控制结构独立路径的基本集合。文章提出了根据程序设计的伪码，自动生成程序控制流图的数据结构和详细的算法，为进行控制优化、软件基本路径测试以及程序控制相关性分析提供了良好的基础。关键词程序控制流图；数据结构；PDLToCFG算法中图分类号TP311AutomaticGenerationAlg

2、orithmoftheControlFlowGraphZhangYan’LinYing2(ComputerScienceDepartment，SouthwestForestryUniversity”，Kunming650224)(SchoolofSoftware，YunnanUniversitye’，Kunming650091)AbstractWiththecontrolflowgraph。itiseasytomeasurethecomplexityofthelogicoftheprogram，anddeterminethestructureofsoftwaretestinginthec

3、ontroltestofthebasicsetofindependentpaths．Thispaperproposesthedatastruc—tureandautomaticgenerationalgorithmofcontrolflowgraphaccordingtothePDL．Itprovidesthebasisofconveniencetocontrolforoptimization，softwaretestinginthebasicpathofthetestandtheprogramcontrolrelatedanalysis．KeyWordsprogramcontro1fl

4、owgraph，datastructure，PDLToCFGalgorithmClassN-吖lberTP31]态是指程序中所有变量的值构成的向量(n，az，1引言⋯，a)。有向边表示计算的控制转移，如果结点流图被用于刻划程序的结构，其定义如下l_1]：到结点咒有一条边，则表示只有结点7"／上的计算一个流图是一个有向图G一％NG，EG>，它完成时，计算的控制才从7"／转移到z。由有限多个结点的集合NG={n)和结点间的有向2程序控制流图的生成边的有限集合睡NG×NG构成，它还必须满足如下条件：程序控制流图可以描绘程序的控制流程，在流1)流图中有且只有一个人口结点，它的入度图l2]中，用圆

5、代表结点，一个圆代表一条或多条语为0；句。流图中的箭头线称为边，一条边必须终止于一2)流图中有且只有一个出口结点，它的出度个结点。为0；在程序中遇到复合条件时，如条件语句中的多3)图中任意一个结点都在从流图的人口结点个布尔运算符(逻辑0R、AND)时，为每个条件创到出口结点的一条路径上。建一个独立的结点，包含条件的结点为条件结点，流图中一个结点，z表示程序的一列顺序计算，从每一个条件结点引出两条或多条边。它可抽象地看作是改成程序状态的函数。程序状在算法设计阶段可采用工具PDL来描述程序收稿日期：2009年10月9日，修回日期：2009年11月20日作者简介：张雁，女，副教授，研究方向：软

6、件工程，信息安全。林英，女，讲师，研究方向：软件工程，信息安全。2010年第2期计算机与数字工程的执行流程，下面介绍如何将PDL描述的伪码转E0f(F)：表示伪码F结束；换为流图。GetKW(Line)：表示从line行伪码中获取关键字；CreateNode(Ndata，Ntype)：产生一个结点，编号为2．1PDL描述的伪码Ndata，类型为Ntype；以求平均值过程的PDL伪码l2为例。AddEdge(tailvex，headvex，predicate)：增加一条弧。PROCEDUREaverage；在PDL设计中经常涉及到块结构或嵌套结构，／*这个过程计算100个数中非负数的平均值

7、*／1：i：一1；Tota1．input：一tota1．valid：一0；Sum：一0；所以在算法中应设置一个栈stack，stack中的每一个2：whiletota1．input<100元素是一个结点，该结点的结构如图3所示。3：tota1．input++；臣[4：ifvalue]-i]~0图3stack中结点结构5：thentota1．valid：一tota1．valid+1；sum：一sum其中的关键字为“if”、“then”