コンパイラ自作
製作物概要
RPN表記の四則演算式をコンパイルできるコンパイラを製作します。入力をRPN式としたのは時間的な制約でパースする段階をすっ飛ばしたかったからです。前置表記でも良かったけどLispだとアレルギー出る人いるし
次のような順序で製作していきます。
整数をコンパイルするプログラム
RPNとスタックマシン
四則演算式をコンパイルできるように
整数をコンパイルするプログラム
まず、引数として整数を入力するとその整数を終了ステータスとして返すプログラムを標準出力に出力するコンパイラを書きます。
次のようなアセンブリを出力できるようにすれば勝ちです。
code:out.s
.intel_syntax noprefix
.globl main
main:
mov rax, <返す整数>
ret
ただしmacOSでは.globlで指定するエントリポイントは_mainとなるので、以降mainと出力すべきところは_mainに置き換えてください。
1行目はアセンブリ内でインテル構文を使うという指定です。
2行目はリンクのためmainラベルをglobal属性にしています。リンカの動きは難しくて僕も分かりません。
3行目以降が本体ですが、二つの命令しかありません。
mov命令は第二引数の値(今回は即値)を第一引数のレジスタに格納します。
retはreturnです。関数からの復帰を行います。
これを出力させるくらいC言語でコマンドライン引数を使えば楽勝ですね。
適当なディレクトリを作って中で書いていきましょう。
プログラム名はKC3 Calculator Compilerを略しkc5とします。
code:kc5.c
int main(int argc, char *argv[]) {
if(argc != 2) {
fprintf(stderr, "illegal number of arguments\n");
return 1;
}
puts(".intel_syntax noprefix");
puts(".globl main"); //mac勢は_main
puts("main:"); //mac勢は_main
printf(" mov rax, %d\n", atoi(argv1)); puts(" ret");
return 0;
}
実行してみましょう。
./kc5 42の実行結果をtmp.sに保存し、tmp.sをアセンブルして実行して終了ステータスを出力します。
gcc kc5.c -o kc5
./kc5 42 > tmp.s
gcc tmp.s -o tmp
./tmp
echo $?
実行結果で42が出力されれば成功です。
テストの作成
いちいちコンパイルして実行結果を保存しそれをアセンブルして実行、というのが大変なのでテストを書いていきます。
こんな感じのシェルスクリプトを書けばテストが実行できます。
code:test.sh
assert() {
expected="$1"
input="$2"
./kc5 "$input" > tmp.s
gcc -o tmp tmp.s
./tmp
actual="$?"
echo "$input => $actual"
else
echo "$input => $expected expected, but got $actual"
exit 1
fi
}
# Add your test expression -----
assert 0 '0'
assert 42 '42'
# ------------------------------
echo OK
書き終わったらchmod +x test.shで実行権限を与えましょう。
次にMakefileを書いていきます。Makefileを書くことでビルドを1コマンドで実行したりその他コマンドを定義したりできます。
コピペした時にScrapboxの仕様で変なスペースが入るかもしれないので手でインデントし直した方が良いかもです
code:Makefile
CFLAGS=-std=c11 -g
kc5: kc5.c
test: kc5
./test.sh
clean:
rm -f kc5 *.o tmp* a.out
.PHONY: test clean
1行目でコンパイルオプションを指定しています。
それからkc5, test, cleanコマンドを定義しています。
test: kc5から始まる2行ではmake testコマンドを実行したときにmake kc5を行った後test.shを実行することを意味します。makeはコマンド名(ここではtest)のコロンの後に書いたコマンドを行ってからそのコマンドを行います。2行目以降にそのコマンドを実行するときの操作を記述します。ここではtab文字を使うことに注意してください。
kc5: kc5.cではmake kc5を行ったときにkc5.cをコンパイルさせることを意味します。2行目のコマンドが省略されていますがこの場合依存ファイル(kc5.c)をCコンパイルしてくれます。
最後に、cleanコマンドを定義してmake cleanを行ったときに不要な一時ファイルや実行ファイルを一括削除できるようにしています。
.PHONYの行はmake testやmake cleanを行ったときにもしディレクトリにtest/cleanといったファイルが存在していてもそのファイルのコンパイルではなくコマンドの方を優先してくれます。
これでmakeコマンドを使ったビルドとテストができるはずです。
RPNとスタックマシン
RPNとは逆ポーランド記法とも呼ばれ演算子を後置する記法です。
例
1 + 2 => 1 2 +
1 + 2 + 3 => 1 2 + 3 +
スタックマシンはスタックをデータ保存領域として持っているコンピュータを指します。
スタックマシンとRPNは相性が良く、RPNを一要素ずつ処理することでそのままスタック上で演算することができます。
code:(3 + 4) * (1 - 2)を計算する例
// 3 + 4を計算
PUSH 3
PUSH 4
// 1 - 2を計算
PUSH 1
PUSH 2
// (3 + 4) * (1 - 2)を計算
実際には、x86_64はスタックマシンではなくレジスタマシンです。しかし、メモリ領域のスタックと二つの汎用レジスタを活用することでスタックマシンの動きをエミュレートできます。
x86_64にはメモリのスタック領域の先頭に値を追加するpush命令と先頭から値を取り出すpop命令が存在します。そのため、演算子を適用するにはスタック領域の先頭2値をrdi,raxの二つのレジスタにそれぞれpopし、演算を行ってその結果を改めてpushすれば良いのです。
つまり先ほどの(3 + 4) * (1 - 2)を計算するアセンブリは次のようになります。
code:out.s
.intel_syntax noprefix
.globl main
main:
push 3
push 4
pop rdi
pop rax
add rax, rdi
push rax
push 1
push 2
pop rdi
pop rax
sub rax, rdi
push rax
pop rdi
pop rax
imul rax, rdi
push rax
pop rax
ret
四則演算式をコンパイルできるように
ここまでを理解したところで、いよいよ実装していきます。
まずは加算に対応させます。
引数で文字列を受け取ったら文字ポインタを用いて一文字ずつ見ていきます。
code:kc5.c
//ctype.hヘッダを追加
int main(int argc, char *argv[]) {
//エラー処理は省略,下3行も先ほどのコードと同じまま
puts(".intel_syntax noprefix");
puts(".globl main");
puts("main:");
//新たに文字ポインタ変数pを用意
//argv1の最後の文字まで一字ずつ見ていくループ while(*p) {
//空白文字なら次の文字へ
if(isspace(*p)) {
p++;
continue;
}
//数値なら最後の桁まで読み、その値をスタックにpush
if(isdigit(*p)) {
int n = 0;
while(isdigit(*p)) {
n = n * 10 + (*p - '0'); // 312 => (3 * 10 + 1) * 10 + 2のように計算される
p++;
}
printf(" push %d\n", n);
continue;
}
//+演算子なら先頭2値をレジスタにpopし、それらを足した後結果をpushする
if (*p == '+') {
puts(" pop rdi");
puts(" pop rax");
puts(" add rax, rdi");
puts(" push rax");
p++;
continue;
}
// どれにも当てはまらなければエラー
fprintf(stderr, "unexpected character: '%c'\n", *p);
return 1;
}
//先ほどのコードにあったmov rax, atoi(argv1)の行は削除 puts(" pop rax");
puts(" ret");
return 0;
}
ここまで書けば足し算ができるようになります。
test.shの最後の方にassert 10 '2 8 +'のような式を追加してテストしていきましょう。
code:test.sh
...(前半省略)
# Add your test expression -----
assert 0 '0'
assert 42 '42'
assert 10 '2 8 +'
assert 47 '32 15 +'
# ------------------------------
echo OK
あとは条件分岐に演算子を追加すれば良いだけです。
-演算:sub rax, rdi
raxとrdiに値をpopする順序に気を付けましょう。5 4 -はスタックには[4 5](右がスタックの底方向)のように積まれているので、先にrdiにpopしてからraxにpopする必要があります。
*演算:imul rax, rdi
imul命令は符号付乗算を行う。
/演算:cqo命令の後にidiv rdiを行う
idiv命令は暗黙のうちにrdxとraxレジスタを合わせた128bitを取ってそれを引数のレジスタの値で割り、商をrax、余りをrdxにセットする。したがってraxに入っている値を128bitに引き延ばしてrdxとraxにセットできるcqo命令を事前に呼んでいる。
code:kc5.c
int main(int argc, char *argv[]) {
if(argc != 2) {
fprintf(stderr, "illegal number of arguments\n");
return 1;
}
puts(".intel_syntax noprefix");
puts(".globl main");
puts("main:");
while(*p) {
if(isspace(*p)) {
p++;
continue;
}
if(isdigit(*p)) {
int n = 0;
while(isdigit(*p)) n = n * 10 + (*p++ - '0');
printf(" push %d\n", n);
continue;
}
if(*p == '+') {
puts(" pop rdi");
puts(" pop rax");
puts(" add rax, rdi");
puts(" push rax");
p++;
continue;
}
if(*p == '-') {
puts(" pop rdi");
puts(" pop rax");
puts(" sub rax, rdi");
puts(" push rax");
p++;
continue;
}
if(*p == '*') {
puts(" pop rdi");
puts(" pop rax");
puts(" imul rax, rdi");
puts(" push rax");
p++;
continue;
}
if(*p == '/') {
puts(" pop rdi");
puts(" pop rax");
puts(" cqo");
puts(" idiv rdi");
puts(" push rax");
p++;
continue;
}
fprintf(stderr, "unexpected character: '%c'\n", *p);
return 1;
}
puts(" pop rax");
puts(" ret");
return 0;
}
最後に四則演算のテストを追加しましょう。
好きなRPN式を追加してください。テストが通れば完成です。
code:test.sh
...
assert 4 '9 5 -'
assert 25 '5 5 *'
assert 2 '8 4 /'
assert 21 '5 20 + 4 -'
assert 47 '6 7 * 5 +'
assert 15 '9 6 - 5 *'
assert 4 '3 5 + 2 /'
...
お疲れさまでした!