低レイヤを知りたい人のためのCコンパイラ作成入門を3ヶ月くらいかけてやってみた。 目的はおもちゃCコンパイラを作って、最適化の実装をいろいろ試したかったのだけど全然そこまで行かず。
C言語で外部ライブラリなどを使わず一からCコンパイラを作っていきます。細かくステップが分かれていて、順番にやっていくと少しずつコンパイラの機能が増えていきます。三ヶ月かけて、執筆してあるステップ25くらいまできました。ここまでやって、基本的な演算、配列、ポインター、関数呼び出しができる程度です。できないこともまだまだあります。今時のコンパイラの本だと仮想マシーンで動かすのですが、実機で動くアセンブラを出す所も特徴的です。生成したアセンブラのコンパイラ、リンクはgccを使ってます。
大変だったけどとても面白かったです。ぜひ皆さんも挑戦してください。
今回はRust力を上げたかったのでRustで実装しました。試行錯誤して時に泣きながら書いたので参考にはならないと思いますが、一応テストは通っているから記念に晒しておきます。
おもしろい所
コンパイラの実装をするにあたって、メタなレベルでトリッキーな所があって、とてもおもしろかったです。
例えば、最初の変数の扱いはスタック上に26文字分の領域を確保し一文字の変数を簡単に扱えるようにしています。これでトーカナイザーはアルファベットが出てくればその文字を変数として捌けばコンパイルできます。これで変数の動きを確認した後、複数の文字列の変数を実装して行きます。
C言語ならではの方法として、gccでコンパイルした関数をリンクすることで関数の定義の前に関数呼び出しの実装を行っています。これを見た時は、おおっと声が出てしまいました。発想がすごい。
やってみてわかったこと
C言語の難しさ
他のコンパイラの教科書に載っているような擬似言語と違って、実際に使われているC言語は一部面倒なところがあります。他のコンパイラ作って見よう系の教科書は、面倒な所を上手く隠しているなと分かりました。
具体的には配列とポインターの変換。Cのプログラミングではまることはないけど、実際にコンパイラとして作るとなると、きっちり整理しないと上手く行きませんでした。
あと型宣言がめんどくさい。
int x [2][3]; int *a, b;
xの型情報がxの前と後ろにあるのがすごい面倒。今回の範囲には無いけど下のaはポインターだけど、bはintってのも、コンパイラ実装する上では無駄に面倒な気がする。（面倒な割によい事が全くない）
実機で動かす難しさ
x86-64のアセンブラで上手く動かないときgdbの出番になってちょっと面倒でした。これがVMだと同じIDEを使って同じ感覚でデバッグできるので大分楽。面倒だけどgdb使えば一発で解決ってのが多かったのでしょうがない。
Rust実装
ここは低レイヤを知りたい人のためのCコンパイラ作成入門と関係無いトピックです。Rustも良い所と悪いところが当然あって良い所はみんな書くので省略。
Rustは試行錯誤しながら作っていく開発とは相性が悪い。最終形が見えていれば良いが、最終形がどうなるか分からない物を作っていくとき、どうしても開発速度は落ちる。エラーが起きたらそのまま死んでくれれば良いような物でもとりあえずResult返す、ポインターがNULLの場合を愚直にOptionで表すと、戻り値がどんどん入れ子になって、再帰しているから関係している関数の戻りを全部直していくのが大変だった。
Rustのメモリモデルに近いようなデータ構造はそれなりに実装出来る。後で変更しないツリー構造なんかは楽。Cソースファイルみたいなオブジェクトを作ってトーカナイザーと相互参照させるとかは実装が難しい。
今から思うと、変数の型みたいのは1次元（intへのポインターの配列の配列とか）だからCのリンクリストみたいにしないでvecでやればずいぶん楽だったと思う。リンクリストの指すところがNULLかどうかは長さ見ればすぐに分かったのにと。そんなことを考えて思っていたら関数宣言の所で型は分岐するよ～ってテキストの後ろに書いてあってvecにしていたら全部修正だったなと考えてました。
Rust力が上がれば、変更するであろうな箇所に対して無難な書き方ができるのかもしれない。
プログラムの完成形が見えていて、登場する小難しいアルゴリズムをライブラリ使うなり自力で実装できる目処が立っていればRustはベストだと思う。
進め方
最初の方はテキストを読みながらゆっくり実装してました。途中からは、ここの変更履歴を見ながら同じように実装進めました。
まずcommit単位からtest.shを開いて、testを自分の環境にコピーします。そこから、このテストを通しつつ、過去のテストもちゃんと通ることを確認する事をずっと続けていました。ステップに沿ったテストが揃っているのは本当に素晴らしい。
他の言語で実装するときも関数名だけは一対一対応させておいた方が良いです。
困ったところ
面倒だったのとは別に苦労したところ。教科書のCソースをダウンロードして動かして比較するのは負けだと思っていたので頑張った。
- アドレスの上下がどっちか分からず変数に書き込むとき戻り番地を書き換えて死んだ。gdbで一発だった。
- 変数を追加していくとき、僕の実装は後ろに足していったけど、教科書実装は前に足していくので一部テストが通らなかった。
- 自分で生成したアセンブラが何をやっているか分からなかった。アセンブラソース(.s)に直接コメントを出力することで解決出来た。
- 変数とポインターの所。この時この変数はこうなりますという解説が無かったので、頑張ってソースを追うしかなかった。
- パースが終わったときにASTをdotで可視化するのはできたが、パースが失敗したときにそこまでのパース結果を可視化する仕組みが作れなかった。欲しいのこっち。こんなときCommon LispだったらグローバルにASTを置いて、エラーハンドラから可視化関数呼べば良いのに・・・と思ったがRustではやり方分からなかった。
あとはソース追いながらじっくりやればなんとかなると思う。
コンパイラのCについて
他の人も言っていたと思うが、C言語そのものを普段使いしていないと仕様の理解と参考ソースの理解とどっちも辛いんじゃないかと思いました。教科書のソースは非常に洗練されていて、Cの入門書読んだレベルでは歯が立たないのでは無いかと思う。
例えば、変数を追加するところでlocalsがCのグローバル変数として定義されていて、リンクリストで動的にリストに追加していきます。Cの初心者向けの本だとリンクを最後までたどって最後に新しい変数を足しそうだけど、ここでは当然のように先頭に足す。今時の言語だとあまり使わないテクニックだ。
static Obj *new_lvar(char *name, Type *ty) { Obj *var = new_var(name, ty); var->is_local = true; var->next = locals; locals = var; return var; }
他にも、いっぱいポインタ出てきますがcallocで領域確保していてそれが初期化も兼ねているのも難しい。p=NULLといった明示的な初期化もしないままif(p)でNULL比較してます。ここもif(p!=NULL)ではない所ではまる人いないのだろうかと心配になりました。
ターゲット言語としてCを理解するだけでなく、コンパイラのかっこいい実装を学ぶんだくらいの勢いで乗り切って欲しいです。
compiler explorerとの比較
自分で作ったコンパイラとcompiler explorerの比較をしてみた。 教科書は困ったらcompiler explorerの出力を参考にするんだと書いてあったが、まだまだ差がありすぎてあまり参考にはならなかったです。
Cソース。
char foo() { char *x = "abc"; return x[0]; }
自作コンパイラの出力。教科書通りに実装すれば、同じ出力になるはず。 （仕事でCコンパイラがこんな出力してきたらぶち切れると思う。）
.data .globl .L..0 .L..0: .string "abc" .globl foo .text foo: push %rbp mov %rsp, %rbp sub $16, %rsp # val.offset -8 mov %rdi, -8(%rbp) # assign lea -8(%rbp), %rax push %rax lea .L..0(%rip), %rax pop %rdi mov %rax, (%rdi) # deref mov $8, %rax push %rax mov $0, %rax pop %rdi # op Mult imul %rdi, %rax push %rax lea -8(%rbp), %rax mov (%rax), %rax pop %rdi # op Add add %rdi, %rax # deref load mov (%rax), %rax jmp .L.return.foo .L.return.foo: mov %rbp, %rsp pop %rbp ret
compiler explorerの「最適化無し」の出力。 最適化無しでもとても短い。
.LC0: .string "abc" foo: pushq %rbp movq %rsp, %rbp movq $.LC0, -8(%rbp) movq -8(%rbp), %rax movzbl (%rax), %eax popq %rbp ret
0をかけて足すところはなくせる、関数の入り口出口はもうちょっとすっきりできる、くらいはぱっと思いつくが、実際にこう出るように実装するのはまた違う難しさがありそう。
先はながい
他のお勧め本
Writing Compilers and Interpreters: A Software Engineering Approach
同じようなアプローチで、まずは1行のプログラムを動かして見ようという本です。
感想は以前書きました。お勧め。
実践Rust入門
簡単なパーサーの作り方が載っているので、Rust実装の最初の一歩にお勧め。
実践Rust入門 [言語仕様から開発手法まで] | κeen, 河野 達也, 小松 礼人 | コンピュータ・IT | Kindleストア | Amazon
