Главная » Arduino
Призовой фонд
на октябрь 2017 г.
1. Термометр Relsib WT51
Рэлсиб
2. 1000 руб
PCBWay
3. Регулируемый паяльник 60 Вт
Паяльник
4. 100 руб.
От пользователей

Разрабатываем интерпретатор brainfuck на Arduino

Шла последняя неделя Августа, я неожиданно подумал. Пора бы сделать что, нибудь полезное для этого мира, так появился он - порт языка Brainfuck на ардуино. Каждый кто достаточно долгое время увлекается программированием слышал про такой миниатюрный язык программирования Brainfuck, который не зря получил такое название. Ну а если вы не знаете то вот вам краткий экскурс:

Brainfuck - экзотический тьюринг-полный язык программирования, содержащий в себе всего 8 операторов. У программы на brainfuck есть память , с которой она (программа) может взаимодействовать. Память представляет из себя массив чисел. Программа взаимодействует с ячейкой на которой в данный момент стоит курсор. 

Оператор Значение
> Сдвинуть курсор вправо
< Сдвинуть курсор
+ увеличить значение в ячейке на единицу
- уменьшить значение в ячейке на единицу
[ начало цикла, команды внутри цикла повторяются до тех пор пока значение в ячейке не равно нулю
] конец цикла
. вывести данные из ячейки на экран в виде ASCII символа
, получить один символ от пользователя и преобразовать его в число по таблиц ASCII

Думаю что суть языка понятная и можно переходить к разработке.

Разработка

Для начала создадим функцию в которую мы будем передавать код и которая будет его выполнять.

void BrainFuck(const char code[]){}

Как мы видим на вход функция принимает константный массив символов - это и есть код программы на BrainFuck.

Теперь внутри функции создадим несколько переменных необходимых для нашего интерпретатора.

int codeCursor = 0;
byte memory[255] = {0};
byte memCursor;

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

Создадим цикл в котором мы будем выполнять программу.

while (code[codeCursor] != 0){
 codeCursor++;
}

Как мы видим цикл у нас идет до тех пор пока ячейка в коде (на которую указывает codeCursor) не станет равной нулю. Что за магия здесь происходит? А дело все в том, что любая строка (массив символов) в ASCII заканчивается нулевым байтом т.е нулем. Это необходимо что бы мы понимали когда закачивается строка и не лезли в ту область памяти которая не относится к строке.

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

while (code[codeCursor] != 0){
    switch(code[codeCursor]){
          case '>':
             memCursor++;  
          break;
    }
    codeCursor++;
}

Для обработки операторов мы будем использовать конструкцию switch - case . Данная конструкция позволяет нам избавился от кучи Ifов. В начале мы указываем переменную с которой мы будем сравнивать в нашем случае это текущая ячейка в коде (code[codeCursor]) далее внутри тела swich мы прописываем сами сравнения. Сравнения выглядят следующим образом

case константа_с_которой_мы_сравниваем :
   //код который выполняется в случае если переменная и константа равны
break

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

while (code[codeCursor] != 0){
    switch(code[codeCursor]){
      case '>':
        memCursor++;  
        break;
        
      case '<':
        memCursor--;
        break;

      case '+':
        memory[memCursor]++;
        break;
      
      case '-':
        memory[memCursor]--;
      break; 
   codeCursor++;
  }  
}

Думаю с первыми 4мя операторами все понятно. Перейдем к более сложным вещам, а именно ввод и вывод в нашем языке.

Он будет выглядеть следующим образом.

case '.':
        Serial.print(char(memory[memCursor]));
        break;

      case ',': 
        while(true){
          if(Serial.available() >0){
            memory[memCursor] = Serial.read();
            break;
          }
        }
break;

Кстати, поскольку мы используем Serial, незабываем в начале функции добавить

Serial.begin(9600);

Думаю что с выводом данных все понятно, мы просто берем число из ячейки, трансформируем его в символ и выводим на монитор. То с вводом все немного сложнее. Здесь мы запускаем бесконечный цикл и внутри с помощью команды Serial.available() проверяем пришли ли нам данные от пользователя (возвращает длину данных в serial буфере, если их нет то длина равна 0). Если в буфере появились данные мы записываем первый байт в текущую ячейку (Serial.read() возвращает первый байт из буфера) и выходим из цикла.

Вот мы уже почти доделали наш интерпретатор языка brainfuck осталось самое сложное, но и самое интересное, именно циклы.

Циклы мы реализуем с помощью стека поэтому добавим в начале нашей функции следующие переменные

int stack[255] = {0};
byte stackCursor = 0;

Думаю логику циклов лучше разобрать сразу на примере кода так, что приступим.

case '[':
        if(memory[memCursor]){
          stackCursor++;
          stack[stackCursor] = codeCursor;
        }
        else{
          while(code[codeCursor] != ']'){
            codeCursor++;
          }
        }
        break;

Разберем код обработки начала цикла. Если вы вдруг забыли, циклы исполняют команды внутри себя если значение в текущей ячейке не ноль. Так что вначале мы проверяем значение в текущей ячейке. Если оно не ноль, то сдвигаем указатель стека на одну клетку и записываем в шапку стека индекс текущей позиции в коде (на нее мы будем возвращаться когда дойдем до конца цикла). Кстати, если вы не знаете что такое стек, советую вам почитать. Теперь обработаем обратную ситуацию, если значение в ячейке - ноль, то просто пропускаем все операторы пока не дойдем до конца цикла.

Разберем код обработки конца цикла.

 case ']':
        if(memory[memCursor])
          codeCursor = stack[stackCursor];
        else
          stackCursor--;
        break;

Тут код намного проще по сравнению с предыдущим. А именно, если значение в ячейке не ноль, то присваиваем текущую позицию в коде шапке объявления цикла, иначе просто убираем цикл из стека (передвигаем курсор на ячейку вниз).

Вот и весь код, а вы ожидали чего, то сложного ?)

void BrainFuck(const char code[]){
  int codeCursor = 0;
  
  byte memory[255] = {0};
  byte memCursor;

  int stack[255] = {0};
  byte stackCursor = 0;
  
  Serial.begin(9600);
  
  while (code[codeCursor] != 0){
    switch(code[codeCursor]){
      case '>':
        memCursor++;  
        break;
        
      case '<':
        memCursor--;
        break;

      case '+':
        memory[memCursor]++;
        break;
      
      case '-':
        memory[memCursor]--;
        break;

      case '.':
        Serial.print(char(memory[memCursor]));
        break;

      case ',': 
        while(true){
          if(Serial.available() >0){
            memory[memCursor] = Serial.read();
            break;
          }
        }
        break;
      case '[':
        if(memory[memCursor]){
          stackCursor++;
          stack[stackCursor] = codeCursor;
        }
        else{
          while(code[codeCursor] != ']'){
            codeCursor++;
          }
        }
        break;

      case ']':
        if(memory[memCursor])
          codeCursor = stack[stackCursor];
        else
          stackCursor--;
        break;
    }
    
    codeCursor++;
  }  
}

void setup() {
}

void loop() {
}

Ну и напоследок Hello World

Hello World на Brainfuck будет выглядеть следующим образом

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

Для того что бы наш код заработал, просто добавим в функцию setup следующую строчку.

BrainFuck("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.");

Таким образом мы исполним код и получим следующе сообщение в Serial-мониторе.

А зачем?

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

Чуть не забыл, исходный код:

Репозиторий проекта: тык

Онлайн интерпретатор Brainfuck: жмак

Теги:

Опубликована: 0 0
Я собрал 0 0
x

Оценить статью

  • Техническая грамотность
  • Актуальность материала
  • Изложение материала
  • Полезность устройства
  • Повторяемость устройства
  • Орфография
0

Средний балл статьи: 0 Проголосовало: 0 чел.

Комментарии (1) | Я собрал (0) | Подписаться

+1
StrannikM #
Автор молодец: сам догадался вставить главу "А зачем?".
Надо добавить ещё главу "Куда это применить практически?"
Иногда надоедает кушать торты и пироги, и очень хочется обычного чёрствого хлеба.
Когда надоедает простота написания кода, хочется чегой-то эндакого...
Остаётся только написать приложение, конвертирующее исходники нормальных языков в это "+++ ... --.>+.>."
Как по мне, если не нравится как ассемблер оптимизирует код - пишите прямо в кодах. Я когда-то с этого начинал. Очень увлекательное занятие. Развивает память и сообразительность.
Ответить
Добавить комментарий
Имя:
E-mail:
не публикуется
Текст:
Защита от спама:
В чем измеряется электрическое сопротивление?
Файлы:
 
Для выбора нескольких файлов использйте CTRL

Raspberry Pi 2
Raspberry Pi 2
Металлоискатель MD3010II UNI-T UT-61A
вверх