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
1.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
180
プログラミングの暗黙知
takoeight0821
0
80
git logで振り返る大学4年間
takoeight0821
1
170
自作言語にモジュールを実装した話
takoeight0821
0
390
量子コンピュータで乱数を生成した話
takoeight0821
1
260
自作言語コンパイラを作った話
takoeight0821
0
160
自作言語malgoのコンパイラをリファクタリングした話
takoeight0821
0
330
Language Server Protocolの話
takoeight0821
0
420
GraalVMで遊ぶ
takoeight0821
0
170
Other Decks in Programming
See All in Programming
20250704_教育事業におけるアジャイルなデータ基盤構築
hanon52_
5
790
Goで作る、開発・CI環境
sin392
0
230
PipeCDのプラグイン化で目指すところ
warashi
1
280
Team operations that are not burdened by SRE
kazatohiei
1
310
VS Code Update for GitHub Copilot
74th
2
650
なんとなくわかった気になるブロックテーマ入門/contents.nagoya 2025 6.28
chiilog
1
270
ふつうの技術スタックでアート作品を作ってみる
akira888
1
860
PicoRuby on Rails
makicamel
2
130
AI時代の『改訂新版 良いコード/悪いコードで学ぶ設計入門』 / ai-good-code-bad-code
minodriven
14
5.2k
プロダクト志向ってなんなんだろうね
righttouch
PRO
0
190
Code as Context 〜 1にコードで 2にリンタ 34がなくて 5にルール? 〜
yodakeisuke
0
130
第9回 情シス転職ミートアップ 株式会社IVRy(アイブリー)の紹介
ivry_presentationmaterials
1
320
Featured
See All Featured
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
Building Applications with DynamoDB
mza
95
6.5k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
13k
Documentation Writing (for coders)
carmenintech
72
4.9k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
31
2.4k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
130
19k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
357
30k
A better future with KSS
kneath
238
17k
How GitHub (no longer) Works
holman
314
140k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
34
3.1k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
15
1.5k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
46
9.6k
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コンパイラ本 実際のコンパイラのソースを読んでみる