はじめに
今回の記事は前回の続きとなっております。ぜひ前回の記事も見ていただけると嬉しいです。
さて、今回は前回と比べてかなりプログラミング言語っぽくなってきたのではないでしょうか。今回実装したのは 変数 と 出力 です。
文字列 → トークナイザ → トークン列 → パーサ → 命令流れとしては、前回と同じになってます。
↓こちらがリポジトリになります。
実装
これが今の五右衛門のソースです。変数に値を保持して、値の出力ができるようになりました。
//今の五右衛門ソース
b = 105 + 1051 + 1051;
print b;これを内部では、
- 数値を順番に評価
- 加算命令（OP_ADD）に変換
- 結果をメモリに保存（OP_STORE）
という形で処理しています。
前々回の五右衛門だと、push 1 → OP_PUSH 1 といった形にしていたんですが、前回実装したミニトークンナイザのおかげもあって、かなり進化しました。
//前回の五右衛門ソース
push 1
push 1
addこちらがコンパイラのソースになります。前回実装したミニトークンナイザがリッチになりました。
Token tokens[256];
int tokenize (char *p) {
int i = 0;
while(*p) {
if (isspace(*p)) { p++; continue;}
...省略
//ここでprint かどうかの判定します。print だったら、tokensでTK_PRINTを保持します。
if (strncmp(p, "print", 5) == 0 && (isspace(p[5]) || p[5] == '\0')) {
printf("print\n");
tokens[i++].kind = TK_PRINT;
p += 5;
continue;
}
//ここで + かどうかの判定します。+ だったら、tokensでTK_PLUS を保持します。
if (*p == '+') {
tokens[i++].kind = TK_PLUS;
p++;
continue;
}
//; を判定します。
if (*p == ';') {
tokens[i++].kind = TK_SEMI;
p++;
continue;
}
//ここで 変数名を判定します。
if (isalpha(*p) || *p == '_') {
int len = 0;
while (isalnum(*p) || *p == '_') {
tokens[i].str[len++] = *p++;
}
tokens[i].str[len] = '\0';
if (*p == ':') {
tokens[i].kind = TK_IDENT;
i++;
tokens[i++].kind = TK_COLON;
p++;
} else {
tokens[i++].kind = TK_IDENT;
}
continue;
}
// = を判定します。
if (*p == '=') {
tokens[i++].kind = TK_ASSIGN;
p++;
continue;
}
p++;
printf("不明な文字ですぞ: %c\n", *p);
}
tokens[i].kind = TK_EOF;
return i;
}そして、tokens を元に解析とOP_CODEに変換をします。
int pos = 0;
Token* next_token() {
return &tokens[pos++];
}
int bytecode[1024];
int count = 0;
void emit_op (OpCode op_code, int *val) {
bytecode[count++] = op_code;
if (val != NULL) {
bytecode[count++] = *val;
}
}
void parse_primary() {
Token *t = next_token();
if (t->kind == TK_NUMBER) {
emit_op(OP_PUSH, &t->val);
} else if (t->kind == TK_IDENT) {
int addr = find_variable(t->str);
emit_op(OP_LOAD, &addr);
}
}
void parse_expression() {
parse_primary();
while (tokens[pos].kind == TK_PLUS) {
next_token();
parse_primary();
emit_op(OP_ADD, NULL);
}
}
void parse_generate () {
pos = 0;
while (tokens[pos].kind != TK_EOF) {
Token *t = next_token();
switch(t->kind) {
case TK_PUSH: {
Token *num = next_token();
if (num->kind != TK_NUMBER) {
printf("エラー: pushの次は数値を置いてくだされ");
exit(1);
}
emit_op(OP_PUSH, &num->val);
break;
}
...省略
case TK_PRINT: {
Token *value = next_token();
if (value->kind == TK_IDENT) {
int addr = find_variable(value->str);
emit_op(OP_LOAD, &addr);
}
emit_op(OP_PRINT, NULL);
break;
}
case TK_IDENT: {
if (tokens[pos].kind == TK_COLON) {
next_token();
}
if (tokens[pos].kind == TK_ASSIGN) {
next_token();
parse_expression();
if (tokens[pos].kind == TK_SEMI) {
//ここに入った時点でOP_STOREは確定
int addr = find_variable(t->str);
emit_op(OP_STORE, &addr);
}
}
break;
}
}
}
emit_op(OP_HALT, NULL);
FILE *dest = fopen("examples/study.gb", "wb");
fwrite(bytecode, sizeof(int), count, dest);
fclose(dest);
}今回の実装での肝はparse_generate()からのparse_expression()で再帰的に+ を探すところになります。いわゆる、再帰下降構文解析 というものになります。はい、私も今回初めて知りました。wiki などでも詳しくみることができますが、かなり難しかったです。
簡単にまとめると parse_expression関数の中で parse_primary関数を呼んで、+ が見つからなくなるまで回し続ける感じです。
そして、こちらがVM側の処理になります。
void run(int* program) {
int stack[1024];
int memory[2048];
int 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_PUSH:
stack[++sp] = program[pc++];
if (sp >= 255) {
printf("限界突破！スタックが溢れましたぞ！ (pc=%d)\n", pc);
return;
}
break;
case OP_ADD: {
if (sp < 1) {
printf("エラー: スタックが足りませぬ！ (pc=%d)\n", pc);
return;
}
int b = stack[sp--];
int a = stack[sp--];
stack[++sp] = a + b;
break;
}
省略...
case OP_STORE: {
int address = program[pc++];
int value = stack[sp--];
memory[address] = value;
break;
}
case OP_LOAD: {
int address = program[pc++];
stack[++sp] = memory[address];
break;
}
省略...
case OP_PRINT:
if (sp < 0) {
printf("エラー：スタックが空なのに print しようとしましたぞ！\n");
} else {
printf("VM Output: %d\n", stack[sp]);
}
break;
case OP_HALT:
return;
}
}
}パーサでバイナリに変換したコードをstackに格納し、最後のstackをOP_PRINTだったら出力しています。
最後に処理の流れを振り返ります。
ソースコードをトークンに分解（Tokenizer）
↓
トークン列を解析（Parser）
↓
バイトコード生成
↓
実行VMで実行最後に
現状の五右衛門には以下の課題があります。
- if文がない
- ループがない
- 関数がない
- AST構造が未導入
つまり、まだ「小さな言語」の途中段階です。今後は以下の機能を追加していく予定です。
- 条件分岐（if）
- 繰り返し（while）
- 関数定義
- より柔軟な式解析
ここまで来ると、いよいよ「実用的なミニ言語」に近づいていきます。もし次の④を書くとしたら、「if文実装」「制御構文」「VM強化」あたりがかなり読み物として強くなると思います。そして、ここからが本格的な言語設計フェーズになると思います。
最後まで見ていただきありがとうございました。
コメント