3

インターネット全体を検索しましたが、バックパッチがどのように機能するかについての適切な説明が見つかりませんでしたか?

バックパッチの仕組みを教えてください。マーカーはどのように機能しますか?

私はそれが2つの主要なタイプのマーカーを持っていることを知っています:

  1. その中に次のクワッドがある
  2. その中に次のリストがある

入力ファイルを取得し、RISKI 言語でファイルを作成しているこのコードを見つけました。

最初のロールでは、次のものがあります。

PROGRAM : N FUNCTION M MAIN_FUNCTION

N と M がマーカーであることがわかります (これらは空のロールです)。

4

1 に答える 1

9

ワンパス コード生成には、条件のコード生成に関する小さな問題があります。典型的なifステートメント:

if CONDITION then ALTERNATIVE_1 else ALTERNATIVE_2

次のようなものにコンパイルする必要があります。

  compute CONDITION
  JUMP_IF_TRUE label1
  JUMP_IF_FALSE label2

label1:
  code for ALTERNATIVE_1
  JUMP label3

label2:
  code for ALTERNATIVE_2
  JUMP label3

label3:
  next statement

しかし、 のコードCONDITIONが生成されているとき、label1とがどこにあるのかはわかりません。label2ALTERNATIVE_1ALTERNATIVE_2label3

これを行う 1 つの方法は、上記の疑似コードのようにラベルに記号名を使用し、既知の場合は実際の値を入力することです。これには、ジャンプ ステートメントにシンボリック名を格納する必要があり、データ構造が複雑になります (特に、バイナリ アセンブラー コードだけを使用することはできません)。また、ジャンプ ターゲットを埋めるためだけに、2 回目のパスも必要です。

(おそらく) より簡単な方法は、ジャンプ ステートメントのアドレスを記憶し、それがわかっているときにターゲット アドレスにパッチを適用することです。これは、生成されたコードに戻ってパッチを適用するため、「バックパッチ」として知られています。

多くの場合、同じラベルに複数のブランチが存在することになります。&&典型的なケースは、C ファミリのand||演算子のような「短絡」ブール値です。たとえば、元の例を拡張すると、次のようになります。

if (CONDITION_1 and CONDITION_2) or CONDITION_3 then ALTERNATIVE_1 else ALTERNATIVE_2

  compute CONDITION_1
  JUMP_IF_TRUE label1
  JUMP_IF_FALSE label2

label1:
  compute CONDITION_2
  JUMP_IF_TRUE label3
  JUMP_IF_FALSE label2

label2:
  compute CONDITION_3
  JUMP_IF_TRUE label3
  JUMP_IF_FALSE label4

label3:
  code for ALTERNATIVE_1
  JUMP label5

label4:
  code for ALTERNATIVE_2
  JUMP label5

label5:
  next statement

単純な言語の場合、2 つの不完全な jump ステートメント (しばしば「true」と「false」と呼ばれます) を覚えるだけでよいことがわかります。同じターゲットへの複数のジャンプが存在する可能性があるため、これらのそれぞれは実際には不完全なジャンプ ステートメントのリンク リストであり、ターゲット アドレスはリスト内の次のジャンプを指すために使用されます。したがって、バックパッチはリストをさかのぼり、正しいターゲットにパッチを適用し、元のターゲットを使用して、パッチを適用する必要がある前のステートメントを見つけます。

あなたがマーカーと呼んでいるもの (yacc/bison が「Mid-Rule Productions」と呼んでいるもののインスタンスです) は、実際にはバックパッチとは関係ありません。それらは多くの目的に使用できます。ワンパス コード生成では、多くの場合、ルールの途中で何らかのアクションを実行する必要があり、バックパッチはその一例にすぎません。

たとえば、架空のステートメントでは、が解析されるif前にバックパッチ リストを初期化し、 and句の先頭でバックパッチを適用する必要があります。(ステートメント全体の解析の最後に別のバックパッチがトリガーされますが、それはルールの最終アクションになります。)CONDITIONTHENELSEif

ルールの途中でアクションを実行する最も簡単な方法は、ルールの途中でアクションを挿入することです。これは、指し示すバイソン ファイルの例のように、空の「マーカー」プロダクションをアクションで挿入することと同じです。

于 2014-01-23T01:22:46.590 に答える