簡易アセンブリの相対ラベル

正規表現や構文解析器の仮想マシンをいじって遊びたいとき、簡易アセンブリを使えるようにしておきたくなります。例えば、 Russ Cox の RE1 仮想マシン相当のアセンブリで、命令列を直打ちするには次のようにするとしましょう。ラベルと命令コードを Symbol インスタンスとして、 split や jmp 命令のオペランドになるアドレスをラベルで指定できるようにしておきます。

program = asm [
# (a+)(b+)
      :save,  2,
:L1,  :char,  'a',
      :split, :L1, :L2,
:L2,  :save,  3,
      :save,  4,
:L3,  :char,  'b',
      :split, :L3, :L4,
:L4,  :save,  5,
      :match,
]
#=> [[:save, 2],
#    [:char, "a"],
#    [:split, 1, 3],
#    [:save, 3],
#    [:save, 4],
#    [:char, "b"],
#    [:split, 5, 7],
#    [:save, 5],
#    [:match]]

話を単純にするため、入れ子の配列へアセンブルし、 split や jmp 命令のオペランドを配列の添字で表した絶対アドレスで扱うことにします。

ところで、この手のコードでは局所的なアドレス参照が圧倒的に多いため、命令の直前にあるラベル、もしくは直後のラベル、みたいな記述が利用できると、さらに楽になるでしょう。例えば、 D. Knuth の MIX アセンブリでは、整数ラベルを利用でき、オペランド B1 だと直前の整数ラベル 1 を、オペランド F1 だと直後のラベル 1 を参照することができるようになっています。同様のラベルは GNU アセンブリ (gas) でも利用できます。

program = asm [
# (a+)(b+)
      :save,  2,
1,    :char,  'a',
      :split, :B1, :F1,
1,    :save,  3,
      :save,  4,
1,    :char,  'b',
      :split, :B1, :F1,
1,    :save,  5,
      :match,
]

整数ラベルは何度も登場することができるため、ラベルの定義位置のアドレスの配列にしておくのが自然でしょう。ラベル定義位置を dic ハッシュに入れることにすると、上の場合は、次のようになっているものとします。

dic = {
  1 => [1, 3, 5, 7],
}

命令を格納するアドレスを dot で現すものとしましょう。すると、最初の split 命令の dot は 2 です。この命令のオペランドは B1 と F1 となっています。 B1 に対応するラベル 1 のアドレスは 1 であり、 F1 に対応するラベル 1 のアドレスは 3 です。このように、 dot アドレスにある命令のオペランドのアドレスを求めるには、 B1 に対して、 dic のラベル 1 の配列の中で、 dot 未満のアドレス集合 (1) の中から最大値 1 を選びます。 F1 に対して、 dot より大きなアドレス集合 (3, 5, 7) の中から最小値 3 を選びます。

素朴にラベルのアドレス解決手続きを記述すると、このようになります。なお、オペランドが F1 や B1 以外のシンボル L1 等だったときは、 dic ハッシュにそのまま L1 からアドレスが関連付けされているものとしましょう。

def asm_addr(dic, operand, dot)
  if Symbol === operand
    if %r/\AB(\d+)\z/ =~ operand.to_s
      dic[$1.to_i]&.select {|x| x < dot }&.max
    elsif %r/\AF(\d+)\z/ =~ operand.to_s
      dic[$1.to_i]&.select {|x| x > dot }&.min
    else
      dic[operand]
    end or raise "label #{operand} not found"
  else
    operand
  end
end

同じ数値ラベルを多く使うことを考慮すると、もう少し工夫したくなってきます。数値ラベルに dic で関連付けしてあるアドレスの配列が昇順だとして、二分探索を使いましょう。 F1 のような、 dot より大きなうちから最小値を探すのは bsearch の動きそのものなので、簡単です。一方、 B1 のような、 dot より小さなうちから最大値を探すには、少し工夫が必要です。まず、 dot 以上のうちの最小値の位置を bsearch_index で見つけます。見つからないときは、配列サイズを位置にしておきます。そして、この見つけた位置の一つ前に、求めたいアドレスが入っているはずです。

def asm_addr(dic, operand, dot)
  if Symbol === operand
    if %r/\AB(\d+)\z/ =~ operand.to_s
      ary = dic[$1.to_i] \
      and i = ary.bsearch_index {|x| x >= dot } || ary.size \
      and i > 0 and ary[i - 1]
    elsif %r/\AF(\d+)\z/ =~ operand.to_s
      dic[$1.to_i]&.bsearch {|x| x > dot }
    else
      dic[operand]
    end or raise "label #{operand} not found"
  else
    operand
  end
end

アセンブリは 2 パスで書いておきます。

パス 1 では、命令を生成せずに、すべてのラベルにアドレスを関連付けします。ニモニックとオペランドを読み飛ばし、ラベルへのアドレスを登録していきます。整数ラベルは配列にアドレスを順に格納していき、シンボル・ラベルはそのままアドレスに関連付けます。

def asm_pass1(src, dic, dot)
  sp = 0
  while sp < src.size
    case src[sp]
    when :char, :save, :jmp
      dot += 1
      sp += 2
    when :match
      dot += 1
      sp += 1
    when :split
      dot += 1
      sp += 3
    when Integer
      n = src[sp]
      dic[n] ||= []
      dic[n] << dot
      sp += 1
    when Symbol
      sym = src[sp]
      dic[sym] = dot
      sp += 1
    else
      raise "invalid source"
    end
  end
end

パス 2 では、 dic を使って、命令を生成します。ラベルを読み飛ばし、オペランドを dic を使ってアドレスを解決し、ニモニックと合わせて命令を作ります。

def asm_pass2(src, dic, program)
  sp = 0
  while sp < src.size
    case src[sp]
    when :char, :save
      program << [src[sp], src[sp + 1]]
      sp += 2
    when :match
      program << [src[sp]]
      sp += 1
    when :jmp
      x = asm_addr(dic, src[sp + 1], program.size)
      program << [src[sp], x]
      sp += 2
    when :split
      x = asm_addr(dic, src[sp + 1], program.size)
      y = asm_addr(dic, src[sp + 2], program.size)
      program << [src[sp], x, y]
      sp += 3
    when Integer, Symbol
      sp += 1
    end
  end
  program
end

asm は両方のパスを順に実行します。

def asm(src)
  dic = {}
  asm_pass1(src, dic, 0)
  asm_pass2(src, dic, [])
end