6章 アセンブラ

# はじめに

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

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


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

## 目標
* Hackコンピュータのアセンブラを作成する
* 1章から5章で作成したHackコンピュータを使い変換後の機械語を動作させる
 
## 材料
* Nand2Tetrisで定義しているアセンブラのAPI(仕様)
* Ruby
* アセンブラ
* CPUエミュレータ
* ハードウェアエミュレータ

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

### Parserモジュール

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

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

```ruby:Parser.rb
  def initialize(filename)
    @asmFile = File.open(filename, "r")
  end
```

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

```ruby:Parser.rb
  def hasMoreCommands
    return !@asmFile.eof?
  end
```

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

```ruby:Parser.rb
  def advance 
    command = @asmFile.readline
    command.strip!
    @chars = command.split(//)
  end    
```
#### commandType
今回のアセンブラの文を見て、1文字目をチェックし＠か（によって分類することで命令の種別を決めれることを確認する。
最初、他のメソッドと同様に一文字取り出していたが、C_COMMANDのとき問題となるためfirstにより一文字確認する。

```ruby: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のときはカッコ内の文字列を返す。

```ruby: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処理を行えるようにアンドゥする

```ruby: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
;までの文字列を返す
;が存在しないときは、残りの文字列

```ruby: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
残りの文字列を返す。
コメントが後ろにつくこともおおくあるため削除する

```ruby: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部の文字列を返す

```ruby: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部の文字列を返す

```ruby: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部の文字列を返す

```ruby: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を作成する

```ruby:SymbolTable.rb
  def initialize
    @symbolTable = Hash.new()
  end
```
#### addEntry
Hashにシンボルとアドレスを追加する

```ruby:SymbolTable.rb
  def addEntry(symbol, address)
    @symbolTable.store(symbol, address)
  end
```
#### contains
Hashにキーが含まれているか

```ruby:SymbolTable.rb
  def contains(symbol)
    return @symbolTable.key?(symbol)
  end
```

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

```ruby:SymbolTable.rb
  def getAddress(symbol)
    return @symbolTable[symbol]
  end
```
### Assembler

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

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

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

```ruby: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回目のパスは、ファイルを最初から最後までパースし、ラベルのときはシンボル表に追加し、それ以外のときは命令数をカウントする

```ruby: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の命令では、文字列のパースの順番と登録の順番が異なり、少しデバッグに苦労した。

```ruby: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を呼ぶだけのドライバーである。

```ruby:Assembler.rb
# Main
filename = ARGV.first

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

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

```shell:
% Assembler.rb add/Add.asm 
```

| TestProgram | OK NG |
|:-:|:-:|
| Add  |  OK |
| Max  |  OK |
| Rect  | OK  |
| Pong  | OK  |