自动GOTO清除算法

Question

我听说理论上可以用图灵完备语言表达任何控制流,只使用结构化编程结构(条件,循环和循环中断,以及子程序调用),而不需要任何GOTO语句.有没有办法使用该理论自动重构包含GOTOs代码的代码？

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

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

Answer 1

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

始终消除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.
    }
}

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

希望这可以帮助!

Answer 2

我认为您想阅读Erosa和Hendren于1994年提出的“ 驯服控制流”。（Google学者的早期链接）。

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

如果目标语言具有尾调用优化（最好是内联），则可以通过将循环变成尾递归函数来机械地消除中断并继续。（如果index变量被循环体修改，则您需要为此做更多的工作。我将仅显示最简单的情况。）这是一个简单循环的转换：

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” 的语句恰好是continue和的转换break。实际上，该过程的第一步可能是用原始语言将循环重写为等效形式：

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