Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
コンパイラ作りの魅力を語る / Making compilers is fun
Search
DQNEO
March 30, 2019
Programming
10
8.5k
コンパイラ作りの魅力を語る / Making compilers is fun
PHPerKaigi 2019で、C/Goコンパイラを作る過程で学んだことについて話しました。
DQNEO
March 30, 2019
Tweet
Share
More Decks by DQNEO
See All by DQNEO
英和辞書付きGo言語仕様書 / Word Wise Go Spec
dqneo
1
530
Go言語低レイヤー入門 Hello world が 画面に表示されるまで / Introduction to low level programming in Go
dqneo
6
1.6k
入門Go言語仕様 / Go Specification Untyped Constants
dqneo
1
1.3k
入門Go言語仕様 Underlying Type / Go Language Underlying Type
dqneo
9
5k
How to write a self hosted Go compiler from scratch (Gophercon 2020)
dqneo
3
1.6k
もっと気軽にOSSに Pull Requestを出そう!/ Let's make a PR to OSS more easily
dqneo
6
8.3k
Goコンパイラをゼロから作ってセルフホスト達成するまで / How I wrote a self hosted Go compiler from scratch
dqneo
15
14k
コンパイラをつくってみよう / How to make a compiler
dqneo
9
11k
Goのmapとheapを自作してみた / How to create your own map and heap in Go
dqneo
0
3.1k
Other Decks in Programming
See All in Programming
LT 2025-06-30: プロダクトエンジニアの役割
yamamotok
0
750
効率的な開発手段として VRTを活用する
ishkawa
0
140
Is Xcode slowly dying out in 2025?
uetyo
1
270
Modern Angular with Signals and Signal Store:New Rules for Your Architecture @enterJS Advanced Angular Day 2025
manfredsteyer
PRO
0
220
AIと”コードの評価関数”を共有する / Share the "code evaluation function" with AI
euglena1215
1
160
A2A プロトコルを試してみる
azukiazusa1
2
1.4k
#kanrk08 / 公開版 PicoRubyとマイコンでの自作トレーニング計測装置を用いたワークアウトの理想と現実
bash0c7
1
770
AIプログラマーDevinは PHPerの夢を見るか?
shinyasaita
1
220
20250704_教育事業におけるアジャイルなデータ基盤構築
hanon52_
5
780
『自分のデータだけ見せたい!』を叶える──Laravel × Casbin で複雑権限をスッキリ解きほぐす 25 分
akitotsukahara
2
640
今ならAmazon ECSのサービス間通信をどう選ぶか / Selection of ECS Interservice Communication 2025
tkikuc
21
4k
チームで開発し事業を加速するための"良い"設計の考え方 @ サポーターズCoLab 2025-07-08
agatan
1
410
Featured
See All Featured
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
20
1.3k
Agile that works and the tools we love
rasmusluckow
329
21k
Being A Developer After 40
akosma
90
590k
Rebuilding a faster, lazier Slack
samanthasiow
82
9.1k
VelocityConf: Rendering Performance Case Studies
addyosmani
332
24k
Why Our Code Smells
bkeepers
PRO
336
57k
Rails Girls Zürich Keynote
gr2m
95
14k
Build your cross-platform service in a week with App Engine
jlugia
231
18k
Building Adaptive Systems
keathley
43
2.7k
4 Signs Your Business is Dying
shpigford
184
22k
Typedesign – Prime Four
hannesfritz
42
2.7k
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
30
2.1k
Transcript
コンパイラ作りの 魅力を語る @DQNEO phperkaigi 2019.3.30
自己紹介 @DQNEO どきゅねお アメリカ版メルカリを開発しています • PHPer • C初心者 • Go中級者
目次 • デモ • コンパイラとは何か?何をしているのか? • なんで作ろうと思ったのか? • どうやって作ったのか?
趣味: コンパイラ作り Cコンパイラ https://github.com/DQNEO/8cc.go 8ccをGoに移植したもの Goコンパイラ https://github.com/DQNEO/minigo Goで書いたGoコンパイラ
デモ: Cコンパイラ Fizz Buzz
デモ: Goコンパイラ Fizz Buzz
PHPerとCコンパイラ <?php php-src (C) C compiler Assembly Binary /usr/bin/php スクリプト
処理系
コンパイラとは何か
コンパイラとは何か 広義: 言語Xのコードを言語Yに変換するソフトウェア 狭義: 言語Xのコードを低レベル言語(アセンブリ/機械語 /etc)に変換するプログラム
コンパイラは 何をしているのか
Cコンパイラ (8cc) int sum(int a, int b) { return a
+ b; } sum: push %rbp mov %rsp, %rbp push %rdi push %rsi mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret C言語 GNU assembler
コンパイラを作ってわかったこと アセンブリの知識が必要
コンパイラを作ってわかったこと • (多くの)コンパイラはアセンブリを吐く • アセンブリを理解し読み書きするスキル必要 = CPUのはたらきを理解すること
sum: push %rbp mov %rsp, %rbp push %rdi push %rsi
mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret アセンブリ言語 ≒ マシン語 • 各行がCPUへの「命令」 • どの行も、ハードウェア に対して副作用を生じる (レジスタ(後述)またはメ モリ上のデータを変更す る)
sum: push %rbp mov %rsp, %rbp push %rdi push %rsi
mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret GNU Assembler CPUへの命令
sum: push %rbp mov %rsp, %rbp push %rdi push %rsi
mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret GNU assembler メモリ 読み書き
sum: push %rbp mov %rsp, %rbp push %rdi push %rsi
mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret GNU assembler レジスタ 読み書き
コンパイラを作ってわかったこと “レジスタ”が主役 ※私の主観です
CPU内にある超高速な一時記憶装置 CPU ← レジスタ “レジスタ”が主役 出典: http://ftp.procmail.org/~sskulrat/Courses/2006F-170/lectures/chap14/part1.html
Cコンパイラ (8cc) int sum(int a, int b) { return a
+ b; } sum: push %rbp mov %rsp, %rbp push %rdi push %rsi mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret C GNU Assembler 関数 → 関数 変数 → メモリ何番目
コンパイラを作ってわかったこと • C言語上の関数はアセンブリ上でも関数 • アセンブリには変数がない。 ◦ ハードウェア(メモリ/レジスタ)に「書く、読む」 • 「書き込む」「読み取る」という動作が基本
値とは何か
高級言語視点 値: 式を評価すると得られる もの 1;
mov $1, %rax 低級言語視点
値とは何か 1; mov $1, %rax C GNU assembler
値とは何か 式を評価して値を得る ↓ ある手続きを実行した際に、ハード ウェアのある場所に値を書き込む
値とは副作用である ※私個人の考えです
値とは何か 8ccの場合、一連の処理の最後に必 ずraxに値を書き込む約束になってい る。 raxが保持しているデータ、 これが「値」の実体
式を評価して値を得る x + y; mov -8(%rbp), %rax mov -16(%rbp), %rcx
add %rcx, %rax 演算の結果をraxに書き込む
隠れた副作用 実はrcxに副作用が残ったまま。 コンパイラ側で、このrcx値は再利用しないよう に気をつける。 これにより、副作用が1個(式の結果が1値)のよ うに見せかけている。 x + y; mov
-8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax
関数の戻り値 int sum(int x, int y) { return x +
y; } sum: push %rbp mov %rsp, %rbp push %rdi push %rsi mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret raxに値を書き込ん で関数を抜ける。 これが戻り値。 受け取る側は、rax から値を読み出す。 int sum(int x, int y) { return x + y; }
関数の戻り値 int sum(int x, int y) { return x +
y; } sum: push %rbp mov %rsp, %rbp push %rdi push %rsi mov -8(%rbp), %rax mov -16(%rbp), %rcx add %rcx, %rax leave ret int sum(int x, int y) { return x + y; } 「純粋な関数」 も、ハードウェア レベルでは副作 用がある
コンパイラを作ってわかったこと • if文とfor文は仕組みがほぼ同じ ◦ 条件判定とジャンプ • ローカル変数とグローバル変数は扱いが全然 違う • 「スタック」とローカル変数の関係
コンパイラ作りで得たもの1 • アセンブラの読み書き能力 • 字句解析・構文解析の知識 • 対象言語(C,Go)の仕様に詳しくなった
コンパイラ作りで得たもの2 • 原典にあたる習慣 ◦ 言語仕様書 ◦ Intel CPUマニュアル ◦ gdb,
gasマニュアル
Intel® 64 and IA-32 Architectures Software Developer’s Manual
コンパイラ作りで得たもの3 • Segmentation Fault に負けない心 ◦ gdb/gccなどのコンパイラツール系スキル
None
簡単なC/Goのコードな ら 脳内コンパイルできる
何でコンパイラを作ろうと思っ たのか?
もともとは普通の PHPアプリケーション 開発者だった
コンパイラ知識ゼロからのスタート • 字句解析・構文解析の解説を読んでも理解不能 • C,Goもそんなに詳しくない 「プログラムが動く原理を知りたい」
Rebuild.fm153回 https://rebuild.fm/153/ Rui Ueyama さんが Cコンパイラ(8cc)を作った話 きっかけ めちゃくちゃ面白い!!
• C言語製Cコンパイラ • スクラッチから開発 • インクリメンタル開発 8cc https://github.com/rui314/8cc
さっそく git clone
8cc 1コミット目 #include <stdio.h> #include <stdlib.h> int main(int argc, char
**argv) { int val; if (scanf("%d", &val) == EOF) { perror("scanf"); exit(1); } printf("\t.text\n\t" ".global mymain\n" "mymain:\n\t" "mov $%d, %%eax\n\t" "ret\n", val); return 0; } #include <stdio.h> extern int mymain(void); int main(int argc, char **argv) { int val = mymain(); printf("%d\n", val); return 0; } https://github.com/rui314/8cc/commit/3764b2071b9601067b81976d80175a0851d0f209
なんとなくわかる! しかし、ただ読んでるだけでは身につ かなそう Goに移植してみよう!
1コミット移植してみた https://github.com/DQNEO/8cc.go/commit/b711967431 07e50e0ac945383abc5b2c3bf2e302 動いた! 8cc.go (Goへの移植)
8ccのコミット履歴を1個ずつ • テストの追加分を見る • そのテストをパスするC実装を自力でやってみる • 無理なら正解をチラ見する • 自力でCで再現する •
無理なら写経 • Goに移植する 延々と繰り返す 8cc.go (Goへの移植)
• 5ヶ月半毎日継続 • 95コミット移植完了 • 基本的な文法はだいたい動く 8cc.go (Goへの移植)
移植で見えてきた問題点 • 8ccの字句読み取りの設計が複雑 • 9ccはきれいに設計できてる • 自分でもゼロから設計してみたい!
Goコンパイラ開発 • 試しにGoでGoのtokenizerを書いてみた • あっさり動いた!感動! → その勢いでGoコンパイラ開発に突入
minigo (Goコンパイラ) • 1日目:足し算が動いた! • 2日目:引き算・掛け算・関数呼び出しが動いた! • 5日目: helloworld.go が動いた!
minigo (Goコンパイラ) • 1ヶ月後:FizzBuzzが動いた!
• 5ヶ月後:自分自身のコンパイルに成功! (時間があればデモ) minigo (Goコンパイラ)
野望 • 夏〜秋ごろにセルフホスト達成予定 • 来年のアメリカのGopherConに応募するぞ
コンパイラはいいぞ
ご清聴 ありがとうございました