はじめに
今回の記事は前回の続きとなってます。前回の記事も見ていただけると、嬉しいです。
今回はさらにfor文を追加するとともに、AST（抽象構文木）を導入してコンパイラ内部の設計を改善します。また、自動テストも導入し、今後の機能追加を安全に進められるようにします。
↓こちらが現在作成中の自作言語になります。
AST化
AST化よりも先にfor文を実装したのですが、今のコンパイラはAST を前提としたコードになっているため、先にAST化についてお話しします。
そもそも、AST とはなんでしょうか？
AST（抽象構文木: Abstract Syntax Tree）は、ソースコードの文法構造を木（ツリー）で表現したデータ構造です。プログラムは「式の中に式がある」「if文の中に文がある」といった階層構造を持つため、木構造で表現すると扱いやすくなります。また、一度パースした結果を保持しておけるため、コード生成や最適化などの後続処理でも再利用できます。AST を実装することにより、責務の分離をします。つまり、パーサは「解析するだけ」、コード生成器は「バイトコードを生成するだけ」という役割になります。
前回までの処理の流れがこちらになります。
五右衛門プログラム
↓
tokenize関数(トークン化)
↓
parse_program関数(2パスでパース処理)
↓
バイトコード生成
↓
VM実行ASTの実装やリファクタリングで、このようになりました。
五右衛門プログラム
↓
tokenize関数(トークン化)
↓
parse_program関数(1パスでパースし、Nodeを作成します。)
↓
generate(パーサで作成したNode を元にバイトコードを作成します。)
↓
バイトコード
↓
VM実行前回までのコンパイラはパーサが直接バイトコードを生成していました。言語の規模が小さいうちはこれでも問題ありませんが、今後は関数などさらに複雑な機能を実装していく予定です。その前に設計を見直し、ASTを導入しました。
//パース処理でそれぞれ、バイトコード生成していましたが、Node構造体を返すようにしました。
typedef struct Node {
NodeKind kind;
struct Node *lhs;
struct Node *rhs;
struct Node *condition;
struct Node *body;
struct Node *else_stmt;
struct Node *init;
struct Node *update;
struct Node *params;
struct Node *next;
int val;
char name[32];
char func_name[64];
} Node;
int node_depth = 0;
Node* parse_evaluation();
Node* parse_expression();
Node* parse_if();
Node* parse_while();
Node* parse_for();
Node* parse_statement() {
Token *t = next_token();
switch(t->kind) {
...省略
case TK_NUMBER: {
return new_num_node(&t->val);
}
case TK_IF: {
return parse_if();
}
case TK_WHILE: {
return parse_while();
}
case TK_BREAK: {
return new_simple_node(ND_BREAK);
}
case TK_CONTINUE: {
return new_simple_node(ND_CONTINUE);
}
case TK_FOR: {
return parse_for();
}
case TK_FUNCTION: {
return parse_function();
}
default:
return NULL;
}
}
Node* parse_program () {
pos = 0;
Node *head = NULL;
Node *tail = NULL;
while (tokens[pos].kind != TK_EOF) {
Node *stmt = parse_statement();
if (!stmt) continue;
if (!head) {
head = stmt;
tail = stmt;
} else {
tail->next = stmt;
tail = stmt;
}
}
return head;
}始まりは parse_program です。main関数から呼ばれます。そして、トークンを上から読み込んでいき、パースをし、Nodeを返します。そして、連結リストでNode を繋げていき、最終的には先頭のNode(ルートノード)を返します。
五右衛門プログラムが下記のとき、木構造はこのようになります。
a = 0;
b = 1;
i = 0;
while (i < 10) {
print a;
temp = a + b;
a = b;
b = temp;
i++;
}木構造
[ASSIGN]
[VAR](a)
[NUM] val=0
[ASSIGN]
[VAR](b)
[NUM] val=1
[ASSIGN]
[VAR](i)
[NUM] val=0
[WHILE]
[CONDITION]
[LT]
[VAR](i)
[NUM] val=10
[BODY]
[PRINT]
[VAR](a)
[ASSIGN]
[VAR](temp)
[ADD]
[VAR](a)
[VAR](b)
[ASSIGN]
[VAR](a)
[VAR](b)
[ASSIGN]
[VAR](b)
[VAR](temp)
[INC]
[VAR](i)
この木構造を用いて、バイトコードを生成します。
void generate(Node *node) {
if (node == NULL) return;
while (node) {
switch (node->kind) {
case ND_NUM: {
emit_op(OP_PUSH, &node->val);
break;
}
case ND_ASSIGN: {
generate(node->rhs);
int addr = find_variable(node->lhs->name);
emit_op(OP_STORE, &addr);
break;
}
case ND_VAR: {
int addr = find_variable(node->name);
emit_op(OP_LOAD, &addr);
break;
}
case ND_PRINT: {
generate(node->lhs);
emit_op(OP_PRINT, NULL);
break;
}
case ND_ADD: {
generate_binary(node, OP_ADD);
break;
}
case ND_MINUS: {
generate_binary(node, OP_SUB);
break;
}
..省略
case ND_IF: {
generate(node->condition);
int my_jz_idx = count;
int zero = 0;
emit_op(OP_JZ, &zero);
generate(node->body);
if (node->else_stmt) {
int my_jmp_idx = count;
emit_op(OP_JMP, &zero);
bytecode[my_jz_idx + 1] = count;
generate(node->else_stmt);
bytecode[my_jmp_idx + 1] = count;
} else {
bytecode[my_jz_idx + 1] = count;
}
break;
}
default:
printf("Unknown node: %d\n", node->kind);
exit(1);
}
node = node->next;
}
}パースで行っていた、バックパッチの処理などもgenerate関数内で行っています。generate関数は、Parserが作成したNodeを深さ優先で再帰的にたどりながら、対応するバイトコードを生成します。コード量が多いため、全文は載せません。詳細について知りたい方はリポジトリを参照してください。
for文
for文の考え方はwhile と基本的には同じです。ASTを導入したことで、for文も他の制御構文と同様にNodeとして表現できるようになりました。コード生成時にはwhile文とほぼ同じ考え方で実装できます。
case ND_FOR: {
loop_depth++;
loop_stack[loop_depth].break_count = 0;
generate(node->init);
int cond_start_idx = count;
generate(node->condition);
int my_jz_idx = count;
int zero = 0;
emit_op(OP_JZ, &zero);
int jump_to_body_idx = count;
emit_op(OP_JMP, &zero);
int update_start_idx = count;
loop_stack[loop_depth].continue_target = update_start_idx;
generate(node->update);
emit_op(OP_JMP, &cond_start_idx);
bytecode[jump_to_body_idx + 1] = count;
generate(node->body);
emit_op(OP_JMP, &update_start_idx);
bytecode[my_jz_idx + 1] = count;
for (int i = 0; i < loop_stack[loop_depth].break_count; i++) {
int break_jz_idx = loop_stack[loop_depth].breaks[i];
bytecode[break_jz_idx + 1] = count;
}
loop_depth--;
break;
}while文と違うところはfor文には初期化があることです。方針としては下記になります。
初期化(i = 0;)
↓
判定(i < 10;)
↓
偽(0)なら、ブロックを飛び越す
↓
更新文を飛び越して、ブロックの中の処理に進む
↓
ブロックの中の処理が終われば、更新文(i++)を実行
↓
判定文に飛ばすwhile文は「条件判定→本体→条件判定」という単純な流れですが、for文は更新式を実行する必要があるため、一度更新式を飛び越えて本体へ移動し、その後更新式へ戻るジャンプが必要になります。そのため、while文よりJMP命令が多くなります。
自動テスト
自動テストを実装するメリットしては、実装箇所だけでなく、既存機能が壊れていないことを確認できるようになります。大規模なリファクタリングをする場合、影響範囲が大きいため、都度手動でテストをする必要があります。規模が大きくなればなるほど、コストが大きくなります。そのため、五右衛門にも簡単ではありますが、自動テストを導入しました。
makefileにmake test でテストを実行できるように定義します。
CC = gcc
CFLAGS = -Wall -Wextra -O2
TARGET_EXEC = kama-e
TARGET_COMP = kama-c
all: ${TARGET_EXEC} ${TARGET_COMP}
$(TARGET_EXEC): Kama/kama_execute.c
$(CC) $(CFLAGS) -o $(TARGET_EXEC) Kama/kama_execute.c
$(TARGET_COMP): Kama/kama_compile.c
$(CC) $(CFLAGS) -o $(TARGET_COMP) Kama/kama_compile.c
run: all
./$(TARGET_COMP) --ast --token --binary examples/study.goe examples/study.gb
./$(TARGET_EXEC) examples/study.gb
clean:
rm -f $(TARGET_EXEC) $(TARGET_COMP) examples/*.gb
test: all
./tests/run_tests.shテスト本体はシェルスクリプトに書いていきます。
#!/bin/bash
set -e
GREEN='\033[32m'
RED='\033[31m'
NC='\033[0m'
echo "=== Runtime Tests ==="
for testfile in tests/exec/*.goe
do
name=$(basename "$testfile" .goe)
expected="tests/exec/${name}.expected"
bytecode="tests/exec/${name}.gb"
echo "Testing $name"
./kama-c "$testfile" "$bytecode" > /dev/null
./kama-e "$bytecode" > actual.txt
if diff actual.txt "$expected" > /dev/null; then
echo -e "${GREEN}✓ [PASS]${NC} $name"
else
echo -e "${RED}✗ [FAIL]${NC} $name"
exit 1
fi
done
echo
echo "=== AST Tests ==="
for testfile in tests/ast/*.goe
do
name=$(basename "$testfile" .goe)
expected="tests/ast/${name}.expected"
bytecode="tests/ast/${name}.gb"
echo "Testing AST $name"
./kama-c --ast "$testfile" "$bytecode" > actual.txt
if diff actual.txt "$expected" > /dev/null; then
echo -e "${GREEN}✓ [PASS]${NC} $name"
else
echo -e "${RED}✗ [FAIL]${NC} $name"
exit 1
fi
done
rm -f actual.txt実行内容としては、tests/exec/ ディレクトリとtests/ast/ ディレクトリ内の.goeファイルを実行して、コンソールに表示された結果と.expected が一致するかを確認します。
最後に
今回ASTを導入したことで、パーサとコード生成を分離でき、今後の機能追加やリファクタリングがしやすい構成になりました。実際、今回実装したfor文もASTを前提としたことで整理された形で実装できています。
最後まで見ていただきありがとうございました。次回は関数の実装や、returnの実装についての記事になるかと思います。
コメント