80コメント24KB

ブートストラッピングでコンパイラを作ろう

■ このスレッドは過去ログ倉庫に格納されています

0001デフォルトの名無しさん

2009/12/27(日) 19:33:59

言語Lのコンパイラを言語Lで実装するにはブートストラッピングをしますが、
それをできるだけ原始的なレベルからやってみようと思います。
自分が実装するので、突っ込みお願いします。

コンパイラの勉強が主目的で、面白い言語を作ることは目的ではありません。

具体的には>>2

0002デフォルトの名無しさん

2009/12/27(日) 19:37:11

使用ツール: エディタ・アセンブラ・リンカのみ

手順:
1. アセンブラでLのものすごく小さなサブセット言語L1のコンパイラを作る
2. L1でL1のコンパイラを作る
3. L1で少しだけ多機能なL2言語のコンパイラを作る (これを繰り返す)

(オプショナルな目標)
4. どっかの段階でlex/yaccに相当するものをLで作る

0003デフォルトの名無しさん

2009/12/27(日) 19:42:14

×: 3. L1で少しだけ多機能なL2言語のコンパイラを作る (これを繰り返す)
○: 3. Lnで少しだけ多機能なLn+1言語のコンパイラを作る (これを繰り返す)

00041

2009/12/28(月) 00:00:09

誰も見てないかもですが・・・

一番最初のコンパイラの方針を考えました。
アセンブラで作るのでめちゃめちゃ簡単な言語(ほぼアセンブリ言語)にします。

- 標準入力からコード入力 → アセンブリ言語にコンパイル → 標準出力に出力
- リンカは手動で実行することにする

- 制御構造はifとgotoのみ
- 整数型のみ
- ハッシュテーブルがまだ無いので、識別子はx0，x1，…:レジスタ変数，y0，y1，・・・自動変数.の形式のみ。
- 関数は実装する
- 再帰下降型でパース

0005デフォルトの名無しさん

2009/12/28(月) 00:12:29

具体的な対象CPUやOSが書いてないよね

00061

2009/12/28(月) 00:26:48

>>5
CPU:x86系
OS:Linux

でやります。
今自分が使ってるのは
OS : Linux version 2.6.18-6-686 (Debian)
as/ld: 2.17
です。

0007デフォルトの名無しさん

2009/12/28(月) 00:32:19

それあとほぼあらゆる問題が「GCCのソース見ろ」で終わりそうですね

0008デフォルトの名無しさん

2009/12/28(月) 00:32:58

期待する

00091

2009/12/28(月) 00:59:27

>>7
読むだけより作った方が勉強になることもあるかと思いますので。

githubに空のリポジトリ作りました。
ttp://github.com/nineties/growl
開発コードはgrowl(growing language)です。

明日からちょびちょび頑張って作っていきますので応援よろしくお願いします。

0010デフォルトの名無しさん

2009/12/28(月) 09:09:20

GCC のソースを見るなんて筋が悪すぎる

0011デフォルトの名無しさん

2009/12/28(月) 10:14:15

そう言えば、GCCは自由を守るために、わざとおかしな造りにしてるって聞いたことがあった気がする

0012デフォルトの名無しさん

2009/12/28(月) 10:21:12

それでもっと自由な LLVM に置き換えられる訳か…

00131

2009/12/29(火) 08:45:58

作り始めました。
とりあえず、flush/getc/putc/exitだけ実装しました。
まだただのechoプログラムです。

続きは夜やります。
字句解析器作ります。

0014デフォルトの名無しさん

2009/12/29(火) 17:45:09

>>1
今時の実装だとNativeコード生成じゃなく
仮想プロセッサのコードへのコンパイラを作って
仮想プロセッサ->JIT->ネイティブ
の方がいいのじゃなかろうか？

0015デフォルトの名無しさん

2009/12/29(火) 18:23:02

smalltalk みたいだね

00161

2009/12/30(水) 00:08:59

>>14
自分もそう思います。
ただ、growlの言語機能が貧弱なうちは出来るだけ単純な構造で作ります。

今ざっくりと考えているロードマップ:
growl0 : アセンブラで実装 (超シンプルに作る)
growl1 : growl0で実装。制御構造・型の種類などを増強。
growl2 : growl1で実装。ヒープの利用・データ構造定義などを可能にする。
growl3以降 : 後で考える。

データ構造が定義できるようになれば、ハッシュテーブル等の利用が可能になり、
構文木も作れるようになるので、実装の幅が広がります。
growl2まではコンパイラと言うよりはほとんどテキストフィルタの様な物になると思います。

0017 【970円】【大吉】

2010/01/01(金) 00:53:16

あけおめ
>>1が成就しますように

00181

2010/01/01(金) 09:19:13

あけましておめでとうございます。

>>17
ありがとうございます。頑張ります。

00191

2010/01/05(火) 00:02:34

正月も明けたので再開します。明けましておめでとうございます。

字句解析ですが、いずれ字句解析器生成器を作る事も考えて、状態遷移モデルで書く事にしました。
状態遷移表ベースじゃなく遷移図ベースにします。

00201

2010/01/07(木) 00:20:04

字句解析器を
- 整数定数・キャラクタ定数・文字列定数・識別子・その他記号
まで実装してコミットしました。
次は予約語を実装して、その後コンパイラ本体の実装に入ります。

00211

2010/01/07(木) 00:20:45

現状の動作例：
% cd glc0
% cat test.c
#include <stdio.h>
int main(void) {
puts("Hello World");
}
% make
% ./glc0 < test.c
SYMBOL #
IDENT include
SYMBOL <
IDENT stdio
SYMBOL .
IDENT h
SYMBOL >
IDENT int
IDENT main
SYMBOL (
IDENT void
SYMBOL )
SYMBOL {
IDENT puts
SYMBOL (
STRING "Hello World"
SYMBOL )
SYMBOL ;
SYMBOL }

00221

2010/01/07(木) 19:51:09

lexerに予約語実装しました。(if goto returnのみ)
次はコンパイラ本体を書きます。
アセンブリでヒープ使うコード書きたく無いので、growl0では構文木を作らずに
パースしつつ逐次コード生成します。

growlの言語仕様は漠然と考えてますが、具体的には作りながら決めてきます。

特に以下の物についてみなさんのアイデアを頂けると嬉しいです。
1. Cのプリプロセッサ(include含め)のような事は止めたいです。

00231

2010/01/07(木) 19:59:36

(途中で切れちゃいました)

1. Cのプリプロセッサ(include含め)の代わり
テンプレートベースのメタプログラミングを出来るようにするつもり。
C++的なのではなく、template haskellみたいに、growl自身でメタプログラミングできるようにしたい。

2. データ構造定義
- オブジェクト指向にはしない予定
- variant・パターンマッチを使えるようにする

3. メモリ管理関係
- GCを搭載するかどうかは悩み中
- shared_ptr的なのは用意したい

00241

2010/01/10(日) 03:01:08

growl0で書いた以下のコードがコンパイルできるようになりました。

export main;
main: () {
syscall(1, 0); # exit(0)
};

まだ変数など一切使えませんが、結構早くアセンブラを抜け出せそうです。

0025デフォルトの名無しさん

2010/01/10(日) 08:04:11

乙
とか思ったが夜くらい寝ろｗ

00261

2010/01/10(日) 20:02:55

>>25 すいません(^^;

- グローバル変数の定義
- 関数コール f(a,b,c)
- 間接代入 *x = ..
などを実装しました。

値の管理はpush/popしまくるという大変非効率的な実装になっています。
構文木も識別子表もないので仕方ないです。

グローバル変数はアセンブリ言語レベルで名前が付けられるので簡単ですが、
ローカル変数などは>>4のような方針で作ります。

0027デフォルトの名無しさん

2010/01/10(日) 21:26:44

こんな感じのコードがコンパイルできるようになりました。↓
プログラミング言語っぽくなってきました。

#
# growl - generation 1
# Copyright (C) 2009 nineties
#

# $Id: stdlib.gl 2010-01-10 21:00:57 nineties $

export STDIN_FD;
export STDOUT_FD;
export STDERR_FD;

STDIN_FD : 0;
STDOUT_FD : 1;
STDERR_FD : 2;

# system calls
SYS_EXIT : 1;
SYS_READ : 3;
SYS_WRITE : 4;

export exit;
exit: (p0) {
# p0 : status
syscall(SYS_EXIT, p0);
};

00281

2010/01/14(木) 02:12:55

しばらくgrowlの構文の設計とそれに伴うコードの書き直しをしていました。
現状：配列とか書けるようになりました。↓

まだ代入構文とかありません。
あと、growl0では型の概念がないんですが、char配列とlong配列をどうやって区別するか悩み中です。
スカラ型についてはlong統一という方針です。

ary : [1,2,3];

f: (p0) {
return ary[p0];
};

export main;
main: () {
exit(f(2));
};

00291

2010/01/14(木) 02:26:34

growl0でHello World書いてみました。今のところはこれが精一杯です。

export main;

STDOUT_FD : 1;
SYS_EXIT : 1;
SYS_WRITE : 4;

main: () {
syscall(SYS_WRITE, STDOUT_FD, "Hello World\n", 12);
syscall(SYS_EXIT, 0);
};

現状だと文字列リテラルはtextエリアのど真ん中に確保して、
jmpで飛び越すというコードにコンパイルされます(笑)
後で直します。

movl STDOUT_FD,%eax
pushl %eax
jmp _lbl0
.section .rodata
_lbl1: .string "Hello World\n"
.text
_lbl0:
movl $_lbl1,%eax
pushl %eax

0030デフォルトの名無しさん

2010/01/14(木) 10:51:03

>>29
実行形式に落としてからobjdump -dにかけてみれ。

まあ.sが読みにくいので直したほうがいいとは思うが。

00311

2010/01/14(木) 14:03:28

>>30
なるほど、コンパイル時に並び替えしてくれるんですね。知りませんでした。
てことはjmpもいらないのか～。

0032デフォルトの名無しさん

2010/01/30(土) 03:48:29

ず～っと規制で書き込めませんでしたorz
現状、rowl1の実装を進めています。
アセンブリからdlopen()をコールする為のコードを書いている所です。

0033デフォルトの名無しさん

2010/02/12(金) 06:48:47

そろそろ完成したかな？

0034デフォルトの名無しさん

2010/02/12(金) 18:32:30

リポジトリの更新も止まってるし
てこずってるよう棚

0035デフォルトの名無しさん

2010/02/14(日) 00:57:43

レポジトリ見るとallocとかが実装され始めてるようだね。
1/22から更新がないようだがガンガレ

00361

2010/02/15(月) 21:08:17

久しく間があいてしまってすいません。
しばらく趣味に裂く時間がありませんで停滞しておりました。
そろそろペースを戻していきたいと思います。

dlopen()の実装は流石に挫折しましたのでglibcを直接呼ぶ方向にしたいと思います。
がんばります。

0037デフォルトの名無しさん

2010/02/21(日) 12:58:18

これは良いものが出来そうですね。
Linuxが普及する原動力になると思います。
期待しています。

0038デフォルトの名無しさん

2010/02/21(日) 18:37:39

↑なにいってんだこいつ

0039デフォルトの名無しさん

2010/02/21(日) 18:43:07

↓なにいってんだこいつ

0040デフォルトの名無しさん

2010/02/21(日) 21:42:19

これは良いものが出来そうですね。
Linuxが普及する原動力になると思います。
期待しています。

0041デフォルトの名無しさん

2010/02/21(日) 22:19:56

↑なにいってんだこいつ

0042デフォルトの名無しさん

2010/02/22(月) 23:18:01

とりあえず>>1すげぇな・・・・
とてもじゃないが俺には出来ん・・・
でも勉強に見させてもらうよ

00431

2010/02/27(土) 00:29:19

>>42
どうもありがとうございます。頑張りますので応援してください。

現在rowl2コンパイラを実装していますが、
Hindley-Milnerの型システム
GC
メタプログラミング機能
などを一気に実装しようとして大分苦しくなってきました。
なので方針を変更して、rowl2では型システムのみ追加することにして高級な機能は先送りに
しようと思います。

0044デフォルトの名無しさん

2010/03/11(木) 04:29:18

>>43
了解。
応援させていただきます。

0045デフォルトの名無しさん

2010/03/15(月) 23:52:43

経過報告です。型システムを黙々と実装中です。
で、単純なHindley-Milnerだと使いにくい言語になると思うんで、何らかの拡張を考えてます。

一つは名前付きのタプルフィールドです。
p : (x : 0.0, y : 0.0);
などと書けて、p.x、p.yとアクセスできるようにしたいと思います。
これは多分kindを使って、健全性・完全性を保ってできると思います。

それから型による多重定義です。
例えば 1 + 1、 1.0 + 1.0、などと書けるようにしたいと思います。
これは安直にやると完全性を壊してしまいそうな気がするので、勉強中です。
もし、よい論文など知っている方がいましたら教えていただけると嬉しいです。

0046デフォルトの名無しさん

2010/03/18(木) 18:05:04

きちんと構文解析してexpressionの型を決めていけばできると思うけど、
もっと簡単にやる方法あるのかな。

応援してる。

00471

2010/03/23(火) 16:13:31

型推論の方針は定まりました。健全性と完全性はある程度犠牲にして、
多重定義・多相的な定数リテラルをサポートできるようにしたいと思います。

それから↓に触発されてrowlでのOS作りに挑戦することにしました。

【超高速】C/C++に代わる低級言語を開発したい
ttp://pc12.2ch.net/test/read.cgi/tech/1268843875/

理想とかあまり考えないで、まったり作ります。

まだ何も出来ていないですけど、
rowl/os/rowlos.img
がそれです。QEMUで実行できます。

0048デフォルトの名無しさん

2010/03/24(水) 00:29:32

間違ってもその痛いスレを参考にしちゃだめだよ
どっちかっつーとひげぽんさん目指した方がいい(割とマジで言うけどあの人の技術面でなく取り組み方の方ね）

00491

2010/03/24(水) 01:13:03

新しいネタを頂いただけで、言語設計は自分の好きなようにやってこうと思います。
こっちはアセンブリのみで実装という縛りがあるんで、逆にあまり言語仕様で悩まなくていいですね。
ひげぽんさんはホント尊敬してます。特にやる気をあれだけ維持出来るのがすごいです。

0050デフォルトの名無しさん

2010/03/24(水) 04:40:08

ひげぽんなんていろいろ手を出してどれも中途半端
他の人のコードを何年も放置した後とりいれて顰蹙かったり
真似したら駄目

00511

2010/03/24(水) 23:14:37

人がどういうやり方してるかあまり気にしても仕方ないので、ひとりでやってる限りは適当にやります。
忠告ありがとうございます。

経過報告です。
型推論の実装は目処が立ったので、バックエンドの実装に入りました。
rowl1では
型付きCore言語→三番地コード→アセンブリ
というパスでやることにします。三番地コードを突っ込んだのは、値管理をスタックに頼らないで、レジスタ割り当てをちゃんとしようと思った為です。

00521

2010/03/26(金) 03:59:53

生存解析を三番地コードに実装しました。(liveness.rl)

00531

2010/03/26(金) 07:41:23

レジスタ割り当てを実装しました。グラフカラーリングで作りました。
これで、型付きCore→アセンブリが繋がったので、あとは命令や機能をいろいろ追加していきます。

予定：
- 数値演算
- 条件分岐
- レキシカルクロージャ
- ループ
その後は、多重定義あたりやってみます。

00541

2010/03/28(日) 01:45:02

経過報告です。
スタックローカルのタプルとかパターンマッチとか実装しました。
ここ数日、快調なペースです。

00551

2010/04/09(金) 01:54:27

rowl1の実装と並行してですが、rowl2の実装を開始しました。
ブートストラップ3週目です。

0056デフォルトの名無しさん

2010/04/16(金) 11:57:09

あれ、いつのまにか growl から rowl になったんですね。

00571

2010/04/19(月) 11:12:40

すいません、growlという名のアプリが既に存在しましたので。
gitのURL変更はアナウンス忘れですorz

0058デフォルトの名無しさん

2010/07/06(火) 17:17:56

00591

2010/10/21(木) 15:13:20

ご無沙汰しております。

ブログ立ててそっちで書いているうちにここの存在をすっかり忘れてしまっておりました。
自分でスレを立てておいて半年も放置してしまって大変申し訳ありません・・・。
いろいろと方針変更がありましたが、開発は続けておりましてGC搭載のVMが動くところまで来ました。
http://github.com/nineties

作ると言ったOSやってなかったり、関数型言語じゃなくなってたりなんかいろいろグダグダですいません。

0060デフォルトの名無しさん

2010/10/21(木) 22:10:22

>>59
がんばれー
かげながら応援してるよー

00611

2010/10/22(金) 01:16:09

>>60
ありがとうございます。頑張ります。

0062デフォルトの名無しさん

2010/12/27(月) 08:01:29

がんばれ!!!
僕も応援してるよ!!!

0063デフォルトの名無しさん

2010/12/27(月) 09:04:03

>>61
github経由でblogも見た、
感動した

00641

2010/12/29(水) 23:27:31

ありがとうございます！

実装を開始して今日で1年経ちました。
これからもがんばりますのでよろしくお願いします。
来年はドキュメントを書いて人に使ってもらえるようにすることが目標です。

0065デフォルトの名無しさん

2010/12/30(木) 15:26:27

頑張れ!!
Twitterもたまに見てますぞ!!

0066デフォルトの名無しさん

2010/12/30(木) 17:49:09

これ>>1は勉強とかのつもりかもしれないけど、やってることって70年代～80年代のbitやcomputer todayの連載記事（とか別冊本)みたいで
ものすごく読んでいて楽しい、最後まで行ったら全部まとめて一冊にして欲しいとか思う

0067デフォルトの名無しさん

2010/12/30(木) 20:49:47

周りも勉強になるから本当に良スレ
2ちゃんはこうあれば良いと思う

0068デフォルトの名無しさん

2010/12/30(木) 22:45:54

一人で誉め殺し乙
そこまでいくとわざとらしい

0069デフォルトの名無しさん

2010/12/31(金) 21:48:45

>>68
目が曇っちゃうとどうしようもないね

0070デフォルトの名無しさん

2011/01/23(日) 10:30:56

いまきた産業だけど
Javaのシンタックスシュガーを増やすとかそのくらいにしとけばいいのに

00711

2011/01/24(月) 13:04:52

おそくなりましたが、あけましておめでとうございます。
現状報告ですが、REPLの実装をしています。
バッファリングしないIOが必要だったりと面倒でちょっと時間がかかりそうな感じです。

>>70
言語作りではなくコンパイラの勉強が目的なので、出来るだけ既存物に頼らないで作ってく予定です。

0072デフォルトの名無しさん

2011/01/30(日) 23:27:29

Pythonとかがスマートポインタやウィークポインタから
ガベージコレクションに乗り換えたけど処理効率より
スコープを隠ぺいすることでコーディングの負担を減らしたいのかな

0073デフォルトの名無しさん

2011/04/01(金) 21:31:23.18

1すごい

0074デフォルトの名無しさん

2011/05/25(水) 17:00:29.86

rowlでOS作ってみるお

0075天使 ◆uL5esZLBSE

2011/07/03(日) 01:09:59.14

これ；デリミタっていうんだけどさ、よく打ち忘れるよね
Rubyだとつけなくてよくなるんだけど

ゴミじゃねーか

0076デフォルトの名無しさん

2011/07/03(日) 09:20:29.84

天使ちゃんマジ天使

0077デフォルトの名無しさん

2011/10/13(木) 07:20:49.66

ほ

0078デフォルトの名無しさん

2011/10/13(木) 12:07:47.17

>>75
;はデリミタじゃないぞ、行コメントだ

0079デフォルトの名無しさん

2011/11/22(火) 01:40:44.22

行コメントだね

0080片山博文MZ ◆0lBZNi.Q7evd

2011/11/23(水) 15:55:47.02

一般的には、;はセミコロンっていうんだけどね。

■ このスレッドは過去ログ倉庫に格納されています