BrainFuck的简单解释器

Toy Interpreter of BrainFuck

发现了一个很有趣的编程语言：BrainFuck，它的语法很简单，只有6个命令，包括了输入、输出、跳转、加、减功能。

• 这种语言基于一个简单的机器模型，除了指令，这个机器还包括：一个以字节为单位、被初始化为零的数组、一个指向该数组的指针（初始时指向数组的第一个字节）、以及用于输入输出的两个字节流。
  这种语言，是一种按照“Turing complete（图灵完备）”思想设计的语言，它的主要设计思路是：用最小的概念实现一种“简单”的语言，BrainF**k 语言只有八种符号，所有的操作都由这八种符号的组合来完成。

使用C语言写一个简单的Brain Fuck解释器

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

#define MAX_STACK_SIZE 1024
#define MAX_PROGRAM_SIZE 2048
#define MAX_MEMORY_SIZE 2048

typedef unsigned char base_t;

int main(int argc, char const *argv[])
{
	char program[MAX_PROGRAM_SIZE] = {0};
	int memory[MAX_MEMORY_SIZE] = {0};
	int stack[MAX_STACK_SIZE] = {0};
	int pos = -1;
	int pc = -1;
	int ptr = MAX_MEMORY_SIZE / 2;
	int programSize;

	if (argc == 1)
	{
		printf("Code file is not sopported\n");
		return -1;
	}
	FILE *fp_in = fopen(argv[1], "r");
	if (fp_in == NULL)
	{
		printf("Can not open the code file\n");
		return -1;
	}
	programSize = fread(program, sizeof(base_t), 2048, fp_in);
	if (ferror(fp_in))
	{
		printf("Error happen when reading code freom %s\n", argv[1]);
		return -1;
	}

	while (++ pc < programSize)
	{
		switch(program[pc])
		{
			case '\n': case '\0': case '\t': case ' ':	break;
			case '+':	memory[ptr] += 1;break;
			case '-':	memory[ptr] -= 1;break;
			case '>':	++ ptr;break;
			case '<':	-- ptr;break;
			case '.':	putchar(memory[ptr]);break;
			case ',':	memory[ptr] = getchar();break;
			case '[': // while(*ptr)
			{
				if (++ pos >= MAX_STACK_SIZE)
				{
					printf("stack overflow\n");
					return -1;
				}
				stack[pos] = pc;
				break;
			}
			case ']': // 返回上一个括号后，若memory[ptr] != 0
			{
				if (memory[ptr])
				{
					if (pos < 0)
					{
						printf("stack downflow\n");
						return -1;
					}
					pc = stack[pos];
				}
				else
					pos -= 1;
				break;
			}
			default:	printf("%c is not a valid character\n", program[pc]);return -1;
		}
	}
	printf("\n");
	return 0;
}

运行以下的BrainFuck代码：

• Hello World

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

得到结果：

$ ./brainFuck tmp.bf 
Hello World!

• 个位数加法

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

得到结果:

$ ./brainFuck tmp.bf 
3+6
9

• 个位数乘法

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

得到结果：

$ ./brainFuck tmp.bf 
2*4
8

使用一连串参数，最终得到的包大小仅有8512字节。

作为参照，Hello World在不加入任何优化参数的情况下，大小为8296字节