そろそろ何か書こうと思ったので書いときます。
お姉さん「お姉さんとー」
山川君「山川君のー」
同時「ILogScriptほげほげなんとか講座ー」
--
山川君 : 普通の青年。最近は「リッチクライアント」とか言ってる。リッチクライアントって何よ。
お姉さん : アレな設定のお姉さん
--
お姉さん「山川君はILogScriptって知ってるかなー？」
山川君「知りません！！」
お姉さん「まあ、それもしかたないか…じゃあ、コンパイラを書きたい、と思ったことはあるかなー？」
山川君「無いですっ！！」
お姉さん「それだと、話が進まないじゃない。この質問は、[Y/y]みたいな感じだと思って返事してよ。」
山川君「そこで、^C」
お姉さん「酷いッ」
--
お姉さん「と、いうわけで、これから、ILogScriptのチュートリアルっぽい説明をしようかと思います。」
山川君「はいっ！ひとついいですか」
お姉さん「はいっ！なんでしょう！？質問しようとすることや、意見を言おうとする姿勢は非常に評価できますよ！！」
山川君「こういう風に説明文を会話形式にすると、 ネットワークの向こう側で"うわーこれ、オタが書いた文だよ…キモッ"とか言ってヒきまくるというような そういう人のイメージがありありと浮かんでくるんですが、その件については、どう対応すればよいでしょうかッ？」
お姉さん「あー…えー…」
--
と、まあ、その件についてなんだけど、この問題は非常に難しい問題であって、 例えば、コンパイラのことを、コン・パイラ君とか呼んじゃったりしてても、 一緒に名前を連ねるのを許しちゃう、みたいな、そういうセンスを理解できるだけの大きな器を持っていないと 立派なコンパイラの先生にはなれないんだぞ。というそういう問題も同時に含んでるのである。 コンパイラ書きというのは、そういう部分も要求されるのだ。多分。
todo: アレな絵を入れる
--
と、いうのは、あんまり本文とは関係無いとして、 このILogScriptチュートリアルでは、コンパイラを実際に実装しながら、ILogScriptについて説明していく。
あと、woはDOSまわりの件については、実際に見たことは無い、というのも補足しておく。一応。
まずは、どういう言語をつくるかを考えることにする。何でもいいんだけど、 いくつか基本的な要素を含めつつ、簡単な感じでいきたいよねぇ…と、いうことで、 次のものを含んだ言語にする
んで、これらを、Cみたいな構文スタイルの上に乗っけることにする。 イメージとしては、こんな感じ
int x = 4; int y = 5; int z = x + y * 5;
こういうことができる、と。 あとは、条件分岐やら、関数呼び出しやらを入れないと、計算したところで 結果が使えないからどうしようもないんだけど、とりあえず、それはまた次回ということで。（いつになるかわからんが）
で、とりあえず、この言語をEBNFみたいなので書いとくと、
program ::= (decl_stmt | expr_stmt)*
// expr
expr_stmt == expr ';'
expr ::= plus_expr
plus_expr ::= plus_expr '+' mult_expr |
plus_expr '-' mult_expr
mult_expr ::= mult_expr '*' term |
mult_expr '/' term
term ::= digit | ident | '(' expr ')'
// decl
decl_stmt ::= 'int' ident ('=' expr)? ';'
// token
ident ::= [_a-zA-Z][_a-zA-Z0-9]*
digit ::= [0-9]+
こんな感じ。
（予定:だらだらと構文木の話とか）
さて、こっからが本番。ILogScriptを使ってアセンブリを生成するところまでの話を。 あと、GCCの内部構造の勉強にも使える…かもしれない。
よくできた文章と違って、ボトムアップ方式で書いていってるので、読みにくいかもしれない。 読みにくいと感じた人は、一番最後の文字から逆方向に読んでいったら トップダウン的に読めたりしていいんじゃないかなー。と。（超適当）
では、まず、簡単な式の構文木の作りかたについての話。
で、ここでは、話を簡単にするために、プログラムコードを 脳内、および手で構文木へと変換してみることにする。 ハンドアセンブルならぬ、ハンドパースと言ったところか。語呂が悪い。
--
まず、簡単な式を考える。
1 + 2
こんなの。定数と定数の加算。これを構文木にすると、
（予定:図書き直す）
+
/ \
/ \
1 2
こんな感じ。まあ、見たまんまというか。
んで、これの木を表すデータをILogScriptで作ってみることにする。それが、次のプログラム。
// 1 + 2 var expr = gcc.build( gcc.PLUS_EXPR, types.integer_type_node, 1, 2 );
build関数が構文木を作る関数。これを呼び出して構文木を作る。
各引数の意味は次のとおり。
こんな感じ。「左辺値が1、右辺値が2のint型のPLUS_EXPR」という意味。
integer_type_nodeというのは、int型のことと思っていただいていいかと。
で、PLUS_EXPRというのは、加算式のこと。減算のMINUS_EXPR、乗算のMULT_EXPR、 その他色々などがある。どういうのがあるかについては、GCCソース内のtree.def参照。
--
まあ、とりあえず、構文木はbuild関数を使って作る、と。 で、作った構文木を確認するには、debug_tree関数を使う。
var expr = gcc.build( gcc.PLUS_EXPR, types.integer_type_node, 1, 2 ); debug_tree( expr );
こーすると、
<plus_expr 87ef18
type <integer_type 84aaf0 SI
size <integer_cst 848558 constant 32>
unit size <integer_cst 848600 constant 4>
align 32 symtab 0 alias set -1 precision 32 min <integer_cst 8485d0 -2147483648> max <integer_cst 8485e8 2147483647>
pointer_to_this <pointer_type 84fa10>>
constant
arg 0 <integer_cst 87eaf8 type <integer_type 84aaf0> constant 1>
arg 1 <integer_cst 87eb28 type <integer_type 84aaf0> constant 2>>
中あたりのごちゃごちゃしたところは抜いてもらって、
<plus_expr
constant
arg 0 <integer_cst constant 1>
arg 1 <integer_cst constant 2>>
こんな感じ。integer_cst というのは、整数定数のこと。arg0 = 1 の arg1 = 2 のplus_exprってなってるのを確認。と。
--
で、続いて、
1*2 + 3*4
こういうのを考える。
これの構文木は、
+
/ \
/ \
/ \
* *
/ \ / \
1 2 3 4
こんな感じ。で、これを組み立てるプログラムが、
// 1 * 2 var lhs = gcc.build( gcc.MULT_EXPR, types.integer_type_node, 1, 2 ); // 3 * 4 var rhs = gcc.build( gcc.MULT_EXPR, types.integer_type_node, 3, 4 ); // lhs + rhs var expr = gcc.build( gcc.PLUS_EXPR, types.integer_type_node, lhs, rhs );
こうなる。と。
--
で、こんな感じで、だらだらと構文木を作ってやって、できた構文木をgccの関数に つっこんでやると、対応するアセンブリが生成される、というわけ。
--
あと、余談として、gcc.foldという構文木中の定数を計算してくれる関数があったりする。 例えば、上のプログラムで、
var lhs = gcc.build( gcc.MULT_EXPR, types.integer_type_node, 1, 2 ); var rhs = gcc.build( gcc.MULT_EXPR, types.integer_type_node, 3, 4 ); var expr = gcc.build( gcc.PLUS_EXPR, types.integer_type_node, lhs, rhs ); debug_tree( gcc.fold(expr) );
こんなふうにしてやると、
<integer_cst 8f18a0 type <integer_type 84aaf0> constant 14>
こんな感じに。
--
まとめ: 式を作るには、build関数を使う。
さて、定数の計算ばっかりやっててもアレなので、変数を弄ってみることにする。 変数を作るには、build_declを使う。
var v = gcc.build_decl( gcc.VAR_DECL, gcc.get_identifier("var_name"), types.integer_type_node );
引数はそれぞれ、
これで、ここから作った変数を使えるようになる。使い方は定数の場合と同じように、 buildを使って構文木を構築するときに混ぜておく。
int hoge ; hoge + 4;
こういう場合を考えると、
// int hoge;
var hoge = gcc.build_decl( gcc.VAR_DECL, gcc.get_identifier("hoge"), types.integer_type_node );
// hoge + 4
var expr = gcc.build( gcc.PLUS_EXPR, types.integer_type_node, hoge, 4 );
debug_tree( expr );
こんな感じで。あー、あと、get_identifier("str")というのは、 じつは、バッククオートを使って、`strと書ける。こっちのほうが短く書けて効率がいいので、 こっちのほうがおすすめ。
ここで、変数の初期値と、いきたいのだけど、ローカル変数とゆーのは、 関数が無いと使えないので、ここらへん、続きが書けない。
で、まあ、そんなこんなで、ちょっとややこしいんだけど、先に関数のつくりかたを説明することにする。
--
とりあえずまとめ: 変数をつくるには、build_declを使う
あとで書く。
とりあえず、expand_stmtの中に書いていけばいい、といった感じで。
namespace langhook
{
function expand_stmt( stmts ) {
// ここに書いていけばいい
}
function type_for_mode( mode, unsignedp ) {
return types.integer_type_node;
}
};
var fn_type = gcc.build_function_type( types.void_type_node, types.void_type_node );
var fn_decl = gcc.build_decl( gcc.FUNCTION_DECL, `main, fn_type );
fn_decl.result = gcc.build_decl( gcc.RESULT_DECL, null, types.void_type_node );
fn_decl.arguments = null;
fn_decl.used = true;
fn_decl.external = false;
fn_decl.static = true;
fn_decl.public = true;
fn_decl.initial = gcc.make_node( gcc.BLOCK );
gcc.tree_rest_of_compilation( fn_decl, false );
で、話をローカル変数に戻しまして、さきほどの例をちょっと変えて、
int hoge = 5; int hoge2 = hoge + 4;
とでもするか。こいつを脳内コンパイルすると、
こんな感じですかね。変数の初期値の指定は、その変数のinitialというメンバに突っこんでおく。 例えば、上のプログラムをつくるのをコードで書くと、
// int hoge = 5; var hoge = gcc.build_decl( gcc.VAR_DECL, `hoge, types.integer_type_node ); hoge.initial = 5; // これが初期値 // hoge + 4 var expr = gcc.build( gcc.PLUS_EXPR, types.integer_type_node, hoge, 4 ); // int hoge2 = hoge + 4; var hoge2 = gcc.build_decl( gcc.VAR_DECL, `hoge2, types.integer_type_node ); hoge2.initial = expr; debug_tree( hoge2 );
こんな感じ？で、変数の宣言のアセンブリを生成するには、expand_decl、 変数の初期値を生成するには、expand_decl_initをそれぞれ使う。
上のプログラムを生成するプログラムが、
// int hoge = 5; var hoge = gcc.build_decl( gcc.VAR_DECL, `hoge, types.integer_type_node ); hoge.initial = 5; gcc.expand_decl( hoge ); // 変数 gcc.expand_decl_init( hoge ); // hoge + 4 var expr = gcc.build( gcc.PLUS_EXPR, types.integer_type_node, hoge, 4 ); // int hoge2 = hoge + 4; var hoge2 = gcc.build_decl( gcc.VAR_DECL, `hoge2, types.integer_type_node ); hoge2.initial = expr; gcc.expand_decl( hoge2 ); gcc.expand_decl_init( hoge2 ); debug_tree( hoge2 );
んで、こいつを、関数生成のexpand_stmtに入れてやると、
namespace langhook
{
function expand_stmt( stmts ) {
// int hoge = 5;
var hoge = gcc.build_decl( gcc.VAR_DECL, `hoge, types.integer_type_node );
hoge.initial = 5;
gcc.expand_decl( hoge );
gcc.expand_decl_init( hoge );
// hoge + 4
var expr = gcc.build( gcc.PLUS_EXPR, types.integer_type_node, hoge, 4 );
// int hoge2 = hoge + 4;
var hoge2 = gcc.build_decl( gcc.VAR_DECL, `hoge2, types.integer_type_node );
hoge2.initial = expr;
gcc.expand_decl( hoge2 );
gcc.expand_decl_init( hoge2 );
}
function type_for_mode( mode, unsignedp ) {
return types.integer_type_node;
}
};
var fn_type = gcc.build_function_type( types.void_type_node, types.void_type_node );
var fn_decl = gcc.build_decl( gcc.FUNCTION_DECL, `main, fn_type );
fn_decl.result = gcc.build_decl( gcc.RESULT_DECL, null, types.void_type_node );
gcc.current_function_decl = fn_decl;
fn_decl.arguments = null;
fn_decl.used = true;
fn_decl.external = false;
fn_decl.static = true;
fn_decl.public = true;
fn_decl.initial = gcc.make_node( gcc.BLOCK );
gcc.tree_rest_of_compilation( fn_decl, false );
こうなる。これで、アセンブリを生成する最低限のプログラム、といったところか。こいつを、hoge.ilogとかに保存して、
$ ilog1 -quiet --script-file=hoge.ilog
こんなふうにして実行してやる。
.file "<stdin>" .text .globl _main .def _main; .scl 2; .type 32; .endef _main: pushl %ebp movl %esp, %ebp subl $8, %esp movl $5, -4(%ebp) # hoge = 5 movl -4(%ebp), %eax # %eax = hoge addl $4, %eax # %eax += 4 movl %eax, -8(%ebp) # hoge2 = %eax leave ret
はい、ここは感動するところですよ。と、いっても、そこらへんは僕にしかわからんだろうけど。
まあ、それはいいか。とりあえず、コード生成はこんな感じになるんですよ、と。
--
まとめ: ローカル変数を出すには、expand_decl。 変数の初期値を出すには、expand_decl_init。 変数の初期値は、その変数のinitialに式を設定する。
さて、脳内でパースしたのを手動で構文木に変換する、というのもなかなかよいかと思うんだけど、 これではあんまりコンパイラっぽくないので、 入力プログラムを構文木に変換するような感じにしますかね。というような話。
まずは、ここから。入力文字列をトークンに分解するというところ。
今回使うトークンは、
[_a-zA-Z][_a-zA-Z0-9]* → 識別子 [0-9]+ → 数 ; → セミコロン int → 'int' キーワード + - * / → 演算子
こんなところか。これが解析できれば問題無いかと。
ILogScriptでは、字句解析は、正規表現のリストを使ってぐにょっと簡単にできるようになってるので、 それを使うことにする。
まずは、'4+5'という文字列を解析するのを考える。 トークンを、「(種類,文字列)」という表現であらわすとすると、こいつを解析した結果は、
(整数,'4') (プラスの演算子,'+') (整数,'5')
という三つの要素のリストになればいいだろう。
これを解析するスクリプトはこんな感じ
var input = stream.string_to_rstream("4+5"); // 入力データ
var lex_table = [
["[0-9]+":`TOK_DIGIT],
["\\+":`TOK_PLUS],
[null:`TOK_EOF] // 最後まできたら `TOK_EOFを返す
];
var lexer = Lex.generate_analyzer( lex_table );
while ( true ) {
var tok = lexer.next_token( input );
if ( tok.value == `TOK_EOF ) {
break;
}
print( "(" );
print( tok.value );
print( "," );
print( tok.chain[0] );
puts( ")" );
}
todo: こんど書く。説明がここらへんに。