数日前からCコンパイラを書き始めた。(GitHub)

植山類さんのオンラインブック、低レイヤを知りたい人のためのCコンパイラ作成入門を読みながら、概ね本の内容に沿って進めている。 自分の書いたコンパイラで自身をコンパイルするセルフホストを目指している。

コンパイラというのはある言語で書かれたプログラムを別の言語に変換するプログラムだ。 ここではC言語をアセンブリに変換するものを指している。
いきなりC言語をコンパイルするのは無理なので、徐々に複雑な入力を受け付けるように改良し、最終的にC言語を受け付けるようにする(したい)。 最初は入力をそのまま出力することから始まり、四則演算ができるようになり、いまは関数呼び出しができるようになった。

本はとても丁寧に書かれていて、参考として実装も2種類ほど存在する。 さらにSlackやYoutube Liveで質問ができるというとても恵まれた環境が揃っている。

実は昨年コンパイラの授業をとっていてコンパイラを少し触っていた。 cmmというCを一部切り取ったような言語と、PL0iという仮想マシン(とそのアセンブリ)に対して言語拡張をする、というようなことだった。 そのときはあまり真面目に実装に凝っていなくて、課題はパスして成績がそこそこもらえるくらいはやったが、実のところコンパイラってよくわからないなという気持ちのまま終わっていた。

このままではよくないという気持ちと、あとは単純な興味(プログラムをデータとして扱うことを体験できる)もあって始めてみた。


はじめてまだ3日ほどだが、パーサについてがちょっと意外だった。 手書きでパーサを書くというのは事前に聞いていたが、LL(1)でいけるらしい。

LL(1)とは構文解析法のこと、つまり、文法がどんな構造になっているかを調べる手法の一つだ。 構文解析は事前にBNF記法などで規則が与えられており、その規則のどれが適用できるかを探す。 授業でLR(0), LR(1), LALR(1)などを扱ったが、LL(1)はそれらよりも単純で手書きでパーサを書くのに向いているらしい。

どうも最近のコンパイラ(gccやclang)はLL1らしい。 大学の授業では、「LALR1じゃないとまともにパースできない(世の中的には主流)(最近は違う場合もある)」といっていた気がして、それにしたがってLALR1の文法解析などをやった記憶があるのだが。(違ったらごめんなさい先生。)

なんだったんだあの勉強はという気持ちに少しなったが、教科書的にはああいうものなのだろう。 授業ではLL1をばっさり飛ばしたのでそんなに深追いしてなかったが、やってみればなるほどという感じ。

LALR1パーサジェネレータを書くなら当時の記憶を掘り返して結構頑張らないときつそうだけど、LL1で書くのは意外といけるものだ。


そんなわけでトークナイザ(レキシカルアナライザと同義?)とパーサは結構スイスイ進む。 やることが見えているしデバッグ用にログを出せば何が起きているか目に見えてわかる。

そこまではいいのだけど、肝心のコード生成がちょっと大変。

アセンブリへの理解が浅い私である。 アセンブリを読むのは少しつらいなぁ、この量でこんなこと言ってたらこの先どうなることやらと思いながらデバッグしている。 今後アセンブリがすらすら読めるようになることを夢見て続けていきたい。


C言語でそれなりのものを書くというのも実はいままであまりやってこなかったので、今回は絶好の機会だ。 いつまで飽きずにやれるかな。