はじめに
今回の記事は前回の続きとなってます。前回の記事も見ていただけると、嬉しいです。
前回は関数の実装をしました。関数の実装で、処理をまとめられるようになりました。トイ言語から少しだけ脱却することができたのではないでしょうか。
今回はコンパイラと実行VMのリファクタリングと1次元配列の実装です。簡易的ではありますが、データを配列でまとめることができるようになりました。
処理の流れは前回とは変わりません。
五右衛門プログラム
↓
tokenize関数(トークン化)
↓
parse_program関数(1パスでパースし、Nodeを作成します。)
↓
name_resolution関数(名前解決)
↓
type_check関数(型チェック)
↓
generate(パーサで作成したNode を元にバイトコードを作成します。)
↓
バイトコード
↓
VM実行↓こちらが現在実装中のコンパイラになります。
リファクタリング
今回のリファクタリングは記事にするほどのものではありませんが、将来の自分のためにも、開発記録として残しておきたいと思います。gitで管理はしており、コミットメッセージも分かりやすくしているつもりです。それでも、自分の書いたコードの意図などは忘れるものです。
リファクタリングをする前の構成がこちらになります。
/Kamaディレクトリ
kama_execute.c
kama_compile.c
├── parser
├── resolver
├── type check
├── codegen
└── ...kama_compile.c でスキャナやパース処理があり、可読性や保守性が悪い状態でした。
リファクタリングを行うことで、下記になりました。
Kama/
├── kama_compile.c
├── kama_execute.c
├── scanner.c
├── parser.c
├── resolver.c
├── type_check.c
├── codegen.c
└── ...それぞれの役割ごとに切り出すことにより、エントリポイントである、kama_compile.c がスマートになりました。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>
#include "token.h"
#include "scanner.h"
#include "debug.h"
#include "ast.h"
#include "parser.h"
#include "resolver.h"
#include "opcode.h"
#include "header.h"
#include "codegen.h"
char *read_file(const char *path) {
FILE *fp = fopen(path, "r");
if (!fp) { perror(path); exit(1); }
fseek(fp, 0, SEEK_END);
long size = ftell(fp);
fseek(fp, 0, SEEK_SET);
char *buf = malloc(size + 1);
fread(buf, 1, size, fp);
buf[size] = '\0';
fclose(fp);
return buf;
}
int main(int argc, char **argv) {
int arg = 1;
while (arg < argc && argv[arg][0] == '-') {
if (strcmp(argv[arg], "--ast") == 0) {
g_debug_ast = true;
} else if (strcmp(argv[arg], "--token") == 0) {
g_debug_token = true;
} else if (strcmp(argv[arg], "--binary") == 0) {
g_debug_binary = true;
} else {
printf("Unknown option: %s\n", argv[arg]);
return 1;
}
arg++;
}
if (argc - arg < 2) {
printf("usage: kama-c [options] input.goe output.gb\n");
printf(" --ast Print AST\n");
return 1;
}
char *src = read_file(argv[arg]);
tokenize(src);
Node *program = parse_program();
emit_count_reset();
name_resolution(program);
if (g_debug_ast) {
debug_ast_node(program, 1);
}
type_check_program(program);
emit_count_reset();
generate(program);
emit_no_operand(OP_HALT);
if (g_debug_binary) {
debug_binary();
}
GoemonHeader hed = header();
FILE *dest = fopen(argv[arg + 1], "wb");
fwrite(&hed, sizeof(GoemonHeader), 1, dest);
fwrite(bytecode, sizeof(int), count, dest);
fwrite(string_table, sizeof(String), string_count, dest);
fclose(dest);
printf("絶景かな！ Compiled study.goe to study.gb\n");
return 0;
}基本的にはコンパイラのパイプラインごとに切り出しています。そして、構造体なども個別に分けています。
スキャナとパーサ
五右衛門の配列の文法はこのような形です。配列はint[5] numbers;のように、型の後ろに要素数を指定する構文にしました。ひとまずは、1次元の配列の宣言から代入・参照までを五右衛門に追加します。また、配列の宣言時のサイズ は数値かつ、静的な値でしか宣言できません。
int[5] numbers;
bool[5] flags;
str[5] texts;
for (int i = 0; i < 5; i++) {
numbers[i] = i + 1;
flags[i] = false;
texts[i] = "hello world";
}
for (int i = 0; i < 5; i++) {
print numbers[i];
print flags[i];
print texts[i];
}配列の実装に入りたいと思います。今回は1次元の配列を実装していきます。実装もコンパイラのパイプライン通りに進めていきます。まずはスキャナからです。3つトークンを追加しました。[ と ]、そして配列宣言を表すTK_ARRAYの3つのトークンを追加しました。
typedef enum {
...省略
TK_LBRACKET,
TK_RBRACKET,
TK_ARRAY,
} TokenKind;
void tokenize (char *p) {
int i = 0;
while(*p) {
...省略
if (strncmp(p, "int", 3) == 0 && (isspace(p[3]) || p[3] == '\0' || p[3] == '[')) {
p += 3;
int len = 0;
tokens[i].line = line;
while (isspace(*p)) {
p++;
}
if (*p == '[') {
p++;
if (isdigit(*p)) {
tokens[i].length = strtol(p, &p, 10);
}
if (*p == ']') p++;
tokens[i].type = TY_INT;
tokens[i++].kind = TK_ARRAY;
} else {
tokens[i++].kind = TK_INT;
}
while (isspace(*p)) {
p++;
}
while (isalnum(*p) || *p == '_') {
tokens[i].str[len++] = *p++;
}
tokens[i].str[len] = '\0';
tokens[i].line = line;
tokens[i++].kind = TK_IDENT;
continue;
}
if (strncmp(p, "str", 3) == 0 && (isspace(p[3]) || p[3] == '\0' || p[3] == '[')) {
p += 3;
int len = 0;
tokens[i].line = line;
while (isspace(*p)) {
p++;
}
if (*p == '[') {
p++;
if (isdigit(*p)) {
tokens[i].length = strtol(p, &p, 10);
}
if (*p == ']') p++;
tokens[i].type = TY_STRING;
tokens[i++].kind = TK_ARRAY;
} else {
tokens[i++].kind = TK_STRING_TYPE;
}
while (isspace(*p)) {
p++;
}
while (isalnum(*p) || *p == '_') {
tokens[i].str[len++] = *p++;
}
tokens[i].str[len] = '\0';
tokens[i].line = line;
tokens[i++].kind = TK_IDENT;
continue;
}
if (strncmp(p, "bool", 4) == 0 && (isspace(p[4]) || p[4] == '\0' || p[4] == '[')) {
p += 4;
int len = 0;
tokens[i].line = line;
while (isspace(*p)) {
p++;
}
if (*p == '[') {
p++;
if (isdigit(*p)) {
tokens[i].length = strtol(p, &p, 10);
}
if (*p == ']') p++;
tokens[i].type = TY_BOOL;
tokens[i++].kind = TK_ARRAY;
} else {
tokens[i++].kind = TK_BOOL_TYPE;
}
while (isspace(*p)) {
p++;
}
while (isalnum(*p) || *p == '_') {
tokens[i].str[len++] = *p++;
}
tokens[i].str[len] = '\0';
tokens[i].line = line;
tokens[i++].kind = TK_IDENT;
continue;
}
...省略
if (*p == '[') {
tokens[i].line = line;
tokens[i++].kind = TK_LBRACKET;
p++;
continue;
}
if (*p == ']') {
tokens[i].line = line;
tokens[i++].kind = TK_RBRACKET;
p++;
continue;
}
...省略
printf("Line %d: Unknown character '%c'\n", line, *p);
exit(1);
}
tokens[i].kind = TK_EOF;
tokens[i].line = line;
if (g_debug_token) debug_token(i);
}スキャナの実装もいずれリファクタリングするつもりなので、ひとまずはこれでご容赦ください。
続いて、パース処理です。ast.c にヘルパー関数を追加します。そして、ast.h にヘルパー関数を外部から呼び出せるように定義を追加し、配列のNodeKindを追加します。配列は宣言時にサイズを指定するため、Node構造体のlen を利用します。len は文字列で使っていましたが、配列でも使います。
//ast.c
Node* new_array_decl_node(NodeKind kind, Node* node1, int *len, TypeKind type) {
int current_idx = node_depth;
node_depth++;
node_tree[current_idx].kind = kind;
node_tree[current_idx].lhs = node1;
node_tree[current_idx].len = *len;
node_tree[current_idx].type = type;
return &node_tree[current_idx];
}
Node* new_array_node(NodeKind kind, Node* node1, char *str) {
int current_idx = node_depth;
node_depth++;
node_tree[current_idx].rhs = node1;
node_tree[current_idx].kind = kind;
strcpy(node_tree[current_idx].name, str);
return &node_tree[current_idx];
}//ast.h
#ifndef AST_H
#define AST_H
#include <stdbool.h>
#include "type.h"
typedef enum {
...省略
ND_ARRAY_DECL,
ND_ARRAY,
ND_ASSIGN_ARRAY,
ND_ARRAY_STORE,
} NodeKind;
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 index;
int val;
bool bool_val;
char str[128];
int len;
char name[32];
char func_name[64];
TypeKind type;
int address;
int depth;
bool is_global;
} Node;
...省略
Node* new_array_decl_node(NodeKind kind, Node* node1, int *len, TypeKind type);
Node* new_array_node(NodeKind kind, Node* node1, char *str);
...省略
#endif//parse.c
static Node* parse_primary() {
...省略
if (t->kind == TK_NUMBER) {
node = new_num_node(&t->val);
} else if (t->kind == TK_IDENT) {
if (tokens[pos].kind == TK_LPAREN) {
next_token();
Node *arg_head = parse_argument_list(TK_RPAREN);
if (tokens[pos].kind == TK_RPAREN) next_token();
node = new_call_node(ND_CALL, t->str, arg_head);
} else if (tokens[pos].kind == TK_INC) {
next_token();
Node *var = new_var_node(t->str);
node = new_unary_node(ND_INC, var);
} else if (tokens[pos].kind == TK_LBRACKET) {
next_token();
Node *index = parse_evaluation();
expect(TK_RBRACKET);
node = new_array_node(ND_ARRAY, index, t->str);
} else {
node = new_var_node(t->str);
}
} else if (t->kind == TK_STRING) {
node = new_str_node(t->str, &t->length);
} else if (t->kind == TK_BOOL) {
node = new_bool_node(t->bool_val);
}
return node;
}
static Node* parse_statement() {
Token *t = next_token();
switch(t->kind) {
...省略
case TK_ARRAY: {
Token *ident = expect_ident();
// Node *lhs = new_array_node(ND_ARRAY, ident->str, index);
Node *lhs = new_var_node(ident->str);
if (t->length <= 0) {
fprintf(stderr,
"[Line: %d]Array size must be greater than 0\n", t->line);
exit(1);
}
return new_array_decl_node(ND_ARRAY_DECL, lhs, &t->length, t->type);
}
...省略
case TK_IDENT: {
consume(TK_COLON);
if (consume(TK_ASSIGN)) {
Node *lhs = new_var_node(t->str);
Node *rhs = parse_evaluation();
expect(TK_SEMI);
return new_binary_node(ND_ASSIGN, lhs, rhs);
} else if (consume(TK_LBRACKET)) {
Node *index = parse_evaluation();
expect(TK_RBRACKET);
expect(TK_ASSIGN);
Node *lhs = new_array_node(ND_ARRAY_STORE, index, t->str);
Node *rhs = parse_evaluation();
// Node *
return new_binary_node(ND_ASSIGN_ARRAY, lhs, rhs);
} else {
prev_token();
return parse_evaluation();
}
}
...省略
default:
return NULL;
}
}追加したNodeKindのそれぞれの役割については、generate関数の実装時に説明します。現時点でのASTはこのようになります。
int[5] numbers;
numbers[0] = 8;
print numbers[0]; [ARRAY_DECL](INT) len=5
[VAR](numbers)(address=0)(depth=0)
[ASSIGN_ARRAY]
[ARRAY_STORE](numbers)(address=0)(depth=0)
[NUM] val=0
[NUM] val=8
[PRINT]
[ARRAY](numbers)(address=0)(depth=0)
[NUM] val=0名前解決と型チェック
名前解決ですが、変数宣言時などと基本的にはやっていることは同じです。変数名の登録や検索です。
void name_resolution(Node *node) {
if (node == NULL) return;
while (node) {
switch (node->kind) {
...省略
case ND_ARRAY_DECL: {
if (node->rhs != NULL) {
name_resolution(node->rhs);
}
resolution_variable(node->lhs, true, &node->type);
emit_count_two_up();
if (node->lhs->is_global) {
emit_count_two_up();
} else {
emit_count_three();
}
break;
}
case ND_ASSIGN_ARRAY: {
name_resolution(node->rhs);
name_resolution(node->lhs);
emit_count_two_up();
break;
}
case ND_ARRAY: {
name_resolution(node->rhs);
resolution_variable(node, false, NULL);
if (node->is_global) {
emit_count_two_up();
} else {
emit_count_three();
}
emit_count_up();
break;
}
case ND_ARRAY_STORE: {
resolution_variable(node, false, &node->type);
name_resolution(node->rhs);
break;
}
default:
printf("Unknown node: %d\n", node->kind);
exit(1);
}
node = node->next;
}
}次は型チェックですが、ここも特別なことはしていません。
static TypeKind type_check(Node* node) {
if (node == NULL) return TY_VOID;
switch (node->kind) {
...省略
case ND_ARRAY_DECL: {
return node->type;
}
case ND_ASSIGN_ARRAY: {
TypeKind lhs = type_check(node->lhs);
TypeKind rhs = type_check(node->rhs);
if (lhs != rhs) {
fprintf(stderr,
"Expected: %s\n", type_name(lhs));
exit(1);
}
return TY_VOID;
}
case ND_ARRAY_STORE: {
if (type_check(node->rhs) != TY_INT) {
fprintf(stderr,
"Expecte: INT\n");
exit(1);
}
return node->type;
}
case ND_ARRAY: {
return node->type;
}
default:
// TODO: implement type check
return TY_VOID;
}
}ND_ARRAY_DECL(配列の宣言)はnode->typeをreturnするだけです。numbers[0] = 5; のように代入時に代入する値の型と変数の型が同じかチェックをします。名前解決と型チェック後のASTはこのようになります。
int[5] numbers;
numbers[0] = 8;
print numbers[0]; [ARRAY_DECL](INT) len=5
[VAR](INT)(numbers)(address=1)
[ASSIGN_ARRAY]
[ARRAY_STORE](INT)(numbers)(address=1)
[NUM] val=0
[NUM] val=8
[PRINT]
[ARRAY](INT)(numbers)(address=1)
[NUM] val=0generate関数とVM
generate関数の前にopcodeの追加をします。
typedef enum {
...省略
OP_MAKE_ARRAY,
OP_ARRAY_STORE,
OP_ARRAY_STORE_LOCAL,
OP_ARRAY_LOAD,
} OpCode;次にgenerate関数です。今回追加したNodeKindのcaseを追加しています。
void generate(Node *node) {
if (node == NULL) return;
while (node) {
switch (node->kind) {
...省略
case ND_ARRAY_DECL: {
emit_two_operand_type(OP_MAKE_ARRAY, &node->len, node->type);
if (node->lhs->is_global) {
emit_one_operand(OP_STORE, &node->lhs->address);
} else {
emit_two_operand(OP_STORE_LOCAL, &node->lhs->address, &node->lhs->depth);
}
break;
}
case ND_ARRAY: {
generate(node->rhs);
if (node->is_global) {
emit_one_operand(OP_LOAD, &node->address);
} else {
emit_two_operand(OP_LOAD_LOCAL, &node->address, &node->depth);
}
emit_no_operand(OP_ARRAY_LOAD);
break;
}
case ND_ASSIGN_ARRAY: {
generate(node->rhs);
generate(node->lhs);
if (node->lhs->is_global) {
emit_one_operand(OP_ARRAY_STORE, &node->lhs->address);
} else {
emit_two_operand(OP_ARRAY_STORE_LOCAL, &node->lhs->address, &node->lhs->depth);
}
break;
}
case ND_ARRAY_STORE: {
generate(node->rhs);
break;
}
default:
printf("Unknown node: %d\n", node->kind);
exit(1);
}
node = node->next;
}
}今回追加したNodeKindの役割を説明します。
ND_ARRAY_DECL
→配列の宣言時のノードになります。
int[5] numbers;
ND_ASSIGN_ARRAY
→配列の要素に代入時のノードになります。
numbers[0] = 8;
ND_ARRAY_STORE
→代入時のND_ASSIGN_ARRAYの子ノードになります。
元々はND_ARRAYだけで、実装していましたが、generate関数内で、参照か代入の制御が煩雑になってしまうため、NodeKindを分けました。
ND_ARRAY
→配列の要素を参照時のノードになります。続いてVM側の実装になります。まずは、配列の作成やメモリ解放などを行うヘルパー関数の実装です。
#include "array.h"
#include <stdlib.h>
#include <stdio.h>
int array_count = 0;
int array_capacity = 128;
Array *array_table;
void init_array_table(void) {
array_table = malloc(sizeof(Array) * 128);
}
static void make_bigger(void) {
int new_capacity = array_capacity * 2;
Array *new_array_table = realloc(array_table, sizeof(Array) * new_capacity);
if (new_array_table == NULL) {
fprintf(stderr,
"Runtime Error: Failed to resize array table\n");
exit(1);
}
array_capacity = new_capacity;
array_table = new_array_table;
}
int make_array(int size, TypeKind type) {
int *array;
if (array_count == array_capacity) {
make_bigger();
}
int index = array_count;
array = malloc(sizeof(int) * size);
array_table[index].length = size;
array_table[index].type = type;
array_table[index].elements = array;
array_count++;
return index;
}
void store_array(int array_index, int index, int value) {
array_table[array_index].elements[index] = value;
}
int load_array(int array_index, int index) {
return array_table[array_index].elements[index];
}
void free_all_arrays(void) {
for (int i = 0; i < array_count; i++) {
free(array_table[i].elements);
array_table[i].elements = NULL;
}
free(array_table);
array_table = NULL;
array_count = 0;
}init_array_tableでarray_tableを初期化します。初期化のサイズは128 です。その後、配列が宣言されるたびに、array_countがインクリメントされ、capacity の値と同じになると、array_tableのサイズをmake_bigger関数でサイズを倍にします。ここの動的配列の実装については次の記事の動的配列へのリファクタリングで解説します。kama_execute.cでArray構造体を使えるようにarray.hファイルに定義しておきます。ここで重要なのが Array構造体のelementsです。配列の要素をヒープ領域に確保し、そのアドレスをelementsで保持します。
numbers
↓
変数テーブル
↓
array_table[0]
├── length = 5
├── type = INT
└── elements ─────→ [0][0][0][0][0]#ifndef ARRAY_H
#define ARRAY_H
#include "type.h"
#include <stdbool.h>
typedef struct {
int length;
TypeKind type;
int *elements;
} Array;
void init_array_table(void);
int make_array(int size, TypeKind type);
void store_array(int heap_index, int index, int value);
int load_array(int heap_index, int index);
void free_all_arrays(void);
#endif
void run(int* program) {
int stack[1024];
int call_stack[128];
int memory[2048];
static int frames[128][128][128];
int sp = -1;
int call_sp = -1;
int pc = 0;
int call_frame = 0;
for(int i = 0; i < 2048; i++) memory[i] = 0;
while (true) {
int instruction = program[pc++];
switch (instruction) {
...省略
case OP_MAKE_ARRAY: {
int len = program[pc++];
int type = program[pc++];
int addr = make_array(len, type);
stack[++sp] = addr;
break;
}
case OP_ARRAY_STORE: {
int var_addr = program[pc++];
int array_index = memory[var_addr];
int index = stack[sp--];
int value = stack[sp--];
store_array(array_index, index, value);
break;
}
case OP_ARRAY_STORE_LOCAL: {
int address = program[pc++];
int depth = program[pc++];
int array_index = frames[call_frame][depth][address];
int index = stack[sp--];
int value = stack[sp--];
store_array(array_index, index, value);
break;
}
case OP_ARRAY_LOAD: {
int array_index = stack[sp--];
int index = stack[sp--];
int value = load_array(array_index, index);
stack[++sp] = value;
break;
}
case OP_HALT:
return;
}
}
}OP_MAKE_ARRAY時に配列を作成します。make_arrayが返したarray_tableのindexをスタックにpushします。generate関数で、OP_MAKE_ARRAYの後にOP_STOREを追加しているため、変数として使えるようになります。
ND_ARRAY_DECL時に
OP_MAKE_ARRAYと配列のサイズをバイトコード化
↓
変数がグローバルかローカルによって
OP_STOREとアドレスをバイトコード化
OP_STORE_LOCALと深さとアドレスをバイトコード化配列宣言時にarray_tableのindex を変数テーブルにSTOREしているので、OP_ARRAY_STORE、OP_ARRAY_STORE_LOCALはarray_tableのindex を参照できます。そして、OP_ARRAY_STOREよりも前に代入する値と代入先のindexをpushしているので、スタックからそれぞれをpopします。そして、store_array関数で代入します。
[ASSIGN_ARRAY]
[ARRAY_STORE](INT)(numbers)(address=1)
[NUM] val=0
[NUM] val=8
ND_ASSIGN_ARRAY時に
node->rhsから先にgenerateし、代入する値を先にバイトコード化します。
その後にnode->lhsをバイトコード化します。
↓
変数がグローバルかローカルによって
OP_ARRAY_STOREとアドレスをバイトコード化
OP_ARRAY_STORE_LOCALと深さとアドレスをバイトコード化[ASSIGN_ARRAY]
[ARRAY_STORE]
[NUM] 0
[NUM] 8
↓ generate
stackには代入する値と配列のindexがあります
8 ← 代入する値
0 ← 配列のindex
↓ OP_LOAD / OP_ARRAY_STORE
array_index
index
value配列の要素を参照時は下記のようになります。
ND_ARRAY時に
node->rhsで参照する配列のindexがpush
↓
変数がグローバルかローカルによって
OP_LOADとアドレスをバイトコード化
OP_LOAD_LOCALと深さとアドレスをバイトコード化最初に参照する配列のindexがスタックにpushされ、その後にOP_LOAD命令によって、array_tableのindexがpushされます。スタックの2つの値をpopし、load_array関数に渡します。そして、戻り値をスタックにpushします。
Array構造体のelementsはint型のポインタですが、五右衛門のstr型とbool型をどのように保持しているかというと、str型は値自体はstring_tableで保持しています。そのindex をarray_tableで管理します。そして、bool型はコンパイル時にtrueなら1に、falseなら0にします。現在の五右衛門の仕様では、int型、str型、bool型しかないため、elementsをint型で設計しました。五右衛門の規模がさらに大きくなった際にdouble型やその他の型を追加時にリファクタリングします。
最後に実際に五右衛門プログラムを動作させてみます。
int[5] numbers;
str[5] texts;
bool[5] flags;
numbers[0] = 8;
texts[0] = "Hello World!";
flags[0] = false;
print numbers[0];
print texts[0];
print flags[0];VM Output: 8
VM Output: Hello World!
VM Output: false最後に
1次元配列までしかサポートしていませんが、五右衛門で配列を使うことができるようになりました。しかし、使えるようになったはものの、今回は動作することを優先した実装になっており、今後リファクタリングする予定の箇所もあります。今回はarray_tableを固定容量128から開始し、容量を超えた場合にはreallocで2倍に拡張する実装にしています。この部分はまだ改善の余地があるため、次回はC言語での動的配列の実装を掘り下げ、五右衛門のコンパイラやVMで使っている配列管理をリファクタリングしたいと思います。最後まで見ていただきありがとうございました。
コメント