Cコンパイラを自作した話です。
コンパイラってどんなもの？ということから、コンパイラの仕組みを簡単に説明していきたいと思います。
コンパイラについて知るメリット
コンパイラには情報学のすべてが詰め込まれています。
（eg.ソフトウェア、ハードウェア、機械語、オートマトン）
そのため、コンパイラを作らなければ、始まらない！みたいな人もいるみたいです。。
普段プログラミングをしている際には、低レイヤの仕組みなどは意識することはないと思います。知らない人から見ればブラックボックス化していますね。
コンパイラを知ることで、その中身がどうなっているかを知ることができます。
箱があったら開けてみたいという精神で、好奇心で勉強していきましょう。
コンパイラとは?
人が書いたプログラムを機械がわかるようにする翻訳機のような役割を果たすものです。
今回作るものは、C言語のコンパイラで、C言語のソースコードからアセンブリコードを吐き出すものとなります。
C言語とアセンブリコード
アセンブリプログラムとは
アセンブリ言語とは、機械語に近いプログラミング言語です。
ストレートに機械語へ翻訳でき、実行速度が速いという特徴もあります。
AST(抽象構文木)について
理論的には、有限なラベル付き有向木である。また、演算子と変数や定数といったオペランドから成る数式などのようなものに対する抽象構文木を例にすると、分枝点は演算子、葉はオペランド（つまり、変数や定数）である。
コンパイラやインタプリタといったプログラミング言語処理系の場合は、中間表現のひとつであり、一部の最適化は抽象構文木の上の操作などによっておこなわれる。
引用（抽象構文木）
Cコンパイラによる出力 （足し算編）
実際にCコンパイラが出力するアセンブリコードを見てみましょう。
例として次のC言語で記述されたプログラムを考えます。
int printf ();
int i;
int main ()
{
i = 2 + 3; // ここに対応するアセンブリコードを紹介します
printf ("%d\n", i);
}
この足し算の部分をASTで表すと、
. . . . AST_expression_assign
. . . . . AST_expression_id
. . . . . . AST_IDENTIFIER
. . . . . AST_expression_add
. . . . . . AST_expression_int
. . . . . . AST_expression_int
これを図解します。
木構造になっており、"="の子ノードが2つ存在し、左辺値と右辺値を評価する。それをさらにたどっていくという仕組みです。
このプログラムの足し算に対応するアセンブリプログラムは以下となります。
pushq $2
pushq $3
popq %rcx
popq %rax
addq %rcx, %rax
pushq %rax
※大域変数の準備、関数の呼び出しなどその他の部分は省略しています。
Cコンパイラのソースコード
ここではさらにクローズアップして、
「i = 2 + 3」のなかの「2 + 3」の部分に注目します。
// 足し算
static void codegen_expression_add (struct AST *ast)
{
assert (!strcmp (ast->ast_type, "AST_expression_add"));
for (int i = 0; i < ast->num_child; i++) {
visit_AST (ast->child[i]);
}
emit_code (ast, "\tpopq\t%%rcx\n");
emit_code (ast, "\tpopq\t%%rax\n");
emit_code (ast, "\taddq\t%%rcx,\t%%rax\n");
emit_code (ast, "\tpushq\t%%rax\n");
frame_height -= 8;
}
上記のコードが足し算のアセンブリコード吐き出すコードです。
visit_AST (); という関数がASTをたどる関数です。それをたどったとき、AST_expression_addというノードにたどり着いたとき、上記の関数である、codegen_expression_add()が実行されます。
関数中の始めにあるfor文を用いて、現在のASTのすべての子ノードをたどります。ここでは、"+"の子ノードとして、intである"2", "3"を評価します。
その下のemit_code ()関数で、アセンブリコードを出力します。
最後にフレームハイトの調整をします。
レジスタにpopを2回、pushが1回でスタックにraxが積まれたため、合計でフレームハイトを8減らします。
最後に
普段見えないところを知れて面白かったです。
コンパイラの仕組みを理解できれば、自作のプログラミング言語も目指すこともできるので、勉強していこうと思います。