Edited at

ステップバイステップで整数電卓コンパイラをつくろう!

Life is Tech! でメンターをしています、ほりーといいます。

AdventCalendarの参加、二回目です。

題材には、コンパイラを選択してみました。慣れないC言語を使って挑戦していきたいと思います


はじめに

プログラムを書いても、コンピュータが理解できる形式でないと実行できません。そう、僕らが書いたプログラムを機械語になおしてくれる、コンパイラが必要です。この記事では、簡単な整数電卓ができるコンパイラを作り、コンパイラに必要な考え方を見ていきます。

今回作るコンパイラはとても簡単です。整数の足し算・引き算・掛け算しかしないことにします。つまり「2 + 3」で5が出力されたり、「2 + 4 * 5」なら22が出力されることを目指します。

Macでコードを書いて行きますので、環境によってややコードが異なります。

正確さを求めて環境ごとの細かい注釈を施すことはせず、コンパイラの動作を理解することを重視します。

それではやっていきましょう


基本的な考え方

コンパイラが行う動作にはいくつかあります。


字句解析

「2 + 34」というコードを考えて見ましょう。僕ら人間は、これをみた瞬間「2」「+」「34」という要素に分解することができますが、この文字列を受け取ったコンパイラからすれば空白が入ったただの文字列に過ぎません。これを意味のあるまとまりとして分けることを字句解析といいます


構文解析

「2 * 4 + 5」というコードを考えてみましょう。これはどのように計算したら良いでしょうか。そうです、コードの頭から「2 に 4 をかけて、5を足」してあげれば大丈夫です。

では「2 + 4 * 5」というコードはどうでしょうか。これはコードの頭から計算するわけにはいきません。「4 に 5 をかけたうえで、2を足」してあげるのが正解ですね。

つまり、トークンの並びかたによっては処理をする順番が変わります。字句解析では単純な一連のトークンであったものを、ある意味のもったデータ構造に変換する必要があります。これが構文解析で行うことです。


コード生成

構文解析で生成されたデータ構造をもとに、コードを生成します。ここでは、機械語を出力する場合もあれば、アセンブリ言語を出力してアセンブラに機械語翻訳を任せる場合などもあります。


実際に作ってみる(基本)

それでは、基本的な考え方をもとに簡単に作りはじめてみましょう。まずは「2 + 3」程度の足し算ができるようになりましょう。

なお、この記事ではC言語を用いて最終的にアセンブリ言語を出力し、gccやclangでアセンブリ言語を機械語に変換することにします


字句解析をやってみる


main.c

// ヘッダは省略

// ========= 字句解析で使う ==========
enum {
T_NUM,
T_OPE,
T_EOF,
};

typedef struct Token {
int type; // トークンのタイプ. T_NUM or T_OPE or T_EOF
int value; // 数値をいれる
char *input; // 出力からの文字列をいれる
} Token;

// サンプルなので固定長のトークン列を持っておく
Token *tokens[100];

// 新しくトークンを作って返す
Token *new_token(int type, int value, char *input) {
Token *token = malloc(sizeof(Token));
token->type = type;
token->value = value;
token->input = input;
return token;
}

void scan(char *p) {
int i = 0;
while (*p) {
// 空白なら処理をせず飛ばす
if (isspace(*p)) {
p++;
continue;
}

// コードの中に + があれば
if (strchr("+", *p)) {
printf("# Ope: %c\n", p[0]);
tokens[i++] = new_token(T_OPE, -1, &p[0]);
p++;
continue;
}

// 数字があればいれる
if (isdigit(*p)) {
int value = (int) strtol(p, &p, 10);
printf("# value: %d\n", value);
tokens[i++] = new_token(T_NUM, value, p);
continue;
}
}

tokens[i] = new_token(T_EOF, -1, -1);
}
// ========== 字句解析ここまで ==========

// ========== 構文解析ここから ==========

// ========== 構文解析ここまで ==========

int main(int argc, char **argv) {
// scanを呼ぶだけ
scan(argv[1]);

return 0;
}


数字と + だけを扱うならこれで十分です。他の演算子を増やしたければ、strchr 内の文字列を増やしましょう。これをコンパイルして実行してみると、こうなります。

$ gcc main.c -o main

$ ./main '2+3+3+4+54+31'

# value: 2
# Ope: +
# value: 3
# Ope: +
# value: 3
# Ope: +
# value: 4
# Ope: +
# value: 54
# Ope: +
# value: 31

できていますね。では構文解析に移りましょう。


構文解析をやってみる

さて、一連のトークン列からどのように構文解析を行うのでしょうか。つまりトークン列から計算順序を判断するにはどうしたらいいのでしょうか。

構文木を使いましょう。

0c8c4e85-10e0-477b-ac3e-a673ce68f1cc.png

構文木で、その中に持つ各ノードの関係を表して行きます。「2 + 3」なら、「2と3が + で結びついている」のでこう表せますね。では、「2 + 3 + 5」の場合はどうでしょうか。

41124039-a279-43d7-a2a7-e3659ac6ed39.png

「2 + 3 のノードと5が + で結びついている」と考えることができますね。足し算については、こんな考え方でとりあえずよさそうです。では一旦コードに起こしてみましょう。


main.c

.

.
.
// ========== 字句解析ここまで ==========

// ========== 構文解析ここから ==========
enum {
N_NUM, // 数字を表す
N_OPE, // 演算子を表す
};

typedef struct Node {
int type; // ノードのタイプを表す
int value; // ノード自体が数字を持っていたら格納
struct Node *lhs; // left-hand-side ノードの左側のノード
struct Node *rhs; // right-hand-side ノードの右側のノード
} Node;

// 数字一文字分のノードを作る
Node *new_term_node(int type, int value) {
Node *n = malloc(sizeof(Node));
n->type = type;
n->value = value;

return n;
}

// 2つのノードをもとに新しくノードを作る
Node *new_node(int type, Node *lhs, Node *rhs) {
Node *n = malloc(sizeof(Node));
n->type = type;
n->lhs = lhs;
n->rhs = rhs;
return n;
}

int token_pos = 0;

// 一文字分の処理
Node *term() {
Token *t = tokens[token_pos++];

if (t->type == T_NUM) {
printf("# value: %d\n", t->value);
return new_term_node(N_NUM, t->value);
}

fprintf(stderr, "number literal expected.");
exit(1);
}

Node *gen_node() {
Node *node = term();

for (;;) {
Token *t = tokens[token_pos];

if (t->type == T_EOF) {
return node;
}

token_pos++;
node = new_node(N_OPE, node, term());
node->value = t->input;
}
}
// ========== 構文解析ここまで ==========

// ========== コード生成ここから ==========

// ========== コード生成ここまで ==========

int main(int argc, char **argv) {
// scanを呼ぶだけ
scan(argv[1]);

// Nodeをつくる
Node *node = gen_node();

return 0;
}


実行してみると、

$ ./main '2+3+5'

# value: 2
# Ope: +
# value: 3
# Ope: +
# value: 5
# value: 2
# value: 3
# value: 5

順番に処理されてそうですね。気になる方は Node の中身を自分で確認してみてください。


コード生成をやってみる

ではここからアセンブリのコードを生成していきましょう。アセンブリを使うためには、まず「レジスタ」のことを知りましょう。レジスタとは、CPUが演算の際に使うデータの格納場所です。レジスタにも用途の違うものがあり適切なレジスタに値を入れることが必要となることもあります。

さて、レジスタをつかった計算を見ていきます。この記事ではIntel構文を使用します。例えば

mov rax, 10

なら、「rax レジスタに 10 という値を上書きしていれる」となります

他にも見てみます。例えばこれ

add rax, 10

は何を表しているかといえば「rax レジスタに格納されている値に10を足して rax レジスタに入れる」を表します。結構簡単ですね。これをうまく使ってあげれば、足し算のコード生成なら簡単にできそうです。

構文解析の結果で計算の順序が分かっているので、それをもとに順に計算してあげます。


main.c

.

.
.
// ========== 構文解析ここまで ==========

// ========== コード生成ここから ==========
enum {
IR_NUM,
IR_ADD
};

typedef struct IR {
int type;
int lhs; // left-hand-sideの計算結果がどのレジスタに記録されているか
int rhs; // right-hand-sideの計算結果がどのレジスタに記録されているか
} IR;

// 使おうと思う汎用レジスタ
char *reg[] = {"r8", "r9", "r10", "r11"};
// どのレジスタを使うか
int reg_pos = 0;

// サンプルなので固定長の配列
IR *irs[100];
int ir_pos = 0;

// 新しいIRを作る
IR *new_ir(int type, int lhs, int rhs) {
IR *ir = malloc(sizeof(IR));
ir->type = type;
ir->lhs = lhs;
ir->rhs = rhs;
return ir;
}

// どのレジスタを使うのか決めるための中間表現に置き換える
int gen_ir(Node *node) {
if (node->type == N_NUM) {
int r = reg_pos;
printf("# r: %d, value: %d\n", r, node->value);
IR *ir = new_ir(IR_NUM, reg_pos, node->value);
irs[ir_pos++] = ir;
return r;
}

// 再帰的に呼び出す
int lhs = gen_ir(node->lhs);
reg_pos++;

// 再帰的に呼び出す
int rhs = gen_ir(node->rhs);
reg_pos--;

if (node->type == N_OPE) {
switch (node->value) {
case '+':
irs[ir_pos++] = new_ir(IR_ADD, lhs, rhs);
break;
default:
printf("unknown operator\n");
}
}

return lhs;
}

// コード生成をする
void gen_code() {
int ir_length = ir_pos;
ir_pos = 0;

for (int i = 0; i < ir_length; i++) {
IR *ir = irs[ir_pos++];

switch (ir->type) {
case IR_NUM:
printf(" mov %s, %d\n", reg[ir->lhs], ir->rhs);
break;
case IR_ADD:
printf(" add %s, %s\n", reg[ir->lhs], reg[ir->rhs]);
break;
default:
fprintf(stderr, "unexpected ir type\n");
exit(1);
}
}
}
// ========== コード生成ここまで ==========

int main(int argc, char **argv) {
// scanを呼ぶだけ
scan(argv[1]);

// Nodeをつくる
Node *node = gen_node();

// コード生成
gen_ir(node);
gen_code();

return 0;
}


ここまで書いたら実行してみます。

$ ./main '2+3+5'

# value: 2
# Ope: +
# value: 3
# Ope: +
# value: 5
# value: 2
# value: 3
# value: 5
# r: 0, value: 2
# r: 1, value: 3
# r: 1, value: 5
mov r8, 2
mov r9, 3
add r8, r9
mov r9, 5
add r8, r9

最後の5行を見て、mov 命令と add 命令が使えていることを確認してください。できていそうですね。最後に main() 関数に少し追記します。


main.c

// ========== コード生成ここまで ==========

int main(int argc, char **argv) {
// scanを呼ぶだけ
scan(argv[1]);

// Nodeをつくる
Node *node = gen_node();

int ret_pos = gen_ir(node);

// Macでの書き方です。Linuxの場合 _main の _ を除いてください。
printf(".intel_syntax noprefix\n");
printf(".global _main\n");
printf("_main:\n");

gen_code();

printf(" mov rax, %s\n", reg[ret_pos]);
printf(" ret\n");

return 0;
}


できたコードをコンパイルして、アセンブリに出力、出力されたアセンブリをコンパイルして完成です。

$ gcc main.c -o main           // コンパイル

$ ./main '2+3+5' > output.S // 計算を入力してアセンブリとして出力
$ gcc output.S -o output // アセンブリをコンパイル
$ ./output // 実行
$ echo $? // 実行結果を見る

$ 10 // 実行結果

2+3+5 が計算できているのがわかりますね。他にも試して見ましょう

$ ./main '2+50+13' > output.S

... 略
$ ./output
$ echo $?
$ 65

できていますね。とりあえず簡単な整数足し算コンパイラは完成しました


実際に作ってみる(応用)

足し算ができたのなら、引き算をやってみましょう。字句解析, 構文解析, コード生成 で引き算に必要な処理を追加してあげます。


字句解析に追加する


main.c

.

.
void scan(char *p) {
int i = 0;
while (*p) {
// 空白なら処理をせず飛ばす
if (isspace(*p)) {
p++;
continue;
}

// コードの中に + があれば
if (strchr("+-", *p)) { <===== ここ
printf("# Ope: %c\n", p[0]);
tokens[i++] = new_token(T_OPE, -1, &p[0]);
p++;
continue;
}

// 数字があればいれる
if (isdigit(*p)) {
int value = (int) strtol(p, &p, 10);
printf("# value: %d\n", value);
tokens[i++] = new_token(T_NUM, value, p);
continue;
}
}

tokens[i] = new_token(T_EOF, -1, -1);
}
.
.


strchr 関数に一文字追加するだけですね。


構文解析に追加する

実は構文解析には追加する必要はありません。なぜなら足し算と引き算は互いに入れ替えても意味は変わらないですからね。


コード生成に追加する


main.c

.

.
// ========== コード生成ここから ==========
enum {
IR_NUM,
IR_ADD,
IR_SUB <==== ここ
};
.
.
if (node->type == N_OPE) {
switch (node->value) {
case '+':
irs[ir_pos++] = new_ir(IR_ADD, lhs, rhs);
break;
case '-': <===== このcase
irs[ir_pos++] = new_ir(IR_SUB, lhs, rhs);
break;
default:
printf("unknown operator\n");
}
}
.
.
void gen_code() {
int ir_length = ir_pos;
ir_pos = 0;
printf("# ir length: %d\n", ir_length);

for (int i = 0; i < ir_length; i++) {
IR *ir = irs[ir_pos++];

switch (ir->type) {
case IR_NUM:
printf(" mov %s, %d\n", reg[ir->lhs], ir->rhs);
break;
case IR_ADD:
printf(" add %s, %s\n", reg[ir->lhs], reg[ir->rhs]);
break;
case IR_SUB: <====== このcase
printf(" sub %s, %s\n", reg[ir->lhs], reg[ir->rhs]);
break;
default:
fprintf(stderr, "unexpected ir type\n");
exit(1);
}
}
}


これだけで引き算に対応できますね。


実際に作ってみる(発展)

では、最後に掛け算に対応していきましょう。引き算と同様に掛け算を追加しても大丈夫でしょうか。

たとえば、何も考えず「2 + 3 * 5」を引き算と同じようにノードを作るとこんな感じになりそうです。

b261e86b-a9b3-468e-995b-f34d24838179.png

あれ?これを計算すると、下から順に計算する仕組みなので「2に3を足して、それに5をかける」なので結果は25になりそうです。これでは計算の結果が異なってしまいます。

正しくはこういうノードができていて欲しいですね。

607928bf-b490-450c-93e3-c93e56728a4b.png

ということは、足し算よりも掛け算などの演算のノードを優先的に作らなければならなそうです。

実装してみましょう。


字句解析に追加する


main.c

void scan(char *p) {

int i = 0;
while (*p) {
.
.
// コードの中に + があれば
if (strchr("+-*", *p)) { // <====== * を追加
printf("# Ope: %c\n", p[0]);
tokens[i++] = new_token(T_OPE, -1, p[0]);
p++;
continue;
}
.
.
}

ここだけですね。新しく * もトークンにいれてあげることにしましょう


構文解析に追加する

先程見たように構文解析の順番は少し考慮する必要がありそうです。


main.c

.

.
Node *term() {
Token *t = tokens[token_pos++];

if (t->type == T_NUM) {
printf("# value: %d\n", t->value);
return new_term_node(N_NUM, t->value);
}

fprintf(stderr, "number literal expected.");
exit(1);
}

Node *mul() { // この処理を追加して、先に処理をするように
Node *node = term();

for (;;) {
Token *t = tokens[token_pos];

if (t->type == T_EOF) {
return node;
}

char ope = t->input;
if (ope != '*') {
return node;
}

token_pos++;
node = new_node(N_OPE, node, term());
node->value = t->input;
}
}

Node *gen_node() {
Node *node = mul(); // <=== 変更

for (;;) {
Token *t = tokens[token_pos];

if (t->type == T_EOF) {
return node;
}

token_pos++;
node = new_node(N_OPE, node, mul()); // <=== 変更
node->value = t->input;
}
}



コード生成に追加する


main.c

.

.
int gen_ir(Node *node) {
.
.
if (node->type == N_OPE) {
switch (node->value) {
.
.
case '*': // <======== 追加
irs[ir_pos++] = new_ir(IR_MUL, lhs, rhs);
break;
default:
printf("# unknown operator\n");
}
}

return lhs;
}

void gen_code() {
.
.
switch (ir->type) {
.
.
case IR_MUL: // <====== 追加
printf(" mov rax, %s\n", reg[ir->lhs]);
printf(" mul %s\n", reg[ir->rhs]);
printf(" mov %s, rax\n", reg[ir->lhs]);
break;
default:
fprintf(stderr, "unexpected ir type\n");
exit(1);
}
}
}


計算をしてもらいましょう

$ ./main '2+3*5+2' > output.S


$ echo $?
$ 19

できていそうですね。この記事の目標は達成しました。お疲れ様です。


おわりに

この記事では簡単な整数演算をするコンパイラを作り、コンパイラの仕組み、またコンピュータの動作の仕組みについて見てきました。コンパイラは計算機の知識を使う必要があり難しい分野ですが、とてもおもしろい題材ですね!