#contents
*はじめに [#a259f028]
CC500というC（のサブセット）のコンパイラを500行で書こうというプロジェクトがあります。これはお出かけの移動中時間に気軽に読める量なので読まないわけにはいきませんね（笑）。というわけで読みます。
*コードを読む前に [#y35caf7c]
まず、[[公式>http://homepage.ntlworld.com/edmund.grimley-evans/cc500/]]のドキュメントを確認しましょう。
-特徴
--自己コンパイル可能！
--標準入力から読み込み、標準出力にELF Linux/x86を書き出す
--生成されるバイナリにはマシン語のexit, getchar, malloc, putcharが含まれている（ので自己コンパイルが可能）
--なお、freeはない
-制限
--プリプロセッサなし、CスタイルコメントはOK
--main()は初めに書く必要あり
--関数の引数や戻り値はintかchar*とみなされる
--いくつかのオペレータは実装されていない。例えばポインタの実態参照（*p）は使えない
--break, continue, switchは使えない（実装ヒントあり）
--structは使えない
--場合によってはgccとかだとエラーになるプログラムもコンパイルできますが実行するとクラッシュします:-P
-実装関連
--シンボルテーブル。関数、グローバル変数、ローカル変数
まあ500行（実際には600行ぐらい）じゃしかたないですよね。ともかくさっそく読んでみましょう。
*全体の流れ [#pc9e7e04]
ドキュメントにあった通り、main()はコードの先頭に書く必要があるので実際の処理はmain()から呼ばれたmain1()から始まります。
#code(C){{
int main1()
{
code_offset = 134512640; /* 0x08048000 */
be_start();
nextc = getchar();
get_token();
program();
be_finish();
return 0;
}
}}
開始処理（be_start）、トークン読み込んで（get_token）、構文解析して（program）、終了処理（be_start）の構成になっています。be_start()に進んでもいいですが今回はボトムアップに見ていくことにしましょう（実際、CC500のソースはそんな感じに構成されています）
開始処理（be_start）、トークン読み込んで（get_token）、構文解析して（program）、終了処理（be_finish）の構成になっています。be_start()に進んでもいいですが今回はボトムアップに見ていくことにしましょう（実際、CC500のソースはそんな感じに構成されています）
*トークン周り [#k96266b4]
トークンの処理はget_token()で行われています。そんなに長くないので読めばわかりますが取得するトークンはいくつかの種類に分かれています。（公式に正規表現で書かれています）
なお、tokenへの値設定はtakechar()で行われます。
#code(C){{
i = 0;
while ((('a' <= nextc) & (nextc <= 'z')) |
(('0' <= nextc) & (nextc <= '9')) | (nextc == '_'))
takechar();
}}
変数名を取得しています。と思ったのですが、キーワードとか数値も取得されますね。浮動小数点数は変なことになるけど、サポートしてないからいいのか（笑）
余談ですが&&じゃなくて&なのは、&&をサポートしていないからです。確かに短絡評価対応すると長くなりますからね（笑）
#code(C){{
if (i == 0)
while ((nextc == '<') | (nextc == '=') | (nextc == '>') |
(nextc == '|') | (nextc == '&') | (nextc == '!'))
takechar();
}}
iというのが何気にグローバル変数なので注意が必要です。先の変数名取得が外れた場合に実行され、条件演算子を取得しています。
#code(C){{
if (nextc == 39) {
takechar();
while (nextc != 39)
takechar();
takechar();
}
}}
39はACIIコードで「'」です。つまり、'A'みたいなものを取得しています。なんでASCIIコード？と思ったら'\''と書けないからですね（笑）
#code(C){{
else if (nextc == '"') {
takechar();
while (nextc != '"')
takechar();
takechar();
}
}}
文字列（"foo"）の取得です。
#code(C){{
else if (nextc != 0-1)
takechar();
}}
その他。演算子とかかな？
*シンボルテーブル周り [#y67b5aae]
次にシンボルテーブル関連の関数を見てみましょう。公式のドキュメントに書かれていますがシンボルテーブルには以下の4タイプが格納されます。
-L：ローカル変数のスタック位置
-A：関数の引数のスタック位置
-D：関数やグローバル関数のポインタ
-U：シンボルが使われている場所へのポインタ（リンクリスト）
ドキュメント通り、シンボルテーブルはchar型の一次元配列char *tableに格納されます。とりあえず一番最初に書いてあるsym_lookup()を見てみましょう。
#code(C){{
int sym_lookup(char *s)
{
int t = 0;
int current_symbol = 0;
while (t <= table_pos - 1) {
i = 0;
while ((s[i] == table[t]) & (s[i] != 0)) {
i = i + 1;
t = t + 1;
}
if (s[i] == table[t])
current_symbol = t;
while (table[t] != 0)
t = t + 1;
t = t + 6;
}
return current_symbol;
}
}}
lookupの名前通り、シンボルテーブルからシンボルの検索を行っています。一瞬、「見つかったのになんでwhile抜けないの？」と思いますが、スコープ対応のためですね。つまり、グローバル変数のiとローカル変数のiがある場合、ローカル変数の方が使われるようにするためです。グローバル変数でiってしてるのここら辺がちゃんと処理できてるかのテスト兼ねてるのかな（笑）
さて、+6としているのはシンボル情報に6バイト使用しているためのようです。sym_lookup()ではそこら辺がわからないのでその下のsym_declare()を見てみましょう。
#code(C){{
void sym_declare(char *s, int type, int value)
{
int t = table_pos;
i = 0;
while (s[i] != 0) {
if (table_size <= t + 10) {
int x = (t + 10) << 1;
table = my_realloc(table, table_size, x);
table_size = x;
}
table[t] = s[i];
i = i + 1;
t = t + 1;
}
table[t] = 0;
table[t + 1] = type;
save_int(table + t + 2, value);
table_pos = t + 6;
}
}}
シンボルテーブルは自動伸長式になっています。なお、tableやtable_sizeの初期値は0(NULL)です。設定されている値からシンボル情報のレイアウトは以下のようになっていることがわかります。
|シンボル名(可変長)|NUL(1バイト)|タイプ(1バイト)|値(4バイト)|
残りのsum_*関数はまた後で見ます（というのも残りの関数はコード生成と密接に関わっているからです）
*構文解析＆コード生成 [#e29c3fbf]
**accept(), expect(), peek() [#gad2c163]
構文解析の補助関数として用意されているのがaccept(), expect(), peek()です。内容としては難しくないですが、コード中で「if (accept(";"))」だったり、「if (accept(";") == 0)」だったりするのでaccept()が0を返すのはどういうときかを少し意識して読む必要があります。（「!accept(";")」と書かないのは否定演算子をサポートしていないためです）
#code(C){{
int peek(char *s)
{
int i = 0;
while ((s[i] == token[i]) & (s[i] != 0))
i = i + 1;
return s[i] == token[i];
}
int accept(char *s)
{
if (peek(s)) {
get_token();
return 1;
}
else
return 0;
}
void expect(char *s)
{
if (accept(s) == 0)
error();
}
}}
**program()〜primary_expr() [#haca6d01]
えっと、みなさん、再帰下降パーサわかりますよねｗ。コード中、前に書かれている関数ほど小さい要素で解析する際はprogramから開始して受理可能な文法をもとに徐々に関数を進んでいきます。
-program()：グローバル変数、関数（前方宣言、本体）
-statement()：ブロック（スコープ処理）、変数宣言、if, while, return
-expression()：式、代入
-bitwise_or_expr()：|
-bitwise_and_expr()：&
-equality_expr()：等号、不等号
-relational_expr()：<=
-shift_expr()：シフト演算
-additive_expr()：足し算引き算
-postfix_expr()：配列、関数呼び出し
-primary_expr()：識別子、定数（数字、文字列）、(式)
普通のコンパイラだと、構文解析を行った後、最適化したりなどなどをしますがCC500ではそのまま実行コードを生成しています。
出力コードを記録する関数はemit()です。まあこの関数自体は何の変哲もないので載せませんがやや注意が必要な点として、
#code(C){{
void be_pop(int n)
{
emit(6, "\x81\xc4...."); /* add $(n * 4),%esp */
save_int(code + codepos - 4, n << 2);
}
}}
「\x81\xc4」とありますがこれは横のコメントになるようにマシン語そのものになります。しかし、その後ろの「....」はマシン語ではありません。この部分は次に続くsave_int()でint値を埋め込むための領域になります。
**be_start() [#u0bc560f]
ではようやくbe_start()を見ます。
#code(C){{
void be_start()
{
emit(16, "\x7f\x45\x4c\x46\x01\x01\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00");
emit(16, "\x02\x00\x03\x00\x01\x00\x00\x00\x54\x80\x04\x08\x34\x00\x00\x00");
emit(16, "\x00\x00\x00\x00\x00\x00\x00\x00\x34\x00\x20\x00\x01\x00\x00\x00");
emit(16, "\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x00\x80\x04\x08");
emit(16, "\x00\x80\x04\x08\x10\x4b\x00\x00\x10\x4b\x00\x00\x07\x00\x00\x00");
emit(16, "\x00\x10\x00\x00\xe8\x00\x00\x00\x00\x89\xc3\x31\xc0\x40\xcd\x80");
sym_define_global(sym_declare_global("exit"));
/* pop %ebx ; pop %ebx ; xor %eax,%eax ; inc %eax ; int $0x80 */
emit(7, "\x5b\x5b\x31\xc0\x40\xcd\x80");
(省略)
sym_define_global(sym_declare_global("putchar"));
/* mov $4,%eax ; xor %ebx,%ebx ; inc %ebx */
emit(8, "\xb8\x04\x00\x00\x00\x31\xdb\x43");
/* lea 4(%esp),%ecx ; mov %ebx,%edx ; int $0x80 ; ret */
emit(9, "\x8d\x4c\x24\x04\x89\xda\xcd\x80\xc3");
save_int(code + 85, codepos - 89); /* entry set to first thing in file */
}
}}
う〜ん、何やっているかは私もわかりませんｗ。とりあえず、be_start()では、
-ELFヘッダの設定
-組み込み関数（exit, getchar, malloc, putchar）の定義
を行っています。ここで気になるのが先ほど飛ばしたsym_declare_global()とsym_define_global()です。
**sym_declare_global(), sym_define_global(), sym_get_value() [#t5705519]
まずsym_declare_global()。特に難しい要素はありません。
#code(C){{
int sym_declare_global(char *s)
{
int current_symbol = sym_lookup(s);
if (current_symbol == 0) {
sym_declare(s, 'U', code_offset);
current_symbol = table_pos - 6;
}
return current_symbol;
}
}}
sym_define_global()。こちらはぱっと見ではわかりません。
#code(C){{
void sym_define_global(int current_symbol)
{
int i;
int j;
int t = current_symbol;
int v = codepos + code_offset;
if (table[t + 1] != 'U')
error(); /* symbol redefined */
i = load_int(table + t + 2) - code_offset;
while (i) {
j = load_int(code + i) - code_offset;
save_int(code + i, v);
i = j;
}
table[t + 1] = 'D';
save_int(table + t + 2, v);
}
}}
何をしているかというと、シンボルが使われているところにそのアドレスを埋め込んでいくということをしています。シンボルのタイプがUの場合、「シンボルが使われている場所へのポインタ（リンクリスト）」が格納されていると言いましたがこれだけだとまだよくわからないので次にsym_get_value()を見てみましょう。
#code(C){{
void sym_get_value(char *s)
{
int t;
if ((t = sym_lookup(s)) == 0)
error();
emit(5, "\xb8...."); /* mov $n,%eax */
save_int(code + codepos - 4, load_int(table + t + 2));
if (table[t + 1] == 'D') { /* defined global */
}
else if (table[t + 1] == 'U') /* undefined global */
save_int(table + t + 2, codepos + code_offset - 4);
else if (table[t + 1] == 'L') { /* local variable */
int k = (stack_pos - table[t + 2] - 1) << 2;
emit(7, "\x8d\x84\x24...."); /* lea (n * 4)(%esp),%eax */
save_int(code + codepos - 4, k);
}
else if (table[t + 1] == 'A') { /* argument */
int k = (stack_pos + number_of_args - table[t + 2] + 1) << 2;
emit(7, "\x8d\x84\x24...."); /* lea (n * 4)(%esp),%eax */
save_int(code + codepos - 4, k);
}
else
error();
}
}}
とりあえずUの場合のみ見ます。Uの場合、以下のコードが実行されるので、
emit(5, "\xb8...."); /* mov $n,%eax */
save_int(code + codepos - 4, load_int(table + t + 2));
save_int(table + t + 2, codepos + code_offset - 4);
コード上に今のシンボルテーブルの値が埋め込まれ、シンボルテーブルに埋め込まれた位置のアドレスが書き込まれます。図解するのがめんどくさいので（ぉ、省きますがこれでシンボル（宣言だけして実体定義はまだのもの）を参照している場所のリンクリストを作ることができます。
**ローカル変数周り [#cc9cb819]
次にローカル変数（スタック）周りを見ます。とりあえず、postfix_expr()を見ると以下のような記述（関数呼び出し）があります。
#code(C){{
else if (accept("(")) {
int s = stack_pos;
be_push();
stack_pos = stack_pos + 1;
if (accept(")") == 0) {
promote(expression());
be_push();
stack_pos = stack_pos + 1;
while (accept(",")) {
promote(expression());
be_push();
stack_pos = stack_pos + 1;
}
expect(")");
}
emit(7, "\x8b\x84\x24...."); /* mov (n * 4)(%esp),%eax */
save_int(code + codepos - 4, (stack_pos - s - 1) << 2);
emit(2, "\xff\xd0"); /* call *%eax */
be_pop(stack_pos - s);
stack_pos = s;
type = 3;
}
}}
be_push()はeaxレジスタをスタックにpushするマシン語を書きこむ関数、be_pop()はespレジスタに引数の値*4を書き込む（ポップする）関数です。この部分では個々の引数に対するマシン語を生成したのち、eaxのレジスタに格納されている関数のアドレスを呼び出しています。えっと、primary_expr()のここも要りますね。
#code(C){{
else if (('a' <= token[0]) & (token[0] <= 'z')) {
sym_get_value(token);
type = 2;
}
}}
ともかく、関数呼び出しの際に重要となるのはstack_posです。みなさん、x86の関数呼び出しなんて一般常識ですよね？説明は省きます:-P
後はローカル変数の部分、statement()にブロックとローカル変数定義があります。
#code(C){{
if (accept("{")) {
int n = table_pos;
int s = stack_pos;
while (accept("}") == 0)
statement();
table_pos = n;
be_pop(stack_pos - s);
stack_pos = s;
}
else if (peek("char") | peek("int")) {
type_name();
sym_declare(token, 'L', stack_pos);
get_token();
if (accept("="))
promote(expression());
expect(";");
be_push();
stack_pos = stack_pos + 1;
}
}}
まあ、説明しなくてもわかりますよね:-P
スクロールさせるのもあれなのでsym_get_value()のローカル変数部分を再掲します。
#code(C){{
else if (table[t + 1] == 'L') { /* local variable */
int k = (stack_pos - table[t + 2] - 1) << 2;
emit(7, "\x8d\x84\x24...."); /* lea (n * 4)(%esp),%eax */
save_int(code + codepos - 4, k);
}
}}
スタックの該当位置から値を取得しています。
**宣言周り [#fac70e82]
最後に、グローバル変数や関数の宣言（前方宣言、実体宣言）です。
#code(C){{
type_name();
current_symbol = sym_declare_global(token);
get_token();
if (accept(";")) {
sym_define_global(current_symbol);
emit(4, "\x00\x00\x00\x00");
}
}}
シンボルがあった直後に「;」の場合、グローバル変数としています。
#code(C){{
else if (accept("(")) {
int n = table_pos;
number_of_args = 0;
while (accept(")") == 0) {
number_of_args = number_of_args + 1;
type_name();
if (peek(")") == 0) {
sym_declare(token, 'A', number_of_args);
get_token();
}
accept(","); /* ignore trailing comma */
}
if (accept(";") == 0) {
sym_define_global(current_symbol);
statement();
emit(1, "\xc3"); /* ret */
}
table_pos = n;
}
}}
こちらが関数です。引数の直後に「;」があったら前方宣言とし、そうでなければ本体として処理を行っています。
**be_finish() [#kffe3c55]
最後、be_finish()でコードを出力して終わりです。
*おわりに [#if7da923]
今回は500行でCコンパイラを作ろうというCC500を見てきました。500行という都合上、「え？なんでこう書かないの？」という部分もいくつかありました。普段何気なく使っている文法もその裏では非常にめんどくさいことをして実装されている（ので行数が増えるので別の書き方をしている）ということがよくわかりました。
この記事の原稿もそろそろ500行なので、終わります:-)
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
