2009-02-27

Brainfuckという難解言語はご存じだろうか？
'>', '<', '+', '-', '.', ',', '[', ']'の8種類の文字のみを使用した、
チューリング完全なチューリングマシンである。

Brainfuckの言語仕様

> ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。
< ポインタをデクリメントする。C言語の「ptr--;」に相当。
+ ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。
- ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。
. ポインタが指す値を出力する。C言語の「putchar(*ptr);」に相当。
, 1バイトを入力してポインタが指す値に代入する。C言語の「*ptr=getchar();」に相当。
[ ポインタが指す値が0なら、対応する ] の直後までジャンプする。C言語の「while(*ptr){」に相当。
] ポインタが指す値が0でないなら、対応する [ にジャンプする。C言語の「}」に相当。

今回作ったインタプリタの仕様

いろいろ面倒なので以下の制限を設けています。

インタプリタないで使用できるメモリは最大1MByte（MAX_MEMORY）
インタプリタで実行するソースの最大長は1MByte（MAX_CODE）

ソース

#include <stdio.h>
#include <stdlib.h>

#define MAX_MEMORY	(1024 * 1024)
#define MAX_CODE	(1024 * 1024)

int run(char **code, char *mem, int p);
int main(int argc, char **argv);

int count_line = 1;
int count_position = 0;

int run(char **code, char *mem, int p) {
	char c, *s = *code;

	while (c = *((*code)++)) {
		count_position++;
		switch (c) {
		case '#':
			while(c  = *((*code)++), c != '\n' && c != '\r' && c != EOF) {}
			break;
		case '<':
			if (--p < 0) {
				fprintf(stderr, "Memory Over\n");
				return -1;
			}
			break;
		case '>':
			if (++p >= MAX_MEMORY) {
				fprintf(stderr, "Memory Over\n");
				return -1;
			}
			break;
		case '+':
			mem[p]++;
			break;
		case '-':
			mem[p]--;
			break;
		case '.':
			putchar(mem[p]);
			break;
		case ',':
			mem[p] = getchar();
			break;
		case '[':
			if ((p = run(code, mem, p)) < 0) return -1;
			break;
		case ']':
			if (mem[p] == 0) return p;
			*code = s;
			break;
		case '\r':
		case '\n':
			count_line++;
			count_position = 0;
		case '\t':
		case ' ':
			break;
		default:
			fprintf(stderr, "Syntax Error [line:%d pos:%d]\n", count_line, count_position);
			return -1;
		}
	}
	return 1;
}

int main(int argc, char **argv) {
	FILE *fp;
	char c, *p;
	char *memory, *code;
	int r = 0;

	memory = (char *)malloc(MAX_MEMORY);
	code = (char *)malloc(MAX_CODE);
	memset(memory, 0, MAX_MEMORY);

	if (argc != 2) {
		fprintf(stderr, "bf [Input File]\n");
		free(memory);
		free(code);
		exit(1);
	}

	if ((fp = fopen(argv[1], "r")) != NULL) {
		p = code;
		while ((*(p++) = fgetc(fp)) != EOF) {}
		*(--p) = '\0';
		fclose(fp);
		p = code;
		run(&p, memory, 0);
	} else {
		fprintf(stderr, "Not found [%d]\n", argv[1]);
		r = 1;
	}

	free(memory);
	free(code);

	return r;
}

ソースの解説

main関数

各メモリの確保と、ソースの全文読み込みを行っています。

run関数

インタプリタを再帰的に実行しています。
また、runは

ファイルの先頭〜ファイルの末尾
'['〜']'

までを実行するようになっており、run関数に入ったときのソースのポインタを保存しておくことで']'を読み込んだときに'['までジャンプできるようになっています。

お決まりの「Hello World!」

ソース

>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++
++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>
++++++++[<++++>-]<+.[-]++++++++++.

実行結果

$ ./bf Hello.bf 
Hello World!

問題なく実行できました。

まとめ

思っていたよりもカナリ簡単だった。
インタプリタ作成の練習にもならないかもしれないけど、以外に楽しいので暇な時に作ってみてはどうだろうかｗ

参照：Brainfuck - Wikipedia

ほんまの走り書き技術メモ

Brainfuckインタプリタを作った