Cコンパイラ実装で躓いたところ

# 低レイヤを知りたい人のためのCコンパイラ作成入門
という Rui Ueyama氏による，有名なサイトが有る．(まったく入門ではないが)
そこを参考にコンパイラを作っていて，躓く点が非常に多かったため，ちょくちょく追加して行こうと思う．

# つまずきポイント

## token->strがNULLのときの動作
入力されたソースコードをtoken毎に分割していく後，最後のtokenは`EOF`だ，というふうな実装になっている．
その際，メンバ変数である`token->str`には`NULL`が代入される．
tokenizeが終わった後，構文木を構築する際，各種`consume`という名の関数でtokenを消費していき構築していく．
その際，構文上予測されるtokenかどうかを判断し，間違っていればエラー処理関数である`error`と，`error_at`を用いる．
この関数を用いると，視覚的に見やすくエラー表示がなされる．

例えばCのソースコードとして

```
1
```

が単体である場合，本来は`;`が来るはずであるが，この場合`NULL`になる．
`error_at`関数は，「;が予測されるけどNULLが入力されてるよ」と出力しようとする．
また，先頭から何文字目か，というのを表示する機能を持っている．以下のようなよく見るやつ．

```console
1
 ^ expected ";" but given ""
```

このとき，位置を算出するために，事前に入力コード全体の文字配列の先頭ポインタを持つ`user_input`が存在し，
それと，`error_at`にて渡される今現在見ている文字のポインタの差を取って，何文字目なのかを算出している．

もしココに`NULL`が渡された場合，(処理系によるが0周辺の値が多い?)差が膨大になるため，大量のスペースが
入力されてしまう．
コレによって，何が原因でエラーが発生したのかがわからなくなり．この問題自体を解決するのに数日かかった．

ちょうどセミコロンを構文に含んだと同時に発生したため，そもそも入力文字列が間違っているという想定がないことも，発見が遅れた原因だと思う．

## extern宣言

extern宣言を用いて，ファイル間での変数の共有を行っているが，最初，変数を参照するすべてのファイルで
グローバル変数の宣言的なものをしてしまっていた．


## Segmentation Fault
幾つかの設計簡略化のため，tokenはグローバルで保持されている．
ポインタでよくある話で，宣言，定義だけでは実体がない．それを失念していて，一生懸命実体のないリストの先頭から要素を追加しようとしていた．

グローバル変数は勝手に初期化されるものと言う認識が謎にあったみたい．（そもそも０で初期化されてるんだから有効なわけがない）

```c:hoge.h
extern Token *token;
```

```c:hoge.c
#include "hoge.h"

Token *token;

Token tok = calloc(1, sizeof(Token));
tok = ...;
token->next = tok;
```

もちろん結果は`Segmentation Fault`． Cのコンパイラどこで発生したか教えてくれないかなぁ(gdb/lldbを使えという話)

## STEP. 10 複数文字のローカル変数

### ポインタ初期化

またもやポインタの初期化を忘れていた．

```c:parse.c
// variable finder
typedef struct LVar LVar;

struct LVar {
  LVar *next;
  char *name;
  int len;
  int offset;
};

LVar *locals;

static LVar *find_lvar(Token *tok) {
  for (LVar *var = locals; var; var = var->next) {
    if (var->len == tok->len && !memcmp(tok->str, var->name, var->len)) {
      return var;
    }
  }
  return NULL;
}
```

登録されてあるかを，連結リストを見て確認するが，初回の`find_lvar`関数の呼び出し時に，グローバル変数`locals`は`NULL`であるので，範囲外アクセスで`Segmentation Fault`．
元記事には存在していなかったので，このぐらい自分でやれよ，なのか，もしかしたら自分が間違えているかも知れないが，よくわからん．
リファレンス実装にも初期化は書いておらず．なぜ動いているのか不明．

```c
if (locals == NULL) {
  locals = calloc(1, sizeof(LVar));
}
```
をfind_lvar関数の頭につけて，NULLだったときに確保してやると動いた．

### 連結リストの実装が意味不明だった

なんとなく連結リストというと，頭のポインタが最初に用意されていて，その後に要素を引っ付けていくイメージだった．
一番最初だけは頭のポインタに要素を打ち込む．末尾のnextは常に`NULL`．

```c
if (locals == NULL) {
  locals = calloc(1, sizeof(LVar));
  locals->name = ...;
  locals->next = NULL;
  return;
}
LVar *lvar = calloc(0, sizeof(LVar));
lvar->name = ....;
lvar->next = NULL;
locals->next = lvar;
```

みたいな感じ．でも記事においては

```c
lvar = calloc(1, sizeof(LVar));
lvar->next = locals;
lvar->name = ...;
locals = lvar;
```

となっていて，最初は意味がわからず，30分ほど考え続けた．
で，漸く，今作った新しい要素を先頭方向に追加して，localsのポインタ値を手前側に持ってくるってことをしていることに気づいた．
先頭のポインタは動かないっていう謎の考えがあったせい．

## STEP. 11 Returnの実装

### tokenizeがうまく言ってなかった ~~(未解決)~~ (解決)

記事通りのコードでは動かない場所があった．この程度も考えて解決できない人はプログラミングは向いてないので，たんぽぽを乗せる仕事をしたほうがいいという啓示だと思う．
自分はまだ考えても全くわかってないので，プログラミング向いていない．

ここでは`return`実装のため，`stmt`に一部変更を加える．
しかし，そのとおりのコードでは動かない．
（自分で作ったコンパイラが吐く）エラーは

```
return 1;
       ^ expected ';', but 1;
```

である．エラーが出力される部分を見てみる．

```c:parse.c
static Node *stmt() {
  Node *node;

  if (consume_keyword(TK_RETURN)) {
    node = calloc(1, sizeof(Node));
    node->kind = ND_RETURN;
    node->lhs = expr();
  } else {
    node = expr();
  }

  if (!consume(";")) {
    error_at(token->str, "expected ';', but %s", token->str);
  }
  return node;
}
```

細かな違いがあるものの大まかには記事と同様のコードである．なぜ動かないのか不明．
return文のEBNFは

```
stmt = expr ";" | "return" expr ";"
```
で，それを表現できてるとは思うのだが...

`return`だったら，`expr`を左のノードに追加する．もう片方は存在しない．
`expr`はかなり上位のノードで，変数や数値，四則演算の式を示すことができる．
先程の`return 1;`では，1はexprなので，それが評価された後，`;`のtokenが消費されるはずなんだけど....
なんで？
`return;`は通るみたいだ．

**追記：後に解決した．**
そもそもtokenizeがうまく言っておらず，`"return"`という文字列が`TK_RETURN`として認識されておらず，変数扱いとなっていたため，エラーが出ていた．
もし`return`という変数名が許容されるのであれば，あのエラーは正当なものになる．

直接的な原因は，自分が`ctype.h`の`isalnum`関数を用いており，この関数の返り値が，`A-z0-9だったら0を返す`であり，記事中で実装されていた独自の関数`is_alnum`とは逆であった．ちゃんと記事通りにしよう．プログラミング出来ないのに，下手にアレンジを加えるとすぐどこかに不整合が生じて，何倍もの時間を要してしまう．

C言語の標準ライブラリが真偽値を返してくれないので，ココらへんがいつになっても慣れない...