Wirth VM の簡易アセンブリ

字下げ判定のための命令を Wirth VM に追加して動かしてみようと考えたのですが、 その前にアセンブリを作っておきます。 Wirth VM はすべての命令に成功時と失敗時の飛び先を記入するため、 飛び先をラベルで指定できないと修正が大変です。 さらに、 すべての命令にラベルを付けるということで、 生成規則ごとに局所ラベルを利用できると便利になります。

次の例では、 label 欄、 succ 欄、 そして、 fail 欄の 3 箇所でラベルを使っています。 アンダースコアで始まるラベルは局所ラベルです。 生成規則 S1 と S2 のそれぞれで、 2 つの局所ラベルを使っています。 局所レベルといっても、 内部では生成規則のラベルを前置句とする大域ラベルを合成しています。

vm = WirthVM.new
vm.asm([
  # ["][^"]*["] / ['][^'][']
  #label opcode     x    y    z
  [:S1, :terminal,  :_1, :S2, '"'], # ラベル欄は :S1、 x 欄は :S1_1,  y 欄は :S2 の意味
  [:_1, :terminal,  0,   :_2, '"'],
  [:_2, :terminal,  :_1, 0,   :any],
  [:S2, :terminal,  :_1, 0,   "'"],
  [:_1, :terminal,  0,   :_2, "'"],
  [:_2, :terminal,  :_1, 0,   :any],
])
#=> [WirthVM::Instruction.new(:trap,      0,  0,   0),     # 番地 0 トラップ
#    WirthVM::Instruction.new(:terminal,  2,  4,   '"'),   # 番地 1
#    WirthVM::Instruction.new(:terminal,  0,  3,   '"'),   # 番地 2
#    WirthVM::Instruction.new(:terminal,  2,  0,   :any),  # 番地 3
#    WirthVM::Instruction.new(:terminal,  5,  0,   "'"),   # 番地 4
#    WirthVM::Instruction.new(:terminal,  0,  6,   "'"),   # 番地 5
#    WirthVM::Instruction.new(:terminal,  5,  0,   :any)]  # 番地 6

2 パス・アセンブラにし、 パス 1 でラベルにアドレスをつけ、 パス 2 でそのアドレスを使って命令コードを生成します。 ラベル欄が非終端記号のときだけ、 @label 表に登録します。

class WirthVM
  class Instruction
    attr_accessor :opcode, :x, :y, :z
    def initialize(f, a, b, c) @opcode, @x, @y, @z = f, a, b, c end
  end

  def initialize()
    @label = {}   # Symbol nonterminal => Integer address
    @rlabel = {}  # Integer address => Symbol nonterminal
    @program = []
  end
   
  def asm(source)
    @label.clear
    tbl = {}
    asm_pass(tbl, source)
    asm_pass(tbl, source)
    @rlabel = @label.invert
    self
  end

  def asm_pass(tbl, source)
    @program.clear
    @program << Instruction.new(:trap, 0, 0, 0)
    entry = nil
    source.each do |label, opcode, a, b, c|
      ip = @program.size
      if Symbol === label
        name = label.to_s
        fullname = '_' == name[0] ? entry + name : name
        if '_' != name[0]
          entry = name
          @label[label] = ip
        end
        tbl[fullname] = ip
      end
      x = asm_addr(tbl, entry, a, ip)
      y = asm_addr(tbl, entry, b, ip)
      case opcode
      when :empty, :terminal, :nonterminal
        z = c
      else
        z = asm_addr(tbl, entry, c, ip)
      end
      @program << Instruction.new(opcode, x, y, z)
    end
    @program
  end

  def asm_addr(tbl, entry, label, ip)
    Symbol === label or return label
    name = label.to_s
    fullname = '_' == name[0] ? entry + name : name
    tbl[fullname] || ip
  end

  def list()
    @program.each_index {|ip| puts disasm(ip) }
    self
  end

  def disasm(ip)
    f1 = if @rlabel[ip].nil? then '' else @rlabel[ip].to_s + ':' end
    op, x, y, z = @program[ip].opcode, @program[ip].x, @program[ip].y, @program[ip].z
    xa = @rlabel[x] || x
    ya = @rlabel[y] || y
    case op
    when :terminal, :empty
      "%2d %-4s%-12s %3s, %3s, %3p" % [ip, f1, op, xa, ya, z]
    when :nonterminal
      "%2d %-4s%-12s %3s, %3s, %3s" % [ip, f1, op, xa, ya, z]
    else
      za = @rlabel[z] || z
      "%2d %-4s%-12s %3s, %3s, %3s" % [ip, f1, op, xa, ya, za]
    end
  end
end