はじめに
今回の記事は前回の続きとなってます。前回の記事も見ていただけると、嬉しいです。
前回は型システムと型チェックの実装をしました。五右衛門の言語仕様は静的型付けになります。コンパイル時に型をチェックすることにより、より厳格にすることができました。
今回は関数の実装です。処理をまとめられるようにすることで、さらにプログラミング言語らしくなります。
処理の流れは前回とは変わりません。
五右衛門プログラム
↓
tokenize関数(トークン化)
↓
parse_program関数(1パスでパースし、Nodeを作成します。)
↓
name_resolution関数(名前解決)
↓
type_check関数(型チェック)
↓
generate(パーサで作成したNode を元にバイトコードを作成します。)
↓
バイトコード
↓
VM実行↓こちらが現在実装中のコンパイラになります。
スキャナとパーサ
まずは、五右衛門プログラムの関数として書いたテキストをトークンにします。TokenKind や NodeKind に追加します。
typedef enum {
...省略
TK_FUNCTION,
TK_RET,
} TokenKind;
typedef enum {
...省略
ND_FUNCTION,
ND_CALL,
ND_RET,
} NodeKind;スキャナにも関数や、return を解析できるように追加します。CALLがNodeだけに存在するのは、generate 時にOPCodeを生成できるように必要だからです。
Token tokens[MAX_TOKENS];
int line = 1;
void tokenize (char *p) {
int i = 0;
while(*p) {
...省略
if (strncmp(p, "function", 8) == 0 && (isspace(p[8]) || p[8] == '\0')) {
tokens[i++].kind = TK_FUNCTION;
p += 8;
continue;
}
if (strncmp(p, "return", 6) == 0 && (isspace(p[6]) || p[6] == '\0')) {
tokens[i++].kind = TK_RET;
p += 6;
continue;
}
...省略
printf("Line %d: Unknown character '%c'\n", line, *p);
exit(1);
}
tokens[i].kind = TK_EOF;
if (g_debug_token) debug_token(i);
}関数やreturn文が見つかれば、それぞれに対応するトークンを格納します。下記のような五右衛門プログラムだった場合、トークンはこのようになります。
function int add(int a, int b) {
return a + b;
}
print add(5, 8);===== TOKEN DUMP =====
[000] TK_FUNCTION [LN: 001]
[001] TK_INT [LN: 001]
[002] TK_IDENT [LN: 001] text="add"
[003] TK_LPAREN [LN: 001]
[004] TK_INT [LN: 001]
[005] TK_IDENT [LN: 001] text="a"
[006] TK_INT [LN: 001]
[007] TK_IDENT [LN: 001] text="b"
[008] TK_RPAREN [LN: 001]
[009] TK_LBRACE [LN: 001]
[010] TK_RET [LN: 002]
[011] TK_IDENT [LN: 002] text="a"
[012] TK_PLUS [LN: 002]
[013] TK_IDENT [LN: 002] text="b"
[014] TK_SEMI [LN: 002]
[015] TK_RBRACE [LN: 003]
[016] TK_PRINT [LN: 005]
[017] TK_IDENT [LN: 005] text="add"
[018] TK_LPAREN [LN: 005]
[019] TK_NUMBER [LN: 005] value=5
[020] TK_NUMBER [LN: 005] value=8
[021] TK_RPAREN [LN: 005]
[022] TK_SEMI [LN: 005]
[023] TK_EOF [LN: 005]
======================このトークンを元にパーサで、ASTを生成します。関数は文なので、専用のparse関数を作ります。
static TypeKind ret_type() {
switch (tokens[pos].kind) {
case TK_INT:
case TK_STRING_TYPE:
case TK_BOOL_TYPE:
case TK_VOID: {
Token *t = next_token();
return token_convert_type(t->kind);
}
case TK_IDENT:
return TY_VOID;
default:
fprintf(stderr,
"Error at line %d: Expected TK_IDENT but got %s\n",
tokens[pos].line,
token_name(tokens[pos].kind));
exit(1);
}
}
Node* new_func_node(NodeKind kind, char *str, Node* params, Node* body, TypeKind type) {
int current_idx = node_depth;
node_depth++;
node_tree[current_idx].kind = kind;
strcpy(node_tree[current_idx].func_name, str);
node_tree[current_idx].params = params;
node_tree[current_idx].body = body;
node_tree[current_idx].type = type;
return &node_tree[current_idx];
}
static Node* parse_function() {
TypeKind ret_kind = ret_type();
Token *ident = expect_ident();
expect(TK_LPAREN);
Node *param_head = parse_statement_list(TK_RPAREN);
expect(TK_RPAREN);
expect(TK_LBRACE);
Node *body_head = parse_statement_list(TK_RBRACE);
expect(TK_RBRACE);
return new_func_node(ND_FUNCTION, ident->str, param_head, body_head, ret_kind);
}
static Node* parse_statement() {
Token *t = next_token();
switch(t->kind) {
...省略
case TK_FUNCTION: {
return parse_function();
}
case TK_RET: {
Node *rhs = parse_evaluation();
return new_unary_node(ND_RET, rhs);
}
default:
return NULL;
}
}
parse_function() の冒頭で TypeKind ret_kind = ret_type(); としていますが、これは関数の戻り値の型をtype_check時にチェックできるようにするためにしています。五右衛門の文法では関数は下記のように定義します。そのため、parse_functionに入った時点で現在のトークンは intになります。
function int name(...){}そして、params とbody それぞれもノード化し、functionノードの子ノードにします。
Node *param_head = parse_statement_list(TK_RPAREN);
...省略
Node *body_head = parse_statement_list(TK_RBRACE);
...省略
return new_func_node(ND_FUNCTION, ident->str, param_head, body_head, ret_kind);そして、return文は明示的に指定があれば、parse_statement_list から再帰的にparse_statement が呼ばれるので、子ノードになります。
関数の呼び出し側はここでパースします。
static Node* parse_primary() {
if (tokens[pos].kind == TK_PLUS) {
next_token();
}
Token *t = next_token();
Node *node = NULL;
if (t->kind == TK_LPAREN) {
node = parse_expression();
next_token();
return node;
}
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;
}変数 や print のパース処理から最終的に呼ばれるparse_primaryの中でパースすることにより、式の中で関数呼び出しを使うことができます。
下記の五右衛門プログラムの時のASTはこのようになります。
function int add(int a, int b) {
return a + b;
}
print add(5, 8); [FUNCTION](INT)
[NAME]
(add)
[PARAMS]
[DECL](INT)
[VAR](a)(address=0)(depth=0)
[DECL](INT)
[VAR](b)(address=0)(depth=0)
[BODY]
[RET]
[ADD]
[VAR](a)(address=0)(depth=0)
[VAR](b)(address=0)(depth=0)
[PRINT]
[CALL](address=0)
[NAME]
(add)
[PARAMS]
[NUM] val=5
[NUM] val=8名前解決と型チェックをする前のASTになります。
名前解決と型チェック
パース処理で作成したASTをもとに名前解決や型チェックを実行します。まずはじめに名前解決で使うヘルパー関数を実装します。
本来であれば、emit_count_up のような関数はgenerate時にバイトコードの位置を管理する際に使いますが、現在の五右衛門では関数を呼び出す際に関数の開始位置を保持する必要があります。そして、それを名前解決時に関数テーブルへ登録して、呼び出し側でASTに付与します。
int program_count = 0;
void emit_count_reset() {
program_count = 0;
}
static void emit_count_up() {
program_count++;
}
static void emit_count_two_up() {
program_count++;
program_count++;
}
static void emit_count_three() {
program_count++;
program_count++;
program_count++;
}
void function_count_up() {
function_table[block_depth].function_count++;
}
void enter_scope() {
block_depth++;
local_scopes[block_depth].variable_count = 0;
// Nested function definitions are scoped.
// Reset the next function table when entering a new function scope.
function_table[block_depth + 1].function_count = 0;
}
void leave_scope() {
local_scopes[block_depth].variable_count = 0;
block_depth--;
}そして、enter_scope() では、次のスコープで使用する関数テーブルの function_count を0にしています。これにより、別のスコープで定義された関数情報が残り続けないようにしています。
名前解決時に関数テーブルに追加できるようにヘルパー関数を追加しておきます。関数をテーブルに保持する処理や検索関数では大掛かりなことをしていますが、ご容赦ください。関数とparamsはそれぞれのテーブルで保持をします。params は型チェック時に使用します。
typedef struct {
char name[64][64];
int address[64];
int function_count;
TypeKind type[64];
} Funcion;
typedef struct {
char name[64][64];
char params[16][16][32];
int param_count[64];
int function_count;
TypeKind type[16][16];
} FuncionParams;
Funcion function_table[128];
FuncionParams function_params_table[128];
FuncionParamsInfo find_function_params(char *name, int depth) {
FuncionParamsInfo var;
var.found = false;
var.address = -1;
for (int i = depth + 1; i >= 0; i--) {
for (int j = 0; j < function_params_table[i].function_count; j++) {
if (strcmp(function_params_table[i].name[j], name) == 0) {
var.found = true;
var.depth = i;
var.param_count = function_params_table[i].param_count[j];
var.params = function_params_table[i].params[j];
var.type = function_params_table[i].type[j];
return var;
}
}
}
return var;
}
void insert_function_params(char *name, Node *params, int depth) {
int current_idx = function_params_table[depth].function_count;
for (int i = 0; i < function_params_table[depth].function_count; i++) {
if (strcmp(function_params_table[depth].name[i], name) == 0) {
return;
}
}
strcpy(function_params_table[depth].name[current_idx], name);
Node *p = params;
int p_count = 0;
while (p) {
if (p->lhs == NULL) {
fprintf(stderr, "Parameter '%s' requires an explicit type declaration.\n", p->name);
exit(1);
}
strcpy(function_params_table[depth].params[current_idx][p_count], p->lhs->name);
function_params_table[depth].type[current_idx][p_count] = p->type;
p_count++;
p = p->next;
}
function_params_table[depth].param_count[current_idx] = p_count;
function_params_table[depth].function_count++;
}
FuncionInfo find_function(char *name, int depth) {
FuncionInfo var;
var.found = false;
var.address = -1;
for (int i = depth + 1; i >= 0; i--) {
for (int j = 0; j < function_table[i].function_count; j++) {
if (strcmp(function_table[i].name[j], name) == 0) {
var.found = true;
var.address = function_table[i].address[j];
var.depth = i;
var.type = function_table[i].type[j];
return var;
}
}
}
return var;
}
void insert_function(char *name, int address, int depth, TypeKind type) {
int current_idx = function_table[depth].function_count;
for (int i = 0; i < function_table[depth].function_count; i++) {
if (strcmp(function_table[depth].name[i], name) == 0) {
return;
}
}
strcpy(function_table[depth].name[current_idx], name);
function_table[depth].address[current_idx] = address;
function_table[depth].function_count++;
function_table[depth].type[current_idx] = type;
}名前解決時の処理を追加します。
static void name_resolution_func(Node *node, int address, int depth) {
node->address = address;
node->depth = depth;
}
static void param_name_resolution(Node *node, char* name, int address, int depth, TypeKind type) {
while (node) {
if (strcmp(node->lhs->name, name) == 0) {
node->lhs->address = address;
node->lhs->depth = depth;
node->lhs->type = type;
return;
}
node = node->next;
}
}
void name_resolution(Node *node) {
if (node == NULL) return;
while (node) {
switch (node->kind) {
...省略
case ND_FUNCTION: {
enter_scope();
emit_count_two_up();
int func_start_address = program_count;
insert_function(node->func_name, func_start_address, block_depth, node->type);
insert_function_params(node->func_name, node->params, block_depth);
FuncionParamsInfo func_params = find_function_params(node->func_name, block_depth);
for (int i = 0; i < func_params.param_count; i++) {
LocalVariablesInfo var = find_local_variable(func_params.params[i], block_depth);
int addr = var.address;
if (!var.found) addr = insert_local_variable(func_params.params[i], block_depth, &func_params.type[i]);
var = find_local_variable(func_params.params[i], block_depth);
param_name_resolution(node->params, func_params.params[i], var.address, var.depth, var.type);
emit_count_three();
}
name_resolution(node->body);
emit_count_up();
leave_scope();
break;
}
case ND_CALL: {
FuncionInfo func = find_function(node->func_name, block_depth);
if (!func.found) {
fprintf(stderr, "Undefined function: %s\n", node->func_name);
exit(1);
}
name_resolution(node->params);
name_resolution_func(node, func.address, func.depth);
emit_count_two_up();
break;
}
case ND_RET: {
name_resolution(node->lhs);
emit_count_up();
break;
}
default:
printf("Unknown node: %d\n", node->kind);
exit(1);
}
node = node->next;
}
}かなり複雑なため、処理の流れを順番に追っていきます。
name_resolution関数
↓
ND_FUNCTION
↓
insert_function関数
テーブルで下記を管理
・関数の開始位置
・関数の名前
・ブロックの深さ
・戻り値の型を渡す
↓
insert_function_params関数
テーブルで下記を管理
・関数の名前
・引数名
・引数の個数
・引数の型
↓
引数テーブルとは別に変数テーブルにも登録
↓
関数の本文の名前解決ND_FUNCTION内の処理はかなり複雑なため、これらは将来的にはリファクタリング対象です。
ND_CALL時は登録されてある関数テーブルから、関数の情報を取得します。現在のブロックの深さを基準に検索します。関数が見つからない場合は、エラーになります。関数テーブルから、取得したアドレスをCALLノード自身に付与します。
次にtype_check関数に追加をします。
static void type_check_params(Node *params, char *name) {
Node *p = params;
FuncionParamsInfo func_params = find_function_params(name, block_depth);
for (int i = 0; i < func_params.param_count; i++) {
TypeKind param = type_check(p);
if (param != func_params.type[i]) {
fprintf(stderr,
"Expected: %s\n", type_name(func_params.type[i]));
exit(1);
}
p = p->next;
}
}
static bool type_check_return(Node* node, TypeKind kind) {
bool has_return = false;
while (node) {
switch (node->kind) {
case ND_IF: {
type_check_return(node->body, kind);
break;
}
case ND_WHILE: {
type_check_return(node->body, kind);
break;
}
case ND_FOR: {
type_check_return(node->body, kind);
break;
}
case ND_RET: {
if (node->lhs == NULL) {
if (kind != TY_VOID) {
fprintf(stderr,
"Expected: %s\n", type_name(kind));
exit(1);
}
break;
}
TypeKind lhs = type_check(node->lhs);
if (lhs != kind) {
fprintf(stderr,
"Expected: %s\n", type_name(kind));
exit(1);
}
has_return = true;
break;
}
default:
break;
}
node = node->next;
}
return has_return;
}
static TypeKind type_check(Node* node) {
if (node == NULL) return TY_VOID;
switch (node->kind) {
...省略
case ND_FUNCTION: {
enter_scope();
function_count_up();
bool has_return = type_check_return(node->body, node->type);
if (node->type != TY_VOID && !has_return) {
fprintf(stderr,
"Expected return statement for function returning %s\n",
type_name(node->type));
exit(1);
}
type_check_program(node->body);
leave_scope();
return node->type;
}
case ND_CALL: {
type_check_params(node->params, node->func_name);
FuncionInfo func = find_function(node->func_name, block_depth);
return func.type;
}
case ND_RET: {
return type_check(node->lhs);
}
default:
// TODO: implement type check
return TY_VOID;
}
}ND_FUNCTIONに入った時点で function_count_upを呼び出します。この関数自体は単純で、function_tableのfunction_countをインクリメントします。ここでインクリメントをしておくことで、ND_CALL時にfunction_tableから、関数を検索することができるようになります。そして、type_check_return 関数を呼び出します。type_check_return関数内で、ブロック内をチェックできるようにND_IFやND_WHILEなどから再帰的にtype_check_return関数を呼び出します。ND_RETが見つかると、関数定義で指定された戻り値の型とreturnの戻り値の型を比較します。一致しない場合はエラーとしてコンパイルを終了します。正常なreturnが見つかった場合は、has_returnをtrueにします。(現在の実装では、関数直下にあるreturn文を基準に、return文の存在を簡易的にチェックしています。if などの分岐内部にあるreturnについては、すべての実行経路を考慮した判定にはなっていません。)
関数呼び出し側は引数の型チェックを行います。名前解決時に関数のparams はテーブルに追加しているので、その型情報と引数の型を比較していきます。
実際にエラーとなる五右衛門プログラムを実行してみます。まずは、関数定義時に型を指定している場合のエラーです。
function str show (str a, str b) {
print a;
print b;
}
print show("hello", "world");
//出力
Expected return statement for function returning STRING
make: *** [run] Error 1文字列をreturnしてくださいと怒られます。
次に引数の型を間違えてみます。
function int add(int a, int b) {
return a + b;
}
print add("hello", 500);
//出力
Expected: INT
make: *** [run] Error 1それぞれのエラーメッセージでは、行数がないため、ユーザに優しくないですが、これはまた別の機会にリファクタリングをします。
型チェックを実装しましたが、まだ、足りないものがあります。return文 が関数内の全ルートに実装されているかのチェックです。しかし、これは制御フローを解析する必要があるため、今回の記事では実装しません。
バイトコード生成とVM
generate関数とVM側に処理を追加します。まずは、OP_CODEを追加します。
typedef enum {
...省略
OP_CALL,
OP_RET,
...省略
} OpCode;続いてgenerate関数内に処理を追加します。
typedef struct {
char name[32];
int address;
int depth;
} ParamsTmp;
void generate(Node *node) {
if (node == NULL) return;
while (node) {
switch (node->kind) {
...省略
case ND_FUNCTION: {
enter_scope();
int my_jmp_idx = count;
int zero = 0;
emit_one_operand(OP_JMP, &zero);
Node *params = node->params;
ParamsTmp params_tmp_table[128];
int p_count = 0;
while (params) {
params_tmp_table[p_count].address = params->lhs->address;
params_tmp_table[p_count].depth = params->lhs->depth;
strcpy(params_tmp_table[p_count].name, params->lhs->name);
p_count++;
params = params->next;
}
for (int i = p_count - 1; i >= 0; i--) {
emit_two_operand(OP_STORE_LOCAL, ¶ms_tmp_table[i].address, ¶ms_tmp_table[i].depth);
}
generate(node->body);
emit_no_operand(OP_RET);
bytecode[my_jmp_idx + 1] = count;
leave_scope();
break;
}
case ND_CALL: {
generate(node->params);
emit_one_operand(OP_CALL, &node->address);
break;
}
case ND_RET: {
generate(node->lhs);
emit_no_operand(OP_RET);
break;
}
default:
printf("Unknown node: %d\n", node->kind);
exit(1);
}
node = node->next;
}
}まず、ND_FUNCTION内ですが、node->params を params_tmp_table に一時保存します。これはVMがスタックマシンベースのアーキテクチャになるためです。下記のような五右衛門プログラムがあった時にparams を順番通りにバイトコードにしていくと、
function int add (int a, int b) {}
//スタックの簡易図
stack[sp++] = a;
stack[sp++] = b;
pop(stack[--sp]); //b
pop(stack[--sp]); //aスタックから取り出すときに bの値から処理がされるため、想定通りの動作にはなりません。そこで、params_tmp_tableに一時保存をし、for文で逆順でバイトコードに変換をしていきます。
そして、ND_FUNTIONの最後に、OP_RETを追加します。これは、ユーザーが明示的に return を記述しなかった場合でも、関数を終了する必要があります。特に TY_VOID の関数では return を省略できるため、関数末尾に OP_RET を生成しています。
次にND_CALLですが、ここでは、新しく追加した OP_CALL と、そのオペランドとして関数の開始アドレスを生成します。
ND_RETの場合は、OP_RETをバイトコードに追加します。
次にVM側の追加です。
void run(int* program) {
int stack[1024];
int call_stack[128];
int memory[2048];
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_STORE_LOCAL: {
int address = program[pc++];
int depth = program[pc++];
int value = stack[sp--];
frames[call_frame][depth][address] = value;
break;
}
case OP_LOAD_LOCAL: {
int address = program[pc++];
int depth = program[pc++];
int value = frames[call_frame][depth][address];
stack[++sp] = value;
break;
}
case OP_CALL: {
call_frame++;
call_stack[++call_sp] = pc + 1;
int target = program[pc++];
pc = target;
break;
}
case OP_RET: {
pc = call_stack[call_sp--];
call_frame--;
break;
}
...省略
}
}まず、OP_CALL ですが、OP_CALLの次の位置をcall_stack で保持します。保持をすることで、関数の処理終了時(OP_RET)に呼び出し側の位置まで戻ることができます。そして、OP_CALL のオペランドとして関数の開始アドレスを埋め込み、そのアドレスを pc に設定することで関数の実行を開始します。
関数が終了したとき(OP_RET)はcall_stack から呼び出し側の位置を取り出し、呼び出し側に戻ります。
そして、OP_STORE_LOCALとOP_LOAD_LOCAL時に使っていたテーブルに call_frameで参照できるように修正していますが、これは関数が再帰的に呼ばれた際のparams をそれぞれのスコープでしか利用できないようにするためです。
最後に
最後に関数の動作テストも兼ねて、再帰的にフィボナッチ数列を表示する関数を実行します。
function int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 2) + fib(n - 1);
}
for (int i = 0; i < 20; i++) {
print fib(i);
}VM Output: 0
VM Output: 1
VM Output: 1
VM Output: 2
VM Output: 3
VM Output: 5
VM Output: 8
VM Output: 13
VM Output: 21
VM Output: 34
VM Output: 55
VM Output: 89
VM Output: 144
VM Output: 233
VM Output: 377
VM Output: 610
VM Output: 987
VM Output: 1597
VM Output: 2584
VM Output: 4181無事に表示することができました。
関数を五右衛門にサポートすることができましたが、return文の全ルートチェックや、関数テーブルなどの動的配列へのリファクタリング、引数の個数チェックなど、まだ足りないことが多くあります。これからも実装やリファクタリングを進めていきたいと思います。
次回は、リファクタリングの記事になるかと思います。次の記事も見ていただけると嬉しいです。
コメント