chibiccを読む～Cコンパイラコードリーディング～ ステップ6
トップページ
jupiteroak.hatenablog.com
「低レイヤを知りたい人のためのCコンパイラ作成入門」のCコンパイラを読んでいきます。
www.sigbus.info
ステップ6に該当
github.com
コンパイラのソースコード
https://github.com/rui314/chibicc/blob/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d/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 *unary();
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 = unary ("*" unary | "/" unary)*
Node *mul() {
Node *node = unary();
for (;;) {
if (consume('*'))
node = new_binary(ND_MUL, node, unary());
else if (consume('/'))
node = new_binary(ND_DIV, node, unary());
else
return node;
}
}
// unary = ("+" | "-")? unary
// | primary
Node *unary() {
if (consume('+'))
return unary();
if (consume('-'))
return new_binary(ND_SUB, new_num(0), unary());
return primary();
}
// 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;
}
追加・修正されたコンパイラのソースコード
mul関数
https://github.com/rui314/chibicc/commit/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR186
https://github.com/rui314/chibicc/blob/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d/main.c#L186
// mul = unary ("*" unary | "/" unary)*
Node *mul() {
Node *node = unary();
for (;;) {
if (consume('*'))
node = new_binary(ND_MUL, node, unary());
else if (consume('/'))
node = new_binary(ND_DIV, node, unary());
else
return node;
}
}mul関数は、生成規則 mul = unary ("*" unary | "/" unary)* に基づいて、抽象構文木のノードを生成します。
unary
https://github.com/rui314/chibicc/commit/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR188
https://github.com/rui314/chibicc/blob/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d/main.c#L188
Node *node = unary();
primary関数をunary関数に変更。
「"*"とprimary または "/"とprimary」を0回以上
for (;;) {
if (consume('*'))
node = new_binary(ND_MUL, node, unary());
else if (consume('/'))
node = new_binary(ND_DIV, node, unary());
else
return node;第三引数のprimary関数をunary関数に変更。
unary関数
https://github.com/rui314/chibicc/commit/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d#diff-a0cb465674c1b01a07d361f25a0ef2b0214b7dfe9412b7777f89add956da10ecR200
https://github.com/rui314/chibicc/blob/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d/main.c#L200
// unary = ("+" | "-")? unary
// | primary
Node *unary() {
if (consume('+'))
return unary();
if (consume('-'))
return new_binary(ND_SUB, new_num(0), unary());
return primary();
}unary関数は、生成規則 unary =("+" | "-")? unary | primaryに基づいて、抽象構文木のノードを生成します。
(低レイヤを知りたい人のためのCコンパイラ作成入門で説明している生成規則と少し異なることに注意)
「"+"または"-" を0回か1回」とunaray
if (consume('+'))
return unary();
if (consume('-'))
return new_binary(ND_SUB, new_num(0), unary());consume('+')の戻り値がtrueとなる場合→着目しているトークンが + の場合は、unary関数を再帰的に呼び出します。
(パースの段階で加算記号を表現するノードと数値を表現するノードを生成するのではなく、数値を表現するノードのみを生成します。+xをxに置き換える)
consume('-')の戻り値がtrueとなる場合→着目しているトークンが - の場合は、new_binary関数を呼び出して、減算記号を表現するノードを生成します。この減算記号を表現するノードは、第二引数のnew_num(0)で生成されたノードと第三引数のunary()で生成されたノードを子ノードとして持ちます。
(パースの段階で減算記号を表現するノードと数値を表現するノードの2つを生成するのではなく、減算記号を表現するノードと0を表現するノードと数値を表現するノードの3つを生成します。-xを0-xに置き換える)
primary
return primary();
consume('+')の戻り値もconsume('-')の戻り値もfalseとなる場合→着目しているトークンが + でも - でもない場合は、primary関数を呼び出します。
テストコード
test.sh
https://github.com/rui314/chibicc/commit/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d#diff-3722d9ba8feb2d3feac8ce71a209a638d4b404e1c53f937188761181594023e2R26
https://github.com/rui314/chibicc/blob/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d/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 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'
assert 10 '-10+20'
assert 10 '- -10'
assert 10 '- - +10'
echo OK
Makefile
https://github.com/rui314/chibicc/blob/bb5fe99dbad62c9516ec6a4bc64e444d09115e6d/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
