Метка: pyway

Есть мнение, что каждый программист должен написать в жизни хотя бы один язык программирования, либо реализовать уже существующий, но своими руками. В качестве примера мы начнем с самого простого и создадим 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 👈