こんばんは。10日ぶりの更新です。
時間が取れなくて前回からだいぶ遅くなった 😭
[https://www.oreilly.co.jp/books/9784873117126/:embed:cite]
vol.6 いまここ
6章 アセンブラ
理論
この章ではアセンブリ言語をアセンブラによって機械語に変換できるようにする。
アセンブリ言語
LOAD R3 7などの人間が読みやすい言語。
機械語
バイナリである。先ほどのLOAD R3 7は、ハードウェアの論理設計上で、
LOADは最初の8ビット。R3（レジスタ）は次の8ビット。7（アドレス）を残りの16ビットで表現するというようなルールが決められており、それに従って出力されたバイナリ
シンボル
アセンブリ言語上でメモリアドレスを間接的に指定できる変数。
任意のシンボルは、どこかのアドレスの位置を参照している
利用方法としては一般的に以下の２種類がある
- ラベル
LOOPなど。gotoやjmpで利用するためのラベル、タグ。この行の次の行のアドレスを指し示す。この行自体は機械語に出力されない。
- 変数
count=0やi=1のように利用できる。変数はRAMと混合しないようにメモリのある地点から格納される。
シンボル解決
アセンブラは、シンボルを使わない場合だとルールに従ってバイナリに変換するだけで良い。しかし
、シンボルを利用する場合はシンボルが表すアドレスを全て保存しシンボルが利用されている箇所全てを置換する必要がある。
理論（Hack）
アセンブリ言語
各行は、以下のうちのどれかで構成される
- A命令またはC命令の命令
- シンボル
- 意味のない行
また、コメントは //で書き、その行のそれ以降の文字は全てアセンブラに無視される
定義済みシンボル
R0...R15やTHISやARGSは定義済みシンボル。
| ラベル | RAMアドレス |
|---|---|
| R0 | 0 |
| R1 | 1 |
| … | … |
| R15 | 15 |
| SP | 0 |
| LCL | 1 |
| ARGS | 2 |
| THIS | 3 |
| THAT | 4 |
実装
アセンブリを実装しなければならない。
２段階で実装する。
- シンボルがないアセンブリの場合のアセンブラ
- シンボルがあるアセンブリの場合のアセンブラ
1の場合は一度アセンブリを舐めるだけで良い。というのも、上から順に変換することが可能であるため。
2の場合、ファイルを舐める作業は２回必要である。というのも、シンボルは先に利用して後から宣言できるため。
こんな場合👇
@LOOP_END
0;JMP
...
...
...
(LOOP_END)
なので、1度目は、L命令を全てシンボルテーブルに保存して、2度目はそれを元に、出力していく。
特にこだわりがないので言語はkotlinでやってみた。
assemblerディレクトリにkotlinのプロジェクトファイルを保存してあります
Parserモジュール
import java.io.File
import java.io.InputStream
class Parser(filePath: String) {
enum class COMMAND_TYPE {
A_COMMAND,
C_COMMAND,
L_COMMAND,
NONE
}
var inputLines = mutableListOf<String>()
var commandIndex: Int = -1
var binaryIndex: Int = -1
init {
val inputStream: InputStream = File(filePath).inputStream()
val lineList = mutableListOf<String>()
inputStream.bufferedReader().useLines { lines -> lines.forEach { lineList.add(it) } }
lineList.forEach {
// コメントは除去
val formattedLine = it.split("//")[0]
if (formattedLine.isEmpty()) {
return@forEach
}
this.inputLines.add(formattedLine)
}
}
// 入力にまだコマンドが存在するか
fun hasMoreCommands(): Boolean {
val nextLine = inputLines.getOrNull(this.commandIndex + 1)
return nextLine !== null
}
// 次のコマンドを読み込む
fun advance() {
this.commandIndex++
}
// 現コマンドの種類を表す
fun commandType(): COMMAND_TYPE {
val command = getCurrentCommand()
return when {
command.startsWith("@") -> COMMAND_TYPE.A_COMMAND
command.startsWith("(") && command.endsWith(")") -> COMMAND_TYPE.L_COMMAND
else -> COMMAND_TYPE.C_COMMAND
}
}
fun symbol(): String {
val command = this.getCurrentCommand()
val commandType = this.commandType()
if (commandType !== COMMAND_TYPE.L_COMMAND && commandType !== COMMAND_TYPE.A_COMMAND) {
return ""
}
if (commandType === COMMAND_TYPE.L_COMMAND) {
return command.replace("(", "").replace(")", "")
}
return command.replace("@", "").trim()
}
fun dest(): String {
val command = this.getCurrentCommand()
if (!command.contains("=")) {
return ""
}
return command.split("=")[0].trim()
}
fun comp(): String {
val command = this.getCurrentCommand()
var comp = command
if (command.contains(";")) {
comp = command.split(";")[0].trim()
}
if (command.contains("=")) {
comp = command.split("=")[1].trim()
}
return comp
}
fun jump(): String {
val command = this.getCurrentCommand()
if (!command.contains(";")) {
return ""
}
return command.split(";")[1].trim()
}
private final fun getCurrentCommand(): String {
return inputLines.get(this.commandIndex).trim()
}
fun reset() {
commandIndex = -1
binaryIndex = -1
}
}
愚直に実装。
ただし以下の部分に注意
// コメントは除去
val formattedLine = it.split("//")[0]
Codeモジュール
destはロジックに落とし込めた。jmpはロジック無理と割り切ってmapで行った。compはロジックに落とそうとすると非常に難しかった。
もしかしてと思って他の人の回答を見ると、そのまさかMapで持たせてた。まあそれが早いよね。
class Code() {
companion object {
fun dest(nimonic: String): String {
var d = ""
d += if (nimonic.contains("A")) {
"1"
} else {
"0"
}
d += if (nimonic.contains("D")) {
"1"
} else {
"0"
}
d += if (nimonic.contains("M")) {
"1"
} else {
"0"
}
return d
}
fun comp(nimonic: String): String {
val map = mapOf(
"0" to "0101010",
"1" to "0111111",
"-1" to "0111010",
"D" to "0001100",
"A" to "0110000",
"!D" to "0001101",
"!A" to "0110001",
"-D" to "0001111",
"-A" to "0110011",
"D+1" to "0011111",
"A+1" to "0110111",
"D-1" to "0001110",
"A-1" to "0110010",
"D+A" to "0000010",
"D-A" to "0010011",
"A-D" to "0000111",
"D&A" to "0000000",
"D|A" to "0010101",
"M" to "1110000",
"!M" to "1110001",
"-M" to "1110011",
"M+1" to "1110111",
"M-1" to "1110010",
"D+M" to "1000010",
"D-M" to "1010011",
"M-D" to "1000111",
"D&M" to "1000000",
"D|M" to "1010101"
)
return map.get(nimonic)!!
}
fun jump(nimonic: String): String {
return when (nimonic) {
"JGT" -> "001"
"JEQ" -> "010"
"JGE" -> "011"
"JLT" -> "100"
"JNE" -> "101"
"JLE" -> "110"
"JMP" -> "111"
else -> "000"
}
}
}
}
Main.kt
import java.io.BufferedWriter
import java.io.File
import java.io.FileWriter
import java.io.PrintWriter
fun main(args: Array<String>) {
// 入力
val parser = Parser("/nand2tetris/projects/06/rect/Rect.asm")
// 出力
val fil = FileWriter("/nand2tetris/projects/06/rect/Rect.hack")
// シンボルテーブル
val symbolTable = SymbolTable()
// 1. 変数保存
while (parser.hasMoreCommands()) {
parser.advance()
if (parser.commandType() == Parser.COMMAND_TYPE.L_COMMAND) {
// 次の行のbinaryIndexを保存
symbolTable.addEntry(parser.symbol(), parser.binaryIndex + 1)
} else {
// L命令ではないので、機械語として出力される=>機械語の行数をカウントアップ
parser.binaryIndex++
}
}
parser.reset()
// 2. 変換出力
val pw = PrintWriter(BufferedWriter(fil))
while (parser.hasMoreCommands()) {
parser.advance()
if (parser.commandType() === Parser.COMMAND_TYPE.NONE) {
continue
}
if (parser.commandType() === Parser.COMMAND_TYPE.L_COMMAND) {
continue
}
if (parser.commandType() === Parser.COMMAND_TYPE.A_COMMAND) {
val symbol = parser.symbol()
// シンボルに文字が含まれる場合
val address = if (symbol.contains(Regex("""\D+"""))) {
// シンボルテーブルに含まれていない場合
if (!symbolTable.contains(symbol)) {
// 新たに追加
symbolTable.addEntry(symbol)
}
// シンボルテーブルからアドレスを解決
symbolTable.getAddress(symbol)
} else {
// シンボルが数値の場合
Integer.parseInt(symbol)
}
pw.println("%016d".format(Integer.toBinaryString(address).toLong()))
continue
}
// C命令
val binaryString = "111" + Code.comp(parser.comp()) + Code.dest(parser.dest()) + Code.jump(parser.jump())
pw.println(binaryString)
}
pw.close()
}
エントリーポイント。ファイルを二回なめている。
commandIndexで、アセンブリ言語の行数をカウントアップしているが、機械語の行数とは一致しないので注意。途中で気づいて、 binaryIndexを生やしてカバーリング。👇
// 1. 変数保存
while (parser.hasMoreCommands()) {
parser.advance()
if (parser.commandType() == Parser.COMMAND_TYPE.L_COMMAND) {
// 次の行のbinaryIndexを保存
symbolTable.addEntry(parser.symbol(), parser.binaryIndex + 1)
} else {
// L命令ではないので、機械語として出力される=>機械語の行数をカウントアップ
parser.binaryIndex++
}
}
SymbolTableモジュール
class SymbolTable() {
var table = mutableMapOf<String, Int>()
init {
table.putAll(mapOf(
"R0" to 0,
"R1" to 1,
"R2" to 2,
"R3" to 3,
"R4" to 4,
"R5" to 5,
"R6" to 6,
"R7" to 7,
"R8" to 8,
"R9" to 9,
"R10" to 10,
"R11" to 11,
"R12" to 12,
"R13" to 13,
"R14" to 14,
"R15" to 15,
"SP" to 0,
"LCL" to 1,
"ARG" to 2,
"THIS" to 3,
"THAT" to 4,
"SCREEN" to 16384,
"KBD" to 24576
))
}
// 保存開始アドレス
var index = 16
fun addEntry(symbol: String, address: Int) {
table[symbol] = address
}
fun addEntry(symbol: String) {
table[symbol] = this.index++
}
fun contains(symbol: String): Boolean {
return table.contains(symbol)
}
fun getAddress(symbol: String): Int {
return table.get(symbol)!!
}
}
愚直に実装。特に面白い点なし。
Pong.hack
30000行近くのアセンブリを機械語に変換して実行。何気に面白い。