chibiccを読む~Cコンパイラコードリーディング~ ステップ9,10,11
トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ9に該当
github.com
ステップ11に該当
github.com
該当ステップなし
github.com
ステップ9に該当
github.com
ステップ10に該当
github.com
- 今回作成するコンパイラ
- 追加・修正されたコンパイラのソースコード(ステップ9、;を使って複数の文を扱えるコンパイラを作成する)
- 追加・修正されたコンパイラのソースコード(ステップ11、return文を扱えるコンパイラを作成する)
- 追加・修正されたコンパイラのソースコード(該当ステップなし、式文を表現するノード追加に伴う修正を行ったコンパイラを作成する)
- 追加・修正されたコンパイラのソースコード(ステップ9、1文字のローカル変数を扱えるコンパイラを作成する)
- 追加・修正されたコンパイラのソースコード(ステップ10、複数文字のローカル変数を扱えるコンパイラを作成する)
- テストコード
- Makefile
今回作成するコンパイラ
1文字のローカル変数(ステップ9、;を使って複数の文を扱えるコンパイラを作成する)
↓
return文(ステップ11、return文を扱えるコンパイラを作成する)
↓
タイトルなし(該当ステップなし、式文を表現するノード追加に伴う修正を行ったコンパイラを作成する)
↓
1文字のローカル変数(ステップ9、1文字のローカル変数を扱えるコンパイラを作成する)
↓
複数文字のローカル変数(ステップ10、複数文字のローカル変数を扱えるコンパイラを作成する)
追加・修正されたコンパイラのソースコード(ステップ9、;を使って複数の文を扱えるコンパイラを作成する)
main関数
https://github.com/rui314/chibicc/commit/b4ff70045f63ff6cff3acb63412002ef3eec78b5#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR10
https://github.com/rui314/chibicc/blob/b4ff70045f63ff6cff3acb63412002ef3eec78b5/main.c#L10
#include "chibicc.h" int main(int argc, char **argv) { if (argc != 2) error("%s: invalid number of arguments", argv[0]); // Tokenize and parse. user_input = argv[1]; token = tokenize(); Node *node = program(); // Traverse the AST to emit assembly. codegen(node); return 0; }
コマンドライン引数の個数をチェックする(変更なし)
if (argc != 2) error("%s: invalid number of arguments", argv[0]);
トークナイズを行う(変更なし)
// Tokenize and parse. user_input = argv[1]; token = tokenize();
tokenize関数
https://github.com/rui314/chibicc/commit/b4ff70045f63ff6cff3acb63412002ef3eec78b5#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R96
https://github.com/rui314/chibicc/blob/b4ff70045f63ff6cff3acb63412002ef3eec78b5/tokenize.c#L96
Token *tokenize() { char *p = user_input; Token head; head.next = NULL; Token *cur = &head; while (*p) { // Skip whitespace characters. if (isspace(*p)) { p++; continue; } // Multi-letter punctuator if (startswith(p, "==") || startswith(p, "!=") || startswith(p, "<=") || startswith(p, ">=")) { cur = new_token(TK_RESERVED, cur, p, 2); p += 2; continue; } // Single-letter punctuator if (strchr("+-*/()<>;", *p)) { cur = new_token(TK_RESERVED, cur, p++, 1); continue; } // Integer literal if (isdigit(*p)) { cur = new_token(TK_NUM, cur, p, 0); char *q = p; cur->val = strtol(p, &p, 10); cur->len = p - q; continue; } error_at(p, "invalid token"); } new_token(TK_EOF, cur, p, 0); return head.next; }
文字列の先頭アドレスを取得する(変更なし)
char *p = user_input;
トークンからなる連結リストのヘッダーを作成する(変更なし)
Token head; head.next = NULL; Token *cur = &head;
空白文字の場合(変更なし)
// Skip whitespace characters. if (isspace(*p)) { p++; continue; }
複数文字の記号の場合(変更なし)
// Multi-letter punctuator if (startswith(p, "==") || startswith(p, "!=") || startswith(p, "<=") || startswith(p, ">=")) { cur = new_token(TK_RESERVED, cur, p, 2); p += 2; continue; }
1文字の記号の場合
// Single-letter punctuator if (strchr("+-*/()<>;", *p)) { cur = new_token(TK_RESERVED, cur, p++, 1); continue; }
第一引数の文字列に ; を追加して、; をトークンとして読み込めるようにしています。
数字の場合(変更なし)
// Integer literal if (isdigit(*p)) { cur = new_token(TK_NUM, cur, p, 0); char *q = p; cur->val = strtol(p, &p, 10); cur->len = p - q; continue; }
その他の場合(変更なし)
error_at(p, "invalid token");
連結リストの先頭トークンを戻り値としてリターンする(変更なし)
return head.next;
Node構造体
https://github.com/rui314/chibicc/commit/b4ff70045f63ff6cff3acb63412002ef3eec78b5#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R60
https://github.com/rui314/chibicc/blob/b4ff70045f63ff6cff3acb63412002ef3eec78b5/chibicc.h#L60
typedef struct Node Node; struct Node { NodeKind kind; // Node kind Node *next; // Next node Node *lhs; // Left-hand side Node *rhs; // Right-hand side int val; // Used if kind == ND_NUM };
C言語の1つの文( ; が終端にある文字列)に1つの抽象構文木(抽象構文木のルートノード)が対応するので、次の文に対応する抽象構文木(抽象構文木のノード)のアドレスの保存先となるnextメンバを追加します。
program関数
https://github.com/rui314/chibicc/commit/b4ff70045f63ff6cff3acb63412002ef3eec78b5#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR31
https://github.com/rui314/chibicc/blob/b4ff70045f63ff6cff3acb63412002ef3eec78b5/parse.c#L31
// program = stmt* Node *program() { Node head; head.next = NULL; Node *cur = &head; while (!at_eof()) { cur->next = stmt(); cur = cur->next; } return head.next; }
prgram関数は、抽象構文木のルートノードからなる連結リストを作成します。
抽象構文木のルートノードからなる連結リストのヘッダーを作成する
Node head; head.next = NULL; Node *cur = &head;
ノード構造体headを定義し、これから作成する連結リスト(ノード構造体からなる連結リスト)のヘッダーとします。
nextメンバの初期値はNULL、連結リストの終端をcurで表現します。
抽象構文木のルートノードからなる連結リストを作成する
while (!at_eof()) { cur->next = stmt(); cur = cur->next; }
at_eof()関数の戻り値がtrueになるまで→着目しているトークンがトークン列の終端を表すトークンになるまで、while文のループを継続します。
stmt関数を呼び出して抽象構文木を生成し、生成された抽象構文木のルートノードのアドレスを戻り値として取得します。
戻り値として取得した抽象構文木のルートノードのアドレスを連結リストの終端要素のnextメンバに格納し、連結リストの終端要素を表すcurを更新します。
連結リストの先頭ノードを戻り値としてリターンする
return head.next;
連結リストの先頭ノード(連結リストのヘッダーの次にあるノード)のアドレスを戻り値としてリターンします。
stmt関数
https://github.com/rui314/chibicc/commit/b4ff70045f63ff6cff3acb63412002ef3eec78b5#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR44
https://github.com/rui314/chibicc/blob/b4ff70045f63ff6cff3acb63412002ef3eec78b5/parse.c#L44
// stmt = expr ";" Node *stmt() { Node *node = expr(); expect(";"); return node; }
stmt関数は、生成規則 stmt = expr ";" に基づいて、抽象構文木のノードを生成します。
codegen関数
https://github.com/rui314/chibicc/commit/b4ff70045f63ff6cff3acb63412002ef3eec78b5#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR59
https://github.com/rui314/chibicc/blob/b4ff70045f63ff6cff3acb63412002ef3eec78b5/codegen.c#L59
void codegen(Node *node) { printf(".intel_syntax noprefix\n"); printf(".global main\n"); printf("main:\n"); for (Node *n = node; n; n = n->next) { gen(n); printf(" pop rax\n"); } printf(" ret\n"); }
codegen関数は、アセンブリコードを生成する処理を行います。
部分的にアセンブリコードを生成する①
printf(".intel_syntax noprefix\n"); printf(".global main\n"); printf("main:\n");
序盤部分のアセンブリコードを生成します。
部分的にアセンブリコードを生成する②
for (Node *n = node; n; n = n->next) { gen(n); printf(" pop rax\n"); }
抽象構文木を用いて、アセンブリコードを生成します。
1つの文が1つ抽象構文木(のルートノード)に対応しており、次の文に対応している抽象構文木(のルートノード)はnextから参照します。
gen関数によって生成されたアセンブリコードの実行時を考慮すると、抽象構文木の結果を表す値はスタックに退避されているので、その抽象構文木の結果を表す値を式文の評価値として取得するために、アセンブリコード"pop rax"を生成しています。
低レイヤを知りたい人のためのCコンパイラ作成入門では、連結リストではなく、配列(Node *code[100])を用いてノードを管理しています。
追加・修正されたコンパイラのソースコード(ステップ11、return文を扱えるコンパイラを作成する)
tokenize関数
https://github.com/rui314/chibicc/commit/5124ded8ea4020da1aae237aeb25247f806089ce#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R95
https://github.com/rui314/chibicc/blob/5124ded8ea4020da1aae237aeb25247f806089ce/tokenize.c#L95
Token *tokenize() { char *p = user_input; Token head; head.next = NULL; Token *cur = &head; while (*p) { // Skip whitespace characters. if (isspace(*p)) { p++; continue; } // Keyword if (startswith(p, "return") && !is_alnum(p[6])) { cur = new_token(TK_RESERVED, cur, p, 6); p += 6; continue; } // Multi-letter punctuator if (startswith(p, "==") || startswith(p, "!=") || startswith(p, "<=") || startswith(p, ">=")) { cur = new_token(TK_RESERVED, cur, p, 2); p += 2; continue; } // Single-letter punctuator if (strchr("+-*/()<>;", *p)) { cur = new_token(TK_RESERVED, cur, p++, 1); continue; } // Integer literal if (isdigit(*p)) { cur = new_token(TK_NUM, cur, p, 0); char *q = p; cur->val = strtol(p, &p, 10); cur->len = p - q; continue; } error_at(p, "invalid token"); } new_token(TK_EOF, cur, p, 0); return head.next; }
文字列の先頭アドレスを取得する(変更なし)
char *p = user_input;
トークンからなる連結リストのヘッダーを作成する(変更なし)
Token head; head.next = NULL; Token *cur = &head;
空白文字の場合(変更なし)
// Skip whitespace characters. if (isspace(*p)) { p++; continue; }
キーワードの場合
// Keyword if (startswith(p, "return") && !is_alnum(p[6])) { cur = new_token(TK_RESERVED, cur, p, 6); p += 6; continue; }
startwith関数の戻り値がtrue、かつ、is_alnum関数の戻値がfalseの場合→文字p*を含む文字列が"return"、かつ、”return”の次の文字p[6]が英数字やアンダーバーではない場合は、キーワードを表現するトークンを生成し、トークンの連結リストを作成します。
変数curには、新規に生成されたトークン(連結リストの終端要素)のアドレスが格納されます。
次の文字を取得するためにchar型へのポインタpを6バイト分("return"の6文字分)インクリメントしてからwhile文のループを継続します。
低レイヤを知りたい人のためのCコンパイラ作成入門では、引数のトークンの型がTK_RESERVEDではなく、TK_RETURNとなっています。
複数文字の記号の場合(変更なし)
// Multi-letter punctuator if (startswith(p, "==") || startswith(p, "!=") || startswith(p, "<=") || startswith(p, ">=")) { cur = new_token(TK_RESERVED, cur, p, 2); p += 2; continue; }
1文字の記号の場合(変更なし)
// Single-letter punctuator if (strchr("+-*/()<>;", *p)) { cur = new_token(TK_RESERVED, cur, p++, 1); continue; }
数字の場合(変更なし)
// Integer literal if (isdigit(*p)) { cur = new_token(TK_NUM, cur, p, 0); char *q = p; cur->val = strtol(p, &p, 10); cur->len = p - q; continue; }
その他の場合(変更なし)
error_at(p, "invalid token");
連結リストの先頭トークンを戻り値としてリターンする(変更なし)
return head.next;
is_alnum関数
https://github.com/rui314/chibicc/commit/5124ded8ea4020da1aae237aeb25247f806089ce#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R77
https://github.com/rui314/chibicc/blob/5124ded8ea4020da1aae237aeb25247f806089ce/tokenize.c#L77
bool is_alnum(char c) { return is_alpha(c) || ('0' <= c && c <= '9'); }
alnum関数は、数cで指定された文字が英数字やアンダーバーであるかを判定します。
is_alpha関数
https://github.com/rui314/chibicc/commit/5124ded8ea4020da1aae237aeb25247f806089ce#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R73
https://github.com/rui314/chibicc/blob/5124ded8ea4020da1aae237aeb25247f806089ce/tokenize.c#L73
bool is_alpha(char c) { return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') || c == '_'; }
alpha関数は、引数cで指定された文字が英字やアンダーバーであるかを判定します。
NodeKind
https://github.com/rui314/chibicc/commit/5124ded8ea4020da1aae237aeb25247f806089ce#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R45
https://github.com/rui314/chibicc/blob/5124ded8ea4020da1aae237aeb25247f806089ce/chibicc.h#L45
typedef enum { ND_ADD, // + ND_SUB, // - ND_MUL, // * ND_DIV, // / ND_EQ, // == ND_NE, // != ND_LT, // < ND_LE, // <= ND_RETURN, // "return" ND_NUM, // Integer } NodeKind;
キーワードreturnを表現するノードの型を追加します。
stmt関数
https://github.com/rui314/chibicc/commit/5124ded8ea4020da1aae237aeb25247f806089ce#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR50
https://github.com/rui314/chibicc/blob/5124ded8ea4020da1aae237aeb25247f806089ce/parse.c#L50
// stmt = "return" expr ";" // | expr ";" Node *stmt() { if (consume("return")) { Node *node = new_unary(ND_RETURN, expr()); expect(";"); return node; } Node *node = expr(); expect(";"); return node; }
stmt関数は、生成規則 stmt = "return" expr ";" | expr ";" に基づいて、抽象構文木のノードを生成します。
"return"とexprと";"
if (consume("return")) { Node *node = new_unary(ND_RETURN, expr()); expect(";"); return node; }
consume("return")の戻り値がtrueとなる場合→着目しているトークンが"return"の場合は、new_unary関数を呼び出して、キーワードreturnを表現するノードを生成します。キーワードreturnを表現するノードは、第二引数のexpr関数で生成されたノードを子ノードとして持ちます。
new_unary関数内でトークン列の読み進めや抽象構文木のノード生成が終わった後は、着目しているトークンが ";" であることが期待されているので、expect(";")を呼び出します。最後に、new_unary関数で生成されたノードのアドレスを戻り値としてリターンします。
new_unary関数
https://github.com/rui314/chibicc/commit/5124ded8ea4020da1aae237aeb25247f806089ce#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR16
https://github.com/rui314/chibicc/blob/5124ded8ea4020da1aae237aeb25247f806089ce/parse.c#L16
Node *new_unary(NodeKind kind, Node *expr) { Node *node = new_node(kind); node->lhs = expr; return node; }
new_unary関数は、抽象構文木のノード(子ノードを1つ持つ)を生成します。
生成されたノードに子ノードを登録する
node->lhs = expr;
引数exprの値(子ノードを指定するアドレス)を生成されるノード構造体のメンバに設定します。
生成されたノードを戻り値としてリターンする
return node;
生成されたノード構造体のアドレスを戻り値としてリターンします。
gen関数
https://github.com/rui314/chibicc/commit/5124ded8ea4020da1aae237aeb25247f806089ce#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR4
https://github.com/rui314/chibicc/blob/5124ded8ea4020da1aae237aeb25247f806089ce/codegen.c#L4
#include "chibicc.h" void gen(Node *node) { switch (node->kind) { case ND_NUM: printf(" push %d\n", node->val); return; case ND_RETURN: gen(node->lhs); printf(" pop rax\n"); printf(" ret\n"); return; } gen(node->lhs); gen(node->rhs); printf(" pop rdi\n"); printf(" pop rax\n"); switch (node->kind) { case ND_ADD: printf(" add rax, rdi\n"); break; case ND_SUB: printf(" sub rax, rdi\n"); break; case ND_MUL: printf(" imul rax, rdi\n"); break; case ND_DIV: printf(" cqo\n"); printf(" idiv rdi\n"); break; case ND_EQ: printf(" cmp rax, rdi\n"); printf(" sete al\n"); printf(" movzb rax, al\n"); break; case ND_NE: printf(" cmp rax, rdi\n"); printf(" setne al\n"); printf(" movzb rax, al\n"); break; case ND_LT: printf(" cmp rax, rdi\n"); printf(" setl al\n"); printf(" movzb rax, al\n"); break; case ND_LE: printf(" cmp rax, rdi\n"); printf(" setle al\n"); printf(" movzb rax, al\n"); break; } printf(" push rax\n"); }
二項演算以外を行うアセンブリコードを生成する
switch (node->kind) { case ND_NUM: printf(" push %d\n", node->val); return; case ND_RETURN: gen(node->lhs); printf(" pop rax\n"); printf(" ret\n"); return; }
ノードの型がND_RETURNの場合(ノードの種類がreturnの場合)における処理を追加します。
ノードの型がND_RETURNの場合は、gen関数を呼び出し、returnを表現するノードの子ノードnode->lhsを用いてアセンブリコードを生成します。
gen(node->lhs)で生成されたアセンブリコードの実行時を考慮すると、ノードnode->lhsの結果に対応する値がスタックに退避されているので、このノードnode->lhsの結果に対応する値を取得するために(expr関数で生成された抽象構文木に対応する式文の評価値を取得するために)、アセンブリコード"pop rax"を生成します。
最後に、returnの処理に相当するアセンブリコード”ret”を生成します。
二項演算の対象となる値を得るためのアセンブリコードを生成する(変更なし)
gen(node->lhs); gen(node->rhs); printf(" pop rdi\n"); printf(" pop rax\n");
二項演算を行うアセンブリコードを生成する(変更なし)
switch (node->kind) { case ND_ADD: printf(" add rax, rdi\n"); break; case ND_SUB: printf(" sub rax, rdi\n"); break; case ND_MUL: printf(" imul rax, rdi\n"); break; case ND_DIV: printf(" cqo\n"); printf(" idiv rdi\n"); break; case ND_EQ: printf(" cmp rax, rdi\n"); printf(" sete al\n"); printf(" movzb rax, al\n"); break; case ND_NE: printf(" cmp rax, rdi\n"); printf(" setne al\n"); printf(" movzb rax, al\n"); break; case ND_LT: printf(" cmp rax, rdi\n"); printf(" setl al\n"); printf(" movzb rax, al\n"); break; case ND_LE: printf(" cmp rax, rdi\n"); printf(" setle al\n"); printf(" movzb rax, al\n"); break; } printf(" push rax\n");
追加・修正されたコンパイラのソースコード(該当ステップなし、式文を表現するノード追加に伴う修正を行ったコンパイラを作成する)
NodeKind
https://github.com/rui314/chibicc/commit/74a759540c71db4529ff689b2245fd2566eb6aa3#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R54
https://github.com/rui314/chibicc/blob/74a759540c71db4529ff689b2245fd2566eb6aa3/chibicc.h#L54
typedef enum { ND_ADD, // + ND_SUB, // - ND_MUL, // * ND_DIV, // / ND_EQ, // == ND_NE, // != ND_LT, // < ND_LE, // <= ND_RETURN, // "return" ND_EXPR_STMT, // Expression statement ND_NUM, // Integer } NodeKind;
式文を表現するノードの型ND_EXPR_STMTを追加します。
stmt関数
https://github.com/rui314/chibicc/commit/74a759540c71db4529ff689b2245fd2566eb6aa3#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR59
https://github.com/rui314/chibicc/blob/74a759540c71db4529ff689b2245fd2566eb6aa3/parse.c#L59
// stmt = "return" expr ";" // | expr ";" Node *stmt() { if (consume("return")) { Node *node = new_unary(ND_RETURN, expr()); expect(";"); return node; } Node *node = new_unary(ND_EXPR_STMT, expr()); expect(";"); return node; }
"return"とexprと";"(変更なし)
if (consume("return")) { Node *node = new_unary(ND_RETURN, expr()); expect(";"); return node; }
exprと";"
Node *node = new_unary(ND_EXPR_STMT, expr()); expect(";"); return node;
expr()からnew_unary(ND_EXPR_STMT, expr())に変更します。
codegen関数
https://github.com/rui314/chibicc/commit/74a759540c71db4529ff689b2245fd2566eb6aa3#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR69
https://github.com/rui314/chibicc/blob/74a759540c71db4529ff689b2245fd2566eb6aa3/codegen.c#L69
void codegen(Node *node) { printf(".intel_syntax noprefix\n"); printf(".global main\n"); printf("main:\n"); for (Node *n = node; n; n = n->next) gen(n); printf(" ret\n"); }
部分的にアセンブリコードを生成する①(変更なし)
printf(".intel_syntax noprefix\n"); printf(".global main\n"); printf("main:\n");
部分的にアセンブリコードを生成する②
for (Node *n = node; n; n = n->next) gen(n);
gen関数の後にあったprintf(" pop rax\n")を削除します。
部分的にアセンブリコードを生成する③(変更なし)
printf(" ret\n");
gen関数
https://github.com/rui314/chibicc/commit/74a759540c71db4529ff689b2245fd2566eb6aa3#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR8
https://github.com/rui314/chibicc/blob/74a759540c71db4529ff689b2245fd2566eb6aa3/codegen.c#L8
void gen(Node *node) { switch (node->kind) { case ND_NUM: printf(" push %d\n", node->val); return; case ND_EXPR_STMT: gen(node->lhs); printf(" add rsp, 8\n"); return; case ND_RETURN: gen(node->lhs); printf(" pop rax\n"); printf(" ret\n"); return; } gen(node->lhs); gen(node->rhs); printf(" pop rdi\n"); printf(" pop rax\n"); switch (node->kind) { case ND_ADD: printf(" add rax, rdi\n"); break; case ND_SUB: printf(" sub rax, rdi\n"); break; case ND_MUL: printf(" imul rax, rdi\n"); break; case ND_DIV: printf(" cqo\n"); printf(" idiv rdi\n"); break; case ND_EQ: printf(" cmp rax, rdi\n"); printf(" sete al\n"); printf(" movzb rax, al\n"); break; case ND_NE: printf(" cmp rax, rdi\n"); printf(" setne al\n"); printf(" movzb rax, al\n"); break; case ND_LT: printf(" cmp rax, rdi\n"); printf(" setl al\n"); printf(" movzb rax, al\n"); break; case ND_LE: printf(" cmp rax, rdi\n"); printf(" setle al\n"); printf(" movzb rax, al\n"); break; } printf(" push rax\n"); }
二項演算以外を行うアセンブリコードを生成する
void gen(Node *node) { switch (node->kind) { case ND_NUM: printf(" push %d\n", node->val); return; case ND_EXPR_STMT: gen(node->lhs); printf(" add rsp, 8\n"); return; case ND_RETURN: gen(node->lhs); printf(" pop rax\n"); printf(" ret\n"); return; }
ノードの型がND_EXPR_STMTの場合(ノードの種類が式文の場合)における処理を追加します。
ノードの型がND_EXPR_STMTの場合は、gen関数を呼び出し、式文を表現するノードの子ノードnode->lhsを用いてアセンブリコードを生成します。
(gen(node->lhs)の後に、なぜアセンブリ命令"add rsp, 8"を生成する必要があるのかがわからない、、、)
二項演算の対象となる値を得るためのアセンブリコードを生成する(変更なし)
gen(node->lhs); gen(node->rhs); printf(" pop rdi\n"); printf(" pop rax\n");
二項演算を行うアセンブリコードを生成する(変更なし)
switch (node->kind) { case ND_ADD: printf(" add rax, rdi\n"); break; case ND_SUB: printf(" sub rax, rdi\n"); break; case ND_MUL: printf(" imul rax, rdi\n"); break; case ND_DIV: printf(" cqo\n"); printf(" idiv rdi\n"); break; case ND_EQ: printf(" cmp rax, rdi\n"); printf(" sete al\n"); printf(" movzb rax, al\n"); break; case ND_NE: printf(" cmp rax, rdi\n"); printf(" setne al\n"); printf(" movzb rax, al\n"); break; case ND_LT: printf(" cmp rax, rdi\n"); printf(" setl al\n"); printf(" movzb rax, al\n"); break; case ND_LE: printf(" cmp rax, rdi\n"); printf(" setle al\n"); printf(" movzb rax, al\n"); break; } printf(" push rax\n"); }
追加・修正されたコンパイラのソースコード(ステップ9、1文字のローカル変数を扱えるコンパイラを作成する)
TokenKind
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R14
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/chibicc.h#L14
typedef enum { TK_RESERVED, // Keywords or punctuators TK_IDENT, // Identifiers TK_NUM, // Integer literals TK_EOF, // End-of-file markers } TokenKind;
識別子を表現するトークン型TK_IDENTを追加します。
tokenize関数
Token *tokenize() { char *p = user_input; Token head; head.next = NULL; Token *cur = &head; while (*p) { // Skip whitespace characters. if (isspace(*p)) { p++; continue; } // Keyword if (startswith(p, "return") && !is_alnum(p[6])) { cur = new_token(TK_RESERVED, cur, p, 6); p += 6; continue; } // Multi-letter punctuator if (startswith(p, "==") || startswith(p, "!=") || startswith(p, "<=") || startswith(p, ">=")) { cur = new_token(TK_RESERVED, cur, p, 2); p += 2; continue; } // Single-letter punctuator if (strchr("+-*/()<>;=", *p)) { cur = new_token(TK_RESERVED, cur, p++, 1); continue; } // Identifier if ('a' <= *p && *p <= 'z') { cur = new_token(TK_IDENT, cur, p++, 1); continue; } // Integer literal if (isdigit(*p)) { cur = new_token(TK_NUM, cur, p, 0); char *q = p; cur->val = strtol(p, &p, 10); cur->len = p - q; continue; } error_at(p, "invalid token"); } new_token(TK_EOF, cur, p, 0); return head.next; }
文字列の先頭アドレスを取得する(変更なし)
char *p = user_input;
トークンからなる連結リストのヘッダーを作成する(変更なし)
Token head; head.next = NULL; Token *cur = &head;
空白文字の場合(変更なし)
// Skip whitespace characters. if (isspace(*p)) { p++; continue; }
キーワードの場合(変更なし)
// Keyword if (startswith(p, "return") && !is_alnum(p[6])) { cur = new_token(TK_RESERVED, cur, p, 6); p += 6; continue; }
複数文字の記号の場合(変更なし)
// Multi-letter punctuator if (startswith(p, "==") || startswith(p, "!=") || startswith(p, "<=") || startswith(p, ">=")) { cur = new_token(TK_RESERVED, cur, p, 2); p += 2; continue; }
1文字の記号の場合
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R120
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/tokenize.c#L120
// Single-letter punctuator if (strchr("+-*/()<>;=", *p)) { cur = new_token(TK_RESERVED, cur, p++, 1); continue; }
第一引数の文字列に = を追加して、= をトークンとして読み込めるようにしています。
識別子の場合
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R125
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/tokenize.c#L125
// Identifier if ('a' <= *p && *p <= 'z') { cur = new_token(TK_IDENT, cur, p++, 1); continue; }
文字*pが小文字の英数字の場合は、new_token関数を呼び出して、識別子を表現するトークンを生成しトークンの連結リストを作成します。
変数curには、新規に生成されたトークン(連結リストの終端要素)のアドレスが格納されます。
次の文字を取得するためにchar型へのポインタpをインクリメントしてからwhile文のループを継続します(char型へのポインタpを後置インクリメントしているので、評価前のpの値が引数として渡されます)。
数字の場合(変更なし)
// Integer literal if (isdigit(*p)) { cur = new_token(TK_NUM, cur, p, 0); char *q = p; cur->val = strtol(p, &p, 10); cur->len = p - q; continue; }
その他の場合(変更なし)
error_at(p, "invalid token");
連結リストの先頭トークンを戻り値としてリターンする(変更なし)
return head.next;
consume_ident関数
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R38
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/tokenize.c#L38
// Consumes the current token if it is an identifier. Token *consume_ident() { if (token->kind != TK_IDENT) return NULL; Token *t = token; token = token->next; return t; }
consume_ident関数は、現在着目しているトークンの種類が識別子である場合に、そのトークンを戻り値として取得し、トークンを1つ読み進めます。
NodeKind
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R55
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/chibicc.h#L55
typedef enum { ND_ADD, // + ND_SUB, // - ND_MUL, // * ND_DIV, // / ND_EQ, // == ND_NE, // != ND_LT, // < ND_LE, // <= ND_ASSIGN, // = ND_RETURN, // "return" ND_EXPR_STMT, // Expression statement ND_LVAR, // Local variable ND_NUM, // Integer } NodeKind;
等号記号を表現するノードの型ND_ASSIGNと、ローカル変数を表現するノードの型ND_LVARを追加します。
Node構造体
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R69
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/chibicc.h#L69
// AST node type typedef struct Node Node; struct Node { NodeKind kind; // Node kind Node *next; // Next node Node *lhs; // Left-hand side Node *rhs; // Right-hand side char name; // Used if kind == ND_LVAR int val; // Used if kind == ND_NUM };
ローカル変数(1文字)の名前を保存するnameメンバを追加します。
低レイヤを知りたい人のためのCコンパイラ作成入門ではローカル変数のアドレス値を算出するのに必要となるoffsetメンバを用意していますが、referenceブランチのコミットではgen_addr関数内でローカル変数のアドレス値を算出しています。
expr関数
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR71
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/parse.c#L71
// expr = assign Node *expr() { return assign(); }
expr関数は、生成規則 expr = assign に基づいて、抽象構文木のノードを生成します。
assign関数
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR76
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/parse.c#L76
// assign = equality ("=" assign)? Node *assign() { Node *node = equality(); if (consume("=")) node = new_binary(ND_ASSIGN, node, assign()); return node; }
assign関数は、生成規則 assign = equality ("=" assign)? に基づいて、抽象構文木のノードを生成します。
「"="とassign」を0回か1回
if (consume("=")) node = new_binary(ND_ASSIGN, node, assign()); return node;
consume(”=”)の戻り値がtrueとなる場合→着目しているトークンが ”=” の場合は、new_binary関数を呼び出して、等号記号を表現するノードを生成します。この等号記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのequality関数)と第三引数のassign関数で生成されたノードを子ノードとして持ちます。
primary関数
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR154
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/parse.c#L154
// primary = "(" expr ")" | ident | num Node *primary() { if (consume("(")) { Node *node = expr(); expect(")"); return node; } Token *tok = consume_ident(); if (tok) return new_lvar(*tok->str); return new_num(expect_number()); }
primary関数は、生成規則 primary = "(" expr ")" | ident | num に基づいて、抽象構文木のノードを生成します。
"("とexprと")"(変更なし)
if (consume("(")) { Node *node = expr(); expect(")"); return node; }
ident
Token *tok = consume_ident(); if (tok) return new_lvar(*tok->str);
consume_ident関数を呼び出して、現在着目しているトークンが識別子であることを確認します。
consume_ident関数の戻り値がNULLではない場合→現在着目しているトークンが識別子だった場合は、new_lvar関数を呼び出して、ローカル変数を表現したノードを生成します。
num(変更なし)
return new_num(expect_number());
new_lvar関数
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR28
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/parse.c#L28
Node *new_lvar(char name) { Node *node = new_node(ND_LVAR); node->name = name; return node; }
new_lvar関数は、抽象構文木のノード(ローカル変数に対応する外部ノード)を新規に生成します。
生成されたノードのメンバに値を設定する
node->name = name;
引数で指定されたnameの値(ローカル変数の名前)を生成されるノード構造体のメンバに設定します。
生成されたノードを戻り値としてリターンする
return node;
生成されたノード構造体のアドレスを戻り値としてリターンします。
codegen関数
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR104
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/codegen.c#L104
void codegen(Node *node) { printf(".intel_syntax noprefix\n"); printf(".global main\n"); printf("main:\n"); // Prologue printf(" push rbp\n"); printf(" mov rbp, rsp\n"); printf(" sub rsp, 208\n"); for (Node *n = node; n; n = n->next) gen(n); // Epilogue printf(".Lreturn:\n"); printf(" mov rsp, rbp\n"); printf(" pop rbp\n"); printf(" ret\n"); }
部分的にアセンブリコードを生成する①(変更なし)
printf(".intel_syntax noprefix\n"); printf(".global main\n"); printf("main:\n");
部分的にアセンブリコードを生成する②
// Prologue printf(" push rbp\n"); printf(" mov rbp, rsp\n"); printf(" sub rsp, 208\n");
mainルーチンのプロローグとなるアセンブリコードを生成します。
ローカル変数26個分のスタック領域(26×8=208バイト)をあらかじめ用意しておきます。
部分的にアセンブリコードを生成する③
for (Node *n = node; n; n = n->next) gen(n);
gen関数
void gen(Node *node) { switch (node->kind) { case ND_NUM: printf(" push %d\n", node->val); return; case ND_EXPR_STMT: gen(node->lhs); printf(" add rsp, 8\n"); return; case ND_LVAR: gen_addr(node); load(); return; case ND_ASSIGN: gen_addr(node->lhs); gen(node->rhs); store(); return; case ND_RETURN: gen(node->lhs); printf(" pop rax\n"); printf(" jmp .Lreturn\n"); return; } gen(node->lhs); gen(node->rhs); printf(" pop rdi\n"); printf(" pop rax\n"); switch (node->kind) { case ND_ADD: printf(" add rax, rdi\n"); break; case ND_SUB: printf(" sub rax, rdi\n"); break; case ND_MUL: printf(" imul rax, rdi\n"); break; case ND_DIV: printf(" cqo\n"); printf(" idiv rdi\n"); break; case ND_EQ: printf(" cmp rax, rdi\n"); printf(" sete al\n"); printf(" movzb rax, al\n"); break; case ND_NE: printf(" cmp rax, rdi\n"); printf(" setne al\n"); printf(" movzb rax, al\n"); break; case ND_LT: printf(" cmp rax, rdi\n"); printf(" setl al\n"); printf(" movzb rax, al\n"); break; case ND_LE: printf(" cmp rax, rdi\n"); printf(" setle al\n"); printf(" movzb rax, al\n"); break; } printf(" push rax\n"); }
二項演算以外を行うアセンブリコードを生成する
switch (node->kind) { case ND_NUM: printf(" push %d\n", node->val); return; case ND_EXPR_STMT: gen(node->lhs); printf(" add rsp, 8\n"); return; case ND_LVAR: gen_addr(node); load(); return; case ND_ASSIGN: gen_addr(node->lhs); gen(node->rhs); store(); return; case ND_RETURN: gen(node->lhs); printf(" pop rax\n"); printf(" jmp .Lreturn\n"); return; }
ノードの型がND_LVARの場合(ノードの種類がローカル変数の場合)、ノードの型がND_ASSIGNの場合(ノードの種類が等号記号の場合)、ノードの型がND_RETURNの場合(ノードの種類がreturnの場合)、における処理をそれぞれ追加します。
ノードの型がND_LVARの場合
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR38
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/codegen.c#L38
ノードの型がND_LVARの場合は、gen_addr関数を呼び出して、ノードに対応するローカル変数の左辺値(アドレス値)を取得するためのアセンブリコードを生成します。その後、load関数を呼び出して、ローカル変数の左辺値(アドレス値)が指定するメモリ領域から右辺値を取得するアセンブリコードを生成します。
ノードの型がND_ASSIGNの場合
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR42
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/codegen.c#L42
ノードの型がND_ASSIGNの場合は、gen_addr(node->lhs)関数を呼び出して、ノードlhsに対応するローカル変数の左辺値(等号記号の左辺にあるローカル変数の左辺値)を取得するためのアセンブリコードを生成します。その後、gen(node->rhs)関数を呼び出して、node->rhsに対応する右辺値を取得するためのアセンブリコードを生成します。最後に、store関数を呼び出して、ノードlhsに対応する左辺値が指定するメモリ領域に、node->rhsに対応する右辺値を保存するアセンブリコードを生成します。
ノードの型がND_RETURNの場合
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR50
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/codegen.c#L50
生成されたアセンブリコードにおいてreturnを実行した時に、mainルーチンへ制御が移るようにアセンブリコード"jmp .Lreturn"を生成するようにします("ret"は削除します)。
二項演算の対象となる値を得るためのアセンブリコードを生成する(変更なし)
gen(node->lhs); gen(node->rhs); printf(" pop rdi\n"); printf(" pop rax\n");
二項演算を行うアセンブリコードを生成する(変更なし)
switch (node->kind) { case ND_ADD: printf(" add rax, rdi\n"); break; case ND_SUB: printf(" sub rax, rdi\n"); break; case ND_MUL: printf(" imul rax, rdi\n"); break; case ND_DIV: printf(" cqo\n"); printf(" idiv rdi\n"); break; case ND_EQ: printf(" cmp rax, rdi\n"); printf(" sete al\n"); printf(" movzb rax, al\n"); break; case ND_NE: printf(" cmp rax, rdi\n"); printf(" setne al\n"); printf(" movzb rax, al\n"); break; case ND_LT: printf(" cmp rax, rdi\n"); printf(" setl al\n"); printf(" movzb rax, al\n"); break; case ND_LE: printf(" cmp rax, rdi\n"); printf(" setle al\n"); printf(" movzb rax, al\n"); break; } printf(" push rax\n"); }
gen_addr
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR3
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/codegen.c#L3
// Pushes the given node's address to the stack. void gen_addr(Node *node) { if (node->kind == ND_LVAR) { int offset = (node->name - 'a' + 1) * 8; printf(" lea rax, [rbp-%d]\n", offset); printf(" push rax\n"); return; } error("not an lvalue"); }
gen_addr関数は、ノードに対応するローカル変数の左辺値(アドレス値)を取得するためのアセンブリコードを生成します。
左辺値を取得するためのアセンブリコードを生成する
if (node->kind == ND_LVAR) { int offset = (node->name - 'a' + 1) * 8; printf(" lea rax, [rbp-%d]\n", offset); printf(" push rax\n"); return; }
ノードの型がND_LVARの場合は(ノードの種類がローカル変数の場合は)、そのローカル変数に応じたアドレスを取得するためのアセンブリコードを生成します。
ローカル変数名(node->nameの値)は小文字の英数字a~zのいずれかなので、aのオフセットは8、bのオフセットは16、cのオフセット24...となるように、文字コードの差name - 'a'を用いてオフセット値を算出します。
エラーメッセージを表示する
error("not an lvalue");
error関数を呼び出し、メッセージを出力してからプログラムを終了します。
load関数
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR15
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/codegen.c#L15
void load() { printf(" pop rax\n"); printf(" mov rax, [rax]\n"); printf(" push rax\n"); }
load関数は、左辺値が指定するメモリ領域から右辺値を取得するアセンブリコードを生成します。
store関数
https://github.com/rui314/chibicc/commit/97a255d2d33e76c0be672cc4ecd32f9035e833ca#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR21
https://github.com/rui314/chibicc/blob/97a255d2d33e76c0be672cc4ecd32f9035e833ca/codegen.c#L21
void store() { printf(" pop rdi\n"); printf(" pop rax\n"); printf(" mov [rax], rdi\n"); printf(" push rdi\n"); }
store関数は、左辺値が指定するメモリ領域に右辺値を保存するアセンブリコードを生成します。
追加・修正されたコンパイラのソースコード(ステップ10、複数文字のローカル変数を扱えるコンパイラを作成する)
main関数
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR10
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/main.c#L10
int main(int argc, char **argv) { if (argc != 2) error("%s: invalid number of arguments", argv[0]); // Tokenize and parse. user_input = argv[1]; token = tokenize(); Program *prog = program(); // Assign offsets to local variables. int offset = 0; for (Var *var = prog->locals; var; var = var->next) { offset += 8; var->offset = offset; } prog->stack_size = offset; // Traverse the AST to emit assembly. codegen(prog); return 0; }
コマンドライン引数の個数をチェックする(変更なし)
if (argc != 2) error("%s: invalid number of arguments", argv[0]);
トークナイズを行う(変更なし)
// Tokenize and parse. user_input = argv[1]; token = tokenize();
パースを行う
Program *prog = program();
program関数の戻り値をnodeからprogへ変更します。program関数で生成された抽象構文木(のルートノードからなる連結リスト)は、Program構造体変数progのnodeメンバから参照することができます。
ローカル変数のアドレスとスタックを用意する
// Assign offsets to local variables. int offset = 0; for (Var *var = prog->locals; var; var = var->next) { offset += 8; var->offset = offset; } prog->stack_size = offset;
ローカル変数を表現したvra構造体のそれぞれが持つoffsetメンバに値をセットします → 各ローカル変数にオフセットを割り当てます。
オフセットは、スタックにおいてベースアドレスからローカル変数が配置されるアドレスまでの差分となる値(バイト単位)で、8、16、24、、、の8バイト境界となる値(0を除く)をとります。そのオフセットの最大値を必要となるスタックサイズとしてprog構造体のstack_sizeメンバに保存します。
tokenize関数
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R133
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/tokenize.c#L133
Token *tokenize() { char *p = user_input; Token head; head.next = NULL; Token *cur = &head; while (*p) { // Skip whitespace characters. if (isspace(*p)) { p++; continue; } // Keyword if (startswith(p, "return") && !is_alnum(p[6])) { cur = new_token(TK_RESERVED, cur, p, 6); p += 6; continue; } // Multi-letter punctuator if (startswith(p, "==") || startswith(p, "!=") || startswith(p, "<=") || startswith(p, ">=")) { cur = new_token(TK_RESERVED, cur, p, 2); p += 2; continue; } // Single-letter punctuator if (strchr("+-*/()<>;=", *p)) { cur = new_token(TK_RESERVED, cur, p++, 1); continue; } // Identifier if (is_alpha(*p)) { char *q = p++; while (is_alnum(*p)) p++; cur = new_token(TK_IDENT, cur, q, p - q); continue; } // Integer literal if (isdigit(*p)) { cur = new_token(TK_NUM, cur, p, 0); char *q = p; cur->val = strtol(p, &p, 10); cur->len = p - q; continue; } error_at(p, "invalid token"); } new_token(TK_EOF, cur, p, 0); return head.next; }
文字列の先頭アドレスを取得する(変更なし)
char *p = user_input;
トークンからなる連結リストのヘッダーを作成する(変更なし)
Token head; head.next = NULL; Token *cur = &head;
空白文字の場合(変更なし)
// Skip whitespace characters. if (isspace(*p)) { p++; continue; }
キーワードの場合(変更なし)
// Keyword if (startswith(p, "return") && !is_alnum(p[6])) { cur = new_token(TK_RESERVED, cur, p, 6); p += 6; continue; }
複数文字の記号の場合(変更なし)
// Multi-letter punctuator if (startswith(p, "==") || startswith(p, "!=") || startswith(p, "<=") || startswith(p, ">=")) { cur = new_token(TK_RESERVED, cur, p, 2); p += 2; continue; }
1文字の記号の場合(変更なし)
// Single-letter punctuator if (strchr("+-*/()<>;=", *p)) { cur = new_token(TK_RESERVED, cur, p++, 1); continue; }
識別子の場合
// Identifier if (is_alpha(*p)) { char *q = p++; while (is_alnum(*p)) p++; cur = new_token(TK_IDENT, cur, q, p - q); continue; }
is_alpha関数の戻り値がtrueとなる場合→文字列の先頭文字が*pが英字の場合は、識別子を表現したトークンを生成します。
次の文字を取得するためにchar型へのポインタpを後置インクリメントし(ポインタqに値を保存してからpをインクリメントし)、is_alnum関数の戻り値がtrueになった回数分だけ(文字*pが英数字やアンダーバーである回数分だけ)pをインクリメントします。その後、new_token関数を呼び出して、識別子を表現するトークンを生成しトークンの連結リストを作成します。
変数curには、新規に生成されたトークン(連結リストの終端要素)のアドレスが格納されます。
数字の場合(変更なし)
// Integer literal if (isdigit(*p)) { cur = new_token(TK_NUM, cur, p, 0); char *q = p; cur->val = strtol(p, &p, 10); cur->len = p - q; continue; }
その他の場合(変更なし)
error_at(p, "invalid token");
連結リストの先頭トークンを戻り値としてリターンする(変更なし)
return head.next;
NodeKind
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R69
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/chibicc.h#L69
typedef enum { ND_ADD, // + ND_SUB, // - ND_MUL, // * ND_DIV, // / ND_EQ, // == ND_NE, // != ND_LT, // < ND_LE, // <= ND_ASSIGN, // = ND_RETURN, // "return" ND_EXPR_STMT, // Expression statement ND_LVAR, // Local variable ND_VAR, // Variable ND_NUM, // Integer } NodeKind;
ローカル変数を表現するノード型ND_LVARを表現するノード型ND_VARに変更します。
Var構造体
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R48
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/chibicc.h#L48
// Local variable typedef struct Var Var; struct Var { Var *next; char *name; // Variable name int offset; // Offset from RBP };
変数を表現し管理するためのデータ構造であるVar構造体を定義します。
locals変数
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR3
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/parse.c#L3
Var *locals;
ローカル変数はVar構造体の連結リストとして管理するので、その連結リストの先頭を示すグローバル変数localsを定義します。
Node構造体
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R80
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/chibicc.h#L80
// AST node type typedef struct Node Node; struct Node { NodeKind kind; // Node kind Node *next; // Next node Node *lhs; // Left-hand side Node *rhs; // Right-hand side Var *var; // Used if kind == ND_VAR int val; // Used if kind == ND_NUM };
var構造体へのポインタvarをメンバとして追加します。
new_var関数
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR38
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/parse.c#L38
Node *new_var(Var *var) { Node *node = new_node(ND_VAR); node->var = var; return node; }
new_var関数は、抽象構文木の外部ノード(ローカル変数に対応するノード)を新規に生成します。
生成されたノードのメンバに値を設定する
node->var = var;
引数varで指定されたvar構造体変数のアドレスを生成されるノード構造体のvarメンバに設定します
生成されたノードを戻り値としてリターンする
return node;
生成されたノード構造体のアドレスを戻り値としてリターンします。
Program構造体
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R84
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/chibicc.h#L84
typedef struct { Node *node; Var *locals; int stack_size; } Program;
生成されるアセンブリコードの抽象構文木、ローカル変数、スタックサイズを管理するためのデータ構造であるProgram構造体を定義します。
program関数
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR63
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/parse.c#L63
Program *program() { locals = NULL; Node head; head.next = NULL; Node *cur = &head; while (!at_eof()) { cur->next = stmt(); cur = cur->next; } Program *prog = calloc(1, sizeof(Program)); prog->node = head.next; prog->locals = locals; return prog; }
抽象構文木のルートノードからなる連結リストのヘッダーを作成する(変更なし)
Node head; head.next = NULL; Node *cur = &head;
抽象構文木のルートノードからなる連結リストを作成する(変更なし)
while (!at_eof()) { cur->next = stmt(); cur = cur->next; }
プログラム構造体をリターンする
Program *prog = calloc(1, sizeof(Program)); prog->node = head.next; prog->locals = locals; return prog;
calloc関数を呼び出して、Program構造体を生成するのに必要なメモリ領域を割り当てます。
nodeメンバに抽象構文木のルートノードのからなる連結リストの先頭要素のアドレス、localsメンバにVar構造体からなる連結リストの先頭要素のアドレス、を格納してから、Program構造体のアドレスを戻り値としてリターンします。
primary関数
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR187
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/parse.c#L187
Node *primary() { if (consume("(")) { Node *node = expr(); expect(")"); return node; } Token *tok = consume_ident(); if (tok) { Var *var = find_var(tok); if (!var) var = push_var(strndup(tok->str, tok->len)); return new_var(var); } return new_num(expect_number()); }
"("とexprと")"(変更なし)
if (consume("(")) { Node *node = expr(); expect(")"); return node; }
ident
Token *tok = consume_ident(); if (tok) { Var *var = find_var(tok); if (!var) var = push_var(strndup(tok->str, tok->len)); return new_var(var); }
consume_ident関数を呼び出してtokが真となる場合 → 識別子(ローカル変数)を表現するトークンを取得できた場合は、find_var関数を呼び出して、Var構造体からなる連結リストから、tokが持つ文字列と同じ名前を持つvar構造体変数を取得します。
!varが真となる場合→tokが持つ文字列と同じ名前を持つvar構造体変数を取得できなかった場合は、push_var関数を呼び出して、var構造体を新規に生成しvar構造体の連結リストに追加します。
最後に、new_var関数を呼び出して、ローカル変数に対応するノードを新規に生成します。
num(変更なし)
return new_num(expect_number());
find_var関数
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR5
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/parse.c#L5
// Find a local variable by name. Var *find_var(Token *tok) { for (Var *var = locals; var; var = var->next) if (strlen(var->name) == tok->len && !memcmp(tok->str, var->name, tok->len)) return var; return NULL; }
find_var関数は、var構造体からなる連結リストからトークンの文字列と同じ名前を持つvar構造体を探索します(今まで定義されたローカル変数からトークンの文字列と同じ名前を持つローカル変数を探索します)。
for文の初期設定式でグローバル変数localsから連結リストにある先頭要素のアドレスを取得します。
strlen関数の戻り値とtok->lenの値が等しい、かつ、memcmp関数の戻り値が0となる場合 → var->nameの長さとtok->lenの長さが同じ、かつ、var->nameの値とtok->strの値が同じ場合 → 今まで定義されたローカル変数名の長さと引数で指定されたトークン文字列の長さが同じ、かつ、今まで定義されたローカル変数名と指定されたトークン文字列が同じ場合は、そのVar構造体変数のアドレスを戻り値としてリターンします。
Var構造体からなる連結リストにトークンの文字列と同じ名前を持つVar構造体がなかった場合は、NULLを戻り値としてリターンします。
push_var関数
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR44
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/parse.c#L44
Var *push_var(char *name) { Var *var = calloc(1, sizeof(Var)); var->next = locals; var->name = name; locals = var; return var; }
push_var関数は、ローカル変数を表現しているvar構造体を新規に生成し、localsが指定するvar構造体の連結リストに追加します。
strndup関数
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R29
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/tokenize.c#L29
char *strndup(char *p, int len) { char *buf = malloc(len + 1); strncpy(buf, p, len); buf[len] = '\0'; return buf; }
strndup関数は、引数pが指定する文字列から、長さlen+1となるヌル終端文字列を取得します。
char *buf = malloc(len + 1);
malloc関数を呼び出して、文字列を格納するために必要なメモリ領域を割り当てます。
割り当てるメモリ領域のサイズは、引数で指定されたlen+1バイトです(文字列+ヌル文字)。
割り当てたメモリ領域の先頭アドレスを戻り値として取得します。
strncpy(buf, p, len);
strncp関数は、第二引数pのアドレスから、第一引数bufのアドレスへ、第三引数lenで指定されたサイズ分の文字データをコピーします。
buf[len] = '\0';
メモリ領域の最後尾1バイトにヌル文字を格納します。
return buf;
割り当てたメモリ領域の先頭アドレスを戻り値としてリターンします。
codegen関数
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR98
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/codegen.c#L98
void codegen(Program *prog) { printf(".intel_syntax noprefix\n"); printf(".global main\n"); printf("main:\n"); // Prologue printf(" push rbp\n"); printf(" mov rbp, rsp\n"); printf(" sub rsp, %d\n", prog->stack_size); // Emit code for (Node *node = prog->node; node; node = node->next) gen(node); // Epilogue printf(".Lreturn:\n"); printf(" mov rsp, rbp\n"); printf(" pop rbp\n"); printf(" ret\n"); }
部分的にアセンブリコードを生成する①(変更なし)
printf(".intel_syntax noprefix\n"); printf(".global main\n"); printf("main:\n");
部分的にアセンブリコードを生成する②
// Prologue printf(" push rbp\n"); printf(" mov rbp, rsp\n"); printf(" sub rsp, %d\n", prog->stack_size);
printf(" sub rsp, 208\n");を削除し、printf(" sub rsp, %d\n", prog->stack_size);を追加します。
prog->stack_sizeで指定された値の分だけ、ローカル変数を退避させるスタック領域を用意しておきます。
部分的にアセンブリコードを生成する③
// Emit code for (Node *node = prog->node; node; node = node->next) gen(node);
prog構造体変数からnodeを取得するように変更します。
部分的にアセンブリコードを生成する④(変更なし)
// Epilogue printf(".Lreturn:\n"); printf(" mov rsp, rbp\n"); printf(" pop rbp\n"); printf(" ret\n");
gen関数
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR37
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/codegen.c#L37
void gen(Node *node) { switch (node->kind) { case ND_NUM: printf(" push %d\n", node->val); return; case ND_EXPR_STMT: gen(node->lhs); printf(" add rsp, 8\n"); return; case ND_VAR: gen_addr(node); load(); return; case ND_ASSIGN: gen_addr(node->lhs); gen(node->rhs); store(); return; case ND_RETURN: gen(node->lhs); printf(" pop rax\n"); printf(" jmp .Lreturn\n"); return; } gen(node->lhs); gen(node->rhs); printf(" pop rdi\n"); printf(" pop rax\n"); switch (node->kind) { case ND_ADD: printf(" add rax, rdi\n"); break; case ND_SUB: printf(" sub rax, rdi\n"); break; case ND_MUL: printf(" imul rax, rdi\n"); break; case ND_DIV: printf(" cqo\n"); printf(" idiv rdi\n"); break; case ND_EQ: printf(" cmp rax, rdi\n"); printf(" sete al\n"); printf(" movzb rax, al\n"); break; case ND_NE: printf(" cmp rax, rdi\n"); printf(" setne al\n"); printf(" movzb rax, al\n"); break; case ND_LT: printf(" cmp rax, rdi\n"); printf(" setl al\n"); printf(" movzb rax, al\n"); break; case ND_LE: printf(" cmp rax, rdi\n"); printf(" setle al\n"); printf(" movzb rax, al\n"); break; } printf(" push rax\n"); }
二項演算以外を行うアセンブリコードを生成する
switch (node->kind) { case ND_NUM: printf(" push %d\n", node->val); return; case ND_EXPR_STMT: gen(node->lhs); printf(" add rsp, 8\n"); return; case ND_VAR: gen_addr(node); load(); return; case ND_ASSIGN: gen_addr(node->lhs); gen(node->rhs); store(); return; case ND_RETURN: gen(node->lhs); printf(" pop rax\n"); printf(" jmp .Lreturn\n"); return; }
ローカル変数を表現するノード型をND_LVARからND_VARへ変更します。
二項演算の対象となる値を得るためのアセンブリコードを生成する(変更なし)
gen(node->lhs); gen(node->rhs); printf(" pop rdi\n"); printf(" pop rax\n");
二項演算を行うアセンブリコードを生成する(変更なし)
switch (node->kind) { case ND_ADD: printf(" add rax, rdi\n"); break; case ND_SUB: printf(" sub rax, rdi\n"); break; case ND_MUL: printf(" imul rax, rdi\n"); break; case ND_DIV: printf(" cqo\n"); printf(" idiv rdi\n"); break; case ND_EQ: printf(" cmp rax, rdi\n"); printf(" sete al\n"); printf(" movzb rax, al\n"); break; case ND_NE: printf(" cmp rax, rdi\n"); printf(" setne al\n"); printf(" movzb rax, al\n"); break; case ND_LT: printf(" cmp rax, rdi\n"); printf(" setl al\n"); printf(" movzb rax, al\n"); break; case ND_LE: printf(" cmp rax, rdi\n"); printf(" setle al\n"); printf(" movzb rax, al\n"); break; } printf(" push rax\n");
gen_addr関数
https://github.com/rui314/chibicc/commit/8a8a35b9241dcbdc39926e5e64f6f22e8174418f#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR5
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/codegen.c#L5
void gen_addr(Node *node) { if (node->kind == ND_VAR) { printf(" lea rax, [rbp-%d]\n", node->var->offset); printf(" push rax\n"); return; } error("not an lvalue"); }
左辺値を取得するためのアセンブリコードを生成する
if (node->kind == ND_VAR) { printf(" lea rax, [rbp-%d]\n", node->var->offset); printf(" push rax\n"); return; }
ローカル変数を表現するノード型をND_LVARからND_VARへ変更します。
gen_addr関数内でオフセットを計算するのではなく、node->var->offsetの値をオフセットとして使用するようにします。
エラーメッセージを表示する(変更なし)
error("not an lvalue");
テストコード
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/test.sh
#!/bin/bash assert() { expected="$1" input="$2" ./chibicc "$input" > tmp.s gcc -static -o tmp tmp.s ./tmp actual="$?" if [ "$actual" = "$expected" ]; then echo "$input => $actual" else echo "$input => $expected expected, but got $actual" exit 1 fi } assert 0 'return 0;' assert 42 'return 42;' assert 21 'return 5+20-4;' assert 41 'return 12 + 34 - 5 ;' assert 47 'return 5+6*7;' assert 15 'return 5*(9-6);' assert 4 'return (3+5)/2;' assert 10 'return -10+20;' assert 10 'return - -10;' assert 10 'return - - +10;' assert 0 'return 0==1;' assert 1 'return 42==42;' assert 1 'return 0!=1;' assert 0 'return 42!=42;' assert 1 'return 0<1;' assert 0 'return 1<1;' assert 0 'return 2<1;' assert 1 'return 0<=1;' assert 1 'return 1<=1;' assert 0 'return 2<=1;' assert 1 'return 1>0;' assert 0 'return 1>1;' assert 0 'return 1>2;' assert 1 'return 1>=0;' assert 1 'return 1>=1;' assert 0 'return 1>=2;' assert 3 'a=3; return a;' assert 8 'a=3; z=5; return a+z;' assert 1 'return 1; 2; 3;' assert 2 '1; return 2; 3;' assert 3 '1; 2; return 3;' assert 3 'foo=3; return foo;' assert 8 'foo123=3; bar=5; return foo123+bar;' echo OK
Makefile
https://github.com/rui314/chibicc/blob/8a8a35b9241dcbdc39926e5e64f6f22e8174418f/Makefile
CFLAGS=-std=c11 -g -static SRCS=$(wildcard *.c) OBJS=$(SRCS:.c=.o) chibicc: $(OBJS) $(CC) -o $@ $(OBJS) $(LDFLAGS) $(OBJS): chibicc.h test: chibicc ./test.sh clean: rm -f chibicc *.o *~ tmp* .PHONY: test clean