Pull to refresh

Интерпретатор Brainfuck на Brainfuck

Reading time7 min
Views13K
После нахождения на Хабре ряда постов имеющих отношение к Brainfuck'у в том числе его интерпретации у меня возникло какое-то желание написать и свой интерпретатор Brainfuck'а. Но для удовлетворение тех необходимых ощущений, которые нам приносит сам язык, нужно это было написать именно на Brainfuck. И у меня это частично получилось. Сразу оговорюсь о том чего нету: этот интерпретатор на данный момент не поддерживает циклы и ввод входных данных (в случае входных данных — нет откуда их считывать, так как на вход подается Brainfuck программа) — если кратко — то не работают комманды "[", "]" и ",".

Ограничения


Из ограничений (помимо того, чего интерпретатор не поддерживает) есть только два следующих:
  • Минимальный индекс ячейки должен быть не меньше чем (-1) (иначе есть риск неправильной работы интерпретатора). Другими словами — писать "<<" в начале программы не стоит.
  • Максимальное количество используемых ячеек — 255.


Скорость


Я думаю вы уже предположили, но я всё-таки уточню, что на Brainfuck не стоит писать интерпретаторы скорость работы оставляет желать лучшего.

Обфускатный исходный код интерпретатора


Если у вас всеравно осталось желание испытать то, что у меня получилось, то вот и сам исходный код:
,[>,]>>>>++<<<<<[<]>[[[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-]>++++++++++[<++++>-]<+++<[>-<-]+>[<->[-]]<[->>>[<+<<+>>>-]<[>+<-]<<[>>>>>>>>>[>>->>]<<<<[<<<<]<<<<<-]>>>>>>>>>>>[>>>>]<+<[-]<<<<[<<<<]<<[<+<<+>>>-]<[>+<-]<<[>>>>>>>>>>>[>>>>]<<+<<<<[<<<<]<<<<<-]>>>>>>>>>[>>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]>]<<<<[<<<<]<<<<<]<<[<]>[[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-]>+++++++++[<+++++>-]<<[>-<-]+>[<->[-]]<[->>>[<+<<+>>>-]<[>+<-]<<[>>>>>>>>>[>>->>]<<<<[<<<<]<<<<<-]>>>>>>>>>>>[>>>>]<-<[-]<<<<[<<<<]<<[<+<<+>>>-]<[>+<-]<<[>>>>>>>>>>>[>>>>]<<+<<<<[<<<<]<<<<<-]>>>>>>>>>[>>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]>]<<<<[<<<<]<<<<<]<<[<]>[[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-]>+++++++++[<+++++>-]<+<[>-<-]+>[<->[-]]<[->>>[<+<<+>>>-]<[>+<-]<<[>>>>>>>>>[>>->>]<<<<[<<<<]<<<<<-]>>>>>>>>>>>[>>>>]<.<<<<<[<<<<]>>>>[>>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]>]<<<<[<<<<]<<<<<]<<[<]>[[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-]>++++++++++[<++++++>-]<<[>-<-]+>[<->[-]]<[->>>-<<<]<<[<]>[[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-]>++++++++++[<++++++>-]<++<[>-<-]+>[<->[-]]<[->>>+<<<]<<[<]>[-]>]

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

Код Brainfuck вы можете исполнить на сайте brainfuck.tk, а в качестве примера входных данных использовать следующий код:
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+.+.>++++++++++.<.-.-.
который должен вывести следущих две строки:
ABC
CBA


Исходный код


Перед исходным кодом уточню некоторый моменты:
  • N — так я позначаю длину входной строки. В нашем случае это должна быть программа на Brainfuck.
  • Осчет ячеек начинается с 0.
  • Код входной программы размещается в ячейках начиная с нулевой.
  • Ячейка (N + 4) — указатель на текущую ячейку. Значение по умолчанию — 2 (для входной программы это ячейка с индексом 0). Значение — 1 — для входной программы доступно как ячейка с индексом (-1).
  • Данные входной программы начинаются с ячейки (N + 10).
  • Структура данных имеет вид: 1-ая ячейка — номер ячейки, 2-ая ячейка — значение, 3-ая и 4-ая ячейки — ячейки для хранения промежуточных результатов.

ASCII коды используемых символов:
  • + — 43
  • - — 45
  • . — 46
  • < — 60
  • > — 62

Исходный код:
,[>,] считывание brainfuck программы
>>>>++<<<< установка значения по умолчанию для ячейки (N плюс 4)
<[<]> переход в начало программы: из позиции N в позицию 0

[
    плюс
    [[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-] копирование текущей команды на позицию (N плюс 1)
    >++++++++++[<++++>-]<+++ запись значения 43 в (N плюс 2) ячейку
    <[>-<-] вычитание кода символа команды из числа 43
    +>[<->[-]]<[- если команда это символ "плюс"; текущая ячейка: (N плюс 1)
        >>>[<+<<+>>>-]<[>+<-]<< копирование ячейки (N плюс 4) в текущую ячейку (N плюс 1)
        [>>>>>>>>>[>>->>]<<<<[<<<<]<<<<<-] вычитание индекса текущей ячейки из индексов каждой ячейки
        >>>>>>>>>>>[>>>>]<+<[-] изменение значения ячейки
        <<<<[<<<<]<<[<+<<+>>>-]<[>+<-]<< копирование ячейки (N плюс 4) в ячейку (N плюс 1)
        [>>>>>>>>>>>[>>>>]<<+<<<<[<<<<]<<<<<-] обновление индекса ячейки
        >>>>>>>>>[>>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]>] восстановление индексов ячеек
        <<<<[<<<<]<<<<< возвращаемся на ячейку (N плюс 1)
    ]
    
    <<[<]> переход в начало программы: из позиции (N плюс 1) в позицию 0
    
    минус
    [[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-] копирование текущей команды на позицию (N плюс 1)
    >+++++++++[<+++++>-]< запись значения 45 в (N плюс 2) ячейку
    <[>-<-] вычитание кода символа команды из числа 45
    +>[<->[-]]<[- если команда это символ "минус"; текущая ячейка: (N плюс 1)
        >>>[<+<<+>>>-]<[>+<-]<< копирование ячейки (N плюс 4) в текущую ячейку (N плюс 1)
        [>>>>>>>>>[>>->>]<<<<[<<<<]<<<<<-] вычитание индекса текущей ячейки из индексов каждой ячейки
        >>>>>>>>>>>[>>>>]<-<[-] изменение значения ячейки
        <<<<[<<<<]<<[<+<<+>>>-]<[>+<-]<< копирование ячейки (N плюс 4) в ячейку (N плюс 1)
        [>>>>>>>>>>>[>>>>]<<+<<<<[<<<<]<<<<<-] обновление индекса ячейки
        >>>>>>>>>[>>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]>] восстановление индексов ячеек
        <<<<[<<<<]<<<<< возвращаемся на ячейку (N плюс 1)
    ]
    
    <<[<]> переход в начало программы: из позиции (N плюс 1) в позицию 0
    
    точка
    [[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-] копирование текущей команды на позицию (N плюс 1)
    >+++++++++[<+++++>-]<+ запись значения 46 в (N плюс 2) ячейку
    <[>-<-] вычитание кода символа команды из числа 46
    +>[<->[-]]<[- если команда это символ "точка"; текущая ячейка: (N плюс 1)
        >>>[<+<<+>>>-]<[>+<-]<< копирование ячейки (N плюс 4) в текущую ячейку (N плюс 1)
        [>>>>>>>>>[>>->>]<<<<[<<<<]<<<<<-] вычитание индекса текущей ячейки из индексов каждой ячейки
        >>>>>>>>>>>[>>>>]<.< вывод значения ячейки
		<<<<[<<<<]>>>>[>>[-]>[-]<<<[>>+>+<<<-]>>>[<<<+>>>-]>] восстановление индексов ячеек
        <<<<[<<<<]<<<<< возвращаемся на ячейку (N плюс 1)
    ]
    
    <<[<]> переход в начало программы: из позиции (N плюс 1) в позицию 0
    
    меньше
    [[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-] копирование текущей команды на позицию (N плюс 1)
    >++++++++++[<++++++>-]< запись значения 60 в (N плюс 2) ячейку
    <[>-<-] вычитание кода символа команды из числа 60
    +>[<->[-]]<[- если команда это символ "меньше"; текущая ячейка: (N плюс 1)
        >>>-<<< изменение указазателя на минус 1
    ]
    
    <<[<]> переход в начало программы: из позиции (N плюс 1) в позицию 0
    
    больше
    [[>]>+>+<<<[<]>-]+[>]>>-[<<<[<]>+[>]>>-] копирование текущей команды на позицию (N плюс 1)
    >++++++++++[<++++++>-]<++ запись значения 62 в (N плюс 2) ячейку
    <[>-<-] вычитание кода символа команды из числа 62
    +>[<->[-]]<[- если команда это символ "больше"; текущая ячейка: (N плюс 1)
        >>>+<<< изменение указазателя на плюс 1
    ]
    
    <<[<]>[-]> переход в начало программы но уже на следующую команду (предыдущая позиция обнуляется)
]

Вместо заключения


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

P.S.
Спасибо хабрачеловеку iSage за предоставленные ссылки на интерпретаторы Brainfuck на Brainfuck.
Tags:
Hubs:
Total votes 89: ↑64 and ↓25+39
Comments51

Articles