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

2019.08.30

セッションの概要

本記事は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コンパイラ

QA

最後にQAがありました。

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