Одним холодным майским днем от скуки решил я таки приступить к изучению этого удивительного языка — Brainfuck'a.
Его интерпретаторы публиковали на Хабре уже очень много раз.
Но мне хотолось изучить поглубже сам язык и алгоритмы на нем, а не писать очередной интерпретатор. Поэтому было решено сделать из мухи слона компилятор какого-нибудь высокоуровневого языка в brainfuck.
Однако очень быстро начался реальный brainfuck: отсутствие оператора if, отсутствие произвольного доступа к ячейкам и куча других проблем сразу свалилась на меня. Пришлось повременить с высокоуровневым языком и сделать для начала ассемблер, в который и будет компилироваться высокоуровневый язык.
О реализации ассемблера под катом.
Реализация основных частей
Для удобства лента была разделена на несколько частей:
- Регистры
- Стек
- Временные ячейки и флаговые ячейки
- Остальная память — используется для хранения массивов и строк
Транслятор предполагает, что выполнение программы начинается на нулевой ячейке заполненной нулями ленты. Лента должна быть закольцованной.
Регистры
Это самая главная часть ассемблера. Именно с ними чаще всего придется взаимодействовать. В регистры можно помещать числа (помним, что в brainfuck'e числа ограничены 255) и символы, прибавлять к ним числа и значения других регистров, отнимать числа и значения других регистров, умножать на другие регистры, делить на другие регистры и сравнивать друг с другом.
В трансляторе используются четыре регистра: ax, bx, cx, dx — по аналогии с ассемблером x86, каждый из которых представлен одной ячейкой памяти.
Примеры:
mov ax 5 // поместили в ax 5
mov bx 6 // а в bx 6
sub ax bx // теперь в ax 255
mov cx 12
mov dx 2
mul cx dx // в cx теперь 24
mov dx 10
div cx dx // деление с остатком: в cx - 2, в dx - 4
Стек
В левую сторону от нулевой ячейки начинается стек. Он хранится примерно по принципу си-строк и может быть любого размера, однако нужно помнить, что память закольцованна и очень большое количество положенных на стек элементов могут попортить другие ваши данные.
Для того, чтобы класть и снимать значения со стека есть команды push и pop, например:
push ax
push 5
pop bx
pop cx
Однако у хранения в виде си-строк есть один недостаток: нельзя на стек положить ноль, так как ноль служит показателем вершины стека. Конечно, можно было организовать и нормальный стек, но тогда его длина была бы ограничена 256 элементами.
Временные ячейки и флаговые ячейки
Временные ячейки используются для промежуточных вычислений в сложных операциях. Три флаговые ячейки используются в операции сравнения, подробнее об этом ниже.
Массивы
Массивы — диапазоны ячеек, к которым можно осуществить доступ по индексу:
array test 10 // массив под именем test из десяти ячеек
set test 0 42 // установили нулевой элемент массива в значение 42
get test 0 ax // получили в ax нулевой элемент массива
Кстати, индексом может быть регистр, содержащий, например, пользовательский ввод, но при этом обратиться к элементам, с индексами больше 255 невозможно.
Строки
Строки объявляются ключевым словом string:
string hello "Hello, World!" // объявили строку hello
puts hello // вывод строки
Строки размещаются в секции массивов и при запуске программы инициализируюся.
Со строками можно обращаться как с массивами:
get hello 0 ax
put ax // выведет 'H'
Основные конструкции
Ввод-вывод
Есть три операции ввода-вывода:
take ax // занесет в регистр ax код введеного символа
put ax // выведет символ, код которого в ax
puts str // выведет строку под именем str
Кстати, командой puts можно печатать и обычные массивы (до первого нуля в нём).
Организация циклов
В принципе, ассемблерные jump'ы тоже можно организовать, но это несколько геморройно, поэтому циклы больше похожи на бейсиковские:
while ax // в while можно писать один из регистров
// do smth.
endwhile
Этот цикл будет что-то делать, пока регистр ax не станет равен нулю.
Сравнения
Сравнение сделано в стиле ассемблера. Чтобы что-то сравнить, нужно применить команду cmp к регистрам:
mov ax 2
mov bx 1
cmp ax bx
После этой команды изменяются значения флаговых ячеек. Их три: на равенство, на меньше и на больше. Если первый регистр равен второму, то флаг равенства устанавливается в ноль, если первый регистр меньше, то в ноль устанавливается второй флаг, а если больше, то третий.
Пользоваться результатом сравнения можно так:
cmp ax bx // флаговые ячейки установлены и не изменяются до следующего сравнения
ne // не равно
// действия на случай, если регистры не равны
end
nl // не меньше
// do
end
ng // не больше
// do
end
eq // равно
// do
end
lt // меньше
// do
end
gt // больше
// do
end
Заключение
Ассемблер сделан с простым синтаксисом и предназначен больше для автоматический генерации, хотя на нем и так можно писать программы. Транслятор написан на Ruby и доступен тут. Там же можно посмотреть примеры программ и написать свои.
Полезные ссылки
Алгоритмы на brainfuck — я использовал оттуда алгоритмы умножения и деления.
BFDev — удобное brainfuck-IDE, все программы тестировались в нём.
BrainFix — высокоуровневый язык, транслируемый в brainfuck. Оттуда был взят алгоритм доступа к элементу массива с неизвестным в compile time индексом.
Автор: alhimik45
