chibiccを読む~Cコンパイラコードリーディング~ ステップ5
トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ5に該当
github.com
- 今回作成するコンパイラ
- コンパイラのソースコード
- 追加・修正されたコンパイラのソースコード
- テストコード
- Makefile
コンパイラのソースコード
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c
#include <ctype.h> #include <stdarg.h> #include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <string.h> // // Tokenizer // typedef enum { TK_RESERVED, // Keywords or punctuators TK_NUM, // Integer literals TK_EOF, // End-of-file markers } TokenKind; // Token type typedef struct Token Token; struct Token { TokenKind kind; // Token kind Token *next; // Next token int val; // If kind is TK_NUM, its value char *str; // Token string }; // Input program char *user_input; // Current token Token *token; // Reports an error and exit. void error(char *fmt, ...) { va_list ap; va_start(ap, fmt); vfprintf(stderr, fmt, ap); fprintf(stderr, "\n"); exit(1); } // Reports an error location and exit. void error_at(char *loc, char *fmt, ...) { va_list ap; va_start(ap, fmt); int pos = loc - user_input; fprintf(stderr, "%s\n", user_input); fprintf(stderr, "%*s", pos, ""); // print pos spaces. fprintf(stderr, "^ "); vfprintf(stderr, fmt, ap); fprintf(stderr, "\n"); exit(1); } // Consumes the current token if it matches `op`. bool consume(char op) { if (token->kind != TK_RESERVED || token->str[0] != op) return false; token = token->next; return true; } // Ensure that the current token is `op`. void expect(char op) { if (token->kind != TK_RESERVED || token->str[0] != op) error_at(token->str, "expected '%c'", op); token = token->next; } // Ensure that the current token is TK_NUM. int expect_number() { if (token->kind != TK_NUM) error_at(token->str, "expected a number"); int val = token->val; token = token->next; return val; } bool at_eof() { return token->kind == TK_EOF; } // Create a new token and add it as the next token of `cur`. Token *new_token(TokenKind kind, Token *cur, char *str) { Token *tok = calloc(1, sizeof(Token)); tok->kind = kind; tok->str = str; cur->next = tok; return tok; } // Tokenize `user_input` and returns new tokens. Token *tokenize() { char *p = user_input; Token head; head.next = NULL; Token *cur = &head; while (*p) { // Skip whitespace characters. if (isspace(*p)) { p++; continue; } // Punctuator if (strchr("+-*/()", *p)) { cur = new_token(TK_RESERVED, cur, p++); continue; } // Integer literal if (isdigit(*p)) { cur = new_token(TK_NUM, cur, p); cur->val = strtol(p, &p, 10); continue; } error_at(p, "invalid token"); } new_token(TK_EOF, cur, p); return head.next; } // // Parser // typedef enum { ND_ADD, // + ND_SUB, // - ND_MUL, // * ND_DIV, // / ND_NUM, // Integer } NodeKind; // AST node type typedef struct Node Node; struct Node { NodeKind kind; // Node kind Node *lhs; // Left-hand side Node *rhs; // Right-hand side int val; // Used if kind == ND_NUM }; Node *new_node(NodeKind kind) { Node *node = calloc(1, sizeof(Node)); node->kind = kind; return node; } Node *new_binary(NodeKind kind, Node *lhs, Node *rhs) { Node *node = new_node(kind); node->lhs = lhs; node->rhs = rhs; return node; } Node *new_num(int val) { Node *node = new_node(ND_NUM); node->val = val; return node; } Node *expr(); Node *mul(); Node *primary(); // expr = mul ("+" mul | "-" mul)* Node *expr() { Node *node = mul(); for (;;) { if (consume('+')) node = new_binary(ND_ADD, node, mul()); else if (consume('-')) node = new_binary(ND_SUB, node, mul()); else return node; } } // mul = primary ("*" primary | "/" primary)* Node *mul() { Node *node = primary(); for (;;) { if (consume('*')) node = new_binary(ND_MUL, node, primary()); else if (consume('/')) node = new_binary(ND_DIV, node, primary()); else return node; } } // primary = "(" expr ")" | num Node *primary() { if (consume('(')) { Node *node = expr(); expect(')'); return node; } return new_num(expect_number()); } // // Code generator // void gen(Node *node) { if (node->kind == ND_NUM) { printf(" push %d\n", node->val); 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; } printf(" push rax\n"); } 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 = expr(); // Print out the first half of assembly. printf(".intel_syntax noprefix\n"); printf(".global main\n"); printf("main:\n"); // Traverse the AST to emit assembly. gen(node); // A result must be at the top of the stack, so pop it // to RAX to make it a program exit code. printf(" pop rax\n"); printf(" ret\n"); return 0; }
追加・修正されたコンパイラのソースコード
main関数
https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR252
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L252
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 = expr(); // Print out the first half of assembly. printf(".intel_syntax noprefix\n"); printf(".global main\n"); printf("main:\n"); // Traverse the AST to emit assembly. gen(node); // A result must be at the top of the stack, so pop it // to RAX to make it a program exit code. printf(" pop rax\n"); printf(" ret\n"); return 0; }
コマンドライン引数の個数をチェックする(変更なし)
if (argc != 2) error("%s: invalid number of arguments", argv[0]);
トークナイズを行う(変更なし)
// Tokenize and parse. user_input = argv[1]; token = tokenize();
部分的にアセンブリコードを生成する①(変更なし)
// Print out the first half of assembly. printf(".intel_syntax noprefix\n"); printf(".global main\n"); printf("main:\n");
部分的にアセンブリコードを生成する②
// Traverse the AST to emit assembly. gen(node);
部分的にアセンブリコードを生成する③
// A result must be at the top of the stack, so pop it // to RAX to make it a program exit code. printf(" pop rax\n"); printf(" ret\n"); return 0;
抽象構文木の最終的な結果を表す値がスタックに退避されているので(gen関数の最後ではアセンブリコード"push rax"を生成しているので)、アセンブリコード"pop rax"を生成して、抽象構文木の最終的な結果を表す値がraxレジスタにセットされるようにします。最後にアセンブリコード"ret"を生成します。
tokenize関数
https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR108
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L108
Token *tokenize() { char *p = user_input; Token head; head.next = NULL; Token *cur = &head; while (*p) { // Skip whitespace characters. if (isspace(*p)) { p++; continue; } // Punctuator if (strchr("+-*/()", *p)) { cur = new_token(TK_RESERVED, cur, p++); continue; } // Integer literal if (isdigit(*p)) { cur = new_token(TK_NUM, cur, p); cur->val = strtol(p, &p, 10); continue; } error_at(p, "invalid token"); } new_token(TK_EOF, cur, p); return head.next; }
文字列の先頭アドレスを取得する(変更なし)
char *p = user_input;
トークンからなる連結リストのヘッダーを作成する(変更なし)
Token head; head.next = NULL; Token *cur = &head;
空白文字の場合(変更なし)
// Skip whitespace characters. if (isspace(*p)) { p++; continue; }
+-*/()の場合
https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR108
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L108
// Punctuator if (strchr("+-*/()", *p)) { cur = new_token(TK_RESERVED, cur, p++); continue; }
str関数は、第一引数で指定された文字列から、第二引数で指定された文字を探索します。
第二引数の文字がみつかった場合は、第一引数の文字列において第二引数の文字が位置しているアドレス値が戻り値となります。
第二引数の文字がみつからなかった場合は、NULLが戻り値となります。
条件式strchr("+-*/()", *p) が真となる場合→文字*pが +、-、*、/、(、) のいずれかの場合は、new_token関数を呼び出して、記号を表現するトークンを生成しトークンの連結リストを作成します。
変数curには、新規に生成されたトークン(連結リストの終端要素)のアドレスが格納されます。
次の文字を取得するためにchar型へのポインタpをインクリメントしてからwhile文のループを継続します(char型へのポインタpを後置インクリメントしているので、評価前のpの値(+または-の文字を指定するアドレス)が引数として渡されます)。
数字の場合(変更なし)
// Integer literal if (isdigit(*p)) { cur = new_token(TK_NUM, cur, p); cur->val = strtol(p, &p, 10); continue; }
その他の場合
error_at(p, "invalid token"); }
エラーメッセージを変更。
連結リストの先頭トークンを戻り値としてリターンする(変更なし)
return head.next;
NodeKind
https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR131
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L131
typedef enum { ND_ADD, // + ND_SUB, // - ND_MUL, // * ND_DIV, // / ND_NUM, // Integer } NodeKind;
enum型を用いて、ノードの種類(ノードの型)を表現する名前付き整数定数を定めます。さらに、typedefキーワードを用いて、enum型をNodeKind型として定義します。
Node構造体
typedef struct Node Node; struct Node { NodeKind kind; // Node kind Node *lhs; // Left-hand side Node *rhs; // Right-hand side int val; // Used if kind == ND_NUM };
ノードを表現するデータ構造であるNode構造体を定義します。
さらに、typedefキーワードを用いて、Node構造体をNode型として定義します。
new_node関数
https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR148
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L148
Node *new_node(NodeKind kind) { Node *node = calloc(1, sizeof(Node)); node->kind = kind; return node; }
new_node関数は、抽象構文木のノードを新規に生成します。
ノードを生成する
Node *node = calloc(1, sizeof(Node));
calloc関数を呼び出して、ノード構造体の生成に必要なメモリ領域を割り当てます。
calloc関数は、第二引数で指定されたバイトサイズ分のメモリ領域を、第一引数で指定された数だけ、割り当てます。
今回は、sizeof(Node)バイトのメモリ領域を1つ割り当てています。
生成されたノードのメンバに値を設定する
node->kind = kind;
引数で指定されたkindの値(ノードの種類、ノードの型)を生成されるノード構造体のメンバに設定します。
生成されたノードを戻り値としてリターンする
return node;
生成されたノード構造体のアドレスを戻り値としてリターンします。
new_binary関数
https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR154
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L154
Node *new_binary(NodeKind kind, Node *lhs, Node *rhs) { Node *node = new_node(kind); node->lhs = lhs; node->rhs = rhs; return node; }
new_binary関数は、抽象構文木のノード(子ノードを2つ持つ)を新規に生成します。
生成されたノードに2つの子ノードを登録する
node->lhs = lhs; node->rhs = rhs;
引数lhsの値(左の子ノードを指定するアドレス)と引数rhsの値(右の子ノードを指定するアドレス)を生成されるノード構造体のメンバに設定します。
生成されたノードを戻り値としてリターンする
return node
生成されたノード構造体のアドレスを戻り値としてリターンします。
new_num関数
https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR161
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L161
Node *new_num(int val) { Node *node = new_node(ND_NUM); node->val = val; return node; }
new_binary関数は、抽象構文木のノード(数値に対応する外部ノード)を新規に生成します。
生成されたノードのメンバに値を設定する
node->val = val;
引数で指定されたvalの値(ノードの種類、ノードの型)を生成されるノード構造体のメンバに設定します。
生成されたノードを戻り値としてリターンする
return node;
生成されたノード構造体のアドレスを戻り値としてリターンします。
expr関数
https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR172
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L172
Node *expr() { Node *node = mul(); for (;;) { if (consume('+')) node = new_binary(ND_ADD, node, mul()); else if (consume('-')) node = new_binary(ND_SUB, node, mul()); else return node; } }
expr関数は、生成規則 expr = mul ("+" mul | "-" mul)* に基づいて、抽象構文木のノードを生成します。
「"+"とmul または "-"とmul」を0回以上
for (;;) { if (consume('+')) node = new_binary(ND_ADD, node, mul()); else if (consume('-')) node = new_binary(ND_SUB, node, mul()); else return node; }
consume('+')の戻り値がtrueとなる場合→着目しているトークンが + の場合は、new_binary関数を呼び出して、加算記号を表現するノードを生成します。この加算記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのmul関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のprimary関数で生成されたノードを子ノードとして持ちます。
consume('-')の戻り値がtrueとなる場合→着目しているトークンが - の場合は、new_binary関数を呼び出して、減算記号を表現するノードを生成します。この減算記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのprimary関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のprimary関数で生成されたノードを子ノードとして持ちます。
上記以外の場合は、最後に生成されたノードのアドレスを戻り値としてリターンします。
mul関数
https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR186
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L186
Node *mul() { Node *node = primary(); for (;;) { if (consume('*')) node = new_binary(ND_MUL, node, primary()); else if (consume('/')) node = new_binary(ND_DIV, node, primary()); else return node; } }
mul関数は、生成規則 mul = primary ("*" primary | "/" primary)* に基づいて、抽象構文木のノードを生成します。
「"*"とprimary または "/"とprimary」を0回以上
for (;;) { if (consume('*')) node = new_binary(ND_MUL, node, primary()); else if (consume('/')) node = new_binary(ND_DIV, node, primary()); else return node;
consume('*')の戻り値がtrueとなる場合→着目しているトークンが * の場合は、new_binary関数を呼び出して、乗算記号を表現するノードを生成します。この乗算記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのprimary関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のprimary関数で生成されたノードを子ノードとして持ちます。
consume('/')の戻り値がtrueとなる場合→着目しているトークンが / の場合は、new_binary関数を呼び出して、除算記号を表現するノードを生成します。この除算記号を表現するノードは、第二引数のnodeが指定するノード(先ほどのprimary関数で生成されたノード、あるいは、for文内で生成されたノード)と第三引数のprimary関数で生成されたノードを子ノードとして持ちます。
上記以外の場合は、最後に生成されたノードのアドレスを戻り値としてリターンします。
primary関数
https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR200
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L200
Node *primary() { if (consume('(')) { Node *node = expr(); expect(')'); return node; } return new_num(expect_number()); }
primary関数は、生成規則 primary = "(" expr ")" | num に基づいて、抽象構文木のノードを生成します。
(低レイヤを知りたい人のためのCコンパイラ作成入門では、primary = num | "(" expr ")" となっていますがどちらでも問題ありません)
gen関数
https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR214
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/main.c#L214
void gen(Node *node) { if (node->kind == ND_NUM) { printf(" push %d\n", node->val); 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; } printf(" push rax\n"); }
gen関数は、引数で指定された抽象構文木のノードを用いて、アセンブリコードを生成します。
数値を得るためのアセンブリコードを生成する
if (node->kind == ND_NUM) { printf(" push %d\n", node->val); return; }
再帰的に呼び出されるgen関数の基底となる処理です(抽象構文木の外部ノードを生成する処理です)。
引数で指定されたノードの型がND_NUMの場合は(ノードの種類が整数の場合は)、"push (ノードが持つ整数の値)"を生成し、リターンします。
二項演算の対象となる値を得るためのアセンブリコードを生成する
gen(node->lhs); gen(node->rhs); printf(" pop rdi\n"); printf(" pop rax\n");
gen(node->lhs)関数を呼び出して、ノードlhsに対応する値(左の部分木の結果)を得るために必要となるアセンブリコードを生成します。
gen(node->rhs)関数を呼び出して、ノードrhsに対応する値(右の部分木の結果)を得るために必要となるアセンブリコードを生成します。
生成されるアセンブリコードの実行時を考慮すると、ノードlhsに対応する値とノードrhsに対応する値はスタックに退避されている状態なので、ノードlhsに対応する値とノードrhsに対応する値をレジスタにセットして演算対象とするために、 アセンブリコード"pop rdi" と "pop rax"を生成します。
スタックには、ボトムからトップの方向へ、ノードlhsに対応する値、ノードrhsに対応する値、の順で退避されているので、rdiレジスタにはノードrhsに対応する値が、raxレジスタにはノードlhsに対応する値が、それぞれセットされます。
二項演算を行うアセンブリコードを生成する
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; } printf(" push rax\n");
ノードの型に応じて、演算で必要となるアセンブリコードを生成します。
ノードの型がND_ADDの場合は(ノードの種類が加算記号の場合は)、アセンブリコード”add rax, rdi”を生成します。
ノードの型がND_SUBの場合は(ノードの種類が減算記号の場合は)、アセンブリコード”sub rax, rdi”を生成します。
ノードの型がND_MULの場合は(ノードの種類が乗算記号の場合は)、アセンブリコード”imul rax, rdi”を生成します。
ノードの型がND_DIVの場合は(ノードの種類が除算記号の場合は)、アセンブリコード”cqo”と”idiv rdi”を生成します。
最後に演算結果の値をスタックへ退避させるために、アセンブリコード"push rax"を生成します。
テストコード
test.sh
https://github.com/rui314/chibicc/commit/3c1e3831009edff2ea237d3e59680ba9d4bb2e14#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R23
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/test.sh
#!/bin/bash assert() { expected="$1" input="$2" ./9cc "$input" > tmp.s cc -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 0 assert 42 42 assert 21 "5+20-4" assert 41 " 12 + 34 - 5 " assert 47 '5+6*7' assert 15 '5*(9-6)' assert 4 '(3+5)/2' echo OK
Makefile
https://github.com/rui314/chibicc/blob/3c1e3831009edff2ea237d3e59680ba9d4bb2e14/Makefile
CFLAGS=-std=c11 -g -static chibicc: main.o $(CC) -o $@ $? $(LDFLAGS) test: chibicc ./test.sh clean: rm -f chibicc *.o *~ tmp* .PHONY: test clean