コンパイラを自作する。

こんにちは、こんばんは。高崎です。

この記事はCCS Advent Calendar 2019 †裏†の10日目の記事です。

adventar.org

前日は

yoooomaruuuu.hatenablog.com

でした。

プログラマの皆さんは必ずやりたい3つの夢を持っていると思います(※個人の感想です)。

自作os、自作cpu、自作言語のこの3つです。今回は自作言語の中でもコンパイラに焦点を当ててみました。

コンパイラとは

コンパイラとは言語aを言語bに変換するプログラムのことです。

今回は「5+4-3」という文字列を受け取って「6」を返すようなコンパイラを作っていきたいと思います。機能としては加減算のみとします。理由は積除算が入ると計算順序を考える必要があり、この記事の中では解説しきれなくなるからです。申し訳ないです。

環境構築

環境としてはLinux(Ubuntuなど)でCPUはx64を想定しています。

理由としてはツールが手に入りやすいのと、情報が多いこと、アセンブリ言語の関係です。

環境構築としては最低限、gccとbinutilsが入っていれば動くと思います。

CPUとアセンブラ

CPUは中央処理装置または中央演算処理装置の頭文字でコンピューターの脳に相当する部分です。このCPUがメモリから機械語を読み取ってデコードし、計算結果を返すのがプログラムの基本的な流れです。

機械語は0と1で表されたCPUが解釈可能なデータ列のことで、画像やテキスト、動画などは実は01の2つの数字の列で表すことができます。このあたりは皆さんご存知なのではないでしょうか。

アセンブラについて知らない方もいるかも知れません。現在、C言語などのプログラミング言語は直接機械語に翻訳されることはほとんど無いです。一回中間表現やアセンブリ言語に翻訳されてから機械語に翻訳されています。これは多くのCPUに対応するため柔軟さをもたせた結果でもあります。

CPUが異なると同じ機械語でも異なる命令ととらえたり、解釈できないことがおこるためこんな仕組みになっています。JavaやC#はまた少し違った仕組みをしているので気になる方は調べてみてください。

話しがそれました、アセンブラについて話しましょう。

アセンブリ言語は機械ごと一対一に対応した、人がわかりやすいかたちに直した言語のことで、アセンブラはそのアセンブリを機械語に翻訳するプログラムのことです。人にわかりやすいというのがどういうことなのかというと

アセンブリだと「MOV EAX, 01234567」のようにかけますが、機械語だと「B867452301」と書かなくてはなりません。ちょっとどころではなく難しいですね。このあたりの詳しい話は昨年のアドベントカレンダーの私のスライドショーを見ていただければ解ると思います。

足し算引き算ができるコンパイラ

さて、本題です。足し算引き算ができるコンパイラを作ってみましょう。「これのどこがコンパイラなんだよ」と思う方もいるかも知れませんが、定義的にはこれも立派なコンパイラなので安心してみていてください。

まずは一個の数字を返すプログラムを書いてみましょう。

C言語だと

int main(int argc, char **argv) { return 42; }

みたいなかんじのものになると思います。

これをアセンブリで書いてみると

.intel_syntax noprefix

.global main

main:

mov rax, 42

ret

これをtest.sと名前をつけて

gcc -o test test.s

./test

echo $?

これで42が表示されると思います。x64のアセンブリではraxに帰り値を渡しておくという規則があるためraxを使っています。また、最初の「.intel_syntax noprefix」はおまじないみたいなものです。今回は説明しません。

アセンブリをc言語で書いて、そして拡張し値を一つ受け取ってそれを返すようにしてみましょう。

#include <stdio.h>

int main(int argc, char **argv) {

printf(".intel_syntax noprefix\n");

printf(".global main\n");

printf(".global main\n");

printf("main:\n");

printf(" mov rax, %d\n", atoi(argv[1]));

printf(" ret\n");

これをminicc.cとして保存して次のコマンドを実行してみてください

gcc -o minicc minicc.c

./minicc 123 > tmp.s

gcc -o tmp tmp.s

echo $?

すると123が得られていることが解ると思います。次は一気に足し算引き算を実装してみましょう。

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
　char *p = argv[1];

　printf(".intel_syntax noprefix\n");
　printf(".global main\n");
　printf("main:\n");
　printf(" mov rax, %ld\n", strtol(p, &p, 10));

　while (*p) {
　　if (*p == '+') {
　　　p++;
　　　printf(" add rax, %ld\n", strtol(p, &p, 10));
　　　continue;
　　}

　　if (*p == '-') {
　　　p++;
　　　printf(" sub rax, %ld\n", strtol(p, &p, 10));
　　　continue;
　　}

　　return 1;
　}

　printf(" ret\n");
　return 0;
}

最初に数字を読み込んで、strtolでポインターを更新し(1文字か2文字かそれ以上かわからないためこの関数を呼んでポインターの更新を行っております)、pが1文字読んで「+」ならaddの命令を、「-」ならsubの命令を読んで、引数にまたstrtolを呼んでいます。

これに以下のコマンドを実行すると、

gcc -o minicc minicc.c

./minicc '12+34-5' > tmp.s

gcc -o tmp tmp.s

echo $?

とすると、41が得られていると思います。

./minicc '12+34-5'の部分を色々いじってみてください。ちゃんと計算されていることが解ると思いますし、tmp.sをみるとちゃんとアセンブリが書かれていることが解ると思います。これで、足し算引き算ができるコンパイラが完成しました。当初の目的、完遂しましたね！お疲れ様です。

この先

これ以上のことを話すと本が書けるレベルの長さになります。というか本になってます。この記事の元ネタもこの本からお借りしています。

www.sigbus.info

興味のある方は再帰下降構文解析やlex、yaccなど調べてみると良いかも知れません。

今、私が自作しているc言語のコンパイラは四則演算、比較演算子、単項演算子、整数型、文字型、ポインター型、構造体、アロー演算子、関数定義、関数呼び出し、ローカル変数、グローバル変数、if文、for文、while文、配列、sizeof演算子などが実装されています。typedefなどの機能が実装できれば自分で自分をコンパイルできるようになる、いわゆるセルフホスティングができるようになります。現在はそれを目指しています。またリンカー、ローダーの開発も行って、アセンブラの開発も行い、オレオレツールチェインを目指すのもいいかも知れません。