Cコンパイラ作成入門のメモ #8 (Step11)
はじめに
こちらをやってみたときのメモを書いていく。
今回はStep11
Commit
Step11
調べたこと・理解したこと
トークナイズ結果出力用関数の実装
イメージ図/コード
// トークナイズした結果を出力する void token_preview(Token *start) { Token *cur = start; fprintf(stderr, ".... start preview tokens ....\n"); for (Token start; cur; cur = cur->next) { char c[100]; memset(c, '\0', sizeof(c)); memcpy(c,cur->str,cur->len); fprintf(stderr, " kind=> %d, str=> %s,\n", cur->kind, c); } fprintf(stderr, ".... finish!! ....\n"); }
メモ
.... start preview tokens .... kind=> 1, str=> foo, kind=> 0, str=> =, kind=> 2, str=> 1, kind=> 0, str=> ;, kind=> 3, str=> return, kind=> 1, str=> foo, kind=> 0, str=> ;, kind=> 4, str=> , .... finish!! ....
- 連結リストを辿っているlvar_findとかを参考に実装した。
参考
文字列用配列の初期化について
文字列を空にする | Programming Place Plus Ｃ言語編 逆引き
文字列の切り出しについて
C 言語でサブストリングを取得する | Delft スタック
思ったこと
パーサの実装について
returnの右側をlhsとしてノードに格納しているところ
Node *stmt() { Node *node; if (consume(TK_RETURN)) { node = calloc(1, sizeof(Node)); node->kind = ND_RETURN; node->lhs = expr(); } else { node = expr(); } if (!consume(';')) error_at(tokens[pos].str, "';'ではないトークンです"); return node; }
上記のパース部分returnの右側をlhsとしてノードに格納している。 直感的には右辺なんだけど、左辺としてデータ登録している部分イマイチしっくりこない。
パーサの文法と、コードの実装の対応
パーサの文法と、コードの実装の対応についてイマイチ腹落ちできていない。文法とコードを横に並べて、どことどこが対応しているか一回整理できれば、おおよそ理解できそうなので、今度一回まとめてみた。
書いて見ると、まぁ大体、対応は理解できた。 新しい構文に対応するときに、文法を自分で考えるのは難しそう。。。
まとめ図
- 画像にするとズレちゃうのでご容赦ください。
テキストに書いてあった複数ret出力されるが気にしないのところの解釈
イマイチしっくりこなかったので、下図にまとめた。
要は、使われることがないretも出力される実装になっている。
でも実装をシンプルにするためであり、実害が無いならそれでもいいよね。 ということと理解した。
まとめ図
エピローグ部分についておさらい
エピローグでやっていることが、やっぱりよくわからなくなったので、図にしてみた。
retでやっていることがいまいち理解できていない。 プログラムカウンタが存在しているはずだが、そこをテキストでは説明されていないので、そこがいまいちしっくり来ていないことが原因なのかも。 retが実行されるとrspは一個上にずれるのは、勝手にされる仕様なのだろうか？
まとめ図
思ったこと
やれば、やるほど、前回のここよくわかってないなぁというのが次々に出てくる。 気づけるだけよいということ？これもブログにoutputしている効能？
同じように9ccテキスト参考に実装してみた系のgithubを見ていると、自分よりもすごい短い期間に実装、コミットされていて自分との距離を感じる。
そんなに長い時間実装集中できないんだよなぁ。
慣れるとできるのかしら？
Cコンパイラ作成入門のメモ #7 (Step10)
はじめに
こちらをやってみたときのメモを書いていく。
今回はStep10
Commit
Step10
調べたこと・理解したこと
ローカル変数管理用の連結リスト周りについて
テキスト読んだだけではいまいち理解できなかったり、エラー吐いたりしたところについて、下図の通りにまとめた
イメージ図
思ったこと
- 連結リストに抵抗感がなくなってきた気がする。
- ローカル変数の管理方法についてよくわからないなぁと思って、次の日もう一度考えたら理解できたのでコツコツやるのは大事だと思った。
Cコンパイラ作成入門のメモ #6 (Step9)
はじめに
こちらをやってみたときのメモを書いていく。
今回はStep9
Commit
Step9
調べたこと、理解したこと
データ構造の流れ
イメージ図
メモ
参考
なし
NodeとCodegen実装の対応を理解
イメージ図
メモ
- gen()でどのようにパースした結果をアセンブリに変換しているのかを順を追って理解した。
参考
なし
スタックの伸びる方向について
イメージ図
メモ
- 「コラム: スタックの伸びる方向」に書いてあることがいまいちイメージできなかったので図にしてみた。
- 上位アドレス、下位アドレスで、上、下方向は図のようなイメージだと思う
参考
なし
consume_ident() の実装について
コード
// 次のトークンがidentのときには、トークンを１つ読み進めて // そのトークンを返す。それ以外の場合はNULLを返す。 static Token *consume_ident() { if (token->kind != TK_IDENT) return NULL;// 期待するトークンと不一致(変数でなければ)の場合はNULL // 次のトークンがIdentのときはreturnするtokenを退避 Token *ret = token; // tokenを次にconsumeする token = token->next; return ret; } // 新：primary = num | ident | "(" expr ")" static Node *primary() { // 次のトークンが"("なら、"(" expr ")"のはず if (consume("(")) { Node *node = expr(); expect(")"); return node; } Token *tok = consume_ident(); if (tok) { Node *node = calloc(1, sizeof(Node)); node->kind = ND_LVAR; //文字コードからaから何文字先かを求めてそれに8byte掛けて、オフセットを計算 node->offset = (tok->str[0] - 'a'+1) * 8; return node; } // （）でもidentでもなければ数値のはず return new_num(expect_number()); }
メモ
- 変数を読み進めるための関数。
- テキストには実装書いてないので、こんな感じに実装した。
- consume()とかを参考に、returnにはtokenを返すように実装
参考
なし
『for (int i = 0; code[i]; i++)』のcode[i]でloop終了条件にしていいの？
コード
// 9cc.c int main(int argc, char **argv) { //中略 // 先頭の式から順にコード生成 // program()でcode[i]の最後はNULLになっているはずなのでfor文の終了条件はcode[i]でOK for (int i = 0; code[i]; i++) { gen(code[i]); // 式の評価結果としてスタックに１つの値が残っている // はずなので、スタックが溢れないようにポップしておく printf(" pop rax\n"); } //中略 } //parse.c // program = stmt* void *program() { int i = 0; while (!at_eof()) code[i++] = stmt(); code[i] = NULL; //ここで末尾にNULLを入れているから, mainのコード生成のfor文の終了条件判定がcode[i]でOKなのか }
メモ
- なんで、for文の終了条件が
code[i]でいいんだろう？と思った。 - ただ単に
program()でperse結果をcode[]に格納するときに、末尾にNULLを格納しているだけ。 - NULLポインタは評価すると
falseになるので、code[]終端でループ抜ける。
参考
- NULLポインタの定義についておさらいした
C言語 NULLポインタ【ポインタの参照を無効化する唯一の方法】
標準エラー出力でデバッグ
イメージ図/コード
// 新しいトークンを作成してcurに繋げる static Token *new_token(TokenKind kind, Token *cur, char *str, int len) { Token *tok = calloc(1, sizeof(Token)); tok->kind = kind; tok->str = str; tok->len = len; cur->next = tok; #ifdef DEBUG fprintf(stderr, "add new token. kind=> %d, str=> %s \n", kind ,str); #endif return tok; }
メモ
ビルドしたら、テスト通らなかったので、printfデバッグを試みた。
が、このコードは標準出力結果をアセンブラとして保存しているので、だめじゃんとなった。
標準エラー出力でデバッグすればよい。ということで、出力方法を調べた。
ちゃんとトークナイズはできてそう。ということはわかった。
ただ結局printfデバッグはあまり活躍せず、吐かれたアセンブリを読んでいって、pushとpopが逆に書いてあったり、いろいろケアレスミスを発見した。という感じで解決。
参考
参考にしたサイト
実装の参考
どう実装したらわからない部分参考にさせてもらった
ローカル変数導入 · pocari/compilerbook-9cc@9dbdc68 · GitHub
drawioファイルをブログに貼り付け
drawioをvscodeで描いて、githubのリンクを使ってブログで使う
Draw.ioをGitHub管理して画像を埋め込む - システム開発で思うところ
Draw.io Integrationの背景が暗いの嫌だなぁ
白背景にする方法
VScodeの拡張機能「Draw.io Integration」で背景色を白色に変更する方法
思ったこと
- 学習のススメ方について
- このステップは平日の仕事後の時間に15min.とかをコツコツ積み重ねながら進められたところがかなりよかった。
- まとまった時間はなくても進められる。と思えた。
- むしろ、よくわからないなぁと思いながら、中断して、次の日、仕事しながらバックグランドでそのことをぼんやり考えるので、ふとしたときに腹に落ちることが何度かあって、良かった。
- 細切れにやった方がよくわからないことを理解するときは、時間区切って、わからない状態で中断することがある意味効率的とも感じた
- draw.ioで図にかきながら理解したことが良かった
Cコンパイラ作成入門のメモ #5 (Step8)
はじめに
こちらをやってみたときのメモを書いていく。
今回は分割コンパイルとリンク、Step8
Commit
Step8
調べたこと
make
コード
CFLAGS=-std=c11 -g -static
SRCS=$(wildcard *.c)
OBJS=$(SRCS:.c=.o)
9cc: $(OBJS)
$(CC) -o 9cc $(OBJS) $(LDFLAGS)
$(OBJS): 9cc.h
test: 9cc
./test.sh
clean:
rm -f 9cc *.o *~ tmp*
.PHONY: test clean
}
実行されるコマンド
$ make cc -std=c11 -g -static -c -o tokenize.o tokenize.c cc -std=c11 -g -static -c -o 9cc.o 9cc.c cc -std=c11 -g -static -c -o parse.o parse.c cc -std=c11 -g -static -c -o codegen.o codegen.c cc -o 9cc tokenize.o 9cc.o parse.o codegen.o
理解したこと
Makefileの前提知識
- コロン(:)で区切られた行と、タブでインデントされた0行以上のコマンドの行が１つのルールを構成する
- コロンの前の名前のことを「ターゲット」という -コロンの後の0個以上のファイル名のことを依存ファイルという
- .PHONY
- ダミーのターゲットを表している
- make test や make cleanのtest,cleanというのは、そういう名前のファイルを作成するために指定しているわけでは無いが、makeにはそれがわからない。
- .PHONYで指定してあげることで、本当にそういう名前のファイルを作りたいわけではなく、指定されたターゲットのファイルが存在しているかどうかに関わらずルールのコマンドを実行するべき。ということをmakeに伝えることができる。
なぜこのMakefileでこのコマンドが実行されるのか
- サフィックスルール
コンパイルオプション
- cc -cオプションって何？
- ld(1) によるリンクを行わず、ソースファイルごとに .o ファイルを作成する
- 参考： cc コンパイラオプション
- ld(1) によるリンクを行わず、ソースファイルごとに .o ファイルを作成する
- cc -oオプションって何?
- 出力ファイルに名前を付ける
ルールを分解して考える
9cc: $(OBJS) $(CC) -o 9cc $(OBJS) $(LDFLAGS)
のルールでmakeがやることは？
変数
SRCSに含まれるのは？⇒tokenize.c,9cc.c, parse.c, codegen.c
OBJSに含まれるのは？⇒tokenize.o,9cc.o, parse.o, codegen.o
流れ
- 9ccを作りたいからOBJSを見に行こう
- OBJSにはtokenize.oが含まれるぞ
- .oには.cが必要だからtokenize.cを見に行こう
- tokenize.cが更新されているからコンパイルしよう
cc -std=c11 -g -static -c -o tokenize.o tokenize.cコマンドが叩かれる
CFLAGSで指定されている引数をつかってコマンドが叩かれる- 上記2. - 5. が全OBJS指定ファイル分繰り返される
- OBJSが揃ったから、いよいよコマンド行の実行をするぞ。
cc -o 9cc tokenize.o 9cc.o parse.o codegen.o - おわり
ちなみに、$(OBJS): 9cc.h の意味は
ちなみにOBJSは9cc.hに依存すると書いてあるので、もし9cc.hが更新されてたら、全.oは再度作り直しの意味
その他
- staticのお作法
- 同一ファイル内で定義された関数からしかアクセスされない関数はstaticをつける
- 参考：組込みソフト向けC言語コーディング規約｜関数の定義と宣言 | ハングスタック
- 文字列リテラルとは
- ソースコード内にべた書きした文字列
- 仕様上は文字列リテラルはその領域の変更は不可
- ただ、定義上はchar型のポインタの扱いになるので、変更してもエラーは出ない
- なので char型ではなく、const char型を使用する
- 参考：文字列リテラルとは｜「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典
- 参考：組込みソフト向けC言語コーディング規約｜変数の定義と宣言 | ハングスタック
思ったこと
- tokenizerについてはファイル分けると書いてなかったが、Referenceも分けているので分けといた
- makeにもccにもユーザが指定せずとも勝手にやってくれていることがたくさんあって、それを理解するのが大変。
- 理解しなくてもいいのかもだけど。
Cコンパイラ作成入門のメモ #4 (Step6, 7)
はじめに
こちらをやってみたときのメモを書いていく。
今回はStep6, 7
Commit
Step6
https://github.com/lvlnaga/9cc/commit/0dd18e522522b32fd049d74d5fdd023eddced843
Step7
https://github.com/lvlnaga/9cc/commit/e89c0bbd2f42a5a409211f38822f7d1b8bc6c45b
調べたこと
startswith
コード
bool startswith(char *p, char *q) { return memcmp(p, q, strlen(q)) == 0; }
詳細
- 文字列が特定のフラグメントで開始しているどうかを確認
- トークナイズするために、期待する文字列一致すれば true, 一致してなければfalseを返す関数を用意している
- Javaとかでは用意されている関数の模様。
参考
JavaのstartsWith、endsWithメソッドの使い方を現役エンジニアが解説【初心者向け】 | TechAcademyマガジン
【Python】startswith・endswith（指定文字で始まる？終わる？） | 鎖プログラム (pg-chain.com)
思ったこと
- 変更は大きいが変更している内容はおおよそ理解できた。
- ただ、これを自分で考えて開発できるかというとそんな気はしない。
- 引き出しが増えればこのパターンとかを引き出せる様になるのかな。
Cコンパイラ作成入門のメモ #3 (Step4, 5)
はじめに
こちらをやってみたときのメモを書いていく。
今回はStep4, 5 commitはこちら Add *, / and () · lvlnaga/9cc@f1b1a96 (github.com)
調べたこと
関数のプロトタイプ宣言について
- プロトタイプ宣言とは
- 「関数の名前」と「引数と返り値の型」だけを先に宣言すること。
- なぜ必要か
- コンパイラは上から順にコードを読んでいく。
- 関数が定義されてないのに、関数をcallされると、それが正しいのかわからない。
- 書き手からすると、関数の中身をまず書かないとcallできないのは面倒。
- プロトタイプ宣言という構文を用意すれば、さきに関数宣言しておいて、中身は後で書く。ということができるようになる。
- どういう嬉しさがあるか
- コンパイラが関数callのミスを検出できる
- 例えば、引数の数、引数のデータ型、戻り値のデータ型のチェック
- コンパイラが関数callのミスを検出できる
参考
C言語 プロトタイプ宣言の効果【関数を安全に呼び出す仕組み】
空returnについて
ここ
void gen(Node *node) { if (node->kind == ND_NUM ) { printf(" push %d\n", node->val); return; // ★ } ...
- 戻り値を持たないということ。NULLを返すのとは違う。
参考
【C言語入門】returnで関数の戻り値を返す方法 | 侍エンジニアブログ
strchr を使って特定文字有無のif文
ここ
if (strchr("+-*/()",*p)) // ★ { cur = new_token(TK_RESERVED, cur, p++); continue; } ...
- strchr関数は文字列の先頭から「文字」を検索して見つかった場所をポインタで返す
- これをif文のconditionとして使うことで、抽出したい文字が含まれるかどうかを確認している
- 賢い使い方というか、テクニック
参考
思ったこと
マインドマップに書きながら理解
読んでるだけじゃ全然いみ分からなかったのでマインドマップにまとめながら読み進めて言ったら、腹落ちできた。
再帰的な処理について
- 再帰的な関数は自分で思いつく気がしない。
- 「慣れてもこれでできるのが、不思議な感じがするものだよ。」という文章があって、そういうもんか。と思った
- 競技プログラミングとかコツコツやれば書けるようになる？
- 再帰的な処理って潜っていくところと、もどってくるところの2フェーズに分けられると思った。
説明の流れについて
- いきなり具体的な環境の話をするのではなく、自分の伝えたいことを伝えるために、まずはシンプルな仮想的な世界における振る舞いを説明する。という説明の流れでわかりやすい。
Cコンパイラ作成入門のメモ #2 (Step2,3)
はじめに
こちらをやってみたときのメモを書いていく。
今回はStep3まで commitはこちら tokenizerにより空白文字のスキップが可能になった · lvlnaga/9cc@056147d (github.com)
調べたこと
連結リスト
- リストは「要素」と「次のデータを指し示すポインタ」の２つからなるデータ数珠のようにつながっているデータ構造
- リストの場合は要素を探すために先頭からポイントをたどる必要あり
- 配列と比べていい点
- データの追加、削除がデータ数に関係なく数ステップでできる
- nextポインタを書き換えればOK
- データの追加、削除がデータ数に関係なく数ステップでできる
参考
うさぎでもわかる配列と連結リスト | 工業大学生ももやまのうさぎ塾 (momoyama-usagi.com)
tokenizeのところ詳細
書いたのはこれ
// 新しいトークンを作成してcurに繋げる Token *new_token(TokenKind kind, Token *cur, char *str){ Token *tok = calloc(1, sizeof(Token)); //? callocの仕様を知りたい tok->kind = kind; tok->str = str; cur->next = tok; return tok; } // 入力文字列pをトークナイズしてそれを返す Token *tokenize(char *p){ Token head; //dummyのhead要素を作る head.next = NULL; Token *cur = &head; //現在のtokenへのポインタにdummyのheadを設定 while (*p) { // 空白文字をスキップ if (isspace(*p)) { p++; continue; } if (*p == '+' || *p == '-') { cur = new_token(TK_RESERVED, cur, p++); //(1) continue; } if (isdigit(*p)) { cur = new_token(TK_NUM, cur, p); //(2) cur->val = strtol(p, &p, 10); continue; } error("トークナイズできません"); } new_token(TK_EOF, cur, p); return head.next; //先頭のトークンを返す }
(1)について
p++は後置演算子なので現在のpが指し示す位置でtokenを作成した後、 pが次の位置へと進められる。ということ
(2)について
strtol(p,&p,10);
で#2引数でpのポインタが次(数字の次の位置)に進められる。
strtolの#2引数には変換が失敗する文字がある位置(数字じゃない文字がある位置)のポインタが入る。
例えば 12 + をトークナイズする場合は、12の次の変換失敗する’ ‘ (スペース)の位置が&pに格納される。
すなわちポインタが次に進められる。
参考
文字列を数値に変換(C言語) - 超初心者向けプログラミング入門 (pc-note.net)`
可変個引数、動的引数 (...)について
// エラーを報告するための関数 // printfと同じ引数をとる void error(char *fmt, ...){ va_list ap; va_start(ap, fmt); vfprintf(stderr, fmt, ap); fprintf(stderr, "\n"); exit(1); }
引数の数を可変に受け取れる関数のこと。
stdarg.hで定義されているマクロとセットで基本的に使用する模様。
詳しくは下記。
可変個引数 | Programming Place Plus Ｃ言語編 第５２章 (programming-place.net)
vprintfについて、詳しくは下記。自前でエラー関数作ったりするときはよくある常套手段のような雰囲気。
vprintf | Programming Place Plus Ｃ言語編 標準ライブラリのリファレンス (programming-place.net)
