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
今日から始める自作コンパイラ ver 0.0.1
Search
Yuya Kono
July 26, 2020
Programming
0
1k
今日から始める自作コンパイラ ver 0.0.1
第28回 #hiro_it で発表した資料です。
自作コンパイラの概論みたいなテキストを書こうとしていて、その進捗報告第1回です。
Yuya Kono
July 26, 2020
Tweet
Share
More Decks by Yuya Kono
See All by Yuya Kono
自作プログラミング言語Malgoの紹介
takoeight0821
0
160
プログラミングの暗黙知
takoeight0821
0
71
git logで振り返る大学4年間
takoeight0821
1
160
自作言語にモジュールを実装した話
takoeight0821
0
360
量子コンピュータで乱数を生成した話
takoeight0821
1
230
自作言語コンパイラを作った話
takoeight0821
0
140
自作言語malgoのコンパイラをリファクタリングした話
takoeight0821
0
300
Language Server Protocolの話
takoeight0821
0
400
GraalVMで遊ぶ
takoeight0821
0
150
Other Decks in Programming
See All in Programming
Return of the Full-Stack Developer
simas
PRO
1
310
Preact、HooksとSignalsの両立 / Preact: Harmonizing Hooks and Signals
ssssota
1
700
自分のために作ったアプリが、グローバルに使われるまで / Indie App Development Lunch LT
pixyzehn
1
120
Go1.24で testing.B.Loopが爆誕
kuro_kurorrr
0
160
아직도 SOLID 를 '글'로만 알고 계신가요?
sh1mj1
0
360
Compose Navigation実装の見通しを良くする
hiroaki404
0
180
RailsでCQRS/ESをやってみたきづき
suzukimar
2
1.5k
20250326_生成AIによる_レビュー承認システムの実現.pdf
takahiromatsui
17
5.5k
いまさら聞けない生成AI入門: 「生成AIを高速キャッチアップ」
soh9834
12
3.7k
本当だってば!俺もTRICK 2022に入賞してたんだってば!
jinroq
0
250
令和トラベルにおけるコンテンツ生成AIアプリケーション開発の実践
ippo012
1
260
PHPer's Guide to Daemon Crafting Taming and Summoning
uzulla
2
1.1k
Featured
See All Featured
Why You Should Never Use an ORM
jnunemaker
PRO
55
9.3k
What’s in a name? Adding method to the madness
productmarketing
PRO
22
3.4k
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
47
5.3k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
12
1.4k
XXLCSS - How to scale CSS and keep your sanity
sugarenia
248
1.3M
Bash Introduction
62gerente
611
210k
A designer walks into a library…
pauljervisheath
205
24k
Speed Design
sergeychernyshev
28
860
Building Flexible Design Systems
yeseniaperezcruz
328
38k
jQuery: Nuts, Bolts and Bling
dougneiner
63
7.7k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
44
7.1k
[RailsConf 2023] Rails as a piece of cake
palkan
53
5.4k
Transcript
今日から始める自作コンパイラ ver 0.0.1 星にゃーん(@takoeight0821) 第28回 #hiro_it
近況 北極圏に埋められました
今日話すこと 自作コンパイラの入門、概論的な話を書いたテキストを作ろうとしています なかなかやる気がでないので、とりあえず書きたい内容をスライドにしました まだまだ未完成ですが、進捗報告みたいな感じで話そうと思います
このスライドの目標 コンパイラを作ってみたい人が、 • そもそもコンパイラとは一体どんなプログラムなのか • どこから手をつければいいのか • どんな情報源があるのか がわかるようになること
(そもそも)コンパイラって何?1/3
(そもそも)コンパイラって何?2/3 • “ある言語(原始言語)で書かれたプログラムを読み込んで、それを別の言語(目的言語)で 書かれた意味的に等価なプログラムへ翻訳するプログラムである ” - 『コンパイラ[第2版] 原理・技法・ツー ル』 ◦
原始言語はソース言語、目的言語はターゲット言語と呼ぶことも多い • 言語Aから言語Bへの翻訳プログラムのこと • gcc:Cからアセンブリ言語へのコンパイラ javac:JavaからJVMバイトコードへのコンパイラ clang:CからLLVM IRへのコンパイラ llc:LLVM IRからアセンブリ言語へのコンパイラ TODO: コンパイラドライバの話
(そもそも)コンパイラって何?3/3 • 一般にコンパイラと呼ばれるのは、ある言語からアセンブリ言語へのコンパイラ ◦ ネイティブコンパイラとも呼ぶ ◦ C、C++、Rust、Go • 独自の仮想マシンのバイトコードへのコンパイラもよくある ◦
Java、C#、ActionScript • アセンブリ言語以外へのコンパイラは「トランスパイラ」と呼ばれることもある ◦ TypeScript、CoffeeScript、”C with Classes”(C++の原型)
コンパイラの基本 ソース言語で書かれたプログラムも目的言語のそれも、たいていはただの文字列。 つまり、こんな感じのプログラムを書けばコンパイラになる!!
何から何へのコンパイラを作るか どんな言語から、どんな言語へのコンパイラを作るかを決めないとコンパイラは作れない。 いくつか考えられる案がある。 1. アセンブリ言語へのコンパイラ a. ふつうのプログラミング言語より表現力が低いので、ソース言語の意味を「かみくだく」必要がある b. どんなCPUアーキテクチャを対象にするか( x86,
ARM, RISC-V)も考えないといけない 2. C言語やJavaScriptへのコンパイラ a. どちらも割とどこでも動く高級言語(ふつうのプログラミング言語) Cコンパイラはいろいろな CPUに対応している。 JavaSciprtはWebブラウザがあれば動く 3. JVMへのコンパイラ a. Javaが動くマシンでなら動く b. Javaや他のJVM言語の資産を使える
アセンブリ言語へのコンパイラ TODO
C言語へのコンパイラ TODO
JavaScriptへのコンパイラ TODO
JVMへのコンパイラ TODO
何からのコンパイラを作るか • 自作言語コンパイラ ◦ 俺がかんがえた最強のプログラミング言語 ◦ 好きなプログラミング言語の特徴を組み合わせてみる(オブジェクト指向 +関数型とか) ◦ 限定継続、Algebraic
Effect、依存型など、まだ広く使われていない概念の実装を試す • C言語コンパイラ ◦ 最近(2019-2020)自作コンパイラ界隈で流行っている ◦ 『低レイヤを知りたい人のための Cコンパイラ作成入門』 • MinCamlコンパイラ ◦ http://esumii.github.io/min-caml/ ◦ 小さく読みやすいコンパイラ実装。これを改造したり移植したり
自作言語コンパイラ TODO 文法と意味を考える Cの関数を呼び出す機能をつけると拡張が楽
C言語コンパイラ TODO https://www.sigbus.info/compilerbook Cコンパイラ作成集中講座
MinCaml TODO http://esumii.github.io/min-caml/ 他言語への移植、機能の拡張 コンパイラの構造の参考
コンパイラを書くための技術 コンパイラにはやることがたくさんある • 構文解析:ソースコード(文字列)を解析して、抽象構文木( AST)を作る • 意味検査:プログラムが正しく動きそうかチェックする ◦ 定義してない変数の使用をチェックする(ミスタイプかも?) ◦
式の型が合っているかチェックする型検査 • 最適化:より速いプログラムに変換する ◦ 1 + 1 は 2 に置き換える、定数回のループは展開する • コード生成:目的言語のプログラムを生成する
構文解析 TODO 正規表現 字句解析 LL(1) LL(k) LR AST パーサコンビネータ
意味検査 TODO 変数の出現検査 2段階の構文解析テクニック 型検査 型推論
最適化 TODO データフロー解析 ループ最適化 SSA
コード生成 TODO プログラムを生成するプログラム 中間表現 レジスタ割当
例:簡単な言語からCへのコンパイラ TODO 変数と四則演算とサブルーチンをもつ言語から Cへのコンパイラ 式ベースで型推論を持つ言語から上の言語へのコンパイラ 組み合わせると下の言語から Cへのコンパイラができる
情報源 TODO 有名な教科書やWebサイト コンパイラ[第2版] 最新コンパイラ構成技法(入手困難) 低レベルプログラミング 計算理論の基礎 オートマトンと言語 MinCaml、Cコンパイラ本 実際のコンパイラのソースを読んでみる