7

LuaやPythonなどに似たバイトコードコンパイラを実装しているとしましょう。

私はASTをトラバースし、バイトコード命令を生成していますが、ループbreakの内部に遭遇しました。if-elsewhile

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

（同等のバイトコードを書き出そうとしましたが、あまり役に立ちませんでした。）

while重要なのは、その例には少なくとも4つの「ジャンプ」命令があり、ASTをコンパイルするときにジャンプアドレスを入力するための洗練されたソリューションを見つけたいということです...ループのジャンプアドレスがわかりませんまたは、break内部ステートメントを完全に「コンパイル」した後まで。

  1. 擬似コードソリューションが理想的です
  2. 解決策は、レジスタベースまたはスタックベースのバイトコードコンパイラを実装しているかどうかに依存するべきではありません（両方で遊んでいます）

私はまだドラゴンの本を読んでいません。

ASTを再帰的にコンパイルしている場合、break任意の数のループとif-elseブロック内のステートメントに到達すると、コンパイラはどの空のラベルにジャンプするかをどのように知る必要がありますか？再帰的なASTウォーキング関数の外部にあるタイプのラベル名スタックを推測しています。

4

1 に答える 1

6

必要な原則は「バックパッチ」と呼ばれます。前方ジャンプのダミー値を入力し、ステートメントの本体のコードを生成してから、戻って最後にダミー値を実際の値に置き換えます。

例えば

# 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、外側のループの本体に対する AST の再帰ウォーク内で発生しwhileます。この再帰呼び出しの内部では、外側のループではなく、内側のループだけを気にする必要があります。

したがって、必要なことは次のとおりです。

  • 処理の開始時に現在のバックパッチ状態を保存します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

現在のbreakバックパッチ リストは、すべての codegen 関数に渡される何らかの状態の一部である必要があります (codegen はbreakそれに追加する必要があります)。whileしかし、保存されたリストはcodegen 関数のローカル変数として追跡できます。

于 2012-10-26T20:55:56.590 に答える