C言語で簡単なトークナイザを実装する

前提

code:c

こいつをまずトークン列に変換したい

token = tokenize(argv[1]);

こういうかんじで使う。

返り値に先頭トークンが入る

tokenの種類と構造体を以下のように定義する

code:c

// トークンの種類

typedef enum {

TK_RESERVED, // 記号

TK_NUM, // 整数トークン

TK_EOF, // 入力の終わりを表すトークン

} TokenKind;

typedef struct Token Token;

// トークン型

struct Token {

TokenKind kind; // トークンの型

Token *next; // 次の入力トークン

int val; // kindがTK_NUMの場合、その数値

char *str; // トークン文字列

};

curに渡したtokenのnextに、新しいtokenを繋げて, 新しい方のtokenを返す

数珠つなぎになる

charのポインタも持っておく

code:c

// 新しいトークンを作成して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;

}

whileループでpポインタをなめつつ

code:c

// 入力文字列pをトークナイズしてそれを返す

Token *tokenize(char *p) {

Token head;

head.next = NULL;

Token *cur = &head;

while (*p) {

// 空白文字をスキップ

if (isspace(*p)) {

p++;

continue;

}

if (*p == '+' || *p == '-') {

cur = new_token(TK_RESERVED, cur, p++);

continue;

}

if (isdigit(*p)) {

cur = new_token(TK_NUM, cur, p);

cur->val = strtol(p, &p, 10);

continue;

}

error("トークナイズできません");

}

new_token(TK_EOF, cur, p);

return head.next;

}

なにもないheadを用意して、ここにnew_tokenで継ぎ足していく

headを返すのではなくhead.nextを返せばいい

以下は、tokenの連結リストをもとに、アセンブリを出力するフェーズ

各種便利関数を用意する

consume

expect

expect_number

現在のtokenはグローバル変数として持っておく

以上の便利関数を呼び出すと、

現在のtokenをみて、条件に当てはまればtoken列を進めたりする　これは関数の副作用として発生する

必要に応じて、返り値に結果を返す

直感的に記述ができる

code:c

while (!at_eof()) {

if (consume('+')) {

printf(" add rax, %d\n", expect_number());

continue;

}

expect('-');

printf(" sub rax, %d\n", expect_number());

}

トークン列を順に読みつつ、数値を取得とか

メモ

8ccでもこれをやってるらしい

tcc　ワンパスを真似たらしい

ruiさんの新しい実装は副作用を持たない方法でやってるらしい

code:c

// 現在着目しているトークン

Token *token;

// 次のトークンが期待している記号のときには、トークンを1つ読み進めて

// 真を返す。それ以外の場合には偽を返す。

bool consume(char op) {

return false;

token = token->next;

return true;

}

// 次のトークンが期待している記号のときには、トークンを1つ読み進める。

// それ以外の場合にはエラーを報告する。

void expect(char op) {

error("'%c'ではありません", op);

token = token->next;

}

// 次のトークンが数値の場合、トークンを1つ読み進めてその数値を返す。

// それ以外の場合にはエラーを報告する。

int expect_number() {

if (token->kind != TK_NUM)

error("数ではありません");

int val = token->val;

token = token->next;

return val;

}

bool at_eof() {

return token->kind == TK_EOF;

}

code:c

int main(int argc, char **argv) {

if (argc != 2) {

error("引数の個数が正しくありません");

return 1;

}

// トークナイズする

// アセンブリの前半部分を出力

printf(".intel_syntax noprefix\n");

printf(".global main\n");

printf("main:\n");

// 式の最初は数でなければならないので、それをチェックして

// 最初のmov命令を出力

printf(" mov rax, %d\n", expect_number());

// アセンブリを出力

while (!at_eof()) {

if (consume('+')) {

printf(" add rax, %d\n", expect_number());

continue;

}

expect('-');

printf(" sub rax, %d\n", expect_number());

}

printf(" ret\n");

return 0;

}

便利util

code:c

// エラーを報告するための関数

// printfと同じ引数を取る

void error(char *fmt, ...) {

va_list ap;

va_start(ap, fmt);

vfprintf(stderr, fmt, ap);

fprintf(stderr, "\n");

exit(1);

}