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

セッションの概要

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

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

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

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

作るコンパイラ

• 足し算と引き算ができるコンパイラ
• 結果の数値でexitする
• 標準入力からコードを受け取る
• Goで書く

ライブコーディング

1. 素のアセンブリを書いて実行

• "42"を返すmain関数をアセンブリで書く
• レジスタとは？
  • CPUの中にある超高速な一次記憶装置

2. Goで1で書いたアセンブリを標準出力に吐き出すコードを書く

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

3. 標準入力からコードを受け取る

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

ソースコードの解釈について

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

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

4. Tokenizerを書く

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

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

5. Parser

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

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

6. 単項式（Unary Expression）

• Expressionを拡張し、operator（+とか-とか）, operand（式。数値リテラルを想定）を定義
  • 式が式を持つ再帰的な構造になる
• パーサーで記号をパースできるようにする
  • punct tokenがきたら、単項式を組み立てる
    • operandは更にパースした結果（再帰になる）
• アセンブルに変換する関数で、unaryを解釈して変換できるようにする

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

7. 多項式（Binary Expression)

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

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

ここまで

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

コンパイラかけるとなにがよい？

• プログラミング言語が動く仕組みがわかる
• 既存のコンパイラが読めるようになる
• コンピュータの動きがちょっとわかるようになる

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

まずやってみよう

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

よくある誤解

• Cで書く必要がある
  • 何言語でもいい
• 特殊な拡張やライブラリが必要
  • いらない
  • 他の言語でやる場合も標準機能だけで書ける
• CSの知識がいる
  • なくても始められる

参考資料: Cコンパイラ

• rui314/8cc
• rui314/chibicc

QA

最後にQAがありました。

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