6 章 アセンブラ
前章までで CPU や Computer の実装が終わり、ハードウェアは完成した。次はソフトウェア部分ということで、一番下のレイヤであるアセンブラを書いていく。この章以降は HDL から離れて好きな言語でコードを書けることになるため、文字列操作に慣れた Python を使うことにした。
コマンドの判別
本書で用いられている機械語は 1 行 1 コマンドであり、@ で開始する A 命令、() で囲まれた L 命令、その他の C 命令のいずれかであるかを判定する必要がある。これは各行の最初の文字を見れば簡単に可能である。
L 命令の処理
- 例えば
(LOOP)という L 命令と@LOOPという A 命令があったとする。A 命令の方が先に登場した場合、まだシンボルテーブルに追加されていないため対応する ROM アドレスに変換することができない。そこで、1 周目の処理でまず L 命令を処理してしまい、そこで作成されたシンボルテーブルを用いて 2 周目で全体の変換を行う方針とする。 - 本書では機械語とバイナリで行数が変わらないため、ROM アドレスには現在の実行ファイルの行数を指定しておけばよい。
A 命令の処理
@の後に続くものが 32678 以下の数字であるなら、当該数字をバイナリに変換するだけでよい。その他の場合はまずシンボルテーブルを検索し、存在しなければ項目を追加することになる。新規シンボルには、まだ割り当てられていない RAM アドレスのうち最も若いものを割り振るようにする。- シンボルには予約語 (
SCREEN,SP,R0など) が存在するため、変換開始前に登録しておく必要がある。
C 命令の処理
- まあまあややこしかったので専用のクラスを作ることにした。
111から開始するのはいいとして、そのあとは comp 領域、dest 領域、jump 領域に分けて実装していくことになる。 - jump 領域は
;の右側、dest 領域は=の左側、comp 領域は=の右側に依存しているので、地道にそれぞれの処理を書いていけばよい。この部分に限ったことではないけど、正しいコードを正しくパースして変換できるようにするだけでも大変なのに、このうえ Syntax error を検知するのはめちゃくちゃきついなという実感があった。例えば下の自作アセンブラはM = A = 1みたいなあからさまに間違った機械語が書かれていた場合でも一応アセンブル自体は通ってしまうわけで、世の中のちゃんとしたアセンブラ/コンパイラ/インタプリタ書いてる人はちゃんと例外処理をしたうえで人間に理解可能なエラーメッセージを出力していて本当にえらいという気持ちに。
実装
上記をまとめると以下のようになる。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
import re
import pathlib
import config
import sys
class CParser():
def __init__(self, line: str, binary_list: 'list[int]') -> None:
self.line = line
self.binary_list = binary_list
def updateDbit(self) -> None:
"""
Update binary_list when dest exists (when '=' is in the line)
"""
if '=' not in self.line:
return
# Extract left side of the '=' (dest)
mnemonic: str = self.line.split('=')[0]
# if mnemonic == 'null':
# return
if 'A' in mnemonic:
self.binary_list[10] = 1
if 'D' in mnemonic:
self.binary_list[11] = 1
if 'M' in mnemonic:
self.binary_list[12] = 1
def updateCbit(self) -> None:
"""
Update binary_list following the C bits in the line
"""
# extract between '=' and ';'
mnemonic: str = self.line
if '=' in mnemonic:
mnemonic = self.line.split('=')[1]
if ';' in mnemonic:
mnemonic = mnemonic.split(';')[0]
# binary[3] (a) is 1 if comp contains 'M'
if 'M' in mnemonic:
self.binary_list[3] = 1
# Convert 'M' to 'A' in order to refer to comp_dic
mnemonic = mnemonic.replace('M', 'A')
# Refer to comp_dic and fill in the comp binary
b: str = config.comp_dic[mnemonic]
for i in range(6):
self.binary_list[i + 4] = str(b[i])
def updateJbit(self) -> None:
"""
Update binary_list when jump exists (when ';' is in the line)
"""
if ';' not in self.line:
return
mnemonic: str = self.line.split(';')[1]
b = config.jump_dic[mnemonic]
self.binary_list[13] = str(b[0])
self.binary_list[14] = str(b[1])
self.binary_list[15] = str(b[2])
def process(self) -> 'list[int]':
# The first three bits are 1
self.binary_list[0] = self.binary_list[1] = self.binary_list[2] = 1
# Update other bits
self.updateDbit()
self.updateCbit()
self.updateJbit()
return self.binary_list
class Parser:
def __init__(self, path: str) -> None:
self.path: str = path
with open(path) as f:
s: str = f.read()
s = s.replace(' ', '') # delete whitespaces
s = re.sub(r'//.*\n', '\n', s) # delete comments
self.lines: list[str] = [line for line in s.split('\n') if line != ''] # split by \n and delete black lines
self.symbol_dic: dict[str, str] = config.symbol_dic
self.clearCache()
def clearCache(self) -> None:
self.output: str = ""
self.output_file_row_idx: int = 0
self.next_memory_idx: int = 16
def combertNumToBinaryStr(self, num: int) -> str:
bin_str: str = format(num, 'b')
return bin_str.rjust(16, '0')
def commandType(self) -> str:
if self.line[0] == '@':
return 'A_COMMAND'
elif self.line[0] == '(':
return 'L_COMMAND'
else:
return 'C_COMMAND'
def extractSymbol(self) -> str:
# Extract symbol str from L_COMMAND or A_COMMAND
return self.line.translate(str.maketrans({'(': '', ')': '', '@': ''}))
def processC(self) -> str:
"""
Process lines that start with neither '@' nor '('
"""
c_parser_obj = CParser(self.line, self.binary_list)
self.binary_list = c_parser_obj.process()
return ''.join([str(i) for i in self.binary_list])
def processA(self) -> str:
"""
Process lines that start with '@'
"""
# Extract symbol str
symbol_mnemonic: str = self.extractSymbol()
# If the input is like '@10'
if symbol_mnemonic.isdecimal():
# If the number is more than 32678, it is invalid as an ROM address and is regarded as a symbol
if int(symbol_mnemonic) < 32768:
bin_str = self.combertNumToBinaryStr(int(symbol_mnemonic))
return bin_str
# If the input is a symbol like '@i' or '@40000'
# If already exist in symbol dic
if symbol_mnemonic in self.symbol_dic:
return self.symbol_dic[symbol_mnemonic]
# If new symbol
bin_str = self.combertNumToBinaryStr(self.next_memory_idx)
self.symbol_dic[symbol_mnemonic] = bin_str
self.next_memory_idx += 1
return bin_str
def processL(self) -> None:
"""
Process lines that start with '('
"""
# Extract symbol str
symbol_mnemonic: str = self.extractSymbol()
# Convert the ROM address to binary string
bin_str: str = self.combertNumToBinaryStr(self.output_file_row_idx)
# Update symbol_dic
self.symbol_dic[symbol_mnemonic] = bin_str
def saveToFile(self) -> None:
p_file = pathlib.Path(self.path)
path_w: pathlib.Path = p_file.with_suffix('.hack')
with open(path_w, mode='w') as f:
f.write(self.output)
def firstRun(self) -> None:
# In the first run, only L_COMMAND is processed
for line in self.lines:
self.line = line
if line[0] == '(':
self.processL()
else:
self.output_file_row_idx += 1
self.clearCache()
return
def secondRun(self) -> None:
for line in self.lines:
self.line = line
self.binary_list: list[int] = [0 for _ in range(16)]
command_type: str = self.commandType()
if command_type == 'L_COMMAND':
continue
# If not L_COMMAND, one row will be added to the output file
self.output_file_row_idx += 1
result: str = ''
if command_type == 'C_COMMAND':
result = self.processC()
else:
result = self.processA()
self.output += result + '\n'
self.saveToFile()
self.clearCache()
return
if __name__ == '__main__':
path = sys.argv[1]
parser_obj = Parser(path)
parser_obj.firstRun()
parser_obj.secondRun()
デフォルトのシンボルテーブルや予約語処理用辞書は別ファイルにまとめて同ディレクトリに置いておくことにする。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
jump_dic = {
'null': '000',
'JGT': '001',
'JEQ': '010',
'JGE': '011',
'JLT': '100',
'JNE': '101',
'JLE': '110',
'JMP': '111'
}
comp_dic = {
'D|A': '010101',
'D&A': '000000',
'A-D': '000111',
'D-A': '010011',
'D+A': '000010',
'A+D': '000010',
'A-1': '110010',
'D-1': '001110',
'A+1': '110111',
'1+A': '110111',
'D+1': '011111',
'1+D': '011111',
'-A': '110011',
'-D': '001111',
'!A': '110001',
'!D': '001101',
'A': '110000',
'D': '001100',
'-1': '111010',
'1': '111111',
'0': '101010',
}
symbol_dic = {
'SP': '0000000000000000',
'LCL': '0000000000000001',
'ARG': '0000000000000010',
'THIS': '0000000000000011',
'THAT': '0000000000000100',
'R0': '0000000000000000',
'R1': '0000000000000001',
'R2': '0000000000000010',
'R3': '0000000000000011',
'R4': '0000000000000100',
'R5': '0000000000000101',
'R6': '0000000000000110',
'R7': '0000000000000111',
'R8': '0000000000001000',
'R9': '0000000000001001',
'R10': '0000000000001010',
'R11': '0000000000001011',
'R12': '0000000000001100',
'R13': '0000000000001101',
'R14': '0000000000001110',
'R15': '0000000000001111',
'SCREEN': '0100000000000000',
'KBD': '0110000000000000'
}
検証
本章では、自作アセンブラが吐いたバイナリと付属の正しいアセンブラが吐いたバイナリの diff をみることによるデバッグが必要となる。少し作業を楽にするための tips として以下のようなものが有効であった。
- 付属のアセンブラが吐いたバイナリを git commit しておき、diff をエディタ上で確認できるようにしておく
- 以下のようなシェルスクリプトを置いておき、複数ファイルの出力をまとめてテストできるようにしておく
1
2
3
4
5
6
7
python -u "Assembler.py" ./add/Add.asm
python -u "Assembler.py" ./max/MaxL.asm
python -u "Assembler.py" ./max/Max.asm
python -u "Assembler.py" ./pong/PongL.asm
python -u "Assembler.py" ./pong/Pong.asm
python -u "Assembler.py" ./rect/RectL.asm
python -u "Assembler.py" ./rect/Rect.asm