Question

过去大部分结构化算法关心如何以引进新布尔变量、代码重复、使用多级出口循环或使用一组常用语言中没有的高级结构为代价从控制流向图中去掉 goto 语句。一个图转换系统也曾经被提出，它的目标是不去掉全部 goto 语句而识别潜在控制结构。下列几节概述在这个领域中做过的工作。

6.1.1 布尔变量的介绍

Bohm 和 Jacopini [BJ66] 证明，利用新布尔变量的引进以及给这些变量赋值，任何程序的流图(flowgraph) 可以表现为另一个流图——它可分解为π(结点序列)、φ(后测试的循环) 和Δ(2 路条件码)。Cooper [Coo67] 指出，如果新变量可以被引进到原来的程序，任何程序能用最多带一个φ的一个结点表示；因此，从实践的观点看，该定理没有意义 [Knu74]。

Ashcroft 和 Manna [AM71] 论证，如果没有引进新变量，goto 程序不能被转换成 while() 程序，并提出一个利用引进新的布尔变量的这些程序转换算法。转换保持原来流程图程序的拓扑学，但是按照不同顺序进行计算。

Williams 和 Ossher [WO78] 提出一个迭代算法，通过引进一个布尔变量和每一个循环一个计数器整型变量，把一个多出口循环转换成一个单出口循环。

Baker 和 Zweben [BZ80] 提出利用新布尔变量的引进把多出口循环结构化。多出口循环的结构化被认为是一个控制流复杂性问题而且在这篇文章中被量化。

Williams 和 Chen [WG85] 提出从 Pascal 语言程序中清除 goto 语句的转换。Goto 语句根据目标标签的位置来分类为：在与对应标签相同的层次上、离开一个结构的分支、从外面一个标签转入一个结构、以及子程序的不正常出口。这些转换需要一个或多个布尔变量的引进，以及必要的赋值语句和测试语句来检查一个布尔变量的值。该算法在一个 PDP11/34 机器上的 Prolog 语言中被实现。

Erosa 和 Hendren [EH93] 提出一个算法把所有的 goto 语句从 C 程序中去除掉。该方法利用 goto-elimination(清除) 和 goto-movement(移动) 的转换，而且为每 goto 引进一个新的布尔变量。为每一个新布尔变量的测试平均引进三条新指令，而且不同的循环和 if 条件被修改以包括新布尔变量。这个方法作为 McCAT 并行化反编译器的组成部分被实现。

新的（布尔) 变量的引进修改了潜在程序(underlying program) 的语义，因为这些变量不是原来程序的组成部分。合成的程序在功能上等价于原来的程序，因此程序产生同样的结果。

6.1.2 代码重复

Knuth 和 Floyd [KF71] 提出各种不同的方法——不使用新变量的引进而消除 goto 语句的使用。他们给出四个方法：递归的引进、新的子过程的引进、结点分割法和一个 repeat..until() 构造的使用。结点分割法技术的使用在最后的程序中复制代码。也证明了，如果不引进新的子过程调用，存在有些程序它的 goto 语句无法被清除掉。

Williams [Wil77] 提出导致非结构化图的五个子图：不正常选择路径、多出口循环、多入口循环、重叠循环和并行循环。为了把这些子图转换成结构化的图，要进行代码复制。

Williams 和 Ossher [WO78] 提出一个用单入口 while() 循环代替多入口循环的算法。该方法利用所有可能被从非正常入口进入该循环而到达的结点的代码复制。

Baker 和 Zweben [BZ80] 提出使用结点分割法技术，通过复制流图的一个或多个结点，生成在执行上等价的流图。结点分割法被认为是一个控制流复杂性问题，而且被量化。

Oulsnam [Oul82] 提出转换法——把六种非结构化图转换成等价的结构化图。该方法学利用结点复制而非函数复制。证明，因结点复制带来的时间开销，其时间增幅因子是至少一个路径加 3。

代码复制由于复制代码/结点一次或多次而修改了原来的程序/图，因此，最后的程序/图是功能上等价于原来的程序/图，但是它的语义和结构已经被修改。

6.1.3 多级出口循环和其它结构

Baker [Bak77] 提出一个算法利用下列控制结构把流图等价地结构化：if..then..else、多级 break、多级 next、和无穷循环。每当图无法用前面这些结构来结构化，就使用 Gotos。该算法也被推广到不可归约图(irreducible graph)。它说明该算法生成格式良好而且适当地嵌套的程序，而且在最后形成的图中任何 goto 语句都是向前跳转。这个算法在运行 Unix 的一台 PDP11/54 机器上被 struct 程序实现。它被用来把 Fortran 程序重写成 Ratfor，一个使用控制结构的扩展的 Fortran 语言。该 struct 程序后来被 J.Reuter 在 decomp 反编译器中用来从带符号信息的目标文件(.obj) 中建立结构化图。

Sharir [Sha80] 提出一个算法在一个流向图中发现潜在控制结构。这个算法检测正常的条件构造和循环构造，但是也检测适当的和不适当的强连通区间、以及适当的和不适当的最远区间。最后的流向图表现为一个分级的流结构。

Ramshaw [Ram88] 提出一个方法，使用向前清除规则和向后清除规则，从程序中清除所有的 goto 语句。 合成的程序是一个结构上等价的程序——它使用无穷的、命名的循环的多级出口。这个算法被用来把 Knuth 的 TEX 编译器的 Pascal 语言版本移植到使用 Mesa 语言的 PARC/CSL。这两个语言都允许使用 goto 语句，不过在 Mesa 中不允许向外的 goto 语句。

多级出口或高级构造的使用在大多数语言中不可用，这限制了该结构化方法的普遍性以及编写程序的结构化版本可以使用的语言数目。目前，大多数第三代语言 (例如，Pascal、Modula-2、C) 不使用多级出口；只有 Ada 语言允许。

6.1.4 图转换系统

Lichtblau [Lic85] 提出通过标识出表现高级控制结构的子图把一个控制流向图转换成一个平凡图的一序列转换规则；高级控制结构如，2 路条件结构、顺序结构、循环结构和多出口循环结构。每当没有任何规则适用于该图的时候，就从该图去掉一个边并且在它的位置上生成一个 goto 语句。这个转换系统被证明是有限的 Church-Rosser，因此该转换能被以任何顺序应用而且得到相同的最后答案。

Lichtblau 通过引进无语境的流图语法——使用把一个图转换成另一个图的生成规则定义的无语境语法——使转换系统定式化 [Lic91]。他证明假如有一个固定的无语境流图语法 GG，就有可能确定能不能从 GG 衍生出一个流图 g。他提供了一个算法以多项式时间复杂度解决这个问题。

通过图转换来做的控制结构检测不更改潜在程序的语义或功能性，因此转换系统提供一个生成语义等价的图的方法。Lichtblau 的方法在图上使用一序列图转换，把该图转换/变换成一个等价的结构化图 (如果可能的话)。这些转换不考虑从缩短评价语言生成的图，在这类语言中一个复合布尔条件的操作数不需要全部被评价，因而依照这个方法学将会生成非结构化的图。

相反地，在这篇论文中提出的结构化算法把一个任意的控制流向图转换成一个功能和语义等价的流向图——它根据一个在普遍使用的高级语言中可用的一般化的控制结构集合（类集) 来结构化，而且每当图无法用普遍化的结构来结构化的时候，就使用 goto 跳转。这些算法考虑由缩短评价生成的图，因而不为这些图生成不必要的 goto 跳转。