compiler-construction - 在字节码编译器中计算跳转地址的智能解决方案？

Question

假设我正在实现一个字节码编译器，类似于 Lua 的/Python 的......等等。

我正在遍历 AST，生成字节码指令，然后遇到了 break内部 if-else内部 while环形:

while (cond1)
    if (cond2)
        ...
    else
        break

(我尝试写出等效的字节码，但看起来并没有太大帮助。)

关键是，在那个例子中至少有 4 个“跳转”指令，我
想找到一个优雅的解决方案来在我编译 AST 时填充跳转地址...
我不知道 while 的跳转地址循环或 break直到我完全
“编译”了内部语句。

伪代码解决方案将是理想的

解决方案不应该取决于我是在实现基于寄存器还是基于堆栈的字节码编译器(我正在使用两者)

我还没读龙书呢。

如果我递归编译 AST，当我到达 break 时一些任意数量的循环和 if-else 内的语句块，编译器如何知道要跳转到哪个空标签？我在猜测递归 AST 行走函数外部的某种类型的标签名称堆栈。

Answer 1

你需要的原理叫做“backpatching”:为向前跳转填充一个虚拟值，生成语句体的代码，然后返回并在最后用真实值替换虚拟值。

例如

# start of codegen for 'while'
L1:
  [evaluate cond1]
  jne L2   # forward reference: use a dummy value for now

# start of codegen for 'if ... else'
L3:
  [evaluate cond2]
  jne L4   # another forward reference: use a dummy value for now
  [code in 'if' branch]
  j L5     # another forward reference: use a dummy value for now
L4:
  [code in 'else' branch before 'break']
  j L2
  [code in 'else' branch after 'break']
L5:   # end of 'if ... else'
  # now go back and fill in references to L4, L5 inside the 'if ... else' block
  # end of codegen for 'if ... else'

  # codegen for 'while' continues...
  j L1   # loop
L2:   # end of 'while' loop
  # now go back and fill in references to L2 inside the 'while' block
  # end of codegen for 'while'

关于您的编辑:

If I'm recursively compiling the AST, when I reach a break statement inside of some arbitrary number of loops and if-else blocks, how should the compiler know which empty label to jump to? I'm guessing some type of label-name stack external to the recursive AST walking function.

实现 break 的跳转目标语句是最里面的封闭循环的结尾；是的，您可以使用显式的外部堆栈来跟踪它。

但是，如果您有递归 AST 遍历函数，则您已经拥有一个隐式堆栈——递归函数调用的调用帧——因此您可能也不需要显式堆栈。

例如在

...
while (outer)
    ...
    if (outer_done)
        break
    ...

    while (inner)
        ...
        if (inner_done)
            break
        ...
    [break from inner 'while' ends up here]

    ...
    if (outer_done_2)
        break
    ...
[break from outer 'while' ends up here]
...

内部 while 的全部代码生成循环发生在外部 while 主体的 AST 递归遍历中环形。在这个递归调用中，你只需要关心内部循环，而不是外部循环。

所以，你需要做的就是:

在开始处理 while 时保存任何当前的 backpatching 状态

开始一个新的空列表来跟踪任何 break出现在此 while 的正文中

处理主体(可能导致递归调用)

应用backpatches

然后在退出前恢复之前的状态。

例如有点像这样:

codegen for while:
    save previous break backpatch list
    initialise break backpatch list as empty
    perform codegen for evaluating condition
    perform codegen for body statements
    apply backpatches
    restore previous break backpatch list

当前 break backpatch 列表必须是传递给所有代码生成函数的某个状态的一部分( break 的代码生成需要附加到它)。但是保存的列表只能作为 while 的局部变量进行跟踪。代码生成函数。