前章でアセンブリ言語からバイナリへの変換ができるようになったため、次は一段階上がってコンパイラを書いていく。本書では Jack という簡易版 Java みたいな高水準言語の処理系を実装していくことになるのだが、これはまず中間コード (VM コード) を経てアセンブリ言語に変換される形式を採っている。7 章および 8 章では、VM コードをアセンブリ言語に変換する VM translator を作成する。
7 章 バーチャルマシン #1: スタック操作
メモリセグメント操作
この章ではスタック操作を扱う。スタックポインタを SP とすると、例えば push constant 2 のように、定数の 2 をスタックのトップに追加する場合は以下のように変換すればよい。*(*(SP)) = 2 という操作をしたあとで、スタックポインタをインクリメントする形になる。
1
2
3
4
5
6
7
@2
D = A
@SP
A = M
M = D
@SP
M = M + 1
この VM には local というセグメントがあり、関数内で定義されたローカル変数は local セグメント (ベースアドレスは @LCL で指定されている) でアクセスできるようになる。例えば pop local 2 は *(*(@LCL) + 2) をスタックのトップにある値で更新する形になる。これをアセンブリ言語で書くと、次のような問題が発生する。
1
2
3
4
5
6
// --- この前にスタックポインタをデクリメントする操作が入る ---
@SP
A = M
D = M // ここでスタックトップの値を D に格納
@2
// ここでいつも通り D = 2 としたいが、そうすると上で格納した D の値が上書きされてしまう
最初にこの本を読んだ際はなんか適当なシンボルを新たに定義してそこを一時的な退避場所として指定していたが、強い人のコード を見たところ @2 とせずに以下の方法で解決していた。なるほど確かに。
1
2
3
4
5
@LCL
A = A + 1
A = A + 1 // 単に定数の回数だけ A をインクリメントすればよい
M = D
// --- この後にスタックをデクリメントする操作が入る ---
また、この VM では pointer というセグメントが用意されており、pointer 0 は this を、pointer 1 は that を指す。例えば pop pointer 0 の場合だと this のベースアドレス (RAM[3] に格納されている値) をスタックの一番上にある値で更新することになる。ややこしいが、pop that 0 の場合は that が指しているアドレスの値 をスタックの一番上の値で更新することになるので注意。
定数でもローカル変数でもポインタでもないものは static で宣言することになっており、例えば hoge.vm にある push static 3 は
1
2
3
@hoge.3
D = M
// 以下、D をスタックにプッシュする処理
のように変換される。これは何か static というセグメントが存在してそれの 3 番目ということではなく、単に一意になるようシンボルを命名しているだけである。
スタック算術
add, sub, and, or はいいとして問題は大小比較を行う演算子である。条件分岐を行い、true の場合はスタックトップに -1 を、false の場合は 0 を格納することになる。例えば eq の場合以下のようなコードを目指すことになる。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@SP
M = M - 1 // decrement SP
@SP
D = M // first operand
A = A - 1
D = M - D // second - first
@TRUE1
D;JEQ
@SP // false
A = M - 1
M = 0
(BACK1)
...
(TRUE1) // true
A = M - 1
M = -1
@BACK1
0;JMP
2 項演算子ならスタックポインタをデクリメントする必要があるが、neg や not ではその必要がないので注意。
完成したコード
以上まとめると次のようになる。
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
186
187
188
189
190
191
192
193
194
195
196
197
import re
import pathlib
import sys
class CodeWriter:
def __init__(self, path) -> None:
self.setFileName(path)
self.dic = {
'local': '@LCL',
'argument': '@ARG',
'this': '@THIS',
'that': '@THAT',
'pointer': '@3',
'temp': '@5',
}
self.snippets = {
'increment_sp': ['@SP', 'M = M + 1'],
'decrement_sp': ['@SP', 'M = M - 1'],
'copy_d_to_stack_top': ['@SP', 'A = M', 'M = D'],
'from_stack_top_value_to_d': ['@SP', 'A = M', 'D = M'],
'update_address_to_top': ['@SP', 'A = M'],
'move_address_backward': ['A = A - 1']
}
self.output: str = ''
self.appendix: str = ''
self.appendix_idx: int = 0
def setFileName(self, path) -> None:
self.p_file = pathlib.Path(path)
self.filename: str = self.p_file.stem # get filename
self.path_w = self.p_file.with_suffix('.asm')
def processPush(self, arg1: str, arg2: str) -> None:
if arg1 == 'constant':
# Place num to stack top. ex) 'push constant 2'
self.addOutputLines([f'@{arg2}', 'D = A'])
elif arg1 == 'static':
# Place the value of a symbol to stack top. ex) 'push static 1'
# Create the name of the symbol. ex) '@filename.1'
self.addOutputLines([f'@{self.filename}.{arg2}', 'D = M'])
elif arg1 == 'pointer' or arg1 == 'temp':
# Place the address of this (pointer[0]) or that (pointer[1]) to stack top. ex) 'push pointer 1', or
# Place the value of temp to stack top. ex) 'push temp 1'
self.addOutputLines([f'@{arg2}', 'D = A', f'{self.dic[arg1]}', 'A = A + D', 'D = M'])
else: # argument, local, this, that
# Place the value of the specified segment[idx] to stack top. ex) 'push argument 3'
self.addOutputLines([f'@{arg2}', 'D = A', f'{self.dic[arg1]}', 'A = M + D', 'D = M'])
self.addOutputLines(self.snippets['copy_d_to_stack_top'] + self.snippets['increment_sp'])
def processPop(self, arg1: str, arg2: str) -> None:
self.addOutputLines(self.snippets['decrement_sp'] + self.snippets['from_stack_top_value_to_d'])
if arg1 == 'constant':
# Remove num from stack top. ex) 'pop constant 2'
# Is 'pop constant' possible in .vm file?
self.addOutputLines([f'@{str(arg2)}', 'M = D'])
elif arg1 == 'static':
# Place the value of a stack top to a symbol. ex) 'pop static 1'
# Create the name of the symbol. ex) '@filename.1'
self.addOutputLines([f'@{self.filename}.{arg2}', 'M = D'])
else:
forward_A_arg2_times: list[str] = ['A = A + 1' for _ in range(int(arg2))]
if arg1 == 'pointer' or arg1 == 'temp':
# Place the value of the stack top to this (pointer[0]) or that (pointer[1]). ex) 'pop pointer 1', or
# Place the value of the stack top to temp. ex) 'pop temp 1'
self.addOutputLines([f'{self.dic[arg1]}'] + forward_A_arg2_times + ['M = D'])
else: # argument, local, this, that
# Place the value of the stack top to specified segment[idx]. ex) 'pop argument 3'
self.addOutputLines([f'{self.dic[arg1]}', 'A = M'] + forward_A_arg2_times + ['M = D'])
def processArithmetric(self, command: str) -> None:
if command == 'neg' or command == 'not':
self.addOutputLines(self.snippets['update_address_to_top'] + self.snippets['move_address_backward'])
self.addOutputLines(['M = -M'] if command == 'neg' else ['M = !M'])
return
self.addOutputLines(
self.snippets['decrement_sp']
+ self.snippets['from_stack_top_value_to_d'] # set the value of the second operand to D
+ self.snippets['move_address_backward']) # move address to the first operand
if command == 'add':
self.addOutputLines(['M = M + D'])
elif command == 'sub':
self.addOutputLines(['M = M - D'])
elif command == 'and':
self.addOutputLines(['M = D & M'])
elif command == 'or':
self.addOutputLines(['M = D | M'])
else: # eq, gt, lt
self.addOutputLines(['D = M - D', f'@TRUE{self.appendix_idx}'])
if command == 'eq':
self.addOutputLines(['D;JEQ'])
if command == 'gt':
self.addOutputLines(['D;JGT'])
if command == 'lt':
self.addOutputLines(['D;JLT'])
# If false, write 0 (false) to the top of the stuck
self.addOutputLines(['@SP', 'A = M - 1', 'M = 0', f'(BACK{str(self.appendix_idx)})'])
# If true, write -1 (true) to the top of the stuck
self.addAppendixLines([f'(TRUE{self.appendix_idx})', '@SP', 'A = M - 1',
'M = -1', f'@BACK{str(self.appendix_idx)}', '0;JMP'])
self.appendix_idx += 1
def addOutputLines(self, lines: 'list[str]') -> None:
self.output += '\n'.join(lines) + '\n'
def addAppendixLines(self, lines: 'list[str]') -> None:
self.appendix += '\n'.join(lines) + '\n'
def saveToFile(self) -> None:
if self.appendix != '':
self.output += '@END\n0;JMP\n' + self.appendix + '(END)\n'
with open(self.path_w, mode='w') as f:
f.write(self.output)
class Parser:
def __init__(self, path: str) -> None:
self.path: str = path
self.p_file = pathlib.Path(self.path)
with open(path) as f:
s: str = f.read()
s = re.sub(r'//.*\n', '\n', s) # delete comments
s = re.sub(r' *\n', '\n', s) # delete spaces at the end of lines
self.lines: list[str] = s.split('\n')
self.lines = [line for line in self.lines if line != ''] # delete black lines
self.line = self.lines[0]
self.line_num = len(self.lines)
self.current_line_num = 0
def commandType(self) -> str:
"""
Determine command type from a line
"""
command: str = self.line.split(' ')[0]
if command == 'push':
return 'C_PUSH'
elif command == 'pop':
return 'C_POP'
elif command == 'label':
return 'C_label'
elif command == 'goto':
return 'C_GOTO'
elif command == 'if-goto':
return 'C_IF'
elif command == 'function':
return 'C_FUNCTION'
elif command == 'return':
return 'C_RETURN'
elif command == 'call':
return 'C_CALL'
else:
return 'C_ARITHMETIC'
def arg1(self) -> str:
"""
Returns the first argument
"""
tmp = self.line.split(' ')
if len(tmp) != 1: # ex) 'local' in 'push local 0'
return tmp[1]
else: # When C_ARITHMETIC, the command itself is returned. ex) 'add'
return tmp[0]
def arg2(self) -> str:
"""
Returns the second argument.
This is called only when 'C_PUSH', 'C_POP', 'C_FUNCTION', or 'C_CALL'
"""
# ex) '0' in 'push local 0'
tmp = self.line.split(' ')
return tmp[2]
def hasMoreCommands(self) -> bool:
return True if self.current_line_num < self.line_num else False
def advance(self) -> bool:
print(self.current_line_num)
self.line = self.lines[self.current_line_num]
self.current_line_num += 1
if __name__ == '__main__':
path: str = sys.argv[1]
parser = Parser(path)
writer = CodeWriter(path)
while parser.hasMoreCommands():
parser.advance()
command_type: str = parser.commandType()
if command_type == 'C_ARITHMETIC':
writer.processArithmetric(parser.arg1())
elif command_type == 'C_PUSH':
writer.processPush(parser.arg1(), parser.arg2())
elif command_type == 'C_POP':
writer.processPop(parser.arg1(), parser.arg2())
writer.saveToFile()
感想
大昔 C 言語をかじったときはポインタのポインタとか具体的に何の役に立つのか全然分からなかったけど、こうして処理系を頑張って自作してみると必要性が実感できてよい。低レイヤは楽しいね。