我听说理论上已经证明可以仅使用结构化编程结构(条件、循环和循环中断以及子例程调用)以图灵完备的语言表达任何控制流,而无需任何任意操作GOTO
声明。有没有什么方法可以使用该理论来自动重构包含以下内容的代码:GOTO
s 进入没有的代码?
假设我有一个使用简单命令式语言(例如 C 或 Pascal)的任意单个子例程。我还有一个解析器,可以验证该子例程是否有效,并从中生成抽象语法树。但代码中包含GOTO
s 和 Labels,它们可以向前或向后跳转到任何任意点,包括进出条件或循环块,但不能跳到子例程本身之外。
是否有一种算法可以采用此 AST 并将其重新加工成语义相同但不包含任何标签或的新代码GOTO
声明?
原则上,这样做总是可以的,尽管结果可能不太好。
始终消除 goto 的一种方法是按以下方式转换程序。首先对原始程序中的所有指令进行编号。例如,给定这个程序:
start:
while (true) {
if (x < 5) goto start;
x++
}
您可以这样对语句进行编号:
0 start:
1 while (x < 3) {
2 if (x < 5) goto start;
3 x++
}
要消除所有 goto,您可以使用 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.
}
}
这是一种非常非常糟糕的翻译方式,但它表明理论上总是可以做到这一点。实际上实现这一点会非常混乱 - 您可能会对函数的基本块进行编号,然后生成将基本块放入循环中的代码,跟踪当前正在执行的基本块,然后模拟运行基本块的效果并从该基本块到适当的下一个基本块的过渡。
希望这可以帮助!
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)