b8b3ab51ad9372a2b9f963650bbf14e714b87b85

Add Map data structure.

お、みんな大好きMapさん。これは楽しみだ。 hash関数を使うのか、open addressなのかlinked-list方式なのか！？

typedef struct {
  Vector *keys;
  Vector *vals;
} Map;

ずこー！

まあ9ccのシンプル一辺倒方針を考えればこれしかないとも言える。

Arrayを2つ並べただけ。おそらくget時はkeyを線形検索して同じindexのvalsを取る的な感じだろう。

main.c

ここでtest用のオプションが追加されている。オプションの形式はgolangとかimagemagickとかと同じ形式(由緒ある名前があるんだろうけどわからん)。

util.c

Mapの実装は想像通り。get時の検索が逆側からの検索になっている。最近セットしたものをよく使うだろうということなのかな？

if (!strcmp(map->keys->data[i], key))

個人的には、わかりやすさを目指すなら

if (strcmp(map->keys->data[i], key) == 0)

と書きたい。が、Cを書く人にはこっちのほうがわかりやすいんだろうか。

util_test.c

util系のユニットテストも書いている。この規模ならいらない気もするが。

ところでmallocは出てくるがfreeが出てこない。

この規模ならまだいらないんだろう。

https://github.com/rui314/9cc/commit/f8a1d0c6903dfe9ab816e719c70efdb27d6f0a4d

いよいよ文法が追加される。returnと;を追加するようだ。

token.c

なるほど、ここでmapをつかって予約語=keywordを登録する。 isalphaなどを使って続いている文字を読み取って、登録済みの予約語ならtokenを追加する。

ここまで書いてみて、ハッと気がついた。これはお題(test.sh)を見て、先に自分の考える実装をやってみてから答え合わせ的に写経したほうが学びが深そうだ。やってみよう。

parse.c(独自実装)

早速困った。return文をどうnode構造として解釈したらいいんだ。

テストを見るに、returnがついていたらそこで試合終了。計算結果をプロセスの終了ステータスにしたい。

この計算結果は既存の関数でできそうだ。

問題は1+2; return 3+4;みたいなパターン。

既存の考えのままだと、nodeの構造が数字と演算子しかないのでreturnとそうでない文を表現できない。

ここで音を上げて、早くもカンニングしてしまう。

なるほど、returnがないnodeとreturnのnodeを作って、これを計算結果の親としてnodeを組み上げれば良いようだ。

parse.cに

  for (;;) {
    t = tokens->data[pos];
    if (t->ty == TK_RETURN) {
      pos++;
      node = new_node(ND_RETURN, expr(), NULL);
      break;
    } else {
      node = new_node(ND_NORETURN, expr(), NULL);
    }
  }

のようなコードを追加した。

ir.c(独自実装)

noreturnなnodeは、変数もない現状では全く無駄なので、計算もせずに単純に飛ばせばいい。

  while (node->ty == ND_NORETURN) {
    node = node->lhs;
  }

あとはreturn nodeだけのはずなので、nodeの小要素でこれまで通り計算するだけ。

  assert(node->ty == ND_RETURN);
  node = node->lhs;
  int r = gen(v, node);

なんと、これだけで動いてしまった。楽しい。答え合わせもしてみよう。

token.c(答え合わせ)

これはすでに見ていたのでまあOK。答えを見てなかったらmapにkeywordを入れることを思いつけたかどうか……。

parse.c(答え合わせ)

typeが想像より多い。

ND_COMP_STMT => 全てのroot
ND_RETURN => return文
ND_EXPR_STMT => returnが無い文

という感じか。

Node構造体もメンバーが追加されている。

stmts => nodeは木構造のはずだが、配列としても用意している。なんでだろう？debug用か？
expr => 予想では計算結果をlhsに詰めていたが、専用にメンバーを用意したんだろう。やや富豪的。わかりやすさ重視かな？

ir.c(答え合わせ)

これまで引数で引き回していたVectorをファイルスコープの変数codeに変更している。Cはファイルスコープの変数やら関数が便利だよなあ。

ND_RETURN``ND_EXPR_STMTは予想通りとして、ND_COMP_STMTはなるほど、各文は木構造ではなく、素直に配列として持つことにしているようだ。

ここまでやって思ったが、ここまでで12 commit見てきた。このペースでは200 commit以上を見ていくのに果てしなく時間がかかってしまう……。

飽きてきたら更新辞めると思います。

スペクトラム

rui312/9ccを写経する-その4