はじめに
今回の記事は前回の続きとなってます。前回の記事も見ていただけると、嬉しいです。
前回は、変数スコープを追加しました。これにより、if文・while文・for文などのブロック内で宣言した変数は、そのブロック内でのみ参照できるようになります。一般的なプログラミング言語と同じようなスコープ管理ができるようになりました。
今回はParserのリファクタリングと名前解決の実装です。前回で変数のスコープを実装したことで、generate関数内で変数の検索やスコープの確認、バイトコード生成など、複数の処理を行うようになっていました。
そこで今回は、名前解決をgenerate関数から切り離し、それぞれの責務を分離します。
五右衛門プログラム
↓
tokenize関数(トークン化)
↓
parse_program関数(1パスでパースし、Nodeを作成します。)
↓
name_resolution関数(名前解決)
↓
generate(パーサで作成したNode を元にバイトコードを作成します。)
↓
バイトコード
↓
VM実行↓こちらが現在実装中のコンパイラになります。
Parserのリファクタリング
以前書いたParserの記事では下記のようなコードでした。これは、ParserがASTを生成し、generate関数がbytecodeを生成するように処理を分離したことで、それぞれの役割が明確になりました。
void parse_while() {
if (tokens[pos].kind == TK_LPAREN) next_token();
int my_jmp_idx = count;
parse_evaluation();
if (tokens[pos].kind == TK_RPAREN) next_token();
int my_jz_idx = count;
int zero = 0;
emit_op(OP_JZ, &zero);
if (tokens[pos].kind == TK_LBRACE) next_token();
while (tokens[pos].kind != TK_RBRACE && tokens[pos].kind != TK_EOF) {
parse_statement();
}
if (tokens[pos].kind == TK_RBRACE) next_token();
emit_op(OP_JMP, &my_jmp_idx);
if (!is_first_pass) {
bytecode[my_jz_idx + 1] = count;
}
}generate関数で分離後
Node* parse_while() {
if (tokens[pos].kind == TK_LPAREN) next_token();
Node *condition = parse_evaluation();
if (tokens[pos].kind == TK_RPAREN) next_token();
if (tokens[pos].kind == TK_LBRACE) next_token();
Node *body_head = NULL;
Node *body_tail = NULL;
Node *body_stmt = NULL;
while (tokens[pos].kind != TK_RBRACE && tokens[pos].kind != TK_EOF) {
body_stmt = parse_statement();
if (!body_stmt) continue;
if (!body_head) {
body_head = body_stmt;
body_tail = body_stmt;
} else {
body_tail->next = body_stmt;
body_tail = body_stmt;
}
}
if (tokens[pos].kind == TK_RBRACE) next_token();
return new_loop_node(ND_WHILE, condition, body_head);
}これでも機能していましたが、より安全にするために、TK_LPAREN や TK_RPAREN などのトークンを明示的に確認するようにしました。ここでは例として、parse_while関数をリファクタリングします。
Node* parse_while() {
consume(TK_LPAREN);
Node *condition = parse_evaluation();
consume(TK_RPAREN);
consume(TK_LBRACE);
Node *body_head = parse_statement_list(TK_RBRACE);
consume(TK_RBRACE);
return new_loop_node(ND_WHILE, condition, body_head);
}( や { などのトークンをチェックするためにヘルパー関数を作ります。
bool consume(TokenKind kind) {
if (tokens[pos].kind != kind) {
return false;
}
next_token();
return true;
}※なお、現在の consume 関数は、期待したトークンが存在するかを確認し、正しければ次のトークンへ進むためのヘルパー関数として実装しています。
現時点では、consume の戻り値が false だった場合のエラー処理までは実装していません。そのため、今後は構文エラーが発生した場合に、どのトークンを期待していたのかなどを表示できるよう、エラー処理を追加する予定です。
parse_forなどでも同様の処理があるので、while内のbodyのパース処理も関数にします。
Node* parse_statement_list(TokenKind kind) {
Node *stmt = NULL;
Node *head = NULL;
Node *tail = NULL;
while (tokens[pos].kind != kind && tokens[pos].kind != TK_EOF) {
stmt = parse_statement();
if (!stmt) continue;
if (!head) {
head = stmt;
tail = stmt;
} else {
tail->next = stmt;
tail = stmt;
}
}
return head;
}parse_if や parse_forなどもリファクタリングをしていますが、全てのコードは載せません。気になる方はリポジトリを見てください。
名前解決の実装
そもそもコンパイラにおける名前解決とはなんでしょうか？
名前解決の役割は、簡単にいうと「プログラム中に書かれた名前が、どの宣言を指しているのかを特定すること」です。
今回の五右衛門では、主に変数を対象として名前解決を行います。変数名をシンボルテーブルから検索し、どのスコープに存在する変数なのか、そしてどのメモリアドレスを使用するのかをNodeに記録します。
一般的なコンパイラでは、関数や型、オーバーロードなども名前解決の対象になる場合があります。
これは、前回の実装でも、シンボルテーブルなどを利用して、スコープを表現していましたが、generate内で名前解決を行なっていたので、関数として切り出します。
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_ASSIGN: {
generate(node->rhs);
emit_variable(node->lhs->name, OP_STORE, OP_STORE_LOCAL, true);
break;
}
case ND_VAR: {
emit_variable(node->name, OP_LOAD, OP_LOAD_LOCAL, false);
break;
}
...省略
int find_global_variable(char *name) {
for (int i = 0; i < global_variable_count; i++) {
if (strcmp(global_variable_table[i].name, name) == 0) {
return global_variable_table[i].memory_index;
}
}
return -1;
}
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;
return var;
}
}
}
return var;
}
int insert_global_variable(char *name) {
int current_idx = global_variable_count;
global_variable_count++;
strcpy(global_variable_table[current_idx].name, name);
if (strncmp(name, "__s", 3) == 0) {
global_variable_table[current_idx].memory_index = 1000 + (global_variable_count * 100);
} else {
global_variable_table[current_idx].memory_index = global_variable_count;
}
return global_variable_table[current_idx].memory_index;
}
int insert_local_variable(char *name, int depth) {
int current_idx = local_scopes[depth].variable_count;
local_scopes[depth].variable_count++;
strcpy(local_scopes[depth].name[current_idx], name);
if (strncmp(name, "__s", 3) == 0) {
local_scopes[depth].address[current_idx] = 1000 + (current_idx * 100);;
} else {
local_scopes[depth].address[current_idx] = current_idx;
}
return local_scopes[depth].address[current_idx];
}エントリポイント(main関数)でgenerateを呼んでますが、その前で名前解決をします。
int main(int argc, char **argv) {
...省略
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);
...省略続いて、名前解決の関数です。generate関数と同じようにAST全てを巡回します。これでようやく、ParserがASTを生成する意味が理解できました。(ASTを使い回せるようにと)
※最新のコードでは、型システム・関数の名前解決などが実装されていますが、今回の記事では、省略します。
void name_resolution(Node *node) {
if (node == NULL) return;
while (node) {
switch (node->kind) {
...省略
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;
}
case ND_VAR: {
resolution_variable(node, false, NULL);
if (node->is_global) {
emit_count_two_up();
} else {
emit_count_three();
}
break;
}
case ND_PRINT: {
name_resolution(node->lhs);
emit_count_up();
break;
}
case ND_ADD: {
name_resolution_binary(node);
break;
}
...省略
case ND_IF: {
enter_scope();
name_resolution(node->condition);
emit_count_two_up();
name_resolution(node->body);
if (node->else_stmt) {
emit_count_two_up();
name_resolution(node->else_stmt);
}
leave_scope();
break;
}
case ND_WHILE: {
enter_scope();
name_resolution(node->condition);
emit_count_two_up();
name_resolution(node->body);
emit_count_two_up();
leave_scope();
break;
}
case ND_INC: {
resolution_variable(node->lhs, false, NULL);
if (node->lhs->is_global) {
emit_count_two_up();
} else {
emit_count_three();
}
break;
}
case ND_BREAK: {
emit_count_two_up();
break;
}
case ND_CONTINUE: {
emit_count_two_up();
break;
}
...省略
default:
printf("Unknown node: %d\n", node->kind);
exit(1);
}
node = node->next;
}
}
void emit_count_up() {
count++;
}
void emit_count_two_up() {
count++;
count++;
}
void emit_count_three() {
count++;
count++;
count++;
}
※五右衛門ではローカル変数のアドレスを決定する際に、現在のブロック深度を管理する必要があります。そのため、名前解決中にもブロック深度を調整しています。
emit_count_* は、この時点では実際にbytecodeを出力しているわけではありません。名前解決の段階で、後続のgenerateによって生成されるbytecodeの命令数をあらかじめ計算するために使用しています。実際にシンボルテーブルを検索・登録する処理をまとめた関数になります。この関数は前回実装したemit_variable関数をリファクタリングしています。そして、Nodeに付与するAddressの計算や、深さを計算するために、ヘルパー関数を追加し、Node構造体にもgenerateで使用するaddressなどを追加しています。
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;
...省略
int address;
int depth;
bool is_global;
} Node;
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;
}
}ローカルスコープ内で変数が見つからなかった場合は、find_local_variable()によって外側のスコープを順番に検索します。それでも見つからない場合は、グローバル変数テーブルを検索します。
前回実装したemit_variable関数では、generate関数から呼ばれ、emit_variable関数内でバイトコードを生成していました。名前解決によって、バイトコード生成から、nodeにアドレスやグローバルフラグなどに付与する実装になりました。これにより、generate関数の役割がバイトコードを生成するだけになりました。
void generate(Node *node) {
if (node == NULL) return;
while (node) {
switch (node->kind) {
...省略
case ND_VAR_DECL: {
if (node->rhs != NULL) {
generate(node->rhs);
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_ASSIGN: {
generate(node->rhs);
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_VAR: {
if (node->is_global) {
emit_one_operand(OP_LOAD, &node->address);
} else {
emit_two_operand(OP_LOAD_LOCAL, &node->address, &node->depth);
}
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;
}
case ND_ADD: {
generate_binary(node, OP_ADD);
break;
}
...省略
case ND_INC: {
if (node->lhs->is_global) {
emit_one_operand(OP_INC, &node->lhs->address);
} else {
emit_two_operand(OP_INC_LOCAL, &node->lhs->address, &node->lhs->depth);
}
break;
}
...省略
default:
printf("Unknown node: %d\n", node->kind);
exit(1);
}
node = node->next;
}
}名前解決の実装はかなり大きな実装になるため、もう少し詳細に解説をします。
main関数(エントリポイント)
↓
tokenize関数(五右衛門プログラムをトークンに変換)
↓
parse_program関数(Parser)
↓
name_resolution関数(名前解決)
↓
generate関数(バイトコード生成)
//名前解決詳細
name_resolution関数(名前解決)
↓
※再帰的にASTを巡回
ND_VAR_DECL(変数宣言)
resolution_variable(node->lhs, true, &node->type);
シンボルテーブルを検索・登録する処理をまとめた関数
変数テーブルはグローバル用のテーブルとローカル用のテーブルがあります。
そして、変数宣言時にはテーブルに登録する必要があるため、作成フラグをtrueで渡します。
ND_ASSIGN(代入)
resolution_variable(node->lhs, false, &node->lhs->type);
代入は新規に変数テーブルに登録する必要がないため、作成フラグをfalseで渡します。
ND_VAR(変数参照)
resolution_variable(node, false, NULL);
ND_INC(インクリメント)
resolution_variable(node->lhs, false, NULL);最後に実際に五右衛門プログラムを動かしてみます。(型システムについては、触れません。)
int num = 500;
print num + 1000;実行します。
test@test goemon-src % make run
======================
[DECL](INT)
[VAR](INT)(num)(address=1)
[NUM] val=500
[PRINT]
[ADD]
[VAR](INT)(num)(address=1)
[NUM] val=1000
==========================
VM Output: 15001500が出力されました。重要なのは、Nodeです。名前解決を行う前のNodeは、単純に「numという名前の変数を参照している」という情報しか持っていません。
名前解決後は、
name = "num"
address = 1
is_global = trueのように、実際にどの変数を参照するのかがNodeに記録されます。
そのためgenerate関数は、改めてシンボルテーブルを検索する必要がありません。Nodeに記録された情報を利用して、対応するバイトコードを生成するだけになります。
最後に
今回の実装によって、Parser・名前解決・コード生成の責務を明確に分離することができました。
前回の記事から間があいたため、その間に五右衛門の実装がかなり進んでいます。そのため、今回の記事で紹介した名前解決のコードには、型システムなど今回の記事では扱っていない処理も含まれています。
今回は名前解決の考え方や、Parserで生成したASTを後続の処理で利用する方法について紹介しました。自作コンパイラを作る際の参考になれば嬉しいです。
最後まで見ていただき、ありがとうございました。
次回は、型システムと型チェックの実装について書く予定です。
コメント