Note #1
Comments
|
次回 |
|
https://chat.openai.com/c/27dd64a7-1de3-41c8-ba23-243add1b5c15
callの動きcallというのは関数を呼び出す命令です。具体的にcallは次のことを行います。
ret の動きretを呼んで関数からリターンしています。具体的にretは次のことを行います。
解説plusからリターンしたところにあるのはmainのret命令です。元のCコードではplusの返り値をそのままmainから返すということになっていました。ここではplusの返り値がRAXに入った状態になっているので、そのままmainからリターンすることで、それをそのままmainからの返り値にすることができます。 章まとめ
|
電卓レベルの言語の作成再帰下降構文解析法(recursive descent paring)
|
step 3: トークナイザを導入https://chat.openai.com/c/1513446d-06e7-41af-9848-251cee461738 void* calloc(size_t num_elements, size_t element_size);element_sizeのサイズを持つものを num_element個分の領域を確保して先頭のアドレスを返す。 step 4: エラーメッセージを改良error_at の第一引数に token->str を渡しているのがミソ。 |
文法の記述方法と再起下降構文解析
木構造による文法構造の表現パーサでは、フラットなトークン列を木構造にする。 左から計算しなければいけない演算子を「左結合」の演算子、 AST表現算術演算のように2つの項に対する演算として定義されているものは２分木にする。 生成規則による文法の定義BNF それ以上展開できない記号を「終端記号」（terminal symbol） 非終端記号は複数の生成規則にマッチしても良い。 生成規則の右辺は、空でもいい。 文字列はダブルクオートで括って"foo"のように書く。文字列は常に終端記号。
例: 単純な生成規則expr = num ( "+" num | "-" num )*EBNFでは木構造を表すだけで、演算を左から順番に行うなどの規則はない。 生成規則による演算子の優先順位の表現expr = mul ("+" mul | "-" mul)*
mul = num ("*" num | "/" num)*平坦な単純な構造では、上記で演算の優先順位が表されている。 再帰を含む生成規則expr = mul ("+" mul | "-" mul )*
mul = primary ("*" primary | "/" primary)*
primary = num | "(" expr ")"カッコも含めた優先順位が表されている。 |
再帰下降構文解析今やりたいことは、生成規則から具象構文木を構成する、つまりプログラムを構成する。 ある種の生成規則については、規則が与えられれば、その規則から生成される文にマッチする構文木を求めるコードを機械的に書くことができる。 次回 |
スタックマシン前回で演算の優先度に対応した抽象構文木の構成方法を学んだ。 加減算の場合は、状態の保持は1つだけ（rax）で良かったが、乗除算が加わった今回は１つだけで済むとは限らない。 スタックマシンの概念スタックマシンのADD命令はスタックから2つ値をpopしてきて、それらを加算し、結果をスタックにpushする。 計算例: // 2"3
PUSH 2
PUSH 3
MUL
// 4*5
PUSH 4
PUSH 5
MUL
// 2*3 + 4*5
ADDCISC と RISCCISCは
RISCは
x86-64以外はCISCだが、それ以外に生き残っているプロセッサはほとんどがRISCベース。 RISCは高速化しやすい。Intelはx86-64の命令を内部的にRISC型の命令に変換して、RISCプロセッサ化し、高速化を行った。 スタックマシンへのコンパイルA + B を抽象構文木化した。 をコンパイルする時は、
PUSH 2
PUSH 3
PUSH 4
MUL
ADDx86-64におけるスタックマシンの実現方法x86-64はスタックマシンではなく、レジスタマシン。 方法: スタックマシンで１つの命令になっているものを、レジスタマシンでは複数の命令に分解する
// 1 + 2
push 1
push 2
pop rdi
pop rax
add rax, rdi
push rax// 2"3 + 4*5
push 2
push 3
pop rdi
pop rax
mul rax, rdi
push rax
push 4
push 5
pop rdi
pop rax
mul rax, rdi
push rax
pop rdi
pop rax
add rax, rdi
push raxidiv 命令idivは符号あり除算を行う命令。 最適化アセンブリを出力するところで最適化するようにせず、出力は素直な実装で行い、出力されたアセンブリをスキャンして特定の系列を別の命令で置き換えるようにした方がよい。 |
step5: 四則演算のできる言語の作成メモリ管理しないポリシーallocで確保しているメモリをfreeで解放していないが、これは意図的。 |
step6: 単項プラスと単項マイナスexpr = mul ( "+" mul | "-" mul)*
mul = unary( "*" unary | "/" unary)*
unary = ("+"|"-")? primary
primary = num | "(" expr ")"を実装。 |
|
https://chat.openai.com/c/8480d41a-6eee-4bb9-a3fc-9f254cc6aa8f step7: 比較演算子トークナイズするときは長さの長い文字列から先にトークナイズする。 expr = equality
equality = relational ("==" relational | "!=" relational)*
relational = add ("<" add | "<=" add | ">" add | ">=" add)*
add = mul ("+" mul | "-" mul)*
mul = unary ("*" unary | "/" unary)*
unary = ("+" | "-")? primary
primary = num | "(" expr ")"アセンブリの生成cmp命令: 同一の場合1、そうでない場合は0 pop rdi
pop rax
cmp rax, rdi
sete al
movzb rax, alx86-64では、比較命令の結果は特別な「フラグレジスタ」というものにセットされる。
ALはRAXの下位8ビットを指す別名レジスタにすぎない。 movzb命令 => コピーする際に、コピー元の下位1バイトはそのままで、上位ビットはゼロを埋める |
|
https://chat.openai.com/c/b03d6948-392f-4cd6-b253-c26a767582e8 分割コンパイル全てのプログラムを一つのファイルに書けば、理論的にはリンカは不要。 分割コンパイル一つのファイルにつき、一つのオブジェクトファイルができる。 ヘッダファイルの必要性とその内容void print_bar(struct Foo *obj) {
printf("%d\n", obj->bar);
}上記のコードを分割コンパイルする場合、struct Foo について知っていなければならない。 例） 別のCファイルに入っている関数を呼び出すコードを出力するために必要な情報
必要ない情報
関数宣言には、宣言を表す extern をつけてもよいが、通常はファイルが分割されていることで見ればわかるのでつけない。 #include "foo.h"と書いておくと、#includeの行がfoo.hファイルの内容に置き換えられる。 typedef もコンパイラに型情報を教えるために使われる。複数のCファイルで使われている場合、ヘッダファイルに書いておく。 一つのファイルに全プログラムを閉じ込めた場合でも、あるものをコンパイルするときに、その行までの情報でコンパイルできなければいけない仕様になっている。 リンクエラー実体がなくても、宣言だけあればコンパイル自体はとおる。 複数のオブジェクトファイルに同じ関数、変数が含まれている場合もリンクエラーになる。 グローバル変数の宣言と定義グローバル変数はアセンブリレベルでは関数と同じようなもの。 グローバル変数はデフォルトでは実行禁止メモリ領域に割り当てられている。 extern をつけると宣言になる。 extern int foo;以下は、どれか一つのファイルでの定義 int foo;初期化で値を与える場合は、「定義」で与えるものであり、「宣言」で与えるものではない。 |
Step 8 ファイル分割とMakefileの変更Makefileコロンの前の名前をターゲットと呼ぶ。 .PHONY はターゲットがその名前のファイルを作りたいわけではない場合に指定する。 |
step9: 1文字のローカル変数変数はアドレスに名前をつけたようなもの。 call命令はリターンアドレスをスタックに積む rsp が始めリターンアドレスを指しており、関数のローカル変数a, b の領域を確保し、スタックは伸長し、rspの指す位置が変わる。 例）ロカール変数x, yを持つ関数gの呼び出し内で、さらにローカル変数x, yを持つ関数fを呼び出した場合
rbpは「fの呼び出し時点のrbp」の位置を指しており、rspはbの位置を指すようにしたい。 push rbp
mov rbp, rsp
sub rsp, 16
rbp:「gの呼び出し時点のrbp」のアドレス
rbp: 「gの呼び出し時点のrbp」のアドレス
rbp: 「fの呼び出し時点のrbp」のアドレス
rbp: 「fの呼び出し時点のrbp」 |
step9 その2関数からリターンするときには、rbpに元の値を書き戻して、rspがリターンアドレスを指している状態にしてret命令を呼び出す。 mov rsp, rbp
pop rbp
ret
rbp: 「fの呼び出し時点のrbp」
rbp: 「fの呼び出し時点のrbp」
rbp: 「gの呼び出し時点のrbp」 pop した値の行き先が rbpだから
rbp: 「gの呼び出し時点のrbp」 call命令は自身の次の命令がある位置のアドレスをスタックに積む。 |
step9 その3program = stmt*
stmt = expr ";"
expr = assign
assign = equality ("=" assign)?
equality = relational ("==" relational | "!=" relational)*
relational = add ("<" add | "<=" add | ">" add | ">=" add)*
add = mul ("+" mul | "-" mul)*
mul = unary ("*" unary | "/" unary)*
unary = ("+" | "-")? primary
primary = num | ident | "(" expr ")"左辺式と右辺式代入式の左辺にくるのは、メモリアドレスを指定する式。 任意のアドレスから値をロードする方法ローカル変数にアクセスするにはスタックトップだけでなく、スタック上の任意の位置にアクセスする必要がある。 mov dst, [src]srcのメモリ位置に入っている値をアドレスとみなして、そのアドレスに入っている値をdstにセットする。 push, pop は rsp をアドレスとみなしてメモリアクセスするので、 mov [rsp], rax
add rsp, 8pop rax mov rax, [rsp]
sub rsp, 8 |
This comment was marked as duplicate.
This comment was marked as duplicate.
step10: 複数文字のローカル変数次回 https://www.sigbus.info/compilerbook#%E3%82%B9%E3%83%86%E3%83%83%E3%83%9711return%E6%96%87 |
step11 return 文program = stmt*
stmt = expr ";" | "return" expr ";"
expr = assign
assign = equality ("=" assign)?
equality = relational ("==" relational | "!=" relational)*
relational = add ("<" add | "<=" add | ">" add | ">=" add)*
add = mul ("+" mul | "-" mul)*
mul = unary ("*" unary | "/" unary)*
unary = ("+" | "-")? primary
primary = num | ident | "(" expr ")"return 用にトークンTK_RETURNを用意する。 |
参照する本
https://www.sigbus.info/compilerbook
参考:
植山先生のWebiner
#2
x86-64機械語入門
https://zenn.dev/mod_poppo/articles/x86-64-machine-code
The text was updated successfully, but these errors were encountered: