自作Cコンパイラの途中経過

Cコンパイラ自作の進捗

以前の記事に書いたとおり、C言語のコンパイラを自作している。

セルフホストには至ってないが、教科書であるオンラインブック「低レイヤを知りたい人のためのCコンパイラ作成入門」の内容が一通り実装し終わったので経過報告をする。

裏で最初は毎日記録をつけていたのだが、だんだん面倒くさくなってやめたので、コミット履歴を見ながら振り返る。

最初のコミットは19日前(5/21)なので、そろそろ三週間経ったところだ。 5/28-30の三日間以外は何かしらコミットしているので、継続的に開発できている。もっともバイトや授業に遮られることがなく、時間がたくさんあるのでできることであるが。

ここまでのマイルストーンとしては、次の機能開発があった。

テストをCで書き直す(オンラインブックStep28) ところでバグが結構見つかって一つ一つ潰すのに時間がかかった。
でもこの頃はGDBの基本的な使い方に慣れてきて、更に当たりをつけてアセンブリを読むことができたので、最初の頃より全然楽だった。

テストファイルをCで書き直し、これを自作コンパイラでコンパイルすると10000万行(デバッグ情報含む)くらいのアセンブリになった。これくらいの規模のプログラムがうまく実行できると、人間を超えていく感じがして楽しい。

ブロックスコープ内の変数の実装方法は自分で考えたものなのだが、結構うまくできたと思っている。

willaniには変数一つを表す構造体があり、これをつなげた2つの単方向リストがそれぞれ、グローバル変数とローカル変数を表している。

スコープのある変数を実装するには次の2つのことを考慮する必要がある。

トークン列をパースするときに次のような方法で 1. 2. を実現した。
なお、私の実装ではブロックスコープの変数はローカル変数の単方向リストに含む。

新しいスコープに入るときに、その前最後に定義されたローカル変数をのポインタをout_of_scopeとして記録する。
変数定義するときは、単方向リストを先頭(最新)からout_of_scopeの前までみて、同じ名前のものがないか調べる。
変数を定義するとき、Var.referable = trueというフラグを立てる。
スコープを出るときに、そのスコープで定義した全ての変数 (out_of_scopeより新しい定義の変数) のフラグを下げる。(falseをセットする。)
以後呼び出す変数を探すときにフラグがfalseなものをスキップさせる。

こうすることで、最新に定義した変数から順番に調べていけば、「1. その変数を定義してよいか」「2. 同名の異なる変数のうちどの変数を指しているか」がわかる。

リストには全てのローカル変数が残っているので、コード生成時に変数の領域を確保するのが簡単だし、パース時にどの変数を指し示すか解釈しておけばコード生成時は変数名の重複を考える必要がない。

植山類さんのコンパイラ実装である 9cc や chibicc 等のコミットログをみて、セルフホストをするためにはあと1倍くらい、完成まではさらに1倍くらいの手間がかかるのではないかと予想している。

セルフホストに必要そうな機能は次の通り。

(括弧がついてるのはサボろうか迷っているもの。特定の文法を自分のコードから削除して書き換えてしまえば、その文法に対応しなくてもセルフホストできてしまう)

構造体とプリプロセスが時間かかりそうだなと見ている。

Cの仕様書をどこまで実装するかは考えものだが、セルフホストはやっぱり楽しみ。

Webのフロントエンドをはじめとする物々にも手を付けねばと思っているし、研究室の論文も読まねばと思っているので、今後はバランスも考えてやっていきたい。

追記: (2020/10/04) 以前の記事へのリンクを相対リンクに修正