はじめに

これは、「コンピュータシステムの理論と実装」(以下「Nand2Tetris」という)の第6章アセンブラのプロジェクトに対するレポートである。

Qiitaでは、画像の利用に制約があるため、フローチャートなど掲載することは省いている。

プロジェクトに対するレポート

目標

Hackコンピュータのアセンブラを作成する
1章から5章で作成したHackコンピュータを使い変換後の機械語を動作させる

材料

Nand2Tetrisで定義しているアセンブラのAPI(仕様)
Ruby
アセンブラ
CPUエミュレータ
ハードウェアエミュレータ

実装

Nand2Tetrisのアセンブラは文字列の変換のため、スクリプト言語が適していると考え、Rubyにより作成することとする。

Parserモジュール

Rubyのクラスにより実装する
API仕様のルーチンは、メソッドにより実装する

コンストラクタ／初期化

引数で入力されたファイルを開く。
コードの煩雑化を防ぐためファイルが存在しないときなどの例外処理は実装していない。

Parser.rb

  def initialize(filename)
    @asmFile = File.open(filename, "r")
  end

hasMoreCommands

RubyのFileオブジェクトのeof?メソッドを利用する

Parser.rb

  def hasMoreCommands
    return !@asmFile.eof?
  end

advance

RubyのFileオブジェクトのreadlineメソッドを使い読み込み文字列の配列に変換する。
Rubyの文字列クラスのstripメソッドを使い空白の削除を行う。

Parser.rb

  def advance 
    command = @asmFile.readline
    command.strip!
    @chars = command.split(//)
  end

commandType

今回のアセンブラの文を見て、1文字目をチェックし＠か（によって分類することで命令の種別を決めれることを確認する。
最初、他のメソッドと同様に一文字取り出していたが、C_COMMANDのとき問題となるためfirstにより一文字確認する。

Parser.rb

  def commandType
    c = @chars.first
    case c
    when "@" 
      return A_COMMAND
    when "("
      return L_COMMAND
    else
      return C_COMMAND
    end
  end

symbol

A_COMMANDのときは＠以外の残りの文字列、L_COMMANDのときはカッコ内の文字列を返す。

Parser.rb

  def symbol
    field = ""
    while c = @chars.shift
      if c == "@"
        next
      elsif c == "("
        next
      elsif c == ")"
        return field
      else
        field.concat c
      end
    end
    return field
  end

dest

=までの文字列を返す
=が存在しないときは、再度Parse処理を行えるようにアンドゥする

Parser.rb

  def dest
    field = ""
    while c = @chars.shift
      if c == "="
        return field
      elsif c == " "
        next
      elsif isComment
        #undo
        @chars = field.split(//)
        field = ""
        return field
      else
        field.concat c
      end
    end
    #undo
    @chars = field.split(//)
    field = ""
    return field
  end

comp

;までの文字列を返す
;が存在しないときは、残りの文字列

Parser.rb

  def comp
    field = ""
    while c = @chars.shift
      if c == ";"
        return field
      elsif isComment
        @chars = []
        return field
      elsif c == " "
        next
      else
        field.concat c
      end
    end
    return field
  end

jump

残りの文字列を返す。
コメントが後ろにつくこともおおくあるため削除する

Parser.rb

  def jump
    field = ""
    while c = @chars.shift
      if c == " "
        next
      elsif isComment
        field.concat c
        return field
      else
        field.concat c
      end
    end
    return field
  end

Codeモジュール

Rubyのクラスにより実装する
API仕様のルーチンは、メソッドにより実装する

dest

入力されたニーモニックによりdest部の文字列を返す

Code.rb

    def dest(mnemonic)
      field = ""
      case mnemonic
      when "M"
        field = "001"
      when "D"
        field = "010"
      when "MD"
        field = "011"
      when "A"
        field = "100"
      when "AM"
        field = "101"
      when "AD"
        field = "110"
      when "AMD"
        field = "111"
      else
        field = "000"
      end
      return field
    end

comp

入力されたニーモニックによりcomp部の文字列を返す

Code.rb

    def comp(mnemonic)
      field = ""
      case mnemonic
      when "0"
        field = "0101010"
      when "1"
        field = "0111111"
      when "-1"
        field = "0111010"
      when "D"
        field = "0001100"
      when "A"
        field = "0110000"
      when "M"
        field = "1110000"
      when "!D"
        field = "0001101"
      when "!A"
        field = "0110001"
      when "!M"
        field = "1110001"
      when "-D"
        field = "0001111"
      when "-A"
        field = "0110011"
      when "-M"
        field = "1110011"
      when "D+1"
        field = "0011111"
      when "A+1"
        field = "0110111"
      when "M+1"
        field = "1110111"
      when "D-1"
        field = "0001110"
      when 'A-1'
        field = "0110010"
      when "M-1"
        field = "1110010"
      when "D+A"
        field = "0000010"
      when "D+M"
        field = "1000010"
      when "D-A"
        field = "0010011"
      when "D-M"
        field = "1010011"
      when "A-D"
        field = "0000111"
      when "M-D"
        field = "1000111"
      when "D&A"
        field = "0000000"
      when "D&M"
        field = "1000000"
      when "D|A"
        field = "0010101"
      when "D|M"
        field = "1010101"
      else
        field = "0000000"
      end
      return field
    end

jump

入力されたニーモニックによりjump部の文字列を返す

Code.rb

    def jump(mnemonic)
      field = ""
      case mnemonic
      when "JGT"
        field = "001"
      when "JEQ"
        field = "010"
      when "JGE"
        field = "011"
      when "JLT"
        field = "100"
      when "JNE"
        field = "101"
      when "JLE"
        field = "110"
      when "JMP"
        field = "111"
      else
        field = "000"
      end
      return field
    end

SymbolTableモジュール

Rubyのクラスにより実装する
API仕様のルーチンは、メソッドにより実装する

コンストラクタ／初期化

Hashにより実装することとし、空のHashを作成する

SymbolTable.rb

  def initialize
    @symbolTable = Hash.new()
  end

addEntry

Hashにシンボルとアドレスを追加する

SymbolTable.rb

  def addEntry(symbol, address)
    @symbolTable.store(symbol, address)
  end

contains

Hashにキーが含まれているか

SymbolTable.rb

  def contains(symbol)
    return @symbolTable.key?(symbol)
  end

getAddress

Hashのキー（シンボル）からアドレスを返す

SymbolTable.rb

  def getAddress(symbol)
    return @symbolTable[symbol]
  end

Assembler

Rubyのクラスにより実装する
APIの仕様は定められていない。
各ルーチンについて記載のとおりに実装する。

APIの仕様は定められていないが、今までに作成した各モジュールを呼び出すため、他の言語でも同じような形になると考える。

初期化

定義済みのシンボルについてシンボル表を作成する

Assembler.rb

def initSymbolTable(asmSymbolTable)
  # defined symbol
  asmSymbolTable.addEntry("SP", 0)
  asmSymbolTable.addEntry("LCL", 1)
  asmSymbolTable.addEntry("ARG", 2)
  asmSymbolTable.addEntry("THIS", 3)
  asmSymbolTable.addEntry("THAT", 4)
  for i in [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
    asmSymbolTable.addEntry("R"+i.to_s, i)
  end
  asmSymbolTable.addEntry("SCREEN", 16384)
  asmSymbolTable.addEntry("KBD", 24576)
end

FirstPass

1回目のパスは、ファイルを最初から最後までパースし、ラベルのときはシンボル表に追加し、それ以外のときは命令数をカウントする

Assembler.rb

def firstPass(filename, asmSymbolTable)
  asmParse = Parser.new(filename)

  n = 0
  while asmParse.hasMoreCommands
    command = asmParse.advance
    if asmParse.isEmpty
      next
    elsif asmParse.isComment
      next
    elsif asmParse.commandType == L_COMMAND
      symbol = asmParse.symbol
      asmSymbolTable.addEntry(symbol, n) 
    else
      n = n + 1
    end
  end
end

SecondPass

Asmファイルの内容をHackファイルに変換して書き込む
A_COMMANDの命令では、登録されていないシンボルがでたときはシンボル表に登録し、そのときの値を使う。
C_COMMANDの命令では、文字列のパースの順番と登録の順番が異なり、少しデバッグに苦労した。

Assembler.rb

def secondPass(filename, asmSymbolTable)
  asmParse = Parser.new(filename)
  asmCode = Code.new()
  # output to hack file
  hackOut = File.open(filename.gsub(/asm/, "hack"), "w+")
  n = 16
  while asmParse.hasMoreCommands
    command = asmParse.advance
    if asmParse.isEmpty
      next
    elsif asmParse.isComment
      next
    elsif asmParse.commandType == A_COMMAND
      symbol = asmParse.symbol
      if symbol =~ /[a-zA-Z]/
        if asmSymbolTable.contains(symbol)
          symbol = asmSymbolTable.getAddress(symbol)
        else
          asmSymbolTable.addEntry(symbol, n)
          symbol = n
          n = n + 1
        end
      end
      field = '0' + format("%015b\n", symbol.to_i) 
    elsif asmParse.commandType == C_COMMAND
      dest = asmParse.dest
      comp = asmParse.comp
      jump = asmParse.jump
      field = "111"
      field = field + asmCode.comp(comp)
      field = field + asmCode.dest(dest)
      field = field + asmCode.jump(jump)
      field = field + "\n"
    else
      next
    end
    hackOut.print field
  end

Main

アセンブラのメイン部は以下の通りFirstPassとSecondPassを呼ぶだけのドライバーである。

Assembler.rb

# Main
filename = ARGV.first

asmSymbolTable = SymbolTable.new()
initSymbolTable(asmSymbolTable)
firstPass(filename, asmSymbolTable)
secondPass(filename, asmSymbolTable)

テスト

以下のように、アセンブラプログラムをアセンブルし、付属のアセンブラと内容を確認とった。Pongは行数が多く比較に時間がかかる。

% Assembler.rb add/Add.asm

TestProgram	OK NG
Add	OK
Max	OK
Rect	OK
Pong	OK