Goコンパイラをゼロから作って147日でセルフホストを達成するまで

DQNEO @DQNEO

GolanによるGo Compiler 作り始めてみました。150行くらい書いたら足し算が動くようになった。github.com/DQNEO/mgc/blob… 設計は8ccをほぼ踏襲しつつ、9ccの知見を一部取り込んでいます。

DQNEO @DQNEO

GolangはCと比べて言語仕様にまつわる歴史的紆余曲折が圧倒的に少ない分、その分パーサー実装は楽な気がする。メモリのアロケーション(stack/heapをコンパイラが判定)とかGCは難易度高そうだけど。あと型推論、interfaceあたりもむずそう。

DQNEO @DQNEO

逆に言うとinterface,型推論,GCなしならC言語より圧倒的に簡単そう。

DQNEO @DQNEO

* 簡易tokenizerが完成 * 足し算と引き算と掛け算が動いた 自分でもびっくりするくらい進捗したw github.com/DQNEO/mgc/comm…

DQNEO @DQNEO

早くも関数呼び出しができるようになった! そして hello worldが動いた!! たった1日でここまでいけるとは、自分でもびっくりw pic.twitter.com/o45cBydtHn

拡大

DQNEO @DQNEO

8ccをCとGoで2回も写経して、それに5ヶ月もかかって、途中何度か心折れそうになったけど、その知識が今めっちゃ役に立ってる。

DQNEO @DQNEO

hello worldがファイルまるごとコンパイルできるようになったー Tour of Goに2回挫折した私ですが、Goコンパイラの開発はできているという不思議。 pic.twitter.com/whWcFVPLYO

拡大

DQNEO @DQNEO

putsやprintfがimportなしで動いてるのは、libcのやつを呼んでいるからですね。(チート感

DQNEO @DQNEO

自作Goコンパイラで hello world 完全版うごいたー pic.twitter.com/hUDcBNWbCS

拡大

DQNEO @DQNEO

演算子の優先順位を考慮した足し算・引き算・掛け算ができるようになったー pic.twitter.com/nw2uh12LC8

拡大

DQNEO @DQNEO

ローカル変数の宣言、代入、参照ができるようになったー github.com/DQNEO/mgc/comm…

DQNEO @DQNEO

設計の参考にするためにGo本家のコンパイラのソースを読んでみたんだけど、意外と読めた。特に ASTの構造体の設計がめちゃきれいだった。 github.com/golang/go/blob…

DQNEO @DQNEO

Go本体を読んでて気づいたんだけど、Goって代入文は式じゃないのね。 a = b = 3 はコンパイルエラーになった。 そして、宣言文( var i =1 ) も式じゃないっぽい。 処理系本体を読んで言語仕様を知るの、普通の学び方とは逆な気がするけど、こういう学び方もアリだな。

DQNEO @DQNEO

Go文法の改行とセミコロンの仕様を完全に理解した( = 実装した) github.com/DQNEO/mgc/comm…

DQNEO @DQNEO

ローカル変数とグローバル変数の宣言、代入、参照を実装した。(型はintのみ) あと大胆に内部設計をリファクタリングして、8cc/9cc風の巨大構造体を使うのをやめて、小さい構造体をたくさん定義してみた。この方がIDE補完効くのと、Go本家の設計に寄せたかったという理由。 github.com/DQNEO/minigo/c…

DQNEO @DQNEO

* インラインコメント、ブロックコメント機能を実装した。 * 変数スコープを多段入れ子になるようにちゃんと実装した。 * 内部的に使ってたスペーストークンを廃止。Goの文法はセミコロンと改行、コメントとスペースの関係が少しややこしいので、いったんシンプルにした github.com/DQNEO/minigo/c…

DQNEO @DQNEO

コンパイラ作り始めて1週間で、こんなコードがコンパイルできるようになった。それなりにプログラミング言語っぽく見えるw github.com/DQNEO/minigo/b…

DQNEO @DQNEO

関数パラメータが動いた〜 睡眠時間が... pic.twitter.com/Y80BidOt3l

拡大

DQNEO @DQNEO

自作コンパイラ開発は、初期段階はイテレーティブ(字句解析・構文解析・コード生成をそれぞれ少しずついじって育てていくアプローチ)にやる方がいいのは間違いないけど、ある段階まできたらウォーターフォルに切り替えた方が効率がいいと思う。字句解析器だけ先に完成させてしまうみたいな。

DQNEO @DQNEO

あと、似た機能は同時にまとめて開発した方がよい。比較演算==を実装するなら!=も一緒にやる。大小比較(<=, <)も一緒にやる。フロー制御をやるならfor,while,if,elseは一緒にやる。

DQNEO @DQNEO

構文解析で宣言のパーズをやるときは、変数・定数・型のパーズを一気にやる。そのときはパーズだけ書いてemitterはやらない、みたいな。 そうすれば脳のモード切替をしなくてすむので圧倒的にスピードが速い。

DQNEO @DQNEO

とにかくコンパイラというのは複雑なソフトウェアなので、いかに脳みその負担を減らすかが重要。コンパイラ内部の動きを可視化するのも重要。 ロガーを仕込むとかエラーメッセージをわかりやすくするとか、パーサの入れ子になったスタックトレースをログ表示のインデントで可視化するとか。

DQNEO @DQNEO

そう考えて可視化をやってみたら、めちゃくちゃ生産性があがった。ログ出力のために多少コードのきれいさを犠牲にしてもよいことにした。可視化の方が圧倒的に重要。 pic.twitter.com/jLxo2EL8nP

拡大

DQNEO @DQNEO

上の画像のfor文のパースに失敗してエラーになった例。for文を式(Expr)として解析しようとしているが、for文は文(Statement)なので、for文のパースを開始する際の前提が間違っていることがわかる。