程序结构分析之控制流分析

控制流分析

由于非结构化程序会给测试、排错和程序的维护带来许多不必要的困难，人们有理由要求写出的程序是结构良好的。70年代以来，结构化程序的概念逐渐为人们普遍接受。体现这一要求对于若干新的语言，如Pascal、C等并不困难，因为它们都具有反映基本控制结构的相应控制语句。但对于早期开发的语言来说，要作到这一点，程序编写人员需要特别注意，不应忽视程序结构化的要求。使用汇编语言编写程序，要注意这个问题的道理就更为明显了。

正是由于这个原因，系统地检查程序的控制结构成为十分有意义的工作。

1、控制流图

程序流程图（flowchart）又称框图，也许是人们最熟悉，也是最容易接受的一种程序控制结构的图形表示了。在这种图上的框内常常标明了处理要求或条件，这些在做路径分析时是不重要的。为了更加突出控制流的结构，需要对程序流程图做些简化。在图3中给出了简化的例子。其中（a）是一个含有两出口判断和循环的程序流程图，我们把它简化成（b）的形式，称这种简化了的流程图为控制流图（Control-flow graph）。

在控制流图中只有两种图形符号，它们是：

① 节点：以标有编号的圆圈表示。它代表了程序流程图中矩形框所表示的处理、菱形表示的两至多出口判断以及两至多条流线相交的汇合点。

② 控制流线或弧：以箭头表示。它与程序流程图中的流线是一致的，表明了控制的顺序。为讨论方便，控制流线通常标有名字，如图中所标的a、b、c等。

为便于在机器上表示和处理控制流图，我们可以把它表示成矩阵的形式，称为控制流图矩阵（Control-flow graph matrix）。图4表示了图3的控制流图矩阵。这个矩阵有5行5列，是由该控制图中含有5个节点决定的。矩阵中6个元素a、b、c、d、e和f的位置决定于它们所联接节点的号码。例如，弧d在矩阵中处于第3行第4列，那是因为它在控制流图中联接了节点3至节点4。这里必须注意方向。图中节点4至节点3是没有弧的，矩阵中第4行第3列也就没有元素。

2、程序结构的基本要求

我们对于程序结构提出以下4点基本要求，这些要求是，写出的程序不应包含：

① 转向并不存在的标号；

② 没有用的语句标号；

③ 从程序入口进入后无法达到的语句；

④ 不能达到停机语句的语句。

显然，提出这些要求是合理的。在编写程序时稍加注意，做到这几点也是很容易的。这里我们更为关心的是如何进行检测，把以上4种问题从程序中找出来。目前对这四种情况的检测主要通过编译器和程序分析工具来实现。