问题自动GOTO清除算法

我听说理论上已经证明可以使用结构化编程结构（条件，循环和循环中断，以及子程序调用）在图灵完备语言中表达任何控制流，而不是任意的 GOTO 声明。有没有办法使用该理论自动重构包含的代码 GOTOs代码没有？

假设我在一个简单的命令式语言中有一个任意的单个子例程，比如C或Pascal。我还有一个解析器可以验证这个子例程是否有效，并从中生成一个抽象语法树。但代码包含 GOTOs和标签，可以向前或向后跳转到任意点，包括进入或退出条件或循环块，但不在子程序本身之外。

是否有一种算法可以使用此AST并将其重新编写为新代码，该代码在语义上相同，但不包含任何标签或 GOTO 声明？

2290

2017-12-27 22:00

起源

有关： stackoverflow.com/questions/7671459/... - irrelephant

但是汇编程序将通过（条件）跳转再次替换它！ - wildplasser

@wildplasser：汇编程序无关紧要。我正在尝试将代码从支持GOTO的旧语言（以及经常使用它们的语言）转换为不支持GOTO的新语言，但与其他语言相比具有许多技术优势。我已经可以完成99％的工作，但我不知道如何重构GOTO。 - Mason Wheeler

@irrelephant：我看到了，但它的范围特别局限于只有前进跳跃。我的情况不是，所以不重复。 - Mason Wheeler

提示：如果你需要指标变量，你应该停止。 - wildplasser

答案:

我想你想读驯服控制流程由Erosa和Hendren撰写，1994年。（早先的链接谷歌学术）。

顺便说一句，循环中断也很容易消除。有一个简单的机械过程，包括创建一个布尔状态变量和重组嵌套条件以创建直线控制流。它不会产生漂亮的代码:)

如果您的目标语言具有尾部调用优化（并且理想情况下，内联），则可以通过将循环转换为尾递归函数来机械地删除中断和继续。（如果索引变量被循环体修改，你需要更加努力。我将只展示最简单的情况。）这是一个简单循环的转换：

for (Type Index = Start;        function loop(Index: Type):    
     Condition(Index);              if (Condition)
     Index = Advance(Index)){           return                      // break
   Body                             Body
}                                   return loop(Advance(Index))     // continue
                                loop(Start)

该 return 标有“继续”和“休息”的陈述恰恰是转型 continue 和 break。实际上，该过程的第一步可能是将循环重写为原始语言中的等效形式：

{
    Type Index = Start;
    while (true) {
        if (!Condition(Index))
            break;
        Body;
        continue;
    }
}

2017-12-28 14:38

Taming Control Flow纸张是否可以从任何未锁定在付费墙后面的来源获得？ - Mason Wheeler

@MasonWheeler，在答案中编辑了链接。抱歉。 - rici

谢谢，这很有效。 - Mason Wheeler

那篇论文正是我正在寻找的。它以清晰的语言解释了如何使用GOTO将例程转换为没有它们的例程，并解释了如何操作究竟这种转变，与templatetypedef的答案中给出的蛮力描述相反，后者在效率和可读性方面付出了巨大的代价。 - Mason Wheeler

原则上，总是可以这样做，虽然结果可能不是很好。

始终消除gotos的一种方法是以下列方式转换程序。首先编写原始程序中的所有指令。例如，给定此程序：

start:
    while (true) {
        if (x < 5) goto start;
        x++
    }

您可以对这些语句进行编号：

0 start:
1     while (x < 3) {
2         if (x < 5) goto start;
3         x++
      }

为了消除所有的getos，你可以通过使用while循环，一个包含程序计数器的显式变量和一堆if语句来模拟通过这个函数的控制流。例如，您可以像这样翻译上面的代码：

int PC = 0;
while (PC <= 3) {
    if (PC == 0) {
         PC = 1;             // Label has no effect
    } else if (PC == 1) {
         if (x < 3) PC = 4;  // Skip loop, which ends this function.
         else PC = 2;        // Enter loop.
    } else if (PC == 2) {
         if (x < 5) PC = 0;  // Simulate goto
         else PC = 3;        // Simulate if-statement fall-through
    } else if (PC == 3) {
         x++;
         PC = 1;             // Simulate jump back up to the top of the loop.
    }
}

这是一种非常非常糟糕的翻译方式，但它表明理论上总是可以做到这一点。实际上实现这一点会非常麻烦 - 你可能会对函数的基本块进行编号，然后生成将基本块放入循环的代码，跟踪当前正在执行的基本块，然后模拟运行基本块的效果和从该基本块到适当的下一个基本块的转换。

希望这可以帮助！

2017-12-27 22:24

BTW：这是Jacopini方法。（Google用“与goto Knuth结构化编程”） - wildplasser

@wildplasser-我不知道这有一个名字！谢谢你的参考！ - templatetypedef

我刚刚阅读了Knuth的文章。它有可能很好的观察，BTW。 Knuth最近（〜2004年？）发表了另一个goto驱动的状态机;实际上生成的代码带有计算和有意义的标签（几千......），但我似乎无法再找到它了。同时它很漂亮，也很搞笑。 - wildplasser

这张纸详细讨论转型。他们引用了Jacopini，但他们声称他们的工作更完整。 - Asiri Rathnayake

@Asiri：它是否可以从没有锁定付费墙的任何来源获得？这使得您的链接对这样的一般问答网站的用处不那么有用...... - Mason Wheeler

我使用/和Polyhedron的spag和大量的77to90开始重构fortran的过程，然后将其转换为matlab源。但是，这些工具总是留下程序中goto的1/4到1/2。

我写了一个goto卸妆程序，它完成了与你所描述的类似的东西：它需要fortran代码并重构所有剩余的goto来自程序并用条件替换它们并执行/循环/退出然后可以转换为其他语言，如matlab 。您可以在此处阅读有关我使用的流程的更多信息：

http://engineering.dartmouth.edu/~d30574x/consulting/consulting_gotorefactor.html

这个程序可以适应其他语言，但我还没有达到目的。

2017-09-25 14:14

问题 自动GOTO清除算法

答案:

热门问题

问题自动GOTO清除算法