chibiccを読む～Cコンパイラコードリーディング～ ステップ13
トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ13に該当
github.com
追加・修正されたコンパイラのソースコード
tokenize関数
https://github.com/rui314/chibicc/commit/8eea2ec3a8d9a828d2ddf85cf3f46c303f937a04#diff-289479d6df6940b25dd31a6f2da4881331f916ec642bd1ae47d4ff0a365d8e88R141
https://github.com/rui314/chibicc/blob/8eea2ec3a8d9a828d2ddf85cf3f46c303f937a04/tokenize.c#L141
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 or multi-letter punctuator
char *kw = starts_with_reserved(p);
if (kw) {
int len = strlen(kw);
cur = new_token(TK_RESERVED, cur, p, len);
p += len;
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 or multi-letter punctuator
char *kw = starts_with_reserved(p);
if (kw) {
int len = strlen(kw);
cur = new_token(TK_RESERVED, cur, p, len);
p += len;
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;
}
数字の場合(変更なし)
// 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/8eea2ec3a8d9a828d2ddf85cf3f46c303f937a04#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R71
https://github.com/rui314/chibicc/blob/8eea2ec3a8d9a828d2ddf85cf3f46c303f937a04/chibicc.h#L71
// AST node
typedef enum {
ND_ADD, // +
ND_SUB, // -
ND_MUL, // *
ND_DIV, // /
ND_EQ, // ==
ND_NE, // !=
ND_LT, // <
ND_LE, // <=
ND_ASSIGN, // =
ND_RETURN, // "return"
ND_IF, // "if"
ND_WHILE, // "while"
ND_FOR, // "for"
ND_BLOCK, // { ... }
ND_EXPR_STMT, // Expression statement
ND_VAR, // Variable
ND_NUM, // Integer
} NodeKind;ブロックを表現するノード型ND_BLOCKを追加します。
Node構造体
https://github.com/rui314/chibicc/commit/8eea2ec3a8d9a828d2ddf85cf3f46c303f937a04#diff-d06dbb7ef5899cdf50b340464444680b13aded45363e7aba944dc3551fdf6334R94
https://github.com/rui314/chibicc/blob/8eea2ec3a8d9a828d2ddf85cf3f46c303f937a04/chibicc.h#L94
// 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
// "if, "while" or "for" statement
Node *cond;
Node *then;
Node *els;
Node *init;
Node *inc;
// Block
Node *body;
Var *var; // Used if kind == ND_VAR
int val; // Used if kind == ND_NUM
};ブロックをパースする際に使用する子ノードbodyを追加します。
stmt関数
https://github.com/rui314/chibicc/commit/8eea2ec3a8d9a828d2ddf85cf3f46c303f937a04#diff-a07721cd062be25900bddb926de15fc103cf32ea2726d1fea286f6548b810c6aR137
https://github.com/rui314/chibicc/blob/8eea2ec3a8d9a828d2ddf85cf3f46c303f937a04/parse.c#L137
Node *stmt() {
if (consume("return")) {
Node *node = new_unary(ND_RETURN, expr());
expect(";");
return node;
}
if (consume("if")) {
Node *node = new_node(ND_IF);
expect("(");
node->cond = expr();
expect(")");
node->then = stmt();
if (consume("else"))
node->els = stmt();
return node;
}
if (consume("while")) {
Node *node = new_node(ND_WHILE);
expect("(");
node->cond = expr();
expect(")");
node->then = stmt();
return node;
}
if (consume("for")) {
Node *node = new_node(ND_FOR);
expect("(");
if (!consume(";")) {
node->init = read_expr_stmt();
expect(";");
}
if (!consume(";")) {
node->cond = expr();
expect(";");
}
if (!consume(")")) {
node->inc = read_expr_stmt();
expect(")");
}
node->then = stmt();
return node;
}
if (consume("{")) {
Node head;
head.next = NULL;
Node *cur = &head;
while (!consume("}")) {
cur->next = stmt();
cur = cur->next;
}
Node *node = new_node(ND_BLOCK);
node->body = head.next;
return node;
}
Node *node = read_expr_stmt();
expect(";");
return node;
}stmt関数は、生成規則 stmt = "return" expr ";" | "if" "(" expr ")" stmt ("else" stmt)? | "while" "(" expr ")" stmt | "for" "(" expr? ";" expr? ";" expr? ")" stmt | "{" stmt* "}" | expr ";" に基づいて、抽象構文木のノードを生成します。
"return"、expr、";"(変更なし)
if (consume("return")) {
Node *node = new_unary(ND_RETURN, expr());
expect(";");
return node;
}
"if"、"("、expr、")"、stmt 、「"else" と stmt」を0回か1回(変更なし)
if (consume("if")) {
Node *node = new_node(ND_IF);
expect("(");
node->cond = expr();
expect(")");
node->then = stmt();
if (consume("else"))
node->els = stmt();
return node;
}
"while"、"("、expr、")"、stmt(変更なし)
if (consume("while")) {
Node *node = new_node(ND_WHILE);
expect("(");
node->cond = expr();
expect(")");
node->then = stmt();
return node;
}
"for"、"("、exprを0回か1回、 ";"、exprを0回か1回、";"、exprを0回か1回、")"、stmt
if (consume("for")) {
Node *node = new_node(ND_FOR);
expect("(");
if (!consume(";")) {
node->init = read_expr_stmt();
expect(";");
}
if (!consume(";")) {
node->cond = expr();
expect(";");
}
if (!consume(")")) {
node->inc = read_expr_stmt();
expect(")");
}
node->then = stmt();
return node;
}
"{"、stmtを0回以上、"}"
if (consume("{")) {
Node head;
head.next = NULL;
Node *cur = &head;
while (!consume("}")) {
cur->next = stmt();
cur = cur->next;
}
Node *node = new_node(ND_BLOCK);
node->body = head.next;
return node;
}consume("{")の戻り値がtrueとなる場合→着目しているトークンが"{"の場合は、ブロック(複文)の抽象構文木を生成する処理を行います。
ノード構造体headを定義し、これから作成する連結リスト(ノード構造体からなる連結リスト)のヘッダーとします。
nextメンバの初期値はNULL、連結リストの終端をcurで表現します。
consume("}")の戻り値がtrueになるまで→着目しているトークンが”}”を表すトークンになるまで、while文のループを継続します。
stmt関数を呼び出して抽象構文木を生成し、生成された抽象構文木のルートノードのアドレスを戻り値として取得します。
戻り値として取得した抽象構文木のルートノードのアドレスを連結リストの終端要素のnextメンバに格納し、連結リストの終端要素を表すcurを更新します。
最後に、new_node関数を呼び出してブロックを表すノードを生成し、連結リストの先頭ノード(連結リストのヘッダーの次にあるノード)を子ノードbodyとして登録します。
expr、";"(変更なし)
Node *node = read_expr_stmt();
expect(";");
return node;
gen関数
https://github.com/rui314/chibicc/commit/8eea2ec3a8d9a828d2ddf85cf3f46c303f937a04#diff-629fe11334ae1d560032cdb6cc6f9a4fbb0f5b1365894b6b648d6ee4d5a654beR100
https://github.com/rui314/chibicc/blob/8eea2ec3a8d9a828d2ddf85cf3f46c303f937a04/codegen.c#L100
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_IF: {
int seq = labelseq++;
if (node->els) {
gen(node->cond);
printf(" pop rax\n");
printf(" cmp rax, 0\n");
printf(" je .Lelse%d\n", seq);
gen(node->then);
printf(" jmp .Lend%d\n", seq);
printf(".Lelse%d:\n", seq);
gen(node->els);
printf(".Lend%d:\n", seq);
} else {
gen(node->cond);
printf(" pop rax\n");
printf(" cmp rax, 0\n");
printf(" je .Lend%d\n", seq);
gen(node->then);
printf(".Lend%d:\n", seq);
}
return;
}
case ND_WHILE: {
int seq = labelseq++;
printf(".Lbegin%d:\n", seq);
gen(node->cond);
printf(" pop rax\n");
printf(" cmp rax, 0\n");
printf(" je .Lend%d\n", seq);
gen(node->then);
printf(" jmp .Lbegin%d\n", seq);
printf(".Lend%d:\n", seq);
return;
}
case ND_FOR: {
int seq = labelseq++;
if (node->init)
gen(node->init);
printf(".Lbegin%d:\n", seq);
if (node->cond) {
gen(node->cond);
printf(" pop rax\n");
printf(" cmp rax, 0\n");
printf(" je .Lend%d\n", seq);
}
gen(node->then);
if (node->inc)
gen(node->inc);
printf(" jmp .Lbegin%d\n", seq);
printf(".Lend%d:\n", seq);
return;
}
case ND_BLOCK:
for (Node *n = node->body; n; n = n->next)
gen(n);
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_IF: {
int seq = labelseq++;
if (node->els) {
gen(node->cond);
printf(" pop rax\n");
printf(" cmp rax, 0\n");
printf(" je .Lelse%d\n", seq);
gen(node->then);
printf(" jmp .Lend%d\n", seq);
printf(".Lelse%d:\n", seq);
gen(node->els);
printf(".Lend%d:\n", seq);
} else {
gen(node->cond);
printf(" pop rax\n");
printf(" cmp rax, 0\n");
printf(" je .Lend%d\n", seq);
gen(node->then);
printf(".Lend%d:\n", seq);
}
return;
}
case ND_WHILE: {
int seq = labelseq++;
printf(".Lbegin%d:\n", seq);
gen(node->cond);
printf(" pop rax\n");
printf(" cmp rax, 0\n");
printf(" je .Lend%d\n", seq);
gen(node->then);
printf(" jmp .Lbegin%d\n", seq);
printf(".Lend%d:\n", seq);
return;
}
case ND_FOR: {
int seq = labelseq++;
if (node->init)
gen(node->init);
printf(".Lbegin%d:\n", seq);
if (node->cond) {
gen(node->cond);
printf(" pop rax\n");
printf(" cmp rax, 0\n");
printf(" je .Lend%d\n", seq);
}
gen(node->then);
if (node->inc)
gen(node->inc);
printf(" jmp .Lbegin%d\n", seq);
printf(".Lend%d:\n", seq);
return;
}
case ND_BLOCK:
for (Node *n = node->body; n; n = n->next)
gen(n);
return;
case ND_RETURN:
gen(node->lhs);
printf(" pop rax\n");
printf(" jmp .Lreturn\n");
return;
}ノードの型がND_BLOCKの場合の処理を追加します。
ノードの型がND_BLOCKの場合は、抽象構文木のルートノードからなる連結リストbodyを用いてgen関数を呼び出し、ブロック内の式文に対応するアセンブリコードを生成します。
二項演算の対象となる値を得るためのアセンブリコードを生成する(変更なし)
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");
}
テストコード
https://github.com/rui314/chibicc/commit/8eea2ec3a8d9a828d2ddf85cf3f46c303f937a04#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R64
https://github.com/rui314/chibicc/blob/8eea2ec3a8d9a828d2ddf85cf3f46c303f937a04/test.sh#L64
#!/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;'
assert 3 'if (0) return 2; return 3;'
assert 3 'if (1-1) return 2; return 3;'
assert 2 'if (1) return 2; return 3;'
assert 2 'if (2-1) return 2; return 3;'
assert 3 '{1; {2;} return 3;}'
assert 10 'i=0; while(i<10) i=i+1; return i;'
assert 55 'i=0; j=0; while(i<=10) {j=i+j; i=i+1;} return j;'
assert 55 'i=0; j=0; for (i=0; i<=10; i=i+1) j=i+j; return j;'
assert 3 'for (;;) return 3; return 5;'
echo OK
Makefile
https://github.com/rui314/chibicc/blob/8eea2ec3a8d9a828d2ddf85cf3f46c303f937a04/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
