Assembler для Brainfuck

Одним холодным майским днем от скуки решил я таки приступить к изучению этого удивительного языка — Brainfuck'a.
Его ^[1] интерпретаторы ^[2] публиковали ^[3] на ^[4] Хабре ^[5] уже ^[6] очень ^[7] много ^[8] раз ^[9].
Но мне хотолось изучить поглубже сам язык и алгоритмы на нем, а не писать очередной интерпретатор. Поэтому было решено сделать из мухи слона компилятор какого-нибудь высокоуровневого языка в 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 и доступен тут ^[10]. Там же можно посмотреть примеры программ и написать свои.

Полезные ссылки

Алгоритмы на brainfuck ^[11] — я использовал оттуда алгоритмы умножения и деления.

BFDev ^[12] — удобное brainfuck-IDE, все программы тестировались в нём.

BrainFix ^[13] — высокоуровневый язык, транслируемый в brainfuck. Оттуда был взят алгоритм доступа к элементу массива с неизвестным в compile time индексом.

Автор: alhimik45

Источник ^[14]