[builderscon 2019 レポート] コンパイラを作ってみよう #builderscon

稲葉純

2019.08.30

この記事は公開されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。

セッションの概要

本記事はbuilderscon 2019のセッション、DQNEO様による「コンパイラをつくってみよう」のレポートとなります。

本セッションはライブコーディングでフルスクラッチのコンパイルを書く、という発表でした。

また、本セッションの資料はすでに公開されています。

以下、レポートの内容となります。

これを動かすとアセンブリを吐き出してくれるので、これをアセンブルすると動かせる。

Goで標準入力から受け取った値をintに変換して、アセンブリに埋め込む。

全てはByte列
- ByteReader
- ソースコードをバイト列に変換
- -12であれば'-','1','2'
全てはトークン（単語）の列
- Tokenizer（字句解析）
  - 単語の区切りを解釈できる
- バイト列をトークン列変換
- -12であれば'-','12'
全ては構造である
- Parser
  - 構文解析
  - 入れ子を認識したりできる
- バイト列を構造に変換
- -12であれば'-'（単項演算子）,'12'（数値リテラル）まで解釈

構造をアセンブルするとアセンブリが吐き出される。

Token structを定義
- 種類と値
tokenize関数を書く
- コードを1文字ずつ読みながらコードをトークンに分割
- 先頭1文字呼んで、数値なら連続する数値を読み込んで、Tokenオブジェクトを作る
  - kind:intliteral
入力した値をtokenizeに渡す
これで数値のトークンが認識できる
数値以外が認識できないので、スペース、改行コードをtokenizerが無視するよう修正
+とか-とかセミコロンも解釈できるようにする
- kind:punct

ここまでで、足し算、引き算のtokenizeができる。

Exxpression（式）を定義する
- kindとvalue
- intliteral型なら、intliteralを持つ
parse関数を定義
- トークンを1つ受け取る
- トークンの種類で分岐
  - コンパイラ書くときは、switchで分岐してdefaultはpanicで落とすのがコツ
  - 数値だったら、intliteral式に変換
式をアセンブルに変換する関数を作る
- 式の種類に対して吐き出すアセンブルを定義

ここまでで、数値リテラル構文解析してアセンブルできる。

-10 ;とか +10; とかを構文解析してアセンブルできる。

Expressionに左辺、右辺を追加
- これをparserでパースできるようにする
- unary expressionで式をパースした後、次のtokenが+とか-ならbinary Expressionを生成
  - operatorがtokenのvalueで、operandはなしで、leftがparseした式、rightは更に次にパースした式
アセンブルに変換する関数で、binaryを解釈して変換できるようにする

ここまでで、足し算、引き算ができるようになる。

この勢いであと1万行書くとコンパイラができる！ DQNEO/minigoの最初の7コミットしたのが、ライブコーディングでやったのと同様のコード。

このセッションは、「はじめ方がわからない」というところを解決したかった

学ぶ→つくる、じゃなくて作りながら学ぶ、を提唱したい。

最後にQAがありました。

コンパイラ完成までにモチベーションを保つには？
- 他のことをしない
- 他の勉強もしたかったが、コンパイラ作成が終わるまで他のことをしない、と決めた
四則演算以降って急にハードルがあがるけど、それ以降のトピックでおすすめある？
- hello world
- 関数呼び出し
- if/forまでやるとfizz/buzzが動くので、本格的になってきてモチベーションあがるとおもう
各ステージのテストはどう書いてる？構文木を手書きしたりすると大変だと思うが
- 構文を追加するたびに、コンパイルしてちゃんと動くか、をテストしてる
- E2E
- 関数の単体テストは書いてない
なんでrbxがないのか
- libcかOSの規約で書き換えてはいけない、となっている
アセンブリを理解しないと行けないと思っているが、アセンブリの入門に良い資料、書籍はあるか？どう勉強したか？
- コンパイラ書きながら覚えた
- ググったりQiitaの記事見たり
- 本は特に呼んでない
- gccで小さいcを出力するコードを見て勉強したりした