今日から始める自作コンパイラ ver 0.0.1

第28回 #hiro_it で発表した資料です。
自作コンパイラの概論みたいなテキストを書こうとしていて、その進捗報告第１回です。

Transcript

1. 今日から始める自作コンパイラ ver 0.0.1 星にゃーん（@takoeight0821） 第28回 #hiro_it
2. 近況 北極圏に埋められました
3. 今日話すこと 自作コンパイラの入門、概論的な話を書いたテキストを作ろうとしています なかなかやる気がでないので、とりあえず書きたい内容をスライドにしました まだまだ未完成ですが、進捗報告みたいな感じで話そうと思います
4. このスライドの目標 コンパイラを作ってみたい人が、 • そもそもコンパイラとは一体どんなプログラムなのか • どこから手をつければいいのか • どんな情報源があるのか がわかるようになること
5. （そもそも）コンパイラって何？1/3
6. （そもそも）コンパイラって何？2/3 • “ある言語（原始言語）で書かれたプログラムを読み込んで、それを別の言語（目的言語）で 書かれた意味的に等価なプログラムへ翻訳するプログラムである ” - 『コンパイラ[第2版] 原理・技法・ツー ル』 ◦ 原始言語はソース言語、目的言語はターゲット言語と呼ぶことも多い • 言語Aから言語Bへの翻訳プログラムのこと • gcc：Cからアセンブリ言語へのコンパイラ javac：JavaからJVMバイトコードへのコンパイラ clang：CからLLVM IRへのコンパイラ llc：LLVM IRからアセンブリ言語へのコンパイラ TODO: コンパイラドライバの話
7. （そもそも）コンパイラって何？3/3 • 一般にコンパイラと呼ばれるのは、ある言語からアセンブリ言語へのコンパイラ ◦ ネイティブコンパイラとも呼ぶ ◦ C、C++、Rust、Go • 独自の仮想マシンのバイトコードへのコンパイラもよくある ◦ Java、C#、ActionScript • アセンブリ言語以外へのコンパイラは「トランスパイラ」と呼ばれることもある ◦ TypeScript、CoffeeScript、”C with Classes”（C++の原型）
8. コンパイラの基本 ソース言語で書かれたプログラムも目的言語のそれも、たいていはただの文字列。 つまり、こんな感じのプログラムを書けばコンパイラになる！！
9. 何から何へのコンパイラを作るか どんな言語から、どんな言語へのコンパイラを作るかを決めないとコンパイラは作れない。 いくつか考えられる案がある。 1. アセンブリ言語へのコンパイラ a. ふつうのプログラミング言語より表現力が低いので、ソース言語の意味を「かみくだく」必要がある b. どんなCPUアーキテクチャを対象にするか（ x86, ARM, RISC-V）も考えないといけない 2. C言語やJavaScriptへのコンパイラ a. どちらも割とどこでも動く高級言語（ふつうのプログラミング言語） Cコンパイラはいろいろな CPUに対応している。 JavaSciprtはWebブラウザがあれば動く 3. JVMへのコンパイラ a. Javaが動くマシンでなら動く b. Javaや他のJVM言語の資産を使える
10. アセンブリ言語へのコンパイラ TODO
11. C言語へのコンパイラ TODO
12. JavaScriptへのコンパイラ TODO
13. JVMへのコンパイラ TODO
14. 何からのコンパイラを作るか • 自作言語コンパイラ ◦ 俺がかんがえた最強のプログラミング言語 ◦ 好きなプログラミング言語の特徴を組み合わせてみる（オブジェクト指向 +関数型とか） ◦ 限定継続、Algebraic Effect、依存型など、まだ広く使われていない概念の実装を試す • C言語コンパイラ ◦ 最近（2019-2020）自作コンパイラ界隈で流行っている ◦ 『低レイヤを知りたい人のための Cコンパイラ作成入門』 • MinCamlコンパイラ ◦ http://esumii.github.io/min-caml/ ◦ 小さく読みやすいコンパイラ実装。これを改造したり移植したり
15. 自作言語コンパイラ TODO 文法と意味を考える Cの関数を呼び出す機能をつけると拡張が楽
16. C言語コンパイラ TODO https://www.sigbus.info/compilerbook Cコンパイラ作成集中講座
17. MinCaml TODO http://esumii.github.io/min-caml/ 他言語への移植、機能の拡張 コンパイラの構造の参考
18. コンパイラを書くための技術 コンパイラにはやることがたくさんある • 構文解析：ソースコード（文字列）を解析して、抽象構文木（ AST）を作る • 意味検査：プログラムが正しく動きそうかチェックする ◦ 定義してない変数の使用をチェックする（ミスタイプかも？） ◦ 式の型が合っているかチェックする型検査 • 最適化：より速いプログラムに変換する ◦ 1 + 1 は 2 に置き換える、定数回のループは展開する • コード生成：目的言語のプログラムを生成する
19. 構文解析 TODO 正規表現　字句解析 LL(1) LL(k) LR AST パーサコンビネータ
20. 意味検査 TODO 変数の出現検査 2段階の構文解析テクニック 型検査 型推論
21. 最適化 TODO データフロー解析 ループ最適化 SSA
22. コード生成 TODO プログラムを生成するプログラム 中間表現 レジスタ割当
23. 例：簡単な言語からCへのコンパイラ TODO 変数と四則演算とサブルーチンをもつ言語から Cへのコンパイラ 式ベースで型推論を持つ言語から上の言語へのコンパイラ 組み合わせると下の言語から Cへのコンパイラができる
24. 情報源 TODO 有名な教科書やWebサイト コンパイラ[第2版] 最新コンパイラ構成技法（入手困難） 低レベルプログラミング 計算理論の基礎　オートマトンと言語 MinCaml、Cコンパイラ本 実際のコンパイラのソースを読んでみる