AlterVision Антон Резниченко

Порой преподаватели университета дают весьма интересные задания. На этот раз идеей многоуважаемого Эдуарда Эмильевича Александрова, уже натолкнувшего меня на создание менеджера памяти MC Heappie и OpenGL-генератора Landscape Winter, было создание компилятора …
Одно «но» — разумеется, он по началу не уточнил, какого именно)
Мой хороший товарищ Тим в своё время говорил о замечательном языке программирования, который «трахает мозг» … Полистав свою любимую Википедию, я наткнулся на крайне интересный язык программирования — Brainfuck!

Brainfuck (англ. brain мозг + fuck) — один из известнейших эзотерических языков программирования, придуман Урбаном Мюллером (Urban Muller) в 1993 году для забавы. Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainfuck представляет собой последовательность этих символов без какого-либо дополнительного синтаксиса.

Одним из мотивов Урбана Мюллера было создание языка с как можно меньшим компилятором. Отчасти он был вдохновлен языком FALSE, для которого существовал компилятор размера 1024 байта. Существуют компиляторы языка Brainfuck размера меньше 200 байт. Программы на языке Brainfuck писать сложно, за что его иногда называют языком для мазохистов. Но при этом важно отметить, что Brainfuck является вполне естественным, полным и простым языком и может использоваться при определении понятия вычислимости.

Машина, которой управляют команды Brainfuck, состоит из упорядоченного набора ячеек и указателя текущей ячейки, напоминая ленту и головку машины Тьюринга. Кроме того, подразумевается устройство общения с внешним миром (см. команды . и ,) через поток ввода и поток вывода.

Подробнее о самом языке Вы можете легко почитать на соответственной страничке — Википедия — Brainfuck (ru).

Главное, что нужно знать для написания компилятора — это интерпретация команд языка.

Изучив набор команд, можем преступать к созданию самого компилятора.
Программу разобьём на две части — интерпретатор командной строки и сам компилятор.

Командная строка описывается самым элементарным образом. Нам нужна команда run file.bf, которая является основной, а так же дополнительные команды, такие как exit, cls, about, help (man, google).
Интерпретатор получает на вход собственно строку, разбивает её на токены и в зависимости от первого токена выбирает команду.

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

int main ( void ) {

// Commands Definition :: Start

#define COMMANDS	7
#define EXIT_C		0
#define ABOUT_C		1
#define RUN_C		2
#define CLS_C		3
#define HELP_C		4

typedef struct _command {
	int		code;
	char	name[20];
} command_t;

command_t commands[COMMANDS] = {
	{ABOUT_C,	"about"},		// About program
	{EXIT_C,	"exit"},		// Exit program
	{RUN_C,		"run"},			// Run file
	{CLS_C,		"cls"},			// Clear Screen
	{HELP_C,	"help"},		// Help command
	{HELP_C,	"man"},			// Help alias
	{HELP_C,	"google"}		// Idiot help alias (... use google, Luke ...)
};

// Command Definition :: End

char command_prompt[255];
char *command;
int work_code, command_code, command_help_code, i;

printf( "Welcome to BrainFuck Compiler (by AlterVision)n" );
printf( "For help, please type "help" to get list of known commandsn" );

work_code = 1;
while (work_code) {

	// Asking for Command String
	printf( "# " );
	gets(command_prompt);

	// Checking Command
	command_code = -1;
	if (strlen(command_prompt)) {
		command = strtok ( command_prompt, " " );
		for (i = 0; i < COMMANDS; i++) {
			if (strcmp(command, commands[i].name) == 0) {
				command_code = commands[i].code;
				break;
			}
		}
	}

	// Running Specified Command
	switch (command_code) {

		case ABOUT_C:
			printf( "  Small Compiler, version 0.1n" );
			printf( "  Created by Anton Reznichenko aka AlterVisionn" );
			break;

		case CLS_C:
			system( "cls" );
			break;

		case RUN_C:
			command = strtok( NULL, " " );
			brainfuck (command);
			break;

		case HELP_C:
			// Help Commands Here
			break;

		case EXIT_C:
			printf( "  Good bye!n" );
			work_code = 0;
			break;

		default:
			printf( "  Unknown commandn" );

	}

}
return 0;

}

Как видно, сам командный интерпретатор может порой быть даже сложнее компилятора)

Теперь перейдём собственно к брейнфакеру — к компилятору языка.

Прежде всего, нам понадобится header-файл для подключения функций компилера — compiler.h

#define null NULL
#define true 1
// #define true false // А спорим, пропрёт!?

#define BRAINFUCKS	65532

#define TK_COUNT	8
#define TK_NEXT		'>'
#define	TK_PREV		'<'
#define	TK_INC		'+'
#define	TK_DEC		'-'
#define	TK_OUT		'.'
#define TK_IN		','
#define	TK_STR		'['
#define	TK_END		']'

typedef struct _stack stack_t, *stack_p;
struct _stack {
	int		command;
	stack_p		next;
};

typedef struct _brainfuck {
	int			ptr;
	unsigned short int	data[BRAINFUCKS];
	int			commands;
	int			pos;
	char			code[BRAINFUCKS];
	stack_t *		stack;
} brainfuck_t;

int brainfuck ( char * );

Здесь мы определяем наши токены, структуры контекста программы, стек и основную функцию, отвечающую собственно за brainfuck’анье файла.

Далее, перейдём к основному файлу. Это compiler.cpp.

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

int brainfuck ( char * file ) {

	// Defining Main Variables
	FILE	*		flptr;			// File
	brainfuck_t		bf;				// Context
	char			in;				// Input Char
	int				i, j;			// Temp Ints
	stack_p			stack_temp;		// Temp Stack Pointer

	// Token List
	char			tokens[] = {
		TK_NEXT, TK_PREV, TK_IN, TK_OUT, TK_INC, TK_DEC, TK_STR, TK_END
	};

	// Initializing Context Vars
	bf.commands = 0;
	bf.pos		= 0;
	bf.ptr		= 0;
	bf.stack	= null;

	// Clearing Context Data
	for ( i = 0; i < BRAINFUCKS; i++ ) {
		bf.code[i]	= 0;
		bf.data[i]	= 0;
	}

	// Loading Code
	flptr = fopen( file, "r" );
	if ( flptr != null) {
		j = 0;
		while ( (in = fgetc(flptr))!= EOF ) {
			// Do not load more than (big number) commands
			if ( j >= BRAINFUCKS ) break;
			for ( i = 0; i < TK_COUNT; i++ ) {
				// Check if it is command not comment
				if ( in == tokens[i] ) {
					bf.code[bf.commands] = in;
					bf.commands ++;
					j ++;
					break;
				}
			}
		}
	} else {
		printf( "Fatal: file not found!n" );
		return 1;
	}
	fclose( flptr );

	// Start Program Cycle
	while ( bf.pos < bf.commands ) {

		// Check Command Code
		switch ( bf.code[bf.pos] ) {

			// Go To Next Cell ( > )
			case TK_NEXT:
				bf.ptr = (bf.ptr + 1) % BRAINFUCKS;
				break;
			// Go To Prev Cell ( < )
			case TK_PREV:
				bf.ptr --;
				if (bf.ptr < 0) bf.ptr = 0;
				break;

			// Inc Cell Value ( + )
			case TK_INC:
				bf.data[bf.ptr] = (bf.data[bf.ptr] + 1) % 256;
				break;

			// Del Cell Value ( - )
			case TK_DEC:
				bf.data[bf.ptr] --;
				if ( bf.data[bf.ptr] < 0 ) bf.data[bf.ptr] = 0;
				break;

			// Input Char from StdIn ( , )
			case TK_IN:
				bf.data[bf.ptr] = getchar();
				break;

			// Print Char to StrOut ( . )
			case TK_OUT:
				putchar(bf.data[bf.ptr]);
				break;

			// Cycle Start ( [ )
			case TK_STR:
				if ( bf.data[bf.ptr] > 0) {
					// Start Cycle if *p != 0
					stack_temp = new stack_t;
					stack_temp->next = bf.stack;
					stack_temp->command = bf.pos;
					bf.stack = stack_temp;
				} else {
					// Go After The ] if *p == 0
					while ( bf.pos < bf.commands ) {
						if ( bf.code[bf.pos] == TK_END ) {
							break;
						} else {
							bf.pos ++;
						}
					}
				}
				break;

			// Cycle End ( ] )
			case TK_END:
				// Go Back Only If *p != 0
				if ( bf.data[bf.ptr] > 0 ) {
					if (bf.stack != null) {
						stack_temp = bf.stack;
						bf.stack = bf.stack->next;
						bf.pos = stack_temp->command - 1;
						delete stack_temp;
					} else {
						printf( "Fatal: stack is empty when ] is called on %d commandn", bf.pos);
						bf.pos = bf.commands;
					}
				}
				break;
		}

		// Next Command
		bf.pos ++;

	}

	// Clearing the Stack if Necessary
	while (bf.stack != null) {
		stack_temp = bf.stack;
		bf.stack = bf.stack->next;
		delete stack_temp;
	}

	return 0;

}

Как видно из самого кода, программа является если не очень элементарной, то как минимум простой. Но всё таки, постараюсь объяснить её построчно.

В самом начале мы обнуляем данные контекста, и заполняем нулями нашу «машину Тьюринга» и её поток команд.
Далее, мы переходим собственно к самому файлу. Считывая по одному символу, заполняем поток команд — если считываемый символ входит в число возможных токенов, то он добавляется к потоку. Все остальные символы считаются комментариями и удаляются. После считывания файл закрывается — больше он нам не понадобится, выполнение самой программы происходит уже из контекста.

Основной программный цикл, идущий далее, реализует выполнение программы brainfuck’a. Он считывает текущую команду из потока команд и выполняет определённое действие.
Команды перемещения «< " и ">» двигают текущий указатель по пространству ячеек машины Тьюринга. При этом, если указатель пытается переместиться в отрицательную область или выходит за пределы пространства, он обнуляется.
Команды изменения значения «+» и «-» отвечают за инкремент и декремент значения в ячейке, на которой находится указатель.
Команда вывода информации «.» печатает содержимое текущей ячейки на экране. Так как ячейки являются байтами, то содержимое легко печатается как символ, соответствующий данному значению ASCII.
Команда ввода «,» считывает один символ из основного ввода — то есть пользователю необходимо нажать на какую-либо клавишу.
Команда начала цикла «[» записывает текущий указатель команды в стек и начинает выполнение цикла, если значение текущей ячейки больше нуля.
Команда окончания цикла «]» считывает из стека последний указатель команды и возвращается на него.

По окончанию программы выполняется очистка стека в случае, если возникли какие либо ошибки. На этом работа функции заканчивается и считается, что программа завершилась успешно … или почти успешно)

А теперь — самое главное — «Hello World!» на BrainFuck!!

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

Сохраняем это в файл hw.bf, и запускаем его как run hw.bf из командной строки. Что мы видим? Hello World! Значит, компилятор удался!!

Скачать: исходные коды программы и сам компилятор, а также пара примеров.

Выполнено на Microsoft Visual Studio 2008, лицензия МГУ им.Н.П.Огарёва, ФЭТ.
Автор кода: © Антон /AlterVision/ Резниченко