重写修改后的 goto 语义的算法
我有一大堆使用旧的自行设计的脚本语言编写的遗留代码，我们将它们编译/翻译成 javascript。
该语言有条件跳转，跳转到标签。与普通 goto 语句的区别在于，不可能向后跳转。该语言中没有嵌套的 if 语句或循环。
由于 javascript 中不存在 goto，因此我正在寻找一种算法，将 goto mylabel 和 mylabel: 转换为语义上等效的结构。
我想过使用 ifs 但发现它并不简单，因为 goto 标签的任意嵌套。
示例：
if cond1 goto a
do something1
if cond2 goto b
do something2
a:
do something3
if cond3 goto c
do something4
c:
do something5
b:
可以重写为：
lbl_b=false;
lbl_c=false;
lbl_a = cond1;
if (!cond1) {
do something1;
lbl_b = cond2;
if (!lbl_b) {
do something2;
}
}
if (!lbl_b) {
do something3;
lbl_c = cond3;
if (!lbl_c) {
do something4;
}
do something5;
}
但是，我无法从中推导出通用算法。
I've got an large bunch of legacy code in an old self-conceived scripting language that we compile/translate into javascript.
That language has a conditional jump, jumping to a label. Difference to common goto statement is, that no backward jumps are possible. There are no nested if statements nor loops in that language.
As goto does not exist in javascript, I'm looking for an algorithm that transforms goto mylabeland mylabel: into semantically equivalent structure.
I thought of using ifs but found it not trivial because of the arbitrary nesting of the goto labels.
Example:
if cond1 goto a
do something1
if cond2 goto b
do something2
a:
do something3
if cond3 goto c
do something4
c:
do something5
b:
Could be rewritten as:
lbl_b=false;
lbl_c=false;
lbl_a = cond1;
if (!cond1) {
do something1;
lbl_b = cond2;
if (!lbl_b) {
do something2;
}
}
if (!lbl_b) {
do something3;
lbl_c = cond3;
if (!lbl_c) {
do something4;
}
do something5;
}
However, I was not able to derive a general algorithm from that.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
这通常称为Goto Removal，我们只有一次学生工作，其任务是为 C 实现它。一般来说，您必须使用循环（遗憾的是我们没有将该工作放到网上）。但由于您有只能向前跳转的限制，因此相对容易：
解析所有行并收集所有标签。为每个标签创建一个标志“skip_to_label”。在开始时将所有标志初始化为 false。当您满足标签 X 的条件 goto 时，您现在将在每一行前面添加“if not skip_to_label”，直到标签行，并将标志设置为 true。
这应该已经足够并且可以工作了，但当然不是很理想。
如何优化它：不必预先添加 if，只需为每一行维护一组标志，也不必将某些内容设置为 false，只需为行添加集合中相应的标志即可。
现在，您可以为包含所有行的组创建 if，其中集合不会更改，条件是集合的布尔标志。
给定代码的示例：
现在，您可以在每行前面写入 if(s)，或者从顶部开始并创建一个 if 块，只要集合保持不变。
因此，当你开始时，你的第一个是空的，它是一个条件跳转，所以你
现在设置你的标志，集合发生变化，并且你用集合的 if 引入你的块：
集合中的下一个变化，所以新的 if 块：
等等上（我想你现在明白了）。
编辑：正如人们可以很好地看到示例中的集合一样，通常不可能使用嵌套的 if 对其进行建模，例如带有skip_to_a的行和带有skip_to_b的行重叠，但都不包含其他齐全。
This is usually called Goto Removal, we had just once a student work where the task was to implement it for C. In general you have to work with loops (sadly we did not put that work online). But as you have the restriction that you can only jump forward it is relatively easy:
Parse once over all lines and collect all labels. Create for every label a flag "skip_to_label". Initialize at beginning all flags to false. When you meet the conditional goto for label X you now prepend every single line , up to the label line with "if not skip_to_label" and set the flag to true.
This should be already enough and work, but is of course not very optimal.
How you can optimize it: Instead of prepanding the if, just maintain a set of flags for every line, and instead of setting something to false, just add for the lines the corrosponding flag in the set.
Now you can make the if for a group that contains all lines, where the set does not change, and the condition are the boolean flags of the set.
Example with your given code:
Now you write in front of each line either the if(s) or you start at the top and make an if block as long as the set remains the same.
So when you start you get your first at empty, its a conditional goto so instead you set your flag
now the set changes, and you introduce your block with the if of the set:
next change in set, so new if block:
and so on (I guess you get now the idea).
EDIT: As one can nicely see with the sets in the example it is in general not possible to model it with nested ifs, as e.g. the lines with skip_to_a and the ones with skip_to_b overlap, but neither contains the other complete.
你可以做一些类似在 while 循环中跟踪 goto 状态的事情，但它看起来不太漂亮：
You could do something like tracking the goto state in a while loop, but it wouldn't look too pretty:
编译为另一种语言通常比必要的更困难。更简单的方法是，不编译为其他语言，而是用 javascript 解释代码。这样就可以轻松地生成具有您想要的任何类型语义的 goto 语句。
但是，如果您这样做，则需要将所有解析逻辑移至 JavaScript 代码中，这可能很难做。另一种方法是编译一些更容易解释的格式，即字节码，以便您可以从解析器、所有标签位置等预先计算您需要的所有内容。
Compiling to another language is usually harder than necessary. A simpler method would be, not to compile to the other language, but to interpret the code in javascript. This way it would easily be possible to produce your goto statement with any kind of semantics you would like.
However if you do it like this, you would need to move all the parsing logic into your javascript code, which might be ugly to do. Another method would be to compile some easier interpretable format, i.e. bytecode, so that you can precompute everything you need from the parser, all label positions etc.
一种替代解决方案是将每个标签放入一个方法中，该方法包含从该标签开头到下一个标签开头的代码，然后调用为下一个标签生成的函数。
这样做的优点是可以用简单的方法调用代替 goto。缺点是，对于长脚本或循环，您最终可能会得到相当大的调用堆栈。
使用此方法，一个简单的算法将是：
这可能最终会导致其他问题。例如，变量的范围是什么？但是，至少这是一种替代方法，我希望它能让你的思想开始沿着更多的轨道发展。 ;)
One alternative solution would be to make each label into a method containing the code from the start of that label to the beginning of the following label, followed by a call to the function generated for the following label.
The pro for this is that a goto can be replaced by a simple method call. The drawback is that, for long scripts or loops you may end up with rather large call stacks.
Using this method, a simple algorithm would be:
This may end up causing additional problems. For example, what of scope for variables? But, at least it is an alternative approach which I hope should get your mind started along more tracks. ;)