はじめに
今回の記事は前回の続きになります。よかったら前回も見ていただけると嬉しいです。
前回は以下を実装しました。
・VM
・スタックマシン
・四則演算
・変数
・再帰下降パーサ
今回は制御構文を実装します。そして、実際に作成中のコンパイラとVMがこちらになります。
if文の実装
さて、最初にif文の実装からです。例として、下記のプログラムがあったとします。
a = 3;
if (a < 4) {
print a;
}これを上から順番に解析していくと、ある疑問が湧くと思います。if文の条件式が偽の場合の飛び先です。はい、ここで登場するのが2パスコンパイルとバックパッチです。2パスコンパイルはそのままの意味で、解析で2周します。1周目でジャンプ先の位置を計算し、2周目で実際のアドレスを埋め込みます。バックパッチはif文の { が登場したら、先にJZと仮のアドレスを入れておき、 } が登場したら、入れておいた仮のアドレスに } の位置に入れ直します。こうすることで、偽の時に if文のコードブロックを飛ばすことができます。
(一般的なコンパイラでは、1周目でシンボル情報やジャンプ先の位置を収集し、2周目で実際のアドレスを埋め込む2パスコンパイルが使われることがあります。しかし、今回の実装ではバックパッチのみでジャンプ先を解決できるため、厳密には2パスは不要です。現在は学習目的として残していますが、今後リファクタリングを行う予定です。)
バックパッチの例です。 まず最初に emit_op(OP_JZ, &zero); と仮埋めした後に bytecode[my_jmp_idx + 1] = count; ifの最後でカウントを入れ直します。
void parse_if () {
if (tokens[pos].kind == TK_LPAREN) next_token();
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();
if (tokens[pos].kind == TK_ELSE) {
next_token();
int my_jmp_idx = count;
emit_op(OP_JMP, &zero);
if (!is_first_pass) {
bytecode[my_jz_idx + 1] = count;
}
if (tokens[pos].kind == TK_IF) {
next_token();
parse_if();
if (!is_first_pass) {
bytecode[my_jmp_idx + 1] = count;
}
} else {
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();
if (!is_first_pass) {
bytecode[my_jmp_idx + 1] = count;
}
}
} else {
if (!is_first_pass) {
bytecode[my_jz_idx + 1] = count;
}
}
}2パスの例がこちらになります。1周目の時にカウント保持し、2周目にJZの飛び先をbytecodeに入れます。(現時点では、私の実際のソースでは2パス構成の意味がありません。バックパッチだけで、完結できます。) 実際には、読みやすさ・処理速度など様々なケースを考慮した上で設計してください。
void emit_op (OpCode op_code, int *val) {
if (is_first_pass) {
count++;
if (val != NULL) {
count++;
}
} else {
bytecode[count++] = op_code;
if (val != NULL) {
bytecode[count++] = *val;
}
}
}
int main() {
char *src = read_file("examples/study.goe");
int cn = tokenize(src);
debug_token(cn);
is_first_pass = true;
count = 0;
pos = 0;
parse_program();
is_first_pass = false;
count = 0;
pos = 0;
parse_program();
debug_op_code();
printf("絶景かな！ Compiled study.goe to study.gb\n");
return 0;
}コンパイルした形が以下になります。
PUSH 3
STORE 0 ; a = 3
LOAD 0
PUSH 4
LT ; a < 4
JZ 14 ; falseなら飛ぶ
LOAD 0
PRINT ; trueなら実行
HALTelse 文の実装にはJZ だけでなく、JMPも必要になります。if 文の条件式が真の時、if文の中の処理の後にelse のコードブロックをスキップするために、JMP で else の } の位置のアドレスに飛ばします。
ネストのif文の解析にも再帰下降構文解析を用いていますが、前回触れたので、今回は省略します。
while文の実装
次にwhile文の実装をします。while文もif と考え方は同じです。
c = 0;
while (c < 10) {
print c;
c++;
}while文の条件式が偽の時には } まで飛ばしたいので、{ がきたら、JZ と仮のアドレスを入れます。そして、while文の最後で、条件式の先頭アドレスへJMPします。
コンパイラがこちらになります。
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;
}
}実際にコンパイルした結果がこちらになります。
PUSH 0
STORE 0
LOAD 0
PUSH 10
LT
JZ 18
LOAD 0
PRINT
INC 0
JMP 4
HALT実行結果がこちらになります。
絶景かな！ Compiled study.goe to study.gb
./kama-e examples/study.gb
VM Output: 0
VM Output: 1
VM Output: 2
VM Output: 3
VM Output: 4
VM Output: 5
VM Output: 6
VM Output: 7
VM Output: 8
VM Output: 9最後に
おまけとして、最後にフィボナッチ数列を計算してみます。
a = 0;
b = 1;
i = 0;
while (i < 10) {
print a;
temp = a + b;
a = b;
b = temp;
i++;
}実行結果がこちらになります。
絶景かな！ Compiled study.goe to study.gb
./kama-e examples/study.gb
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はい、無事に出力されてますね。今回は if文と while文の実装でした。制御文が実装されたことにより、かなりプログラミング言語っぽくなってきたと思います。次回はbreakやfor文、関数などを実装していきます。次回も見ていただけると嬉しいです。最後まで見ていただき、ありがとうございました。
コメント