程序流图的单性流图类与道路分析

"程序流图的道路问题是计算机科学领域中关于程序分析的一个重要研究主题。本文主要探讨了一种特殊的图结构——单性流图类，该类图同时包含了简单的不可归约流图和不具互优反向点的可归约流图。在程序流图中，分析问题通常涉及到对道路集合（尤其是简单道路集和基本道路集）的研究，这些集合的复杂性往往与图中包含的圈的数量和结构有关。然而，由于程序流图受到编程语言规则的约束，其结构相对规则且简单，通常由特定的循环语句（如for-do，while-do，goto，repeat-until等）生成。尽管大多数程序流图可以归约为更简单的形式，但这些归约流图仍然可能包含复杂结构，并不涵盖所有简单的不可归约流图。 作者吴子华在文中分析了程序流图中圈之间的关系，并提出了一种新的分析方法，即针对单性流图类，利用无圈子图的道路集来替代原图的简单道路集进行分析。这种方法有助于简化问题，使之更易于理解和解决。无圈子图，即不含环的图，它的道路集可以用来近似表示含有圈的流图的简单道路集，这为程序分析问题提供了更直接和明确的途径。 文章首先定义了程序流图的基本概念，包括其由结点集N、边集E和初始结点nO组成的三元组表示。在本文中，所有流图都没有自环，并且结点按照深度优先搜索的顺序编号。根据边的方向，边可以被分为反向边和正向边，反向边是从大号结点指向小号结点的边。 接下来，文章深入研究了单性流图的性质，尤其是不具互优反向点的可归约流图。互优反向点是指在流图中，如果存在一条路径从结点A到B，又存在一条从B到A的路径，那么这两个结点就具有互优反向点。这种特性在某些情况下会增加流图的复杂性，因此排除它们可以使分析更加简洁。 通过这种方法，作者提供了一种将复杂的程序分析问题转化为对无圈子图的显式化分析，从而简化了对程序流图的理解和处理。这种方法对于实际的程序设计和优化具有重要的理论和实践意义，因为它可以帮助开发者更好地理解和改进程序的控制流程。 总结来说，这篇1989年的研究论文探讨了程序流图的道路分析问题，特别是在单性流图类中的应用。通过引入无圈子图的概念，论文提出了一种新的分析策略，能够更有效地处理和理解含有复杂圈结构的程序流图，这对当时的程序分析和优化技术发展有着积极的推动作用。"