はじめに
今回の記事は前回の続きとなってます。前回の記事も見ていただけると、嬉しいです。
前回はfor文の実装や、paraserがASTを生成するように設計を変更しました。そして、自動テストの導入により、大規模なリファクタリングなどによる既存のプログラムが壊れていないことを担保できるようになりました。
今回は、変数スコープを追加しました。これにより、if文・while文・for文などのブロック内で宣言した変数は、そのブロック内でのみ参照できるようになります。一般的なプログラミング言語と同じようなスコープ管理ができるようになりました。
変数と変数の代入は実装していましたが、スコープの概念が自作言語にはなかったため、全てグローバル変数でした。当初は言語仕様が固まっていなかったため、まずはグローバル変数のみを実装していました。スコープ管理は実装量も多くなるため、後回しにしていました。
↓こちらが現在作成中の自作言語になります。
変数のスコープ
前回までのgoemon にはスコープの概念がありませんでした。そのため、下記のようなプログラムも動いていました。
//goemon
if (1) {
a = 1;
}
print a;ブロック内で、変数を定義したにも関わらず、参照することが可能でした。前回までは、テーブル1つで変数を管理していました。今回はグローバル変数テーブルとローカル変数テーブルの2つを用意して、同スコープ内と親スコープおよびグローバル変数しか、参照できないようにしました。(今はまだ、動的メモリ確保ではなく、静的にメモリを定義しています。動的メモリはもう少し先になるかと思います。)
//前回までは1つのテーブルで管理していました。
Variable variable_table[128];
int variable_count = 0;今回の実装で追加したテーブルや、構造体がこちらです。ローカル変数の管理はLocalVariables構造体でスコープごとに管理をします。LocalVariablesInfo はローカル変数の検索結果として使用します。
Variable global_variable_table[128];
int global_variable_count = 0;
typedef struct {
int variable_count;
char name[32][32];
int address[32];
} LocalVariables;
typedef struct {
int address;
int depth;
bool found;
} LocalVariablesInfo;
LocalVariables local_scopes[128];
int block_depth = 0;そして、重要なのが、block_depth になります。ネストの深さを管理するために、使用します。local_scopes[block_depth] で スコープを表現しています。block_depth は現在どのブロックにいるかを表します。そして local_scopes[block_depth] が、そのブロック専用のローカル変数テーブルになります。例としては if文 や while文 などに入る度に、block_depth をインクリメントします。
if (1) {
//block_depthが1
a = 1;
if (1) {
//block_depthが2
b = 1;
}
print b; //エラーになります。
}実際のコンパイラの実装がこちらになります。(詳細についてはリポジトリを参照ください。)
ブロックへ入ると enter_scope() を呼び出し、block_depth をインクリメントします。ブロックを抜けると leave_scope() を呼び出し、block_depth をデクリメントします。同時に、そのスコープの変数カウントをリセットすることで、ブロック単位の変数管理を実現しています。
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--;
}
void generate(Node *node) {
if (node == NULL) return;
while (node) {
switch (node->kind) {
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;
}
...省略
case ND_IF: {
enter_scope();
generate(node->condition);
int my_jz_idx = count;
int zero = 0;
emit_one_operand(OP_JZ, &zero);
generate(node->body);
if (node->else_stmt) {
int my_jmp_idx = count;
emit_one_operand(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;
}
leave_scope();
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;
}関数内では、block_depth が 1以上であるなら 「現在のスコープ → 親スコープ → グローバル変数」の順番で探索します。変数が見つからなかった場合は、エラーとなります。
今回は変数のシャドーイングはサポートしません。親スコープに同名の変数が存在する場合は、常にその変数を参照する仕様としています。(次の記事で紹介する関数の引数についてはシャドーイングをサポートしています。)
void emit_variable(char* name, OpCode global_opcode, OpCode local_opcode, bool allow_create) {
int addr = -1;
if (block_depth >= 1) {
LocalVariablesInfo var = find_local_variable(name, block_depth);
addr = var.address;
int find_depth = var.depth;
if (!var.found) {
addr = find_global_variable(name);
if (addr == -1) {
if (allow_create) {
addr = insert_local_variable(name, block_depth);
var = find_local_variable(name, block_depth);
emit_two_operand(local_opcode, &var.address, &var.depth);
return;
}
fprintf(stderr, "Undefined variable: %s\n", name);
exit(1);
}
emit_one_operand(global_opcode, &addr);
return;
} else {
emit_two_operand(local_opcode, &addr, &find_depth);
}
} else {
addr = find_global_variable(name);
if (addr == -1) {
if (allow_create) {
addr = insert_global_variable(name);
emit_one_operand(global_opcode, &addr);
return;
}
fprintf(stderr, "Undefined variable: %s\n", name);
exit(1);
}
emit_one_operand(global_opcode, &addr);
return;
}
}ローカル変数の時はバイトコードを3つ生成します。1つ目はVMが実行できるOPCODE で、2つ目は変数の格納先です。そして、もう一つが、階層です。今まではOPCODEとアドレスや値の2つだけを生成していましたが、VM側でスコープの階層を表現するのが、難しいため、3つ生成することにしました。
emit_two_operand(local_opcode, &addr, &find_depth);VM側の修正
VM側では、新しくframesテーブルを追加しました。そして、新しいOPCODEの追加です。ローカル変数の時は、専用のOPCODEをバイトコードとして生成し、VM側で framesを参照するようにします。グローバル変数の場合は、今まで通り、memory を使用しています。
memory
├── グローバル変数
frames
├── depth0
├── depth1
├── depth2void 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_STORE: {
int address = program[pc++];
int value = stack[sp--];
memory[address] = value;
break;
}
case OP_STORE_LOCAL: {
int address = program[pc++];
int depth = program[pc++];
int value = stack[sp--];
frames[depth][address] = value;
break;
}
case OP_LOAD: {
int address = program[pc++];
int value = memory[address];
stack[++sp] = value;
break;
}
case OP_LOAD_LOCAL: {
int address = program[pc++];
int depth = program[pc++];
int value = frames[depth][address];
stack[++sp] = value;
break;
}
....省略
case OP_INC: {
int address = program[pc++];
memory[address]++;
break;
}
case OP_INC_LOCAL: {
int address = program[pc++];
int depth = program[pc++];
frames[depth][address]++;
break;
}最後に
今回は変数のスコープを自作言語に実装しました。スコープの仕様は言語によって様々です。そして、コンパイラを作成するにあたって、スコープの概念は避けては通れないとも思います。スコープをサポート・表現できるようになったことで、五右衛門がより一層高度になりました。これからも継続的に開発を続けていきますので、これからも見ていただけると嬉しいです。
次回は関数と関数スコープの記事になります。最後まで見ていただきありがとうございました。
コメント