Компилятор Befunge на Python

В процессе подготовки к курсу «Основы компиляторов» для студентов 4-го курса я изучал различные эзотерические языки программирования. Вот хорошая статья на эту тему. В статье самым интересным мне показался язык Befunge (Крис Пресс, 1993 год), особо отмечу три его особенности:

1. Поле программы представляет собой двумерный тор, т.е. физически это прямоугольная матрица команд-символов, замкнутая по верхней(нижней) границе и по левому(правому) столбцу. По полю передвигается указатель команд (каждая команда – это некий символ с координатами x,y), выполняет команду и двигается дальше. Движение может быть во все 4 стороны (по умолчанию направо с точки 0,0), а при выходе за пределы «поля» указатель появляется с противоположной стороны.
2. В языке есть две команды (p, g), которые меняют само поле, т.е. программа «самопереписывается» в процессе выполнения. Код программы на старте может не быть равен коду на финише. Стартовала программе «123pgpg##@», а закончила работать программа «ABC@1@2@3.14» (не правильный пример).
3. Крис Пресси отмечал, что хотел создать язык, максимально сложный для компиляции. Де-факто это так, создать именно компилятор, который делает из программы exe-файлы адски сложно, я нашел информацию, что на Си кто-то смог это сделать… Лучше всего создавать транслятор из языка в код на Python, который я все равно называю компилятором для простоты.

Поле для программы по стандарту 1993-го года состоит из 25 строк по 80 символов в каждой. Всего в языке 36 команд, каждая из которых это символ таблицы ASCII. Подробную информацию смотрите на википедии, я приведу оттуда краткое описание:

Команды перемещение (9):

> Двигаться вправо
< Двигаться влево
^ Двигаться вверх
v Двигаться вниз
_ Двигаться вправо, если на вершине стека 0, иначе — влево.
| Двигаться вниз, если на вершине стека 0, иначе — вверх.
? Двигаться в случайном направлении
# Пропустить следующую ячейку («трамплин»)
@ Конец программы

Команды манипулирование со стеком (3):

: Поместить в стек копию вершины
\ Обменять местами вершину и подвершину
$ Удалить вершину

Команды модификация кода программы (2):
p «PUT»: со стека извлекаются координаты ячейки и ASCII-код символа, который помещается по этим координатам
g «GET»: со стека извлекаются координаты ячейки; ASCII-код символа по этим координатам помещается в стек

Команды константы (2):

0-9 Поместить число в стек
" Начало/конец символьного режима, в котором ASCII-коды всех текущих символов программы помещаются в стек

Стековые арифметические операции (5):

+ Сложение вершины и подвершины
— Вычитание вершины и подвершины
* Умножение вершины и подвершины
/ Целочисленное деление
% Остаток от деления

Команды для стека и логические операции (2):

! Отрицание: нуль на вершине заменяется на 1, ненулевое значение — на 0
` Сравнение «больше, чем»: если подвершина больше вершины, в стек помещается 1, иначе 0

Команды ввода-вывода (4):

& Запросить у пользователя число и поместить его в стек
~ Запросить у пользователя символ и поместить в стек его ASCII-код
. Распечатать вершину стека как целое число
, Распечатать символ, соответствующий ASCII-коду на вершине стека

Я решил написать компилятор (интерпретатор) языка Befunge на Python по правилам 1993-го года с парой ограничений: 1) поле не 25х80 символов, а минимальное по ширине и высоте текстового блока, 2) поле не закольцовано в тор, т.е. не обрабатывается выход за границы с перескакиванием на противоположную сторону. Это не лень (хотя, кого я обманываю?), для небольших примеров все прекрасно работает, а допилить поле до реального тора довольно просто, было бы желание.

Код вышел местами излишне «в лоб», но это связано с тем, что он для студентов и его задача – быть максимально понятным, а не ужатым до пары строк на китайском языке.

Часть 1

Код приводится от начала до конца с одним исключением (которое будет оговорено), его можно скопировать в файл и запускать. Полный текст доступен по ссылке rentry.co/ivansedov-befunge, выкладываться на GitHub мне пока рано. К слову, там есть около 20 реализаций языка Befunge, но код либо на Си (не мой язык), либо на Python, но такой сложный, что я не решился погружаться. Однако, там можно брать примеры программ для тестов, например, тут github.com/causal-agent/befungee

from sys import *
import time
import random

Импортируем библиотеки:

1. Библиотека sys нужна для того, чтобы получить имя файла-программы. У меня компилятор назывался bbb.py, тестовый пример в этом же каталоге 1.bf, сам Python версии 3.7, а потому вызов программы в консоли выглядел так: python3 bbb.py 1.bf
2. Библиотека time в принципе не нужна, использовалась при тестах, когда требовалось делать 0,5-1,0 секунду задержки между вызовами работы указателя команд.
3. Библиотека random используется один раз для реализации команды «?» (знак вопроса), которая случайным образом меняет направление движения указателя команд. Да-да, в Befunge есть команда-аналог дорожного камня Ильи Муромца, попав на которую указатель «подбрасывает монету» и выбирает куда идти (1 вверх, 2 вправо, 3 вниз, 4 влево). Программа может реально «пойти назад» и выполнятся в обратном порядке.

class Pointer:
    def __init__(self, x=0, y=0, vector=2, value=None):
        self.x = x
        self.y = y
        self.vector = vector
        self.value = value
        self.stack = []
        self.stack_sf = 0

    def __str__(self):
        return 'Point ({},{}) vektor:{} value:{} stack_sf:{} stack:{}'.format(self.x, self.y, self.vector, self.value, self.stack_sf, self.stack)

    def step(self):
        if self.vector == 1:
            self.x -= 1
        elif self.vector == 2:
            self.y += 1
        elif self.vector == 3:
            self.x += 1
        elif self.vector == 4:
            self.y -= 1

    def action(self):
	# Пока тут пусто, смотрите вторую часть

Основной класс, использующийся в программе: Pointer (указатель), имеет 6 свойств и 2 метода. Свойства: 1) координата х (изначально=0), 2) координата у (изначально=0), 3) vector (направление движения, изначально=2 направо), 4) value (значение поля, которое находится по координате x,y, изначально=None), это и есть, собственно, команда, которую надо выполнить, 5) stack (стек программы, изначально=[]) и 6) stack_st (флаг для ввода строк, изначально=0).

У класса два метода: 1) step() шаг указателя, совершенно без всяких проверок и тестов меняет значения координат x,y в зависимости от направления в vector и 2) action() это сердце компилятора, выполнение текущей команды программы. Код action() я приведу во второй части, чтобы он пока не отвлекал от логики.

# ===============================
# =           Функции           =
# ===============================

def open_file(name):
    data = open(name, 'r').read()
    return data

def field_print():
    for row in A:
        for elem in row:
            print(elem, end='')
        print()  

Две вспомогательные функции: 1) open_file(name) открывает файл по присланному имени, читает его и возвращает содержимое и 2) field_print() печать содержимого массива А, в котором находятся символы программы. Создание массива А приведено чуть ниже.

# ===========================================
# =           Начальные настройки           =
# ===========================================

numbers = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
operators = ['+', '-', '*', '/', '%']
point = Pointer()                           # Указатель исполнителя
text = open_file(argv[1]).split("\n")       # Считать программу
n = len(text)                               # n = всего строк
m = 0                                       # m = всего столбцов

# Поиск максимальной строки (это и будет m)
for line in text:
    if len(line) > m:
        m = len(line)

# Поле программы (массив n на m пробелов)
A = [' '] * n
for i in range(n):
    A[i] = [' '] * m

# Забиваем символами программы поле
for i in range(len(text)):
    for j in range(len(text[i])):
        A[i][j] = text[i][j]

Основные настройки программы. В список numbers кладем все цифры от 0 до 9, которые можно писать в программе (10 уже не влезет, два символа). В список operators кладем основные арифметические операторы. Создаем объект point = Pointer(настройки по-умолчанию), с которым будем работать все время…

В переменную text кладем прочитанный текст исполняемой программы, разбитый по символу «новая строка». В результате text состоит из нескольких строк текста разной длины, которые надо поместить в прямоугольный массив пробелов по своим местам. Количество строк найти легко n = len(text), а вот количество столбцов надо вычислить, исходя из максимальной длины строк, входящих в text. Я не нашел другого способа, как сделать это в лоб: пройтись по всем строкам и найти ту, у которой максимальная длина. Имея на руках n и m (число строк и число столбцов будущего поля) можно сделать двумерный массив, заполнить его пробелами, а потом пробежаться по text, чтобы расставить символы по своим местам.

В результате получается прямоугольник символов, между которыми пробелы и все это есть двумерная матрица n на m. После этих настроек можно вызвать функцию field_print() и убедится в том, что все выглядит красиво, ничего не поплыло и не нарушило положения.

# ==========================================
# =           Основная программа           =
# ==========================================

# field_print()

while point.value != '@':
    try:
        point.value = A[point.x][point.y]       # 1) Считали команду под point
        point.action()                          # 2) Выполнили команду
        # print(point)                            # 3) Отладка: вывод указателя
        # time.sleep(0.5)                         # 4) Отладка: задержка 0.5 cек
    except IndexError:                          # Если выход за поле = стоп программа
        print('Кончился стек или вышли за поле')
        break

# field_print()
print()

Все завершается основной программой (цикл), до и после которой можно вывести на экран поле (иногда полезно). Цикл крутится до тех пор, пока указатель не будет указывать на символ «@» (амперсанд, собачка, конец программы). Внутри цикла каждый раз делается 4 действия:

1. В свойство point.value считывается символ, который находится в массиве А по координатам point.x, point.y
2. Вызывается метод point.action(), в котором происходит выполнение текущей (только что прочитанной) команды
3. На экран выводится указатель (все свойства)
4. Делается задержка перед следующей итерацией (0,1 сек – 0,5 сек)

3 и 4 пункты совершенно не обязательны (они даже закомментированы), но для тестирования рекомендую их использовать. Все действия внутри цикла происходят с перехватом ошибки IndexError (ошибка выхода за пределы индекса), это позволяет перехватывать две основные ошибки компилятора:

1. Мы обратились к стеку, а там нет значений
2. Мы случайно вышли за пределы программы(массива) по ширине или высоте

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

Часть 2

Теперь пришло время самого главного кода – содержимое метода point.action() класса Pointer. Все, что приводится ниже, надо вставить туда, где было написано:

    def action(self):
	# Пока тут пусто, смотрите вторую часть

Обратите внимание на отступы:

        if self.value == '"' and self.stack_sf == 0:                # Первая, вторая "
            self.stack_sf = 1
        elif self.value == '"' and self.stack_sf == 1:
            self.stack_sf = 0
        elif self.stack_sf == 1:                                    # "Hello" в стек кодами
            self.stack.append(ord(self.value))
        elif self.value in numbers and self.stack_sf == 0:
            # 123 в стек цифрами
            self.stack.append(int(self.value))

Фактически, код внутри action() это много-много условий, каждое из которых выполняется когда под указателем находится именно эта команда. Все начинается с условия «если текущая команда = кавычке и флаг начала строки stack_sf=0», в этом случае флаг поднимается в 1. Мы вошли в строку.

(Иначе)если текущая команда = кавычке и флаг поднят в 1, то это значит, что кавычка нашлась второй раз и надо прекратить вводить строку (флаг stack_sf опускается в 0). Мы вышли из строки.

(Иначе)если два первых условия не сработали и флаг stack_sf=1, то мы «находимся внутри строки» и надо добавить в стек код текущего символа. Не сам символ, а именно его ASCII-код.

(Иначе)если текущий символ среди элементов numbers и флаг stack_sf=0, то это, во-первых, цифра и, во-вторых, мы не внутри строки, нам надо добавить в стек текущий символ = цифре. Добавить не код символа, а именно сам символ. Все же помнят, что есть цифра 1, а у нее код=49. Так вот, если мы внутри строки, то надо добавить в стек 49, а если просто в программе, то команда 1 должна добавить в стек 1.

Здесь и далее все условия будут elif (иначе, если…), поэтому я буду писать их просто «если». Кроме того, все условия двойные, надо проверить текущий символ на равенство команде и еще тот факт, что мы не находимся внутри строки (внутри строки все символы обрабатываются по-другому). Можно было написать все это более оптимизировано, но это решение в лоб позволяет акцентировать на этом внимание.

        elif self.value in operators and self.stack_sf == 0:
            b = self.stack.pop()
            a = self.stack.pop()
            if self.value == '+':
                res = a + b                                         # a+b в стек
            elif self.value == '-':
                res = a - b                                         # a-b в стек
            elif self.value == '*':
                res = a * b                                         # a*b в стек
            elif self.value == '/':
                if b == 0:
                    res = 0
                else:
                    res = a // b                                    # a//b в стек
            elif self.value == '%':
                res = a % b                                         # a%b в стек
            self.stack.append(res)

Если текущий символ среди operators (и stack_sf=0), то значит мы попали на арифметическую операцию. Все они совершенно одинаковые: 1) со стека снимается (с удалением) число b, 2) со стека снимается (с удалением) число a, 3) res = значение операции между a и b, 4) res кладется на стек. При деление на 0 ответом является 0, хотя автор языка предусматривал выбор 0 либо 1.

        elif self.value == '!' and self.stack_sf == 0:
            a = self.stack.pop()
            if a == 0:
                a = 1
            else:
                a = 0
            # 0->1, 1->0
            self.stack.append(a)

        elif self.value == '`' and self.stack_sf == 0:
            a = self.stack.pop()        # вершина
            b = self.stack.pop()        # подвершина
            if b > a:
                res = 1
            else:
                res = 0
            # b>a -> 1|0
            self.stack.append(res)

Если текущий символ «!», то надо сделать замену головы (вершины) стека: был 0 – станет 1, было что-то отличное от 0 – станет 1. Если текущий символ «`» (апостроф), то надо проверить вершину и подвершину: 1) если подвершина больше вершины, то на стек кладется 1, 2) если подвершина меньше(или равна) вершины, то на стек кладется 0. Обратите внимание, что всегда при снятие элементов для сравнения они именно снимаются (удаляются), а не копируются.

        elif self.value == '?' and self.stack_sf == 0:
            # ? (случайное направление)
            a = random.randint(1, 4)
            self.vector = a

        elif self.value == ':' and self.stack_sf == 0:              # голова голова
            last = self.stack.pop()
            self.stack.append(last)
            self.stack.append(last)

        elif self.value == '\\' and self.stack_sf == 0:             # ab => ba
            a = self.stack.pop()
            b = self.stack.pop()
            self.stack.append(a)
            self.stack.append(b)

Если текущий символ «?», то надо выбрать случайное направление и пойти по нему. Используем функцию random.randint(1, 4), которая генерит числа 1,2,3,4 и заносим новое значение в point.vector

Если текущий символ «:», то помещаем в стек копию вершины стека, т.е. считываем ее, а потом добавляем в стек два раза.

Если текущий символ «\\» (обратная косая), то надо поменять местами вершину и подвершину. Достаем два числа, кладем их на стек в обратном порядке.

        elif self.value == '#' and self.stack_sf == 0:              # прыжок "вперед"
            self.step()

        elif self.value == ',' and self.stack_sf == 0:              # голова=65=A
            value = self.stack.pop()
            print(chr(value), end='')

        elif self.value == '.' and self.stack_sf == 0:              # Print голова
            a = self.stack.pop()
            print(a, end='')

Если текущий символ «#» (решетка), то надо перепрыгнуть следующую (по направлению) команду. Обратите внимание на то, что в конце action() есть безусловной прыжок вперед self.step(), он позволяет передвинутся вперед на следующую команду. Записав в обработку «#» self.step() мы фактически делаем два прыжка и «обскакиваем» следующую команду после «#».

Если текущий символ «,» (запятая), то надо распечатать символ, ASCII-код которого лежит на вершине стека. Если там лежит число 65, то на экран надо вывести «A».

Если текущий символ «.» (точка), то надо распечатать число, которое лежит на вершине стека, именно как число. Если там лежит 65, то надо вывести на экран «65». В обоих случая при выводе задается параметр end=’’, чтобы не было перехода на новую строку.

        elif self.value == '_' and self.stack_sf == 0:              # Условие "_"
            test = self.stack.pop()
            if test == 0:
                # голова = 0, вправо(2)
                self.vector = 2
            else:
                # голова !=0, влево(4)
                self.vector = 4

        elif self.value == '|' and self.stack_sf == 0:              # Условие "|"
            test = self.stack.pop()
            if test == 0:
                self.vector = 3
            else:
                self.vector = 1

Если текущий символ «_» (нижнее подчеркивание), то надо сделать проверку по горизонтали. Снимаем со стека число для проверки (test), если оно =0, то двигаемся вправо (vector=2), если оно !=0, то двигаемся влево (vector=4).

Если текущий символ = «|» (вертикальная черта), то надо сделать проверку по вертикали. Снимаем со стека число (test), если оно =0, то двигаемся вниз (vector=3), иначе двигаемся вверх (vector=1).

        elif self.value == '$' and self.stack_sf == 0:              # удалить голову
            self.stack.pop()

        elif self.value == '~' and self.stack_sf == 0:              # Input: A => 65
            val = input('Введите символ: ')
            self.stack.append(ord(val[0]))

        elif self.value == '&' and self.stack_sf == 0:              # Input: 65 => 65
            val = int(input('Введите число: '))
            self.stack.append((val))

        elif self.value == 'p' and self.stack_sf == 0:              # x, y, symcode
            x = self.stack.pop()                                    # A(x,y) = symcode
            y = self.stack.pop()
            symcode = self.stack.pop()
            A[x][y] = chr(symcode)

        # x, y, value=A(x,y)
        elif self.value == 'g' and self.stack_sf == 0:
            x = self.stack.pop()                                    # ord(value) => стек
            y = self.stack.pop()
            value = A[x][y]
            self.stack.append(ord(value))

Если текущий символ = «$», то надо удалить вершину. Делаем простой pop().

Если текущий символ = «~» (тильда), то просим у пользователя символ и кладем в стек его ASCII-код. Прислал пользователь «А» (английское), мы должны положить в стек 65. На всякий случай класть будем val[0], а то пользователь может ввести «Apple» и переводить его в код не получится.

Если текущий символ = «&» (амперсанд), то мы просим у пользователя число и кладем число в стек. Ввели 65, в стек надо положить 65.

Теперь две самые сложные команды.

Если текущий символ = «p», то надо извлечь со стека координаты ячейки и ASCII-код символа, а потом на поле А положить по этим координатам данный символ. Допустим, в стеке лежало 1,2,65 и мы достали (1,2) и 65, в ячейку (1,2) надо положить символ «А». Еще раз отмечаю: достали три числа, а по координатам положили символ.

Если текущий символ = «g», то со стека извлекаются координаты ячейки, по ним на поле ищется ячейка, оттуда достается символ и его ASCII-код помещается в стек. Допустим, на поле в ячейке (2,3) лежал себе символ «B», у нас текущей командой вышла «g» и мы достали со стека числа 2,3. В этом случае мы идем по координатам (2,3), достаем оттуда символ «B», переводим его в число 66 (код символа B) и кладем 66 на стек.

        elif self.value == '>' and self.stack_sf == 0:              # >
            self.vector = 2
        elif self.value == '<' and self.stack_sf == 0:              # <
            self.vector = 4
        elif self.value == '^' and self.stack_sf == 0:              # ^
            self.vector = 1
        elif self.value == 'v' and self.stack_sf == 0:              # v
            self.vector = 3
        self.step()                                                 # Один шаг

Ну, и последние строки кода: организация перемещения указателя по полю. Тут все просто: смотрим на символ и меняем направление (vector). В самом конце функции action() стоит self.step(), который делает один шаг в текущем направлении. Таким образом, action() это и выполнение действия и шаг на следующий символ.

Заключение

Писать данный компилятор было одно удовольствие. А сколько радости принесли моменты, когда закидываешь в программу некий код, а он исполняется (правильно!) и ты это наблюдаешь! При работе сильно помог сайт befungius.aurlien.net, на котором автор выложил онлайн-интерпретатор Befunge (на JavaScript). Вот его видео с какой-то конференции www.youtube.com/watch?v=oCPT3L33848, на котором он рассказывает о языке.

Для тестирования можно использовать практически любую программу на Befunge, кроме тех, которые требуют поля как тора, т.е. имеют переходы в разные стороны света. Для некоторых программ надо видеть само поле (например, программа-счетчик меняет координату А[0][1]), так что либо в вставляйте вывод этой координаты на экран, либо выводите всю матрицу А после каждого шага.

В любом случае это не вылизанная до блеска программа, а учебный код, который можно дописывать и править. Опечатки возможны, хотя я тестировал его много раз. Критика не приветствуется, но и не возбраняется. Всем удачи и хорошего кода.

Hello world!

0"!dlrow olleH">:#,_@

Bazz

0> 1+:3%v
>^  v%5:_:5% v
,v.:_v     v0_0"zzub"v
"v         #
     >0"zzub"v
"   v"fizz"<         <
^<         $<>:#,_v
    >      #^^#   <

Фибоначчи

62*1+v>01p001>+v>\:02p\:02gv
     0       ^             <
     .         :p
     "         .1
        v 0," "<0
     "  >1g12-+:|
     ,          @
     >^

Count

>91+:9`v
p   v  _v
    >$0 v
^ 01+*68<

А вот это не сработает, выход за пределы поля

0>:00p58*`#@_0>:01p78vv$$<
@^+1g00,+55_v# !`\+*9<>4v$
@v30p20"?~^"< ^+1g10,+*8<$
@>p0\>\::*::882**02g*0v >^
`*:*" d":+*:-*"[Z"+g3 < |<
v-*"[Z"+g30*g20**288\--\<#
>2**5#>8*:*/00g"P"*58*:*v^
v*288 p20/**288:+*"[Z"+-<:
>*%03 p58*:*/01g"3"* v>::^
   \_^#!:-1\+-*2*:*85<^

Ссылки и дополнительные материалы:

1. Полный код
2. Онлайн-версия
3. Она же на JavaScript
4. Документация (английский)
5. Статья на вики (английский)