Язык Brainfuck придумал еще в прошлом веке Urban Mueller. Автор, очевидно, хотел создать язык, обладающий минимальным набором команд, но формально позволяющий решить любую задачу. Разумеется, язык этот не мог иметь практического значения, но зато был бы очень интересен с точки зрения теории программирования.

Увы, его название, столь неблагозвучное для понимающих английский, фактически закрыло для языка возможность его официального признания и включения в учебники. Но тем не менее, язык этот довольно интересен и его стоит рассмотреть подробнее.

Итак, я напомню суть данного языка.

Имеется линейный набор ячеек для хранения данных. Имеется указатель на ячейку, который можно перемещать вдоль ряда ячеек. Набор команд языка содержит всего 8 односимвольных команд:
      "+" - прибавить единицу к значению в текущей ячейке;
      "-" - отнять единицу от значения в текущей ячейке;
      "<" - сдвинуть указатель ячеек на одну влево (к началу набора);
      ">" - сдвинуть указатель ячеек на одну вправо (к концу набора);
      "." - вывести на дисплей содержимое текущей ячейки;
      "," - ввести с клавиатуры один символ в текущую ячейку;
      "[" - если значение в текущей ячейке равно нулю, то перейти на оператор, стоящий после соответствующей по уровню вложения правой (закрывающей) скобки;
      "]" - если значение в текущей ячейке не равно нулю, то перейти на оператор, стоящий после соответствующей по уровню вложения левой (открывающей) скобки.

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

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

Как я уже говорил (и это очевидно), Brainfuck не имеет практического значения. Но лично меня он зантересовал просто потому, что и я сам в свое время придумал язык, который, правда, используется на практике как мной самим, так и многими другими людьми. Этот язык я назвал Ellochka (Эллочка) по имени одной известной людоедки (для тех, кому интересна история его создания, смотрите статью "Эллочка и компьютер").

Так вот, желая ознакомиться ближе со столь "малооператорным" языком, я тоже захотел иметь транслятор. Пользоваться чужими мне показалось неинтересным и я решил написать свой. И написать его я решил именно на Эллочке, поскольку считал использование "серьезных" языков для работы с таким "уродцем" даже несколько неэтичным (из пушки по воробьям, короче). А кроме того, мне хотелось написать транслятор именно на Эллочке (изначально вовсе не предназначенной для таких задач!), посмотреть, получится ли.

ИНТЕРПРЕТАТОР

Разумеется, прежде всего я стал писать интерпретатор. Но тут возник вот какой вопрос. Язык Brainfuck не имеет общепризнанного стандарта и многие вопросы при написании транслятора "повисают в воздухе". Например,

- размер ячеек данных? Один байт или больше?

- возможна ли работа с отрицательными числами?

- как обрабатываются посторонние символы?

- нет работы с файлами, как вводить данные, с клавиш - неудобно.

Правда, последний вопрос решился быстро. Как выяснилось, было принято "негласное расширение" языка, а именно, символ "!" (восклицательный знак) был использован для отделения блока команд от блока данных. И при наличии в программе такого блока, оператор "," считывал данные не с клавиатуры, а из этого блока, каждый раз используя следующий символ в списке. Правда, опять же не регламентировалось, является ли этот список замкнутым.

Прежде чем писать транслятор, я стал исследовать сам язык, стараясь создать на нем своеобразную "библиотеку процедур".

После некоторых трудов получилось следующее (сверху написано, какая из ячеек является текущей и какое у нее содержимое при выполнении данной команды):

      1) Обнуление данных в текущей ячейке
           [-]

      2) Копирование данных ячейки
           N00             NN0
           [>+>+<<-]>>[<<+>>-]

      3) Сложение данных P=X+N
           NX   0P
           [>+<-]

      4) Вычитание данных P=X-N
           NX   0P
           [>-<-]

      5) Умножение данных P=Y*X
           YX000                            0X00P
           [>[>+>+<<-]>>[<<+>>-]<[>>+<<-]<<-]

      6) Заполнение ячеек (без эха)
           [>,]

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

Итак, я стал писать интерпретатор. Рассказывать о нем подробно нет смысла, поскольку на самом деле Brainfuck язык столь простой, что и на Эллочке его интерпретатор получается достаточно компактным и его создание не вызвало трудностей или применения "особых приемов". Я просто сделал два варианта интерпретатора, "малую" и "большую" модели, различающиеся объемом обрабатываемого файла и величиной массива ячеек.

К сожалению, упомянутые выше вопросы мне пришлось решать директивным методом. А именно, я принял допустимый диапазон значений данных в ячейках от 0 до 255 и размер самих ячеек - 1 байт. Причина проста: операторы ввода и вывода в Brainfuck вводят один символ и выводят один символ, поэтому не имеет никакого смысла увеличивать размер ячейки. Что касается отрицательных чисел, то в языке нет операторов для проверки этого условия, сравнение возможно только с нулем. И поэтому использование отрицательных чисел тоже проблематично.

Посторонние символы я решил просто не обрабатывать, поэтому в тексте программы можно помещать любые комментарии (разумеется, не содержащие операторов самого языка). Однако, сам процесс интерпретации при этом будет замедляться.

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

КОМПИЛЯТОР

Как я уже писал, создание интерпретаторов оказалось очень простой и не слишком интересной задачей, с которой моя Эллочка справилась легко. И тогда я, конечно же, захотел написать компилятор, естественно, на той же Эллочке. Времени свободного у меня было мало и работа растянулась на многие месяцы, поэтому невозможно сказать, сколько чистого времени я потратил. Но главное, что есть результат: есть компилятор, написанный на Эллочке!

Работа его выглядит очень просто: в качестве параметра в командной строке подается имя файла с исходной программой на Brainfuck (файлы имеют расширение ".bf"), а на выходе получается файл с тем же именем и расширением ".com", готовый к исполнению.

Скажу сразу, что создание компилятора было гораздо интереснее, хотя опять же ввиду простоты обрабатываемого языка оказалось делом не сложным. Но тут было несколько путей и предстояло выбрать наилучший. В том смысле, что программы на BF часто содержат длинные последовательности одинаковых символов и хотя я и тут отказался от идеи поиска указанных ранее "типовых" последовательностей, обработка повторяющихся символов требовала своего решения. Какие есть варианты? Рассмотрим просто случай фрагмента "++++++++++" (10 знаков "+").

      1) call plus
         call plus
         .........
         call plus
      (повторение вызова 10 раз), при этом можно даже вообще обойтись без вызова, написав 10 раз оператор вроде "inc [bx]"

      2) mov cx,10
         call plus
      В самой процедуре простым циклом повторить "inc [bx]" заданное в cx число раз.

      3) mov ax,10
         add [bx],ax

Каждый из этих вариантов имеет свои плюсы. Вариант 1 очень прост и удобен с точки зрения написания компилятора. Вариант 3 позволяет получить наиболее быстрый код. Вариант 2 позволяет написать единообразную обработку всех операторов при компиляции.

Есть у них и минусы. Собственно говоря, если не проводить проверки на корректность операции, самый простой был бы вариант 1, а самый эффективный - 3. Но я хотел обязательно проверять все промежуточные ситуации на их корректность, а с этой точки зрения вариант 1 никуда не годится. Вариант 3 может оказаться рискованным и вызвать побочные эффекты при большом числе повторений, в то время как его быстродействие на современных машинах не будет заметно.

Взвесив все варианты, я выбрал вариант 2 как "золотую середину". При этом в самой процедуре, конечно же, проводятся все необходимые проверки.

Как и в случае с интерпретатором, я выбрал размер ячеек в 1 байт, а также предусмотрел возможность помещать в текст программы блок данных после восклицательного знака.

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

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

Во-первых, я в своем компиляторе добавил опцию отключать проверку. Теперь можно получать com-файлы с проверкой значений в ячейках или без такой проверки. Во-вторых, отрицательные числа в программах на BF все же используются, да и размер ячеек в этих программах превышает 1 байт. Правда, на самом деле возникает просто неконтролируемое переполнение, но видимо, авторы программ на это и рассчитывали, не знаю. Лучше работать с проверкой!

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

Еще один вопрос при написании компилятора - это организация обращений, хранение данных и т.д. Поскольку компилятор я писал на Эллочке, не очень для этого подходящей, я старался в первую очередь максимально упростить сам процесс компиляции.

Главное, надо было решить, в сколько проходов будет проводиться компиляция. Поскольку размер кода заранее неизвестен ввиду наличия циклов и повторяющихся последовательностей операторов (напомню, был выбран вариант 2 и поэтому простой подсчет числа операторов в исходной программе не мог дать информацию о размере конечного кода), логично было сделать транслятор двухпроходным. Первый проход обеспечивает накопление кодов готовой программы, а второй - определяет текущие адреса переходов и записывает их на оставленные пустые места.

Но я не хотел делать два прохода, главным образом потому, что сама Эллочка - язык интерпретируемый (пока...) и работает не слишком быстро (на моей слабой машине), а каждый проход - это лишнее время, и не маленькое. Кроме того, этот путь уж очень "в лоб", что опять же просто неинтересно.

Для того, чтобы транслятор был однопроходным, необходимо все адреса переходов определять сразу. Сделать это прямо - невозможно, значит, надо все переходы в получаемой программе сделать не прямыми, а косвенными, создав в com-файле таблицу адресов. Замечу по ходу, что я вообще люблю везде использовать косвенную адресацию, она всегда гораздо более гибкая и красивая.

Итак, был создан "базовый блок", включающий в себя процедуры обработки всех операторов языка BF, а также блок аварийных сообщений, блок инициализации, блок завершения и зарезервированы места для хранения данных. Блок, разумеется, был написан на ассемблере. На моем сайте в разделе "Исходники" можно скачать архив с набором всех промежуточных файлов, здесь я не буду их дублировать.

Блок этот был оттранслирован и скомпонован, в результате чего получились com-файл и файл листинга. На основе файла листинга была составлена схема заполнения таблицы переходов, а машинный код процедур и обработки ошибок был в виде фрагмента выделен из com-файла и преобразован в цифры, поскольку программа на Эллочке не может хранить в себе управляющие символы (я не хотел делать вспомогательные файлы, весь компилятор должен был состоять из одного файла "bfcomp.ela"). Кстати, программа для такого преобразования тоже была написана на Эллочке и есть в упомянутом выше архиве.

Разумеется, мне пришлось не один раз проделывать всю эту процедуру, поскольку выявлялись ошибки, а также приходили новые идеи по усовершенствованию процесса.

В конечном итоге схема работы компилятора выглядит следующим образом:

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

2) Последовательность команд программы на BF переводится в машинные коды по варианту 2, т.е. вышеприведенная последовательность "++++++++++" переводится в последовательность

mov cl,10

call [adrplus]

Используется именно регистр "cl", а не "cx", поскольку это короче, а повторы больше чем 255 раз - экзотика (но этот случай также предусмотрен в компиляторе). В области с именем "adrplus" хранится адрес процедуры выполнения оператора "+".

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

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

Скобки, встречающиеся в исходной программе, также преобразуются в коды процессора, но при этом еще производится запись в специальный массив текущих адресов этих скобок. Данные записываются в стекоподобную структуру и при этом подсчитывается общее количество скобок в исходной программе.

3) Создается результирующий com-файл, в который записывается хранящийся в теле компилятора "постоянный код" (процедуры обработки операторов, сообщения об ошибках, заставка компилятора и т.д.).

4) Данные из массива с координатами скобок записываются в com-файл вслед за "постоянным кодом".

5) Далее в com-файл записываются данные из массива кодов процессора, заполненного на этапе 2 (замечу, что для ускорения данной операции запись производится через промежуточный файл, но это связано не с самой компиляцией, а просто с низкоскоростными особенностями Эллочки. Файл затем удаляется и никто его не видит.), а затем пишется команда завершения.

6) Если исходная программа на BF содержала данные для ввода, то этот набор данных записывается вслед за кодом, записанным в пункте 5.

7) На основе накопленных данных о длине кода и прочих характеристиках, заполняется таблица косвенных переходов, куда помещаются стартовый адрес запуска, адрес блока данных и т.д.

Сам процесс компиляции "для придания солидности", а также для контроля, сопровождается сообщениями о выполнении определенных этапов работы с указанием текущего времени.

Рекомендую посмотреть исходные тексты как самого компилятора, так и вспомогательных файлов, которые были использованы на стадии его разработки.

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

Что касается примеров программ на Brainfuck, то помещать чужие примеры - не хочется, а писать свои - просто нет времени. Тем более, что вопрос, например, деления, средствами этого языка решить не так просто (если возможно вообще в силу отсутствия безусловных переходов).

Поэтому приведенные там примеры не только не имеют практического смысла, они и вообще не имеют смысла, их назначение - просто быть тестом для компиляции и показать, что же такое этот странный язык.

Я вполне признаю, что сам процесс программирования на BF - занятие весьма творческое, увлекательное и даже полезное. Но лично у меня просто нет времени этим всерьез заниматься, если у кого-то оно есть - желаю удачи и надеюсь, что созданные мной трансляторы им пригодятся. Единственная просьба - присылайте свои отзывы, если будете пользоваться трансляторами.

Для выполнения программ на Эллочке (в том числе и трансляторов BF) нужен интерпретатор Эллочки. Эту программу - "Dikar" - можно также скачать на моем сайте, как и десятки других утилит на Эллочке, от увлекательных игровых и полезных бытовых до серьезных математических. Смотрите раздел "Программы".