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

Question

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

我正在遍历AST,生成字节码指令,并且我遇到了循环break内部的if-else内部while:

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

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

关键是,该示例中至少有4个"跳转"指令,我想找到一个优雅的解决方案来填充跳转地址,因为我编译AST ...我不知道while循环的跳转地址或者break直到我完全"编译"内部陈述之后.

1. 伪代码解决方案是理想的
2. 解决方案不应该取决于我是否实现了基于寄存器或堆栈的字节码编译器(我正在使用它们)

我还没读这本龙书.

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

Answer 1

您需要的原则称为"反向修补":为前向跳转填充虚拟值,为语句正文生成代码,然后返回并将虚拟值替换为末尾的虚拟值.

例如

# 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 walk函数,你已经有了一个隐式堆栈 - 递归函数调用的调用框架 - 所以你可能也不需要一个显式的.

例如in

...
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
• 处理正文(可能导致递归调用)
• 应用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回调列表必须是某些状态的一部分,该状态将传递给所有codegen函数(break需要附加到codegen的codegen ).但是保存的列表可以作为whilecodegen函数的局部变量进行跟踪.