Есть мнение, что каждый программист должен написать в жизни хотя бы один язык программирования, либо реализовать уже существующий, но своими руками. В качестве примера мы начнем с самого простого и создадим Brainfuck. Согласно Вики:
Brainfuck — один из известнейших эзотерических языков программирования, придуман Урбаном Мюллером (нем.Urban Müller) в 1993 году, известен своим минимализмом. Название языка можно перевести на русский как вынос мозга, оно напрямую образовано от английского выражения brainfuck (brain — мозг, fuck — иметь половое сношение), т. е. заниматься ерундой. Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainfuck представляет собой последовательность этих символов без какого-либо дополнительного синтаксиса.
Википедия.
Описание 8 команд:
Команда Brainfuck | Описание команды |
---|---|
Начало программы | выделяется память под 30 000 ячеек с нулевыми начальными значениями |
> | перейти к следующей ячейке |
< | перейти к предыдущей ячейке |
+ | увеличить значение в текущей ячейке на 1 |
- | уменьшить значение в текущей ячейке на 1 |
. | напечатать значение из текущей ячейки |
, | ввести извне значение и сохранить в текущей ячейке |
[ | если значение текущей ячейки ноль, перейти вперёд по тексту программы на ячейку, следующую за соответствующей ] (с учётом вложенности) |
] | если значение текущей ячейки не нуль, перейти назад по тексту программы на символ [ (с учётом вложенности) |
Реализация интерпретатора на Python
Интерпретатор читает программу и выполняет ее сразу на лету.
Первым делом надо прочитать целиком файл с исходником на BF, имя которого мы передаем первым параметром командной строки:
if __name__ == '__main__': if len(sys.argv) == 2: # один аргумент - имя файла, который надо выполнить with open(sys.argv[1], 'r') as f: code = f.read() run(code) # запустить код else: print(f'usage: python {sys.argv[0]} file.bf')
После того, как код прочитан, мы создаем память из 30 000 ячеек, заполненными нулями. Устанавливаем счетчик команд и указатель на ленте ячеек на 0. Инициализация имеет такой вид:
mem_size = 30000 memory = [0] * mem_size # оперативная память программы data_ptr = 0 # индекс текущей ячейки памяти (memory) instr_ptr = 0 # индекс текущей инструкции кода (code)
Далее в цикле читаем ячейку, если это одна из наших 8 команд, то выполняем, иначе пропускаем (это могут быть пробелы и переносы строк, их просто игнорируем). После выполнения команды, указатель сдвигается вправо по коду (увеличивается на единицу). Программа выполняется до тех пор, пока счетчик инструкций не выйдет за пределы размера кода.
С командами типа «+», «-«, «<«, «>» проблем в понимании быть не должно, они делают простые действия. Разве что, вам следует обратить внимание на то, что я зацикливаю оперативную память, если команда смещения переходит границу (команда < от 0 сдвинет на 29999 ячейку, а команда > с ячейки номер 29999 сдвигает на 0 ячейку).
Фрагмент цикла:
# выполняем - пока не вылетели за пределы кода while instr_ptr < len(code): command = code[instr_ptr] # текущая команда if command == '+': memory[data_ptr] += 1 elif command == '-': memory[data_ptr] -= 1 elif command == '>': data_ptr = (data_ptr + 1) % mem_size # циклическая память elif command == '<': data_ptr = (data_ptr - 1) % mem_size # циклическая память ... instr_ptr += 1 # сдвигаеи к следующей команде
Команда точка «.» печатает на экране единственный символ из текущий ячейки памяти. Я использую функцию chr, чтобы из числа получить символ. end=''
указывает, что не надо переводить строку. Команда запятая «,» вводит символ из потока ввода. Считываю строку, беру первый символ и получаю его код функцией ord. Дополним код цикла обработкой ввода и вывода:
... elif command == '.': # печатаем символ с кодом = значения текущей ячейки print(chr(memory[data_ptr]), end='') elif command == ',': # ввод - берем код первого символа или 0, если ввод пустой inp = input() memory[data_ptr] = ord(inp[0]) if inp else 0 ...
Это еще не все. Осталось самое сложное – обработка циклов (они же играю роль ветвлений в BF). Открывающая квадратная скобка «[« в code – команда, говорит нам, что нужно проверить текущую ячейку памяти в memory на равенство нулю. Если нуль, то прыгаем за пределы цикла – на соответствующую закрывающую скобку «]». Если не нуль, то дальше просто выполняем тело цикла. Когда натакливаемся на «]», тут тоже нужно проверить условие цикла, и если оно даст не ноль – вернуться к началу цикла, а иначе продолжить выполнять код дальше за скобкой.
Каждый раз во время выполнения кода искать нужную скобку – неудобно и медленно. Можно оптимизировать код, заранее пройдя по нему и запомнив, где какая скобка и где ее подруга – парная скобка. Для этого заведем словарь bracket_map. Для учета вложенности будем пользоваться структурой данных – стэк (из обычного списка):
# ключ и значения - индекс байта в коде # по любой скобке находим ей пару bracket_map = {} stack = [] for pos, symbol in enumerate(code): # открыли скобку - положим на вершину стэка ее позицию if symbol == '[': stack.append(pos) elif symbol == ']': # вершина стэка - как раз наша парная скобка - была последней # удалим ее с вершины last_open_pos = stack.pop() # создадим парные записи bracket_map[pos] = last_open_pos bracket_map[last_open_pos] = pos
На иллюстрации ниже показано, что хранит этот словарь на примере простой программы.

Теперь мы готовы добавить в цикл исполнения обработку скобок. Просто проверяем условие, и когда нужно перемещаем указатель текущий команды на парную скобку: из начала цикла в конец, если ячейка содержит 0, и из конца цикла в начало, если не 0:
... elif command == '[': # начало цикла - проверка текущей ячейки if not memory[data_ptr]: # == 0 # значит надо перейти на ячейку за соответствующей ей закрывающей скобкой instr_ptr = bracket_map[instr_ptr] elif command == ']': # проверяем тоже условие, если выполняется, то скачем на начало цилка if memory[data_ptr]: # не ноль # перемещаем на конец цикла instr_ptr = bracket_map[instr_ptr]
Готово! Интерпретатор завершен! Выполним простую программу hello_world.bf:
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++ .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++. ------.--------.>+.>.
(venv) ➜ bf python bf_interpretator.py hello_world.bf Hello World!
Работает! А вот как вам сортировка вставками на Brainfuck:
>>+>,[ <[ [>>+<<-]>[<<+<[->>+[<]]>>>[>]<<-]<<< ]>>[<<+>>-]<[>+<-]>[>>]<, ]<<<[<+<]>[>.>]
Запускаем. Пишем по очереди символы по одному, энтер после каждого. Чтобы завершить ввод массива – просто энтер без символа:
(venv) ➜ bf python bf_interpretator.py isort.bf 8 4 6 1 9 14689
Код программы и примеры загрузил на gist.
Компилятор Brainfuck на Python
Компилятор берет исходный код и превращает его в машинный исполняемый код. Не бойтесь, мы не будем писать в сложные по формату исполняемые файлы ассемблерные команды в виде байт. Поступим хитро. Сначала транслируем программу на BF в код на языке С, а потом обычным компилятором С транслируем код С в исполняемый файл.
Код обрамляется прелюдией, где мы подключаем стандартную библиотеку и инициализируем память. А также завершающими командами:
PRELUDE = """// brainfuck generated: #include <stdio.h> int main() { const int mem_size = 30000; char mem[mem_size]; memset(mem, 0, mem_size); int cur = 0; """ ENDING = """ return 0; } """
Далее код компилятора BF в Си. Все по таблице из Википедии:
def compile_to_c(bf_code): instr_ptr = 0 # индекс текущей инструкции кода (code) indent = 4 # смещение пробелами - для красоты c_code = PRELUDE # выполняем - пока не вылетели за пределы кода for command in bf_code: content = '' if command == '+': content = 'mem[cur]++;' elif command == '-': content = 'mem[cur]--;' elif command == '>': content = 'cur++;' elif command == '<': content = 'cur--;' elif command == '.': content = 'putchar(mem[cur]);' elif command == ',': content = 'mem[cur] = getchar();' elif command == '[': content = 'while(mem[cur]) {' elif command == ']': content = '}' instr_ptr += 1 # сдвигаем к следующей команде if content: if command == ']': indent -= 4 c_code += ' ' * indent + content + '\n' if command == '[': indent += 4 c_code += ENDING return c_code
Сохраняем С-код на диск и вызывем компилятор cc:
c_code = compile_to_c(code) c_file = f'{name}.c' with open(c_file, 'w') as f: f.write(c_code) os.system(f'cc {c_file} -o {name}.out')
Проверка:
(venv) ➜ bf python bf_compiler.py hello_world.bf ...тут какое-то предупреждение от компилятора... (venv) ➜ bf ./hello_world.bf.out Hello World!
Код на Си получится примерно такой (я сократил его значительно, чтобы не занимать много места в статье):
// brainfuck generated: #include <stdio.h> int main() { const int mem_size = 30000; char mem[mem_size]; memset(mem, 0, mem_size); int cur = 0; mem[cur]++; mem[cur]++; mem[cur]++; mem[cur]++; mem[cur]++; while(mem[cur]) { cur++; mem[cur]++; mem[cur]++; mem[cur]++; cur++; mem[cur]++; cur--; cur--; cur--; cur--; mem[cur]--; } cur++; mem[cur]++; mem[cur]++; putchar(mem[cur]); cur++; mem[cur]++; putchar(mem[cur]); mem[cur]++; mem[cur]++; mem[cur]++; mem[cur]++; mem[cur]++; mem[cur]++; putchar(mem[cur]); cur++; putchar(mem[cur]); return 0; }
Код компилятора в том же самом gist.
Замечания. В это варианте запятая будет работать не так, как в интерпретаторе выше. Поэтому код с сортировкой будет вести себя иначе. И второе: проверял компилятор на своей системе macOS, на Windows компилятор скорее всего не будет работать, если только вы его не запускаете из подсистемы Linux или Cygwin или подобных.
Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈