7

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

我正在遍历 AST，生成字节码指令，然后我遇到了一个循环break内部：if-elsewhile

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

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

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

  1. 伪代码解决方案将是理想的
  2. 解决方案不应该取决于我是在实现基于寄存器还是基于堆栈的字节码编译器（我正在使用两者）

我还没看龙书呢。

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

4

1 回答 1

6

你需要的原理叫做“backpatching”：前向跳转填写一个dummy值，生成语句体的代码，然后返回，最后用真值替换dummy值。

例如

# 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'

关于您的编辑：

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

实现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 的递归遍历中。在这个递归调用中，您只需要关心内部循环，而不是外部循环。

所以，你需要做的就是：

  • 在开始处理 a 时保存任何当前的回补状态while
  • 开始一个新的空列表以跟踪break出现在此正文中的任何内容while
  • 处理正文（这可能会导致递归调用）
  • 应用背贴
  • 然后在退出之前恢复以前的状态。

例如有点像这样：

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

当前的breakbackpatch 列表必须是传递给所有 codegen 函数的某个状态的一部分（codegen forbreak需要附加到它）。但是保存的列表可以作为whilecodegen 函数的局部变量进行跟踪。

于 2012-10-26T20:55:56.590 回答