Cコンパイラ作成入門①〜トークナイザの導入まで
低レイヤを知りたい人のためのCコンパイラ作成入門は、最初に電卓程度の機能しか無いコンパイラを作り、徐々に機能を付け足していくという内容である。今回はステップ１〜ステップ３までを自分用にまとめてみる。
すでに知っていたことや、まとめるのが面倒になってしまったこと、結局よくわからないまま読み飛ばしたことは省略した。逆に、わからなかったけれど調べたらなにかわかったような部分については説明を補足している。
開発環境については上記リンク先の「本書の想定する開発環境」参照。なお私の環境は Ubuntu 18.04.4 LTS である。
はじめに〜ステップ１：整数1個をコンパイルする言語の作成
上記リンク先で使用するコマンドをインストールする。Ubuntuの場合は端末で以下のコマンドを実行すればよい。
$ sudo apt update $ sudo apt install -y gcc make git binutils libc6-dev
オプション-yをつけると、すべてのプロンプトに自動的に"yes"と答え、非対話的に実行する（但し、不適切な処理がなされるときは実行を中断する）。
コンパイラ本体の作成
gcc などのコンパイラでは、CプログラムファイルX.cを以下のようにコンパイルすると、$ cc -o X X.c
前処理→コンパイル→アセンブル→リンク
という処理を行う。
我々が目指すのは、Cプログラムファイルをアセンブリ言語で書かれたファイルに変換することだ。アセンブリ言語から機械語への翻訳はアセンブラに任せる。
さて、ここではコンパイラ名を「9cc」としよう（コンパイラ名は各自、自由に名付ければよい）。ステップ１では「整数1個をコンパイルする言語」を作成する。
まずは作業ディレクトリ9ccを作成する。今後ファイルを新規作成するときは、断りのない限りこのディレクトリで作成するものとする。さて、以下のCプログラムファイル9cc.cを作成する。
#include <stdio.h> #include <stdlib.h> int main(int argc, char **argv) { if (argc != 2) { fprintf(stderr, "引数の個数が正しくありません\n"); return 1; } printf(".intel_syntax noprefix\n"); printf(".globl main\n"); printf("main:\n"); printf(" mov rax, %d\n", atoi(argv[1])); printf(" ret\n"); return 0; }
ちなみにコマンドライン引数argc，argvの中身は、例えば
$ cc -o 9cc 9cc.c $ ./9cc 123
とコンパイル＆実行したとき以下のようになる。
| コマンドライン引数 | 中身 | 説明 |
|---|---|---|
| argc | 2 | 配列argvの要素数 |
| argv[0] | "./9cc" | プログラム名 |
| argv[1] | "123" | 第１引数 |
次にatoi関数は文字列を渡すと、int型整数に変換して返してくれる。atoi( "123ABC" )の値は123、atoi( "456" )の値は456となる。
さて、9cc.cを以下のようにコンパイル＆実行してみよう。
$ cc -o 9cc 9cc.c
$ ./9cc 357
.intel_syntax noprefix
.globl main
main:
mov rax, 357
ret
思い通りの出力結果が得られた。この結果をファイルtmp.sに出力してみよう。
$ ./9cc 357 > tmp.s
ファイルtmp.sの中身は、以下のCプログラムをアセンブリ言語に変換したものと等しい。
int main() { return 357: }
ちなみにtmp.sの中身
.intel_syntax noprefix
.globl main
main:
mov rax, 357
ret
の一行目は、複数あるアセンブラの書き方の中でIntel記法というものを選ぶためのアセンブラコマンドである。お約束として書いておく。main:内のmov rax, 357とはレジスタraxに値357を書き込むという意味だ。
さらにtmp.sをアセンブルして、作成された実行ファイルtmpを実行しよう。
$ cc -o tmp tmp.s $ ./tmp $ echo $? 357
すると終了コードは最初にわたした引数357と等しくなる。
自動テスト
次に、テストを行うためのプログラムを作成する。以下のシェルスクリプトtest.shを作成しよう。
#!/bin/bash
assert() {
expected="$1"
input="$2"
./9cc "$input" > tmp.s
cc -o tmp tmp.s
./tmp
actual="$?" ## 終了コード＝$expectedになるはず…
if [ "$actual" = "$expected" ]; then
echo "$input => $actual"
else
echo "$expected expected, but got $actual"
exit 1
fi
}
assert 0 0
assert 42 42
echo OK
実行結果：
0 => 0 42 => 42 OK
例えばassert 42 42 では、第２引数の値42を自作コンパイラでコンパイルしたときの終了コードが、第１引数の値42に等しいかどうか確かめている。
makeによるビルド
毎回コマンドを打ち込むのは面倒なのでMakefileを作成する。Makefileという名前のファイルを以下の内容で作成する。
CFLAGS=-std=c11 -g -static
9cc: 9cc.c
test: 9cc
./test.sh
clean:
rm -f 9cc *.o *~ tmp*
.PHONY: test clean
ターゲット9cc，test，cleanについて説明する。
まずはターゲット9ccについて。$ makeは$ make 9ccと同じである。コマンド$ makeを実行するだけで、9cc.cをコンパイルして実行ファイル9ccを生成する。
$ make cc -std=c11 -g -static 9cc.c -o 9cc`
正確には9cc.cがコンパイル済み&実行ファイル9cc生成済みのときは何もしない。
$ make make: '9cc' は更新済みです. $ touch 9cc.c $ make cc -std=c11 -g -static 9cc.c -o 9cc`
touchコマンドで最終更新日時を今の日時に変えると、再びコンパイルが行われる。勿論9cc.cの内容に変更を加えても、再びコンパイルが行われる。
次はターゲットtestについて。$ make testを行うとどうなるか。
$ make test ./test.sh 0 => 0 42 => 42 25+2-6 => 21 OK
テストを行ってくれる。$makeのときと同様に、必要があればターゲット9ccの処理も行ってくれる。
$ touch 9cc.c $ make test cc -std=c11 -g -static 9cc.c -o 9cc ./test.sh 0 => 0 42 => 42 OK
最後にターゲットcleanについて。$ make cleanでテンポラリファイルを削除する。手動で消すと間違える可能性があるため書かれた。
これで最初のCコンパイラは完成。使ってみよう。
$ ./9cc 123 > tmp.s $ ./tmp $ echo $? 123
最後にGitHubへのアップロードをする。
gitによるバージョン管理
GitHubへのユーザ登録などの準備は済んでいるものとする。
手で書いたファイル（9cc.c，test.sh，Makefile等）しかバージョン管理しない。コマンドを実行することで生成されるようなファイル（9cc，tmp.s，tmp等）は、バージョン管理から外す。
gitでは.gitignoreというファイルに、バージョン管理から外すファイルのパターンを書いておくことができる。今回はテンポラリファイルやエディタのバックアップファイルなどを外す。そのために、以下の内容でファイル.gitignoreを作成しよう。
*~ *.o tmp* a.out 9cc
さて、現在のディレクトリ9ccで以下のコマンドを実行し、ローカルリポジトリを作成する。
$ git init
次にバージョン管理したいファイルをローカルリポジトリのインデックスに追加する。
$ git add 9cc.c test.sh Makefile .gitignore
次にそれらのファイルをローカルリポジトリにcommitする。
$ git commit -m "整数1つをコンパイルするコンパイラを作成"
次にgit remoteでアドレスgit@github.com:naomeo/9cc.gitの短縮名をoriginと設定する。originと名付けるのは慣習なので、自分で違う名前を設定してもよい。masterはデフォルトのブランチ名である。naomeo部分はgitのアカウント名、9cc部分はリポジトリ名である。
$ git remote add origin git@github.com:naomeo/9cc.git
最後にローカルリポジトリの中身を、originという名のリモートサーバの、masterブランチに追加する。
$ git push origin master
プラウザでGitHubの自分のページを見ると、新しい更新が確認できるはずだ。
ステップ２：加減算のできるコンパイラの作成
このステップでは、以下のような挙動を目指す。
$ ./9cc "10+2-3" > tmp.s $ cc -o tmp tmp.s $ ./tmp $ echo $? 9
計算はアセンブラに行わせたい。10+2-3ならこんなアセンブリコードになるはず。
.intel_syntax noprefix
.globl main
main:
mov rax, 10
add rax, 2
sub rax, 3
ret
ファイル9cc.cの内容は以下のようになる。
#include <stdio.h> #include <stdlib.h> int main(int argc, char **argv) { if (argc != 2) { fprintf(stderr, "引数の個数が正しくありません\n"); return 1; } char *p = argv[1]; printf(".intel_syntax noprefix\n"); printf(".globl main\n"); printf("main:\n"); // 最初の数字 printf(" mov rax, %ld\n", strtol(p, &p, 10)); while(*p) { if(*p == '+') { p++; printf(" add %ld\n", strtol(p, &p, 10)); continue; } if(*p == '-') { p++; printf(" sub %ld\n", strtol(p, &p, 10)); continue; } fprintf(stderr, "予期しない文字です : '%c'\n", *p); return 1; } printf(" ret\n"); return 0; }
strtol関数は文字列をlong int型整数に変換する。ヘッダstdlib.hで定義されており、形式はlong int strtol(const char* s, char** endptr, int radix)
である。radixには2から32の数字を入れる。radixを基数にして文字列sをlong int型に変換し、変換できなかった最初の文字から始まる文字列をendptrに格納する。返り値は読み取った文字。以下に例を示した。
#include <stdio.h> #include <stdlib.h> int main() { char *p; p = NULL; printf("返り値： %ld, ", strtol("17", &p, 10)); printf("p： %s\n", p); printf("返り値： %ld, ", strtol("17", &p, 16)); printf("p： %s\n", p); printf("返り値： %ld, ", strtol("17abc", &p, 10)); printf("p： %s\n", p); printf("返り値： %ld, ", strtol("abc17", &p, 10)); printf("p： %s\n", p);xx return 0; }
実行結果：
返り値： 17, p： 返り値： 23, p： 返り値： 17, p： abc 返り値： 0, p： abc17
テストファイルtest.shにテストを書き足しておく。
assert 10 '2+11-3' assert 10 `24-7-7'
ここまでの変更をgitに記録しておこう。
$ git add 9cc.c test.sh $ git commit
$ git commitと入力するとエディタが開く。そこに「足し算と引き算を追加」なるコメントを書き込もう。最後にpushでGitHubに更新をプッシュすればステップ２は完了だ。
$ git push origin master
ステップ３：トークナイザの導入
上のコンパイラでは、記号'+'や'-'の直前に空白を入れるとエラーになる。
$ ./9cc '3 +1' > tmp.s 予期しない文字です : ' '
今回はそれを解決したい。
ちなみに数字の直前に空白を入れてもエラーにはならない。
$ ./9cc ' 3+ 1' > tmp.s
なぜならstrtol関数が勝手に空白を無視してくれているからだ。
char *p; strtol(" 123abc", &p, 10); // 123 strtol(" 123+", &p, 10); // 123
さて、この問題を解決するにはどうすればいいだろうか。入力された文字列を読み取るときに空白文字を飛ばしても解決できる。しかしここでは違う方法をとる。
例えば'2 + 3 - 1'は'2', '+', '3', '-', '1'と５つの単語(token)に分解できる。このトークン列に対して処理を施せばよい。入力された文字列を単語に分解することを「トークナイズする」と言う。
コードは以下のようになる。
#include <ctype.h> #include <stdarg.h> #include <stdbool.h> #include <stdio.h> #include <string.h> #include <stdlib.h> // トークンの種類 typedef enum { TK_RESERVED, // 記号 TK_NUM, // 整数 TK_EOF // 入力の終わりを表す }TokenKind; // トークンの型 typedef struct TokenDummy Token; struct TokenDummy { TokenKind kind; Token *next; // 次のトークン long int num; // 数値（整数トークンであれば） char *str; // トークン文字列 }; // 現在着目しているトークン Token* token; // エラーを報告するための関数 // printf と同じ引数を取る void error( char *fmt, ... ) { va_list args; va_start( args, fmt ); vfprintf( stderr, fmt, args ); fprintf( stderr, "\n" ); exit(1); } // 今のトークンが期待している記号のときには、トークンを1つ読み進めて // 真を返す。それ以外の場合には偽を返す。 bool consume(char op) { if( token->kind != TK_RESERVED || token->str[0] != op ) return false; token = token->next; return true; } // 今のトークンが期待している記号のときには、トークンを1つ読み進める。 // それ以外の場合にはエラーを報告する。 void expect(char op) { if( token->kind != TK_RESERVED || token->str[0] != op ) error( "'%c'ではありません", op ); token = token->next; } // 今のトークンが数値の場合、トークンを1つ読み進めてその数値を返す。 // それ以外の場合にはエラーを報告する。 long int expect_number() { if( token->kind != TK_NUM ) error("数ではありません\n"); long int val = token->num; token = token->next; return val; } // token->kind が TK_EOF なら 1 を、それ以外なら 0 を返す bool at_eof() { return token->kind == TK_EOF; } // 新しいトークンを作成してcurに繋げる Token *new_token(TokenKind kind, Token *cur, char *str) { Token* tok = calloc( 1, sizeof(Token) ); // callocについては後述する tok->kind = kind; tok->str = str; cur->next = tok; return tok; } // 入力文字列pをトークナイズしてそれを返す Token *tokenize(char *p) { Token head; head.next = NULL; Token* cur = &head; while( *p ) { if( isspace( *p ) ) // isspace 関数はヘッダ ctype.h に入っている // 引数が空白文字なら0以外を、空白文字以外なら0を返す { p++; continue; } if( *p == '+' || *p == '-' ) { // cur->nextを設定して、それをcurに代入している cur = new_token( TK_RESERVED, cur, p ); p++; continue; } if( isdigit(*p) ) // isdigit 関数はヘッダ ctype.h に入っている // 引数が数字なら0以外を、数字以外なら0を返す { // cur->nextを設定して、それをcurに代入している cur = new_token( TK_NUM, cur, p ); cur->num = strtol( p, &p, 10 ); continue; } error("トークナイズできません"); } // cur->nextを設定 new_token(TK_EOF, cur, p); return head.next; } int main(int argc, char **argv) { if (argc != 2) { fprintf(stderr, "引数の個数が正しくありません\n"); return 1; } printf(".intel_syntax noprefix\n"); printf(".globl main\n"); printf("main:\n"); token = tokenize(argv[1]); // expect_number() について↓ // 今のトークンが数値の場合、トークンを1つ読み進めてその数値を返す。 // それ以外の場合にはエラーを報告する。 printf(" mov rax, %ld\n", expect_number() ); while(!at_eof()) // token->kind が TK_EOF でない限り { if(consume('+')) // bool consume(char op) について↓ // そのトークンが op を表すものでなければ false を返す // token->str[0]が op の時はtokenを次に進める { printf(" add rax, %ld\n", expect_number()); continue; } expect('-'); // void expect(char op) について↓ // そのトークンが op を表すものでなければエラーを出力 // token->str[0]が op の時はtokenを次に進める printf(" sub rax, %ld\n", expect_number()); } printf( " ret\n"); return 0; }
トークンを直接触る関数は consume や expect といったもののみにした。
テストファイルtest.shに以下の行を書き加えて、GitHubにアップロードしてこのステップは完了。
assert 41 " 12 + 34 - 5 "
Unixのプロセスの終了コードは0〜255ということになっているので、テストを書く時は式全体の結果が0〜255に収まるようにする。
$ git add test.sh 9cc.c $ git commit -m "トークナイザを導入" $ git push
calloc関数とは
malloc関数とfree関数の紹介も行う。
malloc関数とcalloc関数は<stdlib.h>に宣言されている。これらの関数はメモリを動的に確保する。
確保したメモリはfree関数で解放しなければならない。
| 形式 | 戻り値 | 備考 |
|---|---|---|
| void* malloc(size_t size) | 確保したメモリ領域の先頭アドレス。確保に失敗した場合（その原因はたいていメモリ不足）、ヌルポインタを返す。 | 引数には確保したい領域の大きさを入れる。 |
| void* calloc(size_t n, size_t size) | 同上 | 引数nには確保したい領域の要素数を、引数sizeには確保したい領域の1要素あたりの大きさを入れる。確保した領域のメモリは0で埋めてくれる。 |
| void free(void *ptr) | malloc, calloc, reallocで確保されたポインタを開放する。また、ヌルポインタを渡しても何も起こらないことが保証されている。それら以外のポインタを渡してはいけない。解放済みのメモリポインタを渡してもいけない。 |
calloc関数ではメモリ領域のポインタの指す先がゼロクリアされる。malloc関数を実行してからmemset関数で埋めるのと同じことが起きる。int型であれば数値が0になるがそれ以外の型では意味が違ってくる。以下は使用例。
#include <stdlib.h> #include <stdio.h> // free関数の代わりにこのマクロでメモリ領域を解放する // 解放後のポインタをヌルポインタにすることによって、 // 誤って２回連続で解放してしまっても何も起こらないことが保証される // （なぜならfreeはヌルポインタを渡しても何も起こらないことが保証されているから） // とはいえまたfree関数を使うと非効率的なので // if文の条件式でヌルポインタのときは何も処理しないことにしている // ただし同じ領域を指すポインタが２つ以上ある場合は、これだけで確実とはいえない #define SAFE_FREE(ptr) if(ptr != NULL){ free(ptr); ptr = NULL; } // malloc関数やcalloc関数でメモリ領域を確保した後は、 // 確保に失敗していないか（即ち戻り値がヌルポインタでないか） // 確かめる必要がある。もし失敗しているのならプログラムを終了する // 十中八九メモリ不足が原因なのでプログラムの続行が困難だろうし、 // それにこのまま続行したら「ヌルポインタの間接参照」をしてしまうだろうから // これは「未定義動作」なので絶対にしてはいけない void* xmalloc(size_t size) { void* p = malloc(size); if(p == NULL) exit(EXIT_FAILURE); return p; } void* xcalloc(size_t n, size_t size) { void* p = calloc(n, size); if(p == NULL) exit(EXIT_FAILURE); return p; } int main() { int n = 10; char *pc = (char *)xmalloc(sizeof(char) * (n+1)); // n文字分（終端のヌル文字の分の確保が必要） int *pn = (int *)xcalloc(n, sizeof(int)); // n個分 double *pd = (double *)xcalloc(n, sizeof(int)); // n個分 for(int i = 0; i < n; i++) { *(pc+i) = i + 65; } for(int i = 0; i < n; i++) { printf("%d番目：文字は%c、整数は%d、浮動小数点数は%lf\n", i+1, *(pc+i), *(pn+i), *(pd+i)); } SAFE_FREE(pc); SAFE_FREE(pn); SAFE_FREE(pd); }
実行結果：
1番目：文字はA、整数は0、浮動小数点数は0.000000 2番目：文字はB、整数は0、浮動小数点数は0.000000 3番目：文字はC、整数は0、浮動小数点数は0.000000 4番目：文字はD、整数は0、浮動小数点数は0.000000 5番目：文字はE、整数は0、浮動小数点数は0.000000 6番目：文字はF、整数は0、浮動小数点数は0.000000 7番目：文字はG、整数は0、浮動小数点数は-92814515680449404682762993892231767752418376643893800353030666635977673095686505197065389597837902323793617910687840191447592198249733150802535531061322482099385922528301143450509381301005901833674907101457935353760197414790103040.000000 8番目：文字はH、整数は0、浮動小数点数は-0.000000 9番目：文字はI、整数は0、浮動小数点数は-594992427546604190142431982475201895362482393844132071030483778462117173325880190427941624155802662644620859256088401385866208754181687271744662862583640563132807611373800234328854102016.000000 10番目：文字はJ、整数は0、浮動小数点数は-0.000000
疑問： なぜ 低レイヤを知りたい人のためのCコンパイラ作成入門のコードには free 関数でメモリを解放する記述がなかったのか？
