Интерпретатор brainfuck

Сегодня я решил что-нибудь написать на python. Что-нибудь простенькое, но не очень. Решил остановиться на интерпретаторе brainfuck.

Для тех, кто не знает, о чем это я говорю, поясняю: язык brainfuck для хранения данных использует ячейки (по-хорошему бесконечное число ячеек) и состоит всего из восьми команд, поэтому выучить его будет легко.

Вот эти команды:

Итак, вернемся к интерпретатору. Программный код будем считывать со стандартного ввода (если кто захочет, может переделать на считывание из файла).

Итак, будем считать, что прочитали (с помощью встроенной функции input()), затем обработаем строки, удалив все нежелательные символы.

def parse(code):
    new = ''
    for c in code:
        if c in '><+-.,[]':
            new += c
    return new

Или проще:

def parse(code):
    return ''.join(c for c in code if c in '><+-.,[]')

Далее сопоставим начало и конец каждого цикла (кода, заключенного в []).

def block(code):
    opened = []
    blocks = {}
    for i in range(len(code)):
        if code[i] == '[':
            opened.append(i)
        elif code[i] == ']':
            blocks[i] = opened[-1]
            blocks[opened.pop()] = i
    return blocks

Функция возвращает словарь {начало:конец и конец:начало} для быстрой навигации по программному коду.

Ну и, собственно, сам интерпретатор:

def run(code):
    code = parse(code)
    blocks = block(code)
    x = i = 0
    bf = {0: 0}
    while i < len(code):
        sym = code[i]
        if sym == '>':
            x += 1
            bf.setdefault(x, 0)
        elif sym == '<':
            x -= 1
        elif sym == '+':
            bf[x] += 1
        elif sym == '-':
            bf[x] -= 1
        elif sym == '.':
            print(chr(bf[x]), end='')
        elif sym == ',':
            bf[x] = int(input('Input: '))
        elif sym == '[':
            if not bf[x]: i = blocks[i]
        elif sym == ']':
            if bf[x]: i = blocks[i]
        i += 1

Как это работает? Сначала обрабатывается код, составляется список циклов. Далее ячейки, которые я реализовал в качестве словаря. Далее, разбор brainfuck-программы.

Если символ '>', то увеличиваем x (номер ячейки) на единицу, и, если ячейки с таким номером в словаре нет, инициализируем нулем (методом setdefault).

Если '<', то уменьшаем номер ячейки на 1. Так как вообще отрицательные ячейки не разрешены, то и ячейка всегда найдется (если хотите, можете добавить поддержку и отрицательных номеров ячеек). Если символ '[', то проверяем текущую ячейку, и, если она 0, переходим в конец цикла.

Полный код интерпретатора brainfuck:

def block(code):
    opened = []
    blocks = {}
    for i in range(len(code)):
        if code[i] == '[':
            opened.append(i)
        elif code[i] == ']':
            blocks[i] = opened[-1]
            blocks[opened.pop()] = i
    return blocks

def parse(code):
    return ''.join(c for c in code if c in '><+-.,[]')

def run(code):
    code = parse(code)
    x = i = 0
    bf = {0: 0}
    blocks = block(code)
    l = len(code)
    while i < l:
        sym = code[i]
        if sym == '>':
            x += 1
            bf.setdefault(x, 0)
        elif sym == '<':
            x -= 1
        elif sym == '+':
            bf[x] += 1
        elif sym == '-':
            bf[x] -= 1
        elif sym == '.':
            print(chr(bf[x]), end='')
        elif sym == ',':
            bf[x] = int(input('Input: '))
        elif sym == '[':
            if not bf[x]: i = blocks[i]
        elif sym == ']':
            if bf[x]: i = blocks[i]
        i += 1

code = input()
run(code)

И напоследок, hello world на brainfuck. Заодно можете проверить работу интерпретатора :)

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