はじめに
これは、「コンピュータシステムの理論と実装」(以下「Nand2Tetris」という)の第6章 アセンブラのプロジェクトに対するレポートである。
Qiitaでは、画像の利用に制約があるため、フローチャートなど掲載することは省いている。
プロジェクトに対するレポート
目標
- Hackコンピュータのアセンブラを作成する
- 1章から5章で作成したHackコンピュータを使い変換後の機械語を動作させる
材料
- Nand2Tetrisで定義しているアセンブラのAPI(仕様)
- Ruby
- アセンブラ
- CPUエミュレータ
- ハードウェアエミュレータ
実装
Nand2Tetrisのアセンブラは文字列の変換のため、スクリプト言語が適していると考え、Rubyにより作成することとする。
Parserモジュール
- Rubyのクラスにより実装する
- API仕様のルーチンは、メソッドにより実装する
コンストラクタ/初期化
引数で入力されたファイルを開く。
コードの煩雑化を防ぐためファイルが存在しないときなどの例外処理は実装していない。
def initialize(filename)
@asmFile = File.open(filename, "r")
end
hasMoreCommands
RubyのFileオブジェクトのeof?メソッドを利用する
def hasMoreCommands
return !@asmFile.eof?
end
advance
RubyのFileオブジェクトのreadlineメソッドを使い読み込み文字列の配列に変換する。
Rubyの文字列クラスのstripメソッドを使い空白の削除を行う。
def advance
command = @asmFile.readline
command.strip!
@chars = command.split(//)
end
commandType
今回のアセンブラの文を見て、1文字目をチェックし@か(によって分類することで命令の種別を決めれることを確認する。
最初、他のメソッドと同様に一文字取り出していたが、C_COMMANDのとき問題となるためfirstにより一文字確認する。
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のときはカッコ内の文字列を返す。
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処理を行えるようにアンドゥする
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
;までの文字列を返す
;が存在しないときは、残りの文字列
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
残りの文字列を返す。
コメントが後ろにつくこともおおくあるため削除する
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部の文字列を返す
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部の文字列を返す
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部の文字列を返す
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を作成する
def initialize
@symbolTable = Hash.new()
end
addEntry
Hashにシンボルとアドレスを追加する
def addEntry(symbol, address)
@symbolTable.store(symbol, address)
end
contains
Hashにキーが含まれているか
def contains(symbol)
return @symbolTable.key?(symbol)
end
getAddress
Hashのキー(シンボル)からアドレスを返す
def getAddress(symbol)
return @symbolTable[symbol]
end
Assembler
- Rubyのクラスにより実装する
- APIの仕様は定められていない。
- 各ルーチンについて記載のとおりに実装する。
APIの仕様は定められていないが、今までに作成した各モジュールを呼び出すため、他の言語でも同じような形になると考える。
初期化
定義済みのシンボルについてシンボル表を作成する
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回目のパスは、ファイルを最初から最後までパースし、ラベルのときはシンボル表に追加し、それ以外のときは命令数をカウントする
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の命令では、文字列のパースの順番と登録の順番が異なり、少しデバッグに苦労した。
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を呼ぶだけのドライバーである。
# 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 |