2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

6章 アセンブラ

Last updated at Posted at 2021-08-22

はじめに

これは、「コンピュータシステムの理論と実装」(以下「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
2
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?