gcc - yyparse (printf debug with dump-tree)
init は飛ばして(@@@) 字句解析もつまらんから飛ばして (@@@) 、構文解析を見ていこうと思う。(*lang_hooks.parse_file) (set_yydebug); と呼ばれているフックの先は c_common_parse_file のようだ。 pch_init なんてのがあってさすが 3.4 と思った。 c_parse_file ではすぐに yyparse に入ってしまう。
yyparse は c-parse.y にあるのだが、少しびっくりすることにこのファイルは c-parse.in から生成されている。 C と Objective-C のパーサを切り分けるためのようだ。まあつまるところ生成された c-parse.y を読めば良いと思う。さて、 yacc のソースは書く分には良いのですけど処理が追いにくいのがやっかいだ。とはいえとても重要な場所だと思うので、簡単なソースを書いてそれに対する挙動を逐一追っていって理解を深めようと思う。
とりあえずとても簡単な例から考える。
/* main.c */
int main() {
return 0;
}
これに対してどういう手順で木構造が生成されているかを調べる。逐一追う方法としては printf を埋め込んでやることにする。埋める場所のあたりを付けるために c-parse.in を読むと、 fndef は今回の場合、
declspecs_ts setspecs declarator
{ if (! start_function (current_declspecs, $3,
all_prefix_attributes))
YYERROR1;
}
old_style_parm_decls save_location
{ DECL_SOURCE_LOCATION (current_function_decl) = $6;
store_parm_decls (); }
compstmt_or_error
{ finish_function ();
POP_DECLSPEC_STACK; }
がマッチしそうだ。というわけで start_function 内に渡した引数をダンプするものと、 compstmt_or_error で関数の実装をダンプさせてやれば良いだろう。
普段から tree をダンプしたりすると gcc のビルド時に動く xgcc などでもダンプされて五月蝿いので、 -v オプションが付いている時のみダンプする。そのために c-opts.c の bool verbose の static をはずし、 c-decl.c の冒頭で、 extern bool verbose; を書き、 c-decl.c の start_function 内に、
if (verbose) {
FILE* fp = fopen("log", "a");
fprintf(fp, "start_function = {\n");
fprintf(fp, " declspecs =\n");
dump_node(declspecs, 0, fp);
fprintf(fp, " declarator =\n");
dump_node(declarator, 0, fp);
fprintf(fp, " attributes =\n");
if (attributes) dump_node(attributes, 0, fp);
fprintf(fp, "}\n");
fclose(fp);
}
を埋め、 c-parse.in の冒頭に同じく extern bool verbose; を書き、 compstmt: の中に、
if (verbose) {
FILE* fp = fopen("log", "a");
fprintf(fp, "compstmt =\n");
dump_node($1, 0, fp);
fclose(fp);
}
を埋める。これで関数宣言と関数の定義の節の tree がダンプされるはず。早速 tree-dump.c を読んでおいた効果があらわれるわけ。
で、 main.c をダンプすると、
start_function = {
declspecs =
@1 tree_list valu: @2
@2 identifier_node strg: int lngt: 3
declarator =
@1 call_expr fn : @2 args: @3
@2 identifier_node strg: main lngt: 4
@3 tree_list
attributes =
}
compstmt =
@1 compound_stmt line: 1 next: @2
@2 scope_stmt line: 2 begn clnp
next: @3
@3 return_stmt line: 2 expr: @4 next: @5
@4 modify_expr type: @6 op 0: @7 op 1: @8
@5 scope_stmt line: 3 end clnp
@6 integer_type name: @9 size: @10 algn: 32
prec: 32 min : @11 max : @12
@7 result_decl type: @6 srcp: main.c:1
size: @10 algn: 32
@8 integer_cst type: @6 low : 0
この後もだらだらと続くのだが、これ以上先は srcp:
しかし dump-tree の出力はわかりやすい。きちんとそれらしいものができていることがわかる。後で気付いたことだが、このダンプコードを埋め込んだおかげで理解が大幅に容易になった。
gcc - yyparse (declspecs_ts)
では declspecs ができるまで追ってみる。 declspecs_ts は
declspecs_ts: declspecs_nosc_ts_nosa_noea | declspecs_nosc_ts_nosa_ea | declspecs_nosc_ts_sa_noea | declspecs_nosc_ts_sa_ea | declspecs_sc_ts_nosa_noea | declspecs_sc_ts_nosa_ea | declspecs_sc_ts_sa_noea | declspecs_sc_ts_sa_ea ;
とのことで、これらも複雑に似たようなものを呼び出し続ける。 C 言語は型に const だのがべたべたとくっつくのでややこしくなっているのだろう。詳しく見てもあまり本質的では無いだろうから、これらの中で頻繁に呼ばれている tree_cons を読む。 cons は lisp の cons でリストを接続する役割を果たすはず。ここでは新しい node を tree_list 型で作って、
TREE_CHAIN (node) = chain; TREE_PURPOSE (node) = purpose; TREE_VALUE (node) = value;
などとしてメンバに代入している。(例えば TREE_CHAIN(node) は node->chain に化ける)
declspec_ts によって実際にどのように型情報が収められるかどうかを調べる。以下のようなものをコンパイルして tree をダンプさせてみた。
/* declspecs.c */ static volatile const char* volatile const restrict func() {}
ダンプされたものは以下の通り。
start_function = {
declspecs =
@1 tree_list valu: @2 chan: @3
@2 identifier_node strg: char lngt: 4
@3 tree_list valu: @4 chan: @5
@4 identifier_node strg: const lngt: 5
@5 tree_list valu: @6 chan: @7
@6 identifier_node strg: volatile lngt: 8
@7 tree_list valu: @8
@8 identifier_node strg: static lngt: 6
declarator =
@1 indirect_ref type: @2 op 0: @3
@2 tree_list valu: @4 chan: @5
@3 call_expr fn : @6 args: @7
@4 identifier_node strg: restrict lngt: 8
@5 tree_list valu: @8 chan: @9
@6 identifier_node strg: func lngt: 4
@7 tree_list
@8 identifier_node strg: const lngt: 5
@9 tree_list valu: @10
@10 identifier_node strg: volatile lngt: 8
attributes =
}
compstmt =
@1 compound_stmt line: 1
すぐに char => const => volatile => static と chain しているのが見て取れる。後置の修飾子は declarator の方に属するようだ。パーサの書きやすさのためだろうか。こちらは indirect_ref (ポインタのことだろう) => restrict => const => volatile と chain している。 declspecs_ts では purpose は使用されないようだ。
gcc - yyparse (declarator)
次は declarator 。型に対して後置される修飾子がこちらに含まれるというのは前に述べた通り。その部分を無視すると、 '(' の後に parmlist_or_identifiers と来ている。 identifiers をいきなり書くのは K&R 記法で、普通は parmlist の方が来るのだろう。大部慣れてきたので今度はいきなりダンプデータを読んでみる。
/* declarator.c */
void func(int int_variable) {}
これがコード。ダンプデータは
start_function = {
declspecs =
@1 tree_list valu: @2
@2 identifier_node strg: void lngt: 4
declarator =
@1 call_expr fn : @2 args: @3
@2 identifier_node strg: func lngt: 4
@3 tree_list purp: @4 chan: @5
@4 parm_decl name: @6 type: @7 scpe: @8
srcp: declarator.c:2 chan: @9
argt: @7 size: @10 algn: 32
used: 0
@5 tree_list valu: @7 chan: @11
@6 identifier_node strg: int_variable lngt: 12
@7 integer_type name: @12 size: @10 algn: 32
prec: 32 min : @13 max : @14
@8 translation_unit_decl srcp: :0
@9 parm_decl name: @15 type: @16 scpe: @8
srcp: declarator.c:2 argt: @16
size: @17 algn: 8 used: 0
@10 integer_cst type: @18 low : 32
@11 tree_list valu: @16 chan: @19
@12 type_decl name: @20 type: @7 scpe: @8
srcp: :0 chan: @21
@13 integer_cst type: @7 high: -1 low : -2147483648
@14 integer_cst type: @7 low : 2147483647
@15 identifier_node strg: char_variable lngt: 13
@16 integer_type name: @21 size: @17 algn: 8
prec: 8 min : @22 max : @23
@17 integer_cst type: @18 low : 8
@18 integer_type name: @24 size: @25 algn: 64
prec: 36 unsigned min : @26
max : @27
@19 tree_list valu: @28
@20 identifier_node strg: int lngt: 3
@21 type_decl name: @29 type: @16 scpe: @8
srcp: :0 chan: @30
@22 integer_cst type: @16 high: -1 low : -128
@23 integer_cst type: @16 low : 127
@24 identifier_node strg: bit_size_type lngt: 13
@25 integer_cst type: @18 low : 64
@26 integer_cst type: @18 low : 0
@27 integer_cst type: @18 high: 15 low : -1
@28 void_type name: @31 algn: 8
@29 identifier_node strg: char lngt: 4
@30 type_decl name: @32 type: @33 scpe: @8
srcp: :0 chan: @34
@31 type_decl name: @35 type: @28 scpe: @8
srcp: :0 chan: @36
@32 identifier_node strg: long int lngt: 8
@33 integer_type name: @30 size: @10 algn: 32
prec: 32 min : @37 max : @38
@34 type_decl name: @39 type: @40 scpe: @8
srcp: :0 chan: @41
@35 identifier_node strg: void lngt: 4
まだ長々と続くが、
@3 の purpose を見ると @4 => @9 と chain する。 @4 に含まれている情報は多いが、 name には int_variable という識別子名、 type には int という型名が入っていて、 @9 の name は char_variable で type は char という型名、ちゃんとパースできている。
@3 の chain は purpose に含まれている情報なのであまり意味が無いように感じられるが、これが何故かはとりあえず意味解析の段階まで保留 (@@@)。ここに限らず、 tree をこのように構成した理由というのは意味解析も見ないとわからないと考えられる。
実際に木を作るのは parmlist_or_identifiers からいくらか辿って parms のあたり。
parms:
firstparm
{ push_parm_decl ($1); }
| parms ',' parm
{ push_parm_decl ($3); }
;
push_parm_decl は push_decl に入り、 push_decl は長かったが、ようするに current_function_decl グローバル変数に push してくれるようだ。
さて、個々のパラメータだが、今回の場合、 parm の最初のものがマッチするはず。
parm:
declspecs_ts setspecs parm_declarator maybe_attribute
{ $$ = build_tree_list (build_tree_list (current_declspecs,
$3),
chainon ($4, all_prefix_attributes));
POP_DECLSPEC_STACK; }
attribute は気にする必要は無いだろう。 build_tree_list は明解だ。パラメータリストに tree_list を使用する場合のコメントも付記されている。
/* Return a newly created TREE_LIST node whose
purpose and value fields are PARM and VALUE. */
tree
build_tree_list (tree parm, tree value)
{
tree t = make_node (TREE_LIST);
TREE_PURPOSE (t) = parm;
TREE_VALUE (t) = value;
return t;
}
先に見たダンプもこれでだいたい理解できたはずだ。
gcc - yyparse (compstmt)
さて、これもいきなりダンプから。少し飽きてきた感もある。
/* stmt.c */
int main() {
char msg[] = "hello\n";
printf(msg);
return 0;
}
やっと hello world が出てくるわけ。さて compstmt のダンプは、
compstmt =
@1 compound_stmt line: 2 next: @2
@2 scope_stmt line: 3 begn clnp
next: @3
@3 decl_stmt line: 3 decl: @4 next: @5
@4 var_decl name: @6 type: @7 scpe: @8
srcp: stmt.c:3 chan: @9
init: @10 size: @11 algn: 8
used: 1
@5 expr_stmt line: 4 expr: @12 next: @13
@6 identifier_node strg: msg lngt: 3
@7 array_type size: @11 algn: 8 elts: @14
domn: @15
@8 function_decl name: @16 type: @17 scpe: @18
srcp: stmt.c:2 extern
body: @19
@9 function_decl name: @20 type: @21 scpe: @18
srcp: :0 undefined
extern
@10 string_cst type: @22 strg: hello
lngt: 7
@11 integer_cst type: @23 low : 56
@12 call_expr type: @24 fn : @25 args: @26
@13 return_stmt line: 5 expr: @27 next: @28
@14 integer_type name: @29 size: @30 algn: 8
prec: 8 min : @31 max : @32
@15 integer_type size: @33 algn: 32 prec: 32
min : @34 max : @35
@16 identifier_node strg: main lngt: 4
@17 function_type unql: @36 size: @37 algn: 64
retn: @24
@18 translation_unit_decl srcp: :0
@19 expr_stmt line: 0 expr: @38 next: @1
@20 identifier_node strg: printf lngt: 6
@21 function_type size: @37 algn: 64 retn: @24
prms: @39
@22 array_type size: @11 algn: 8 elts: @14
domn: @15
@23 integer_type name: @40 size: @37 algn: 64
prec: 36 unsigned min : @41
max : @42
@24 integer_type name: @43 size: @33 algn: 32
prec: 32 min : @44 max : @45
@25 addr_expr type: @46 op 0: @9
@26 tree_list valu: @47
@27 modify_expr type: @24 op 0: @48 op 1: @49
@28 scope_stmt line: 6 end clnp
ステートメントは next で接続するようだ。 @1 => @2 => @3 => @5 => @13 => @28 と接続されている。 @1 は全体の親ノード、 @2 でスコープ開始 ('{' に対応)、 @3 は char msg[] 、 @5 は printf 、 @13 は return 、 @28 はスコープ終了。
そしてその stmt 達にぶらさがっているノードはだいたい予想通りなものだ。たぶん適切なセッタで適切に代入されているのだろう。 declarator でそれなりに詳細に処理を追っかけたわけだしその詳細はとりあえず追っかけないことにする (@@@)。
gcc - yyparse (for_stmt)
前回の stmt は雑に飛ばしたのだが、少しやってみたいことがあるのでもう少し stmt に留まる。今回は for 文。
/* for_stmt.c */
int main() {
int i;
char msg[] = "hello\n";
for (i = 0; i < sizeof(msg); i++) {
printf("%c", msg[i]);
}
}
このダンプでは、 compstmt は二つ出力される。 for 文の中身のスコープと、 main の中身のスコープだ。 for_stmt まわりだけを示す。
@11 compound_stmt line: 5 body: @24 next: @25
@24 scope_stmt line: 5 begn null
clnp next: @37
@25 scope_stmt line: 8 end clnp
@37 for_stmt line: 5 init: @46 cond: @47
expr: @48 body: @49 next: @50
@46 expr_stmt line: 5 expr: @56
@47 le_expr type: @7 op 0: @57 op 1: @58
@48 postincrement_expr type: @7 op 0: @4 op 1: @59
@49 compound_stmt line: 5 body: @60
@50 scope_stmt line: 7 end null
@60 scope_stmt line: 5 begn null
clnp next: @71
@71 compound_stmt line: 5 body: @78 next: @79
clnp
@78 scope_stmt line: 6 begn clnp
next: @89
@79 scope_stmt line: 7 end null
clnp
@89 expr_stmt line: 6 expr: @98 next: @99
@99 scope_stmt line: 7 end clnp
スコープに二度入っていてわかりにくいが、
@11 => @25
=> @24 => @37 (for) => @50
(init) => @46 (i=0)
(cond) => @47 (iという木構造になっているようだ。 for (init; cond; expr) body のうち、 init と body だけが stmt だが理由は保留 (@@@)。なんとなく理由はわからんでもないが。 ANSI X3.159-1989 が欲しい。
gcc - yyparse (original expansion: foreach)
今までの知識を使って C 言語を勝手に拡張してみよう。 foreach ステートメントを導入する。以下のようなコードをコンパイルできるようにしたいわけだ。
/* foreach.c */
int main() {
int i;
char msg[] = "hello\n";
foreach (i; msg) {
printf("%c", msg[i]);
}
}
もちろん、まだ意味解析を調べていないため、本格的に作成することはできない。しかし、先程既に for_stmt を調べているため、 foreach を見つけたら for の木を作ってやることによって実現することは可能なのではないか。
さて c-parse.in に foreach を教えてやる。該当個所はすぐにわかると思う。
%token SIZEOF ENUM STRUCT UNION IF ELSE WHILE DO FOR FOREACH SWITCH CASE DEFAULT
{ "for", RID_FOR, 0 },
{ "foreach", RID_FOREACH, 0 },
/* RID_FOR */ FOR, /* RID_FOREACH */ FOREACH,
| FOREACH /* empty */
{ printf("foreach comes!\n"); }
| SWITCH '(' expr ')'
これで foreach.c をコンパイルすると、確かに foreach comes! と表示される。字句解析の拡張は成功したようだ。では構文解析部も作ってしまおう。四苦八苦した後、
| FOREACH '(' primary ';' primary ')'
{
tree init, cond, expr;
init = build_stmt(
EXPR_STMT,
build_modify_expr($3, NOP_EXPR, integer_zero_node));
cond = parser_build_binary_op(LT_EXPR, $3,
c_sizeof(TREE_TYPE($5)));
expr = build_unary_op(POSTINCREMENT_EXPR, $3, 0);
$$ = build_stmt (FOR_STMT, init, cond,
expr, NULL_TREE);
add_stmt($<ttype>$);
stmt_count++;
c_in_iteration_stmt++;
}
c99_block_lineno_labeled_stmt
{
RECHAIN_STMTS ($<ttype>7, FOR_BODY ($<ttype>7));
c_in_iteration_stmt--;
}
とすると動いた！これはうれしい。すなおにうれしい。つまらんデバッグを除けば、生まれて始めて gcc の hack に成功したわけだ。ああうれしい。ほんとにうれしい。
冷静に書こう。最初に述べた通り、これは foreach を for に歪めているだけに過ぎない。常識的に考えて FOREACH_STMT を作成して、意味解析でコード生成を行うべきだし、エラー処理も全くしていない。上記のコードは説明を書いていない部分が多いが、ただ for の構成要素を作るコードを呼び出しているだけだし、別に面白くもないので説明しない。
構文解析はこんなもんで終わりだろうか。たぶん次は意味解析、 RTL生成。ここまでは難しくなかったが wo さんをしてさえ RTL 生成は難しいらしい のでまあゆっくり読もう。
