はじめに
今回の記事は前回の続きとなってます。前回の記事も見ていただけると、嬉しいです。
前回は、Parserのリファクタリングと名前解決の実装をしました。これにより、generate関数 の役割がbytecodeを生成するだけになり、コードの見通しがよくなりました。今回は新たに型システムと型チェックの実装をします。また、五右衛門の言語仕様は静的型付けになります。
静的型付けと動的型付けはどちらもメリット・デメリットあるかと思いますが、それぞれの仕様についてはここでは解説しません。
処理の流れは下記になります。
五右衛門プログラム
↓
tokenize関数(トークン化)
↓
parse_program関数(1パスでパースし、Nodeを作成します。)
↓
name_resolution関数(名前解決)
↓
type_check関数(型チェック)
↓
generate(パーサで作成したNode を元にバイトコードを作成します。)
↓
バイトコード
↓
VM実行↓こちらが現在実装中のコンパイラになります。
型システム
今回五右衛門に実装する型はINT型、STRING型、BOOL型、VOID型です。(VOIDは「値を持たないこと」を表す型) NodeでもTypeKindを持てるようにします。
typedef enum {
TY_VOID,
TY_INT,
TY_STRING,
TY_BOOL,
} TypeKind;
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;
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;まずは、スキャナでint などを読み取り、トークンに分解できるようにします。
Token tokens[MAX_TOKENS];
int line = 1;
void tokenize (char *p) {
int i = 0;
while(*p) {
if (*p == '\n') {
p++;
line++;
continue;
}
if (isspace(*p)) { p++; continue;}
...省略
if (strncmp(p, "int", 3) == 0 && (isspace(p[3]) || p[3] == '\0')) {
p += 3;
int len = 0;
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++].kind = TK_IDENT;
continue;
}
if (strncmp(p, "str", 3) == 0 && (isspace(p[3]) || p[3] == '\0')) {
p += 3;
int len = 0;
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++].kind = TK_IDENT;
continue;
}
if (strncmp(p, "bool", 4) == 0 && (isspace(p[4]) || p[4] == '\0')) {
p += 4;
int len = 0;
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++].kind = TK_IDENT;
continue;
}
if (strncmp(p, "true", 4) == 0 && (isspace(p[4]) || p[4] == '\0' || p[4] == ';' || p[4] == ')')) {
tokens[i].kind = TK_BOOL;
tokens[i].bool_val = true;
i++;
p += 4;
continue;
}
if (strncmp(p, "false", 5) == 0 && (isspace(p[5]) || p[5] == '\0' || p[5] == ';' || p[5] == ')')) {
tokens[i].kind = TK_BOOL;
tokens[i].bool_val = false;
i++;
p += 5;
continue;
}
...省略
printf("Line %d: Unknown character '%c'\n", line, *p);
exit(1);
}
tokens[i].kind = TK_EOF;
if (g_debug_token) debug_token(i);
}
ここで生成されるトークンが下記のようになります。
===== TOKEN DUMP =====
[000] TK_INT
[001] TK_IDENT text="num"
[002] TK_ASSIGN
[003] TK_NUMBER value=50
[004] TK_SEMI
[005] TK_STRING_TYPE
[006] TK_IDENT text="text"
[007] TK_ASSIGN
[008] TK_STRING text="Hello World!"
[009] TK_SEMI
[010] TK_PRINT
[011] TK_IDENT text="num"
[012] TK_SEMI
[013] TK_PRINT
[014] TK_IDENT text="text"
[015] TK_SEMI
[016] TK_EOF
======================生成されたトークンからASTを生成できるように追加します。
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 {
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;
}
Node* parse_statement() {
Token *t = next_token();
switch(t->kind) {
...省略
case TK_INT: {
Token *ident = expect_ident();
Node *lhs = new_var_node(ident->str);
if (consume(TK_ASSIGN)) {
Node *rhs = parse_evaluation();
expect(TK_SEMI);
return new_decl_node(ND_VAR_DECL, lhs, rhs, TY_INT);
} else {
return new_decl_no_assignment_node(ND_VAR_DECL, lhs, TY_INT);
}
}
case TK_STRING_TYPE: {
Token *ident = expect_ident();
Node *lhs = new_var_node(ident->str);
if (consume(TK_ASSIGN)) {
Node *rhs = parse_evaluation();
expect(TK_SEMI);
return new_decl_node(ND_VAR_DECL, lhs, rhs, TY_STRING);
} else {
return new_decl_no_assignment_node(ND_VAR_DECL, lhs, TY_STRING);
}
}
case TK_BOOL_TYPE: {
Token *ident = expect_ident();
Node *lhs = new_var_node(ident->str);
if (consume(TK_ASSIGN)) {
Node *rhs = parse_evaluation();
expect(TK_SEMI);
return new_decl_node(ND_VAR_DECL, lhs, rhs, TY_BOOL);
} else {
return new_decl_no_assignment_node(ND_VAR_DECL, lhs, TY_BOOL);
}
}
...省略
default:
return NULL;
}
}それぞれの分岐の最後にNodeを作りますが、Nodeに型を付与するために、ヘルパー関数にはTypeKind を渡します。
Node* new_decl_no_assignment_node(NodeKind kind, Node* node1, 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].type = type;
return &node_tree[current_idx];
}
Node* new_decl_node(NodeKind kind, Node* node1, Node* node2, 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].rhs = node2;
node_tree[current_idx].type = type;
return &node_tree[current_idx];
}
Node* new_bool_node (bool val) {
int current_idx = node_depth;
node_depth++;
node_tree[current_idx].kind = ND_BOOL;
node_tree[current_idx].bool_val = val;
node_tree[current_idx].lhs = NULL;
node_tree[current_idx].rhs = NULL;
node_tree[current_idx].val = val ? 1 : 0;
return &node_tree[current_idx];
}
Node* new_str_node (char *str, int *len) {
int current_idx = node_depth;
node_depth++;
node_tree[current_idx].kind = ND_STR;
strcpy(node_tree[current_idx].str, str);
node_tree[current_idx].len = *len;
node_tree[current_idx].lhs = NULL;
node_tree[current_idx].rhs = NULL;
return &node_tree[current_idx];
}パーサで作ったNodeは名前解決や型チェックやgenerate関数でも使うので、ここで付与をします。付与された型を名前解決時に子ノードに伝播していきます。
実際に生成されたAST(Node)がこちらになります。DECLノードに付与されたTypeを、子ノードであるVARにも付与します。これにより、型チェック時にADDなどの演算で、変数と数値の組み合わせが正しい型になっているかをチェックできます。
======================
[DECL](INT)
[VAR](num)(address=0)(depth=0)
[NUM] val=50
[DECL](STRING)
[VAR](text)(address=0)(depth=0)
[STR] val=Hello World!
[PRINT]
[VAR](num)(address=0)(depth=0)
[PRINT]
[VAR](text)(address=0)(depth=0)前回の記事で変数テーブルに登録する関数にTypeKind を渡していたのはこのためです。
void resolution_variable(Node* node, bool allow_create, TypeKind* type) {
int addr = -1;
if (block_depth >= 1) {
LocalVariablesInfo var = find_local_variable(node->name, block_depth);
addr = var.address;
int find_depth = var.depth;
if (!var.found) {
GlobalVariablesInfo g_var = find_global_variable(node->name);
addr = g_var.address;
if (!g_var.found) {
if (allow_create) {
addr = insert_local_variable(node->name, block_depth, type);
var = find_local_variable(node->name, block_depth);
node->address = var.address;
node->depth = var.depth;
node->is_global = false;
node->type = var.type;
return;
}
fprintf(stderr, "Undefined variable: %s\n", node->name);
exit(1);
}
node->address = addr;
node->is_global = true;
node->type = g_var.type;
return;
} else {
node->address = addr;
node->depth = find_depth;
node->is_global = false;
node->type = var.type;
}
} else {
GlobalVariablesInfo var = find_global_variable(node->name);
if (!var.found) {
if (allow_create) {
addr = insert_global_variable(node->name, type);
var = find_global_variable(node->name);
node->address = var.address;
node->is_global = true;
node->type = var.type;
return;
}
fprintf(stderr, "Undefined variable: %s\n", node->name);
exit(1);
}
node->address = var.address;
node->is_global = true;
node->type = var.type;
return;
}
}
void name_resolution(Node *node) {
if (node == NULL) return;
while (node) {
switch (node->kind) {
case ND_NUM: {
emit_count_two_up();
break;
}
case ND_STR: {
emit_count_two_up();
break;
}
case ND_BOOL: {
emit_count_two_up();
break;
}
case ND_VAR_DECL: {
if (node->rhs != NULL) {
name_resolution(node->rhs);
}
resolution_variable(node->lhs, true, &node->type);
if (node->lhs->is_global) {
emit_count_two_up();
} else {
emit_count_three();
}
break;
}
case ND_ASSIGN: {
name_resolution(node->rhs);
resolution_variable(node->lhs, false, &node->lhs->type);
if (node->lhs->is_global) {
emit_count_two_up();
} else {
emit_count_three();
}
break;
}
...省略
default:
printf("Unknown node: %d\n", node->kind);
exit(1);
}
node = node->next;
}
}名前解決後のASTはこのようになります。
======================
[DECL](INT)
[VAR](INT)(num)(address=1)
[NUM] val=50
[DECL](STRING)
[VAR](STRING)(text)(address=2)
[STR] val=Hello World!
[PRINT]
[VAR](INT)(num)(address=1)
[PRINT]
[VAR](STRING)(text)(address=2)名前解決時に、子ノードであるVARへ型情報を伝播させることができました。
PRINTの子ノードであるVARについても、変数宣言時に変数テーブルへ保存した型情報を取得し、VARに付与しています。
GlobalVariablesInfo find_global_variable(char *name) {
GlobalVariablesInfo var;
var.found = false;
var.address = -1;
for (int i = 0; i < global_variable_count; i++) {
if (strcmp(global_variable_table[i].name, name) == 0) {
var.address = global_variable_table[i].memory_index;
var.type = global_variable_table[i].type;
var.found = true;
return var;
}
}
return var;
}
LocalVariablesInfo find_local_variable(char *name, int depth) {
LocalVariablesInfo var;
var.found = false;
var.address = -1;
for (int i = depth; i >= 0; i--) {
for (int j = 0; j < local_scopes[i].variable_count; j++) {
if (strcmp(local_scopes[i].name[j], name) == 0) {
var.address = local_scopes[i].address[j];
var.depth = i;
var.found = true;
var.type = local_scopes[i].type[j];
return var;
}
}
}
return var;
}これで型チェックする準備が整いました。
型チェック
型チェックは名前解決の後に行います。
五右衛門プログラム
↓
tokenize関数(トークン化)
↓
parse_program関数(1パスでパースし、Nodeを作成します。)
↓
name_resolution関数(名前解決)
↓
type_check関数(型チェック)
↓
generate(パーサで作成したNode を元にバイトコードを作成します。)
↓
バイトコード
↓
VM実行エントリポイントからtype_checkを呼び出します。
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_bynary();
}
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;
}実際のtype_check関数はこちらになります。type_check_programからtype_check関数を呼び出し、type_check関数から再帰的に呼び出しを行います。
void type_check_program(Node *program) {
while(program) {
type_check(program);
program = program->next;
}
}
...省略
TypeKind type_check_expression(Node* node) {
TypeKind lhs = type_check(node->lhs);
TypeKind rhs = type_check(node->rhs);
node->type = TY_INT;
if (lhs != TY_INT || rhs != TY_INT) {
fprintf(stderr,
"Expected: %s\n", type_name(node->type));
exit(1);
}
return TY_INT;
}
..省略
TypeKind type_check(Node* node) {
if (node == NULL) return TY_VOID;
switch (node->kind) {
case ND_NUM: {
return TY_INT;
}
case ND_STR: {
return TY_STRING;
}
case ND_BOOL: {
return TY_BOOL;
}
case ND_VAR_DECL: {
if (node->rhs == NULL) {
return TY_VOID;
}
TypeKind rhs = type_check(node->rhs);
if (rhs != node->type) {
fprintf(stderr,
"Expected: %s\n", type_name(node->type));
exit(1);
}
return TY_VOID;
}
case ND_ASSIGN: {
TypeKind rhs = type_check(node->rhs);
if (rhs != node->lhs->type) {
fprintf(stderr,
"Expected: %s\n", type_name(node->lhs->type));
exit(1);
}
return TY_VOID;
}
case ND_VAR: {
return node->type;
}
case ND_PRINT: {
type_check(node->lhs);
return TY_VOID;
}
case ND_ADD: {
return type_check_expression(node);
}
case ND_MINUS: {
return type_check_expression(node);
}
case ND_MUL: {
return type_check_expression(node);
}
case ND_MOD: {
return type_check_expression(node);
}
case ND_DIV: {
return type_check_expression(node);
}
case ND_LT: {
return type_check_expression(node);
}
case ND_LE: {
return type_check_expression(node);
}
case ND_GT: {
return type_check_expression(node);
}
case ND_GE: {
return type_check_expression(node);
}
case ND_EQ: {
return type_check_expression(node);
}
case ND_NE: {
return type_check_expression(node);
}
case ND_IF: {
enter_scope();
type_check(node->condition);
type_check_program(node->body);
leave_scope();
return TY_VOID;
}
case ND_WHILE: {
enter_scope();
type_check(node->condition);
type_check_program(node->body);
leave_scope();
return TY_VOID;
}
case ND_FOR: {
enter_scope();
type_check(node->init);
type_check(node->condition);
type_check(node->update);
type_check_program(node->body);
leave_scope();
return TY_VOID;
}
...省略
default:
// TODO: implement type check
return TY_VOID;
}
}重要なのはADDなどから呼ばれるtype_check_expression 関数です。この関数はINT型同士であるかをチェックしています。単純ですが、現在の五右衛門では比較演算子はINT型同士しかサポートしていません。type_check_expression() は子ノードを再帰的に型チェックし、その結果を使って演算子の型制約を検証しています。
//許可する組み合わせ
int + int また、変数宣言時に代入を行う際も宣言時の型と右辺の型が一致するかもチェックしています。最後にTY_VOIDを戻り値として返しているのは、変数宣言や代入は「値を返す式」ではないため、型チェック後の戻り値として TY_VOID を返しています。
実際にエラーとなる五右衛門プログラムを書きます。
int num = "Hello World!";
//出力
Expected: INT
make: *** [run] Error 1このようにエラーとなります。(現在は型エラーを検出すると、その時点でコンパイルを終了しています。今後はエラーから復帰してASTの残りも検査し、複数のエラーをまとめて報告できるようにする予定です。)
文字列の出力まで
今回はSTRING型を追加しました。実際に五右衛門内で文字列が出力されるまでを追いかけてみましょう。文字列はバイナリファイル生成時にバイナリコードの下に追加してVMに渡します。(構造体や配列が固定長ですが、動的メモリなども今後実装する予定です。)
typedef struct {
char str[32];
int length;
} String;
String string_table[128];
int string_count = 0;
void generate(Node *node) {
if (node == NULL) return;
while (node) {
switch (node->kind) {
case ND_NUM: {
emit_one_operand(OP_PUSH, &node->val);
break;
}
case ND_STR: {
string_table[string_count].length = node->len;
strcpy(string_table[string_count].str, node->str);
node->address = string_count;
emit_one_operand(OP_PUSH, &node->address);
string_count++;
break;
}
case ND_PRINT: {
generate(node->lhs);
if (node->lhs->kind != ND_STR && node->lhs->type != TY_STRING) {
emit_no_operand(OP_PRINT);
} else {
emit_no_operand(OP_PRINT_STRING);
}
break;
}
...省略
default:
printf("Unknown node: %d\n", node->kind);
exit(1);
}
node = node->next;
}
}generate関数でstring_table に値をコピーしています。そして、テーブルのindexをVMのスタックにpushできるようにします。テーブルをエントリポイントであるmain関数でバイナリファイルに追加し、VM側でもstring_tableを使えるようにします。
int main(int argc, char **argv) {
...省略
generate(program);
...省略
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;
}VM側で
void run(int* program) {
int stack[1024];
int call_stack[128];
int memory[2048];
int frames[128][128];
int sp = -1;
int call_sp = -1;
int pc = 0;
for(int i = 0; i < 2048; i++) memory[i] = 0;
while (true) {
int instruction = program[pc++];
switch (instruction) {
...省略
case OP_PRINT_STRING: {
int address = stack[sp--];
printf("VM Output: %s\n", string_table[address].str);
break;
}
case OP_HALT:
return;
}
}
}
void load_and_run(const char* filename) {
FILE* f = fopen(filename, "rb");
if (!f) return;
GoemonHeader header;
fread(&header, sizeof(GoemonHeader), 1, f);
int *code = malloc(header.bytecode_size * sizeof(int));
if (code == NULL) {
perror("malloc");
exit(1);
}
fseek(f, sizeof(GoemonHeader), SEEK_SET);
fread(code, sizeof(int), header.bytecode_size, f);
fseek(f, sizeof(GoemonHeader) + header.bytecode_size * sizeof(int), SEEK_SET);
string_table = malloc(sizeof(String) * header.string_count);
fread(string_table, sizeof(String), header.string_count, f);
fclose(f);
run(code);
free(code);
}五右衛門プログラムが下記の時の出力です。
print "Hello World!";
//出力
VM Output: Hello World!今はまだ、文字列操作はprintで表示するしかできないので、一旦はgenerate関数内で OP_PRINTとOP_PRINT_STRING を分けています。
最後に
今回は、簡易的ではありますが、五右衛門に型システムと型チェックを実装しました。
現時点では基本的な型チェックのみですが、今後は関数の引数や戻り値の型チェックなど、さらに型システムを拡張していく予定です。
最後まで読んでいただき、ありがとうございました。
次回は、五右衛門の関数を実装していきます。
関数の記事を投稿しました。こちらも見ていただけると嬉しいです。
コメント