自动GOTO去除算法 [英] Automated GOTO removal algorithm

问题描述

我听说它被证明理论上可以EX preSS只使用结构化编程结构，（条件，循环和循环中断，和调用子程序）没有任何一个图灵完备的语言的任何控制流任意 GOTO 语句。有没有办法用这个理论来自动code包含重构 GOTO s转换code表示不？

让我们说我有一个简单的命令式语言，如C或Pascal任意单个子程序。我也有一个分析器，可以验证这子程序是有效的，并从中产生抽象语法树。但是，code包含 GOTO 和标签，它可以向前或向后跳转到任意点，包括进入或退出条件或循环块，但不是外界子程序本身。

有一个算法，可以借此AST和返工成新的code这是语义上相同，但不包含任何标签或 GOTO 语句<？ / P>

解决方案

我想你想读的驯服控制流由Erosa和Hendren，1994年（早前在<一个链接href="http://scholar.google.com.pe/scholar?q=%22Taming+Control+Flow%3A+A+Structured+Approach+to+Eliminating+Goto+Statements%22"相对=nofollow>谷歌学术）。

顺便说一句，环休息也很容易消除。有涉及布尔状态变量的创建和嵌套条件的重组创造直线控制流程，简单的机械过程。它不会产生pretty的code：）

如果您的目标语言有尾调用优化（和，理想情况下，内联），你可以通过机械删除这两个突破，并继续通过转动圈成一个尾递归函数。 （如果索引变量由循环体修改，你需要在此工作更努力，我会只显示简单的情况。）这里有一个简单的循环转变：

 的（类型指数=启动;功能回路（索引：类型）：
     条件（索引）;如果（条件）
     指数=高级（指数））{//返回休息
   车身车身
}返回回路（提前（指数））//继续
                                循环（开始）
 

标有继续和破发

在返回语句是precisely 的转型继续和破发。事实上，在该过程的第一步骤可能已经重写循环成其等效形式的原文：

  {
    键入指数=启动;
    而（真）{
        如果（！条件（指数））
            打破;
        体;
        继续;
    }
}
 

I've heard that it's been proven theoretically possible to express any control flow in a Turing-complete language using only structured programming constructs, (conditionals, loops and loop-breaks, and subroutine calls,) without any arbitrary GOTO statements. Is there any way to use that theory to automate refactoring of code that contains GOTOs into code that does not?

Let's say I have an arbitrary single subroutine in a simple imperative language, such as C or Pascal. I also have a parser that can verify that this subroutine is valid, and produce an Abstract Syntax Tree from it. But the code contains GOTOs and Labels, which could jump forwards or backwards to any arbitrary point, including into or out of conditional or loop blocks, but not outside of the subroutine itself.

Is there an algorithm that could take this AST and rework it into new code which is semantically identical, but does not contain any Labels or GOTO statements?

解决方案

I think you want to read Taming Control Flow by Erosa and Hendren, 1994. (Earlier link on Google scholar).

By the way, loop-breaks are also easy to eliminate. There is a simple mechanical procedure involving the creating of a boolean state variable and the restructuring of nested conditionals to create straight-line control flow. It does not produce pretty code :)

If your target language has tail-call optimization (and, ideally, inlining), you can mechanically remove both break and continue by turning the loop into a tail-recursive function. (If the index variable is modified by the loop body, you need to work harder at this. I'll just show the simplest case.) Here's the transformation of a simple loop:

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)

The return statements labeled "continue" and "break" are precisely the transformation of continue and break. Indeed, the first step in the procedure might have been to rewrite the loop into its equivalent form in the original language:

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

这篇关于自动GOTO去除算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！