compilerbook作成日記

nac-39

compilerbook作成日記

https://www.sigbus.info/compilerbook の作成記録です

nac-39

ステップ9

コンパイルは通るが、上手くtokenizeが動いていないっぽい

tokenizeする時のログ：

[2023/07/19/23 05:08:13] start tokenizing...
[2023/07/19/23 05:08:13] tokenizing: 0;
[2023/07/19/23 05:08:13] tokenizing number(0;): 
[2023/07/19/23 05:08:13] tokenizing: kind=TK_NUM, str=0;, len=1, val=0
[2023/07/19/23 05:08:13] tokenizing: ;
[2023/07/19/23 05:08:13] tokenizing reserved(;): 
[2023/07/19/23 05:08:13] token: kind=TK_NUM, str=0;, len=1, val=0 <-おかしい
[2023/07/19/23 05:08:13] token: kind=TK_NUM, str=0;, len=1, val=0
[2023/07/19/23 05:08:13] token: kind=TK_NUM, str=0;, len=1, val=0
[2023/07/19/23 05:08:13] end tokenizing...

token→lenと実際の文字列の長さが一致してなくてエラーになってることがあった
‘=’を許容する文字列に加えるのを忘れてた

ここまでの実装。
- https://www.sigbus.info/compilerbook#ステップ91文字のローカル変数
本と違うところとしては、
- logger、log用のヘルパー関数を実装した。printfと同じ構文で使えるLOGGER()という関数を定義した。log/log.txtに書き込まれるので、tail +1f ./log/log.txtで末尾だけ表示させ続けるのがやりやすい。
- consume_ident()の実装が書いてなかったので自分で実装した。consume()を参考に実装した。

nac-39

ステップ10, 11

グローバル変数のlocalsを最初にcallocしとかないといけない。LVar *locals;を宣言するだけでは、メモリに領域が確保されるわけではない。
bool consume(Tokenkind kind || char op);を定義したかったが、こんなことができるか分からなかったので、bool consume(char op)とbool consume_token(Tokenkind kind)に分けた。
user_input(p)をトークンにパースする段階で、複数文字のローカル変数のトークンにtoken→lenを文字数の長さ分設定する必要がある。

nac-39

ステップ12

この章から詳細な解説がなくなるので、今までコードのコピペで済ませて理解していなかった部分が浮き彫りになる。
わからないところは面倒でも前の方に戻ってもう一度読み直した方が良い。compilerbookに書いてある情報以外には基本的に必要ないはず。

わかってなかったこと

ツリーとコードの対応
どうやら今までこのツリーとコードの対応を理解していなかったらしい。白丸は関数を表していて、最終的に出来上がるノードに含まれない、ということを理解していなかった。

（左側の図はcompilerbookから拝借した）

nac-39

if文の実装

次のEBNFを実装する

program = stmt*
stmt    = expr ";" | "return" expr ";"
+        | "if" "(" expr ")" stmt　("else" stmt)?

※終端記号を◯、関数を□で表現する

elseがないとき

elseがあるとき
Nodeがlhs(左手)、rhs(右手)以外にelse節を持てるようにする

↓こちらのコードを参考にした。

nodeは完全２分木じゃないといけないと思っていたけど、このコード見てelse用のノードを生やすアイデアを真似させてもらった。

注意

普通のCとはまだ違っていて、if文の中にかけるstmtは一つだけ。なので、

if(1<2) a = 1; b = 2; return a + b; a = 0; b = 1; else return b - a;

みたいに、elseより前に２つ以上stmtがある文はまだコンパイルしなくて良い。
stmtをprogramに置き換えれば良いのかもしれないけど…

nac-39

アセンブリの見方

命令	意味
push x	スタックのトップにxをpush
pop x	スタックのトップからxをpop
rax	関数がリターンする値が入っているレジスタ
rdi	第一引数が入っているレジスタ
rsi	第二引数が入っているレジスタ
ret	スタックからアドレスを一つポップし、そのアドレスにジャンプする

よく見たらチートシートついてた。神か？？

nac-39

`./assembly/tmp.s:38: Error: unknown pseudo-op: '.lend1'`というエラーが出る

フラグに:をつけ忘れるとこのエラーが出るらしい
.Lend1:がうっかり.Lend1になっているとエラーが出る

nac-39

if文だけ追加

nac-39

if-else文の実装

次のEBNFを実装する

program = stmt*
stmt    = expr ";" | "return" expr ";"
        | "if" "(" expr ")" stmt (else stmt ";")?

ifとelseの中のstmtは一つだけなのに注意。stmt*ではない…（ここを間違えてて詰んでた）

ここまでの実装

nac-39

while文の実装

次のEBNFを実装する

stmt       = expr "; | "return" expr ";"
           | "if" "(" expr ")" stmt ("else" stmt)?
           | "while" "(" expr ")" stmt

nac-39

for文の実装

次のEBNFを実装する

stmt       = expr "; | "return" expr ";"
           | "if" "(" expr ")" stmt ("else" stmt)?
           | "while" "(" expr ")" stmt
           | "for" "(" expr? ";" expr? ";" expr? ")" stmt

同時に、if, whileの条件式を格納する場所も変更する

if文を次のように変更してしまう。条件式などをlhs, rhsに入れたままでも動くとは思うが、意味が異なってしまうため。

while文を次のように変更する

for文を次のように実装する

無限ループのテストケースが通らない

for文では、for(expr? ; ; expr?)と条件式をなしにすることで無限ループになるはずである。
しかし、

assert 10 'for(i=1;;) a = i + 1; return a;'

このケースでは無限ループになるのに、

assert 10 'for(i=0;;) a = i + 1; return a;'

とすると無限ループにならない。

for(i=0;;i = i + 1) a = i + 1; return 123456; => 139 expected, but got 64

→いやなんで？？？？？
↑ここまでの実装

後でバグが出てきそうだけどとりあえずこのままにしておくか…

nac-39

ステップ13　ブロック

実装するEBNF

program = stmt*
stmt    = expr ";"
        | "{" stmt* "}"
        | ...
...

↑こういうふうに実装しようとすると、Nodeにnextみたいな単方向リスト用の要素が必要になる？

他の人の実装方法

Vector型を作っている
- https://github.com/dekokun/9cc/blob/master/9cc.h
- https://github.com/hkiyomaru/10cc/blob/master/src/10cc.h#L189
Node->nextを持たせて単方向リストにしてる
https://github.com/pocari/compilerbook-9cc/blob/master/ynicc.h

意外とすんなり実装できてしまった…こんなにうまくいくもん？

nac-39

ステップ14: 関数の呼び出しに対応する

実装するEBNF

...
primary = num
        | ident ("(" ")")?
        | "(" expr ")"

ん？また一段難しくなった…？？？

リンクとは

別々の２つ以上の.cファイルを、他のファイルに依存しているアドレスが虫食い状態になっているオブジェクトファイルにコンパイルして、後からそれらのオブジェクトファイルをガッチャンコするやつ(合ってる…？)

あと、アセンブラだとどの命令をどのアドレスに配置すればいいかは決められないけど、その配置もリンカがやってくれる。

↓パタヘネに載っていたC言語の翻訳階層の図を見て書いた図

引数のない関数を使えるようにする

test.c

int foo() { printf("OK\n"); }

をオブジェクトファイルにコンパイルして、自分のコンパイラの出力とリンクできるようにする。

まずは、この構文をパースできるようにする
実装するEBNF

...
primary = num
        | ident ("(" ")")?
        | "(" expr ")"

x86_64では、call 関数のラベルで関数にジャンプすることができる。
gcc -S test.cでtest.cのアセンブリを確認したところ、test()関数のラベルは.testになっていた。
test()をcallするには、call testを使う。（.testではないことに注意）

C言語で詰まった点：

strncpy(node->fname, tok->str, tok->len);

だけだとセグフォが出るので、一度node->fnameというchar *型のポインタが指す先にchar用の領域を次のように確保してあげます。

node->fname = calloc(1, sizeof(char));
strncpy(node->fname, tok->str, tok->len);

６つまでの引数のある関数を呼び出せるようにする

↓compilerbookにあるありがたい表によると、引数は以下のレジスタに収納すればいいらしい。

レジスタ名	引数
RDI	第1引数
RSI	第2引数
RDX	第3引数
RCX	第4引数
R8	第5引数
R9	第6引数