2ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

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

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

1 :デフォルトの名無しさん:2009/12/27(日) 19:33:59
言語Lのコンパイラを言語Lで実装するにはブートストラッピングをしますが、
それをできるだけ原始的なレベルからやってみようと思います。
自分が実装するので、突っ込みお願いします。

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

具体的には>>2

2 :デフォルトの名無しさん:2009/12/27(日) 19:37:11
使用ツール: エディタ・アセンブラ・リンカのみ

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

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

3 :デフォルトの名無しさん:2009/12/27(日) 19:42:14
×: 3. L1で少しだけ多機能なL2言語のコンパイラを作る (これを繰り返す)
○: 3. Lnで少しだけ多機能なLn+1言語のコンパイラを作る (これを繰り返す)

4 :1:2009/12/28(月) 00:00:09
誰も見てないかもですが・・・

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

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

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

5 :デフォルトの名無しさん:2009/12/28(月) 00:12:29
具体的な対象CPUやOSが書いてないよね

6 :1:2009/12/28(月) 00:26:48
>>5
CPU:x86系
OS:Linux

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

7 :デフォルトの名無しさん:2009/12/28(月) 00:32:19
それあとほぼあらゆる問題が「GCCのソース見ろ」で終わりそうですね

8 :デフォルトの名無しさん:2009/12/28(月) 00:32:58
期待する

9 :1:2009/12/28(月) 00:59:27
>>7
読むだけより作った方が勉強になることもあるかと思いますので。


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

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


10 :デフォルトの名無しさん:2009/12/28(月) 09:09:20
GCC のソースを見るなんて筋が悪すぎる

11 :デフォルトの名無しさん:2009/12/28(月) 10:14:15
そう言えば、GCCは自由を守るために、わざとおかしな造りにしてるって聞いたことがあった気がする

12 :デフォルトの名無しさん:2009/12/28(月) 10:21:12
それでもっと自由な LLVM に置き換えられる訳か…

13 :1:2009/12/29(火) 08:45:58
作り始めました。
とりあえず、flush/getc/putc/exitだけ実装しました。
まだただのechoプログラムです。

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

14 :デフォルトの名無しさん:2009/12/29(火) 17:45:09
>>1
今時の実装だとNativeコード生成じゃなく
仮想プロセッサのコードへのコンパイラを作って
仮想プロセッサ->JIT->ネイティブ
の方がいいのじゃなかろうか?

15 :デフォルトの名無しさん:2009/12/29(火) 18:23:02
smalltalk みたいだね

16 :1:2009/12/30(水) 00:08:59
>>14
自分もそう思います。
ただ、growlの言語機能が貧弱なうちは出来るだけ単純な構造で作ります。

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

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

17 : 【970円】 【大吉】 :2010/01/01(金) 00:53:16
あけおめ
>>1が成就しますように

18 :1:2010/01/01(金) 09:19:13
あけましておめでとうございます。

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

19 :1:2010/01/05(火) 00:02:34
正月も明けたので再開します。明けましておめでとうございます。

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


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

21 :1: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 }

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

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

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


23 :1:2010/01/07(木) 19:59:36
(途中で切れちゃいました)

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

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

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

24 :1:2010/01/10(日) 03:01:08
growl0で書いた以下のコードがコンパイルできるようになりました。

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

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

25 :デフォルトの名無しさん:2010/01/10(日) 08:04:11

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


26 :1:2010/01/10(日) 20:02:55
>>25 すいません(^^;

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

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

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

27 :デフォルトの名無しさん: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);
};


28 :1: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));
};


29 :1: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


30 :デフォルトの名無しさん:2010/01/14(木) 10:51:03
>>29
実行形式に落としてからobjdump -dにかけてみれ。

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


31 :1:2010/01/14(木) 14:03:28
>>30
なるほど、コンパイル時に並び替えしてくれるんですね。知りませんでした。
てことはjmpもいらないのか〜。

32 :デフォルトの名無しさん:2010/01/30(土) 03:48:29
ず〜っと規制で書き込めませんでしたorz
現状、rowl1の実装を進めています。
アセンブリからdlopen()をコールする為のコードを書いている所です。

33 :デフォルトの名無しさん:2010/02/12(金) 06:48:47
そろそろ完成したかな?

34 :デフォルトの名無しさん:2010/02/12(金) 18:32:30
リポジトリの更新も止まってるし
てこずってるよう棚

35 :デフォルトの名無しさん:2010/02/14(日) 00:57:43
レポジトリ見るとallocとかが実装され始めてるようだね。
1/22から更新がないようだがガンガレ


36 :1:2010/02/15(月) 21:08:17
久しく間があいてしまってすいません。
しばらく趣味に裂く時間がありませんで停滞しておりました。
そろそろペースを戻していきたいと思います。

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

37 :デフォルトの名無しさん:2010/02/21(日) 12:58:18
これは良いものが出来そうですね。
Linuxが普及する原動力になると思います。
期待しています。

38 :デフォルトの名無しさん:2010/02/21(日) 18:37:39
↑なにいってんだこいつ

39 :デフォルトの名無しさん:2010/02/21(日) 18:43:07
↓なにいってんだこいつ

40 :デフォルトの名無しさん:2010/02/21(日) 21:42:19
これは良いものが出来そうですね。
Linuxが普及する原動力になると思います。
期待しています。

41 :デフォルトの名無しさん:2010/02/21(日) 22:19:56
↑なにいってんだこいつ

42 :デフォルトの名無しさん:2010/02/22(月) 23:18:01
とりあえず>>1すげぇな・・・・
とてもじゃないが俺には出来ん・・・
でも勉強に見させてもらうよ

43 :1:2010/02/27(土) 00:29:19
>>42
どうもありがとうございます。頑張りますので応援してください。

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

44 :デフォルトの名無しさん:2010/03/11(木) 04:29:18
>>43
了解。
応援させていただきます。

45 :デフォルトの名無しさん: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、などと書けるようにしたいと思います。
これは安直にやると完全性を壊してしまいそうな気がするので、勉強中です。
もし、よい論文など知っている方がいましたら教えていただけると嬉しいです。

46 :デフォルトの名無しさん:2010/03/18(木) 18:05:04
きちんと構文解析してexpressionの型を決めていけばできると思うけど、
もっと簡単にやる方法あるのかな。

応援してる。

47 :1:2010/03/23(火) 16:13:31
型推論の方針は定まりました。健全性と完全性はある程度犠牲にして、
多重定義・多相的な定数リテラルをサポートできるようにしたいと思います。


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

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

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

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

48 :デフォルトの名無しさん:2010/03/24(水) 00:29:32
間違ってもその痛いスレを参考にしちゃだめだよ
どっちかっつーとひげぽんさん目指した方がいい(割とマジで言うけどあの人の技術面でなく取り組み方の方ね)


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

50 :デフォルトの名無しさん:2010/03/24(水) 04:40:08
ひげぽんなんていろいろ手を出してどれも中途半端
他の人のコードを何年も放置した後とりいれて顰蹙かったり
真似したら駄目

51 :1:2010/03/24(水) 23:14:37
人がどういうやり方してるかあまり気にしても仕方ないので、ひとりでやってる限りは適当にやります。
忠告ありがとうございます。

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


52 :1:2010/03/26(金) 03:59:53
生存解析を三番地コードに実装しました。(liveness.rl)

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

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

54 :1:2010/03/28(日) 01:45:02
経過報告です。
スタックローカルのタプルとかパターンマッチとか実装しました。
ここ数日、快調なペースです。

55 :1:2010/04/09(金) 01:54:27
rowl1の実装と並行してですが、rowl2の実装を開始しました。
ブートストラップ3週目です。

56 :デフォルトの名無しさん:2010/04/16(金) 11:57:09
あれ、いつのまにか growl から rowl になったんですね。

57 :1:2010/04/19(月) 11:12:40
すいません、growlという名のアプリが既に存在しましたので。
gitのURL変更はアナウンス忘れですorz

58 :デフォルトの名無しさん:2010/07/06(火) 17:17:56
a

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

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.02.02 2014/06/23 Mango Mangüé ★
FOX ★ DSO(Dynamic Shared Object)