Пишем интерпретатор для своего эзотерического языка

За основу я взял язык Brainfuck он настолько мал, что можно немного расширив получить практически новый и достаточно функциональный язык программирования. И при этом не потерять изюминку исходного языка – мой язык будет все так же терзать мозг программиста, как и его родитель!

Итак, Brainfuck. Вкратце, идея такая, есть N регистров/ячеек. У программиста есть доступ к ним всем но перемещения по ним делаются явным образом. Т.е. из ячейки 2 нельзя перейти к ячейке 7 сразу, нужно последовательно.

“Ключевые слова” языка:

  • > – перейти на ячейку вправо.
  • < – перейти на ячейку влево.
  • + – увеличить значение ячейки на единицу.
  • — – уменьшить значение ячейки на единицу.
  • , – прочесть значение в ячейку со стандартного устройства ввода.
  • . – напечатать значение ячейки стандартным устройством вывода.
  • [ – начать цикл while если значение текущей ячейки не равно 0 и перейти к следующей ячейке.
  • ] – конец блока while. Продолжить цикл, если значение “условной” ячейки не равно 0 ( “условная ячейка” — ячейка на которой начался цикл ).


Добавленные “ключевые слова”:
  • $ – прочитать значение в ячейку как число ( > переопределим как чтение в качестве ANCII символа )
  • ! – напечатать как число
  • { – начало функции, после начала идет имя функции ( именем может служить любая последовательность букв между символами %<имя функции>%. Для любой функции создается копия ячеек, возвращаемое значение записывается в текущий регистр вызвавшего блока
  • } – конец функции
  • ( – начало комментария
  • ) – конец комментария
  • @%<имя функции>% – вызов функции
  • ^ – обнулить ячейку


Так как все множество ключевых слов состоит из ANCII символов, имеем:

// Искомые ключевые слова
const char bf_next = '>';
const char bf_prev = '<';
const char bf_incr = '+';
const char bf_decr = '-';
const char bf_prnt = '.';
const char bf_read = ',';
const char bf_wBeg = '[';
const char bf_wEnd = ']';

// Добавленные ключевые слова
const char bf_pNum = '!' ;
const char bf_rNum = '$';
const char bf_fBeg = '{';
const char bf_fEnd = '}';
const char bf_fNme = '%';
const char bf_comm= '(';
const char bf_call = '@';
const char bf_null = '^';


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

Добавим:

const unsigned long regSize = 256; // Количество регистров

long reg[ regSize ]; // Сами регистры
long stck[ regSize ]; // Стек, у каждой функции свой стек

void resetRegisters(); // Функция для обнуления регистров

void printRegistres(); // Показать состояние регистров


Теперь, скажем имеем test.bf, как входной файл, в котором находится код на моем языке или на родном Brainfuck. Интерпретатор должен обеспечивать “обратную совместимость”.

Опять же, без ограничения общности, можем хранить весь код в некотором ограниченном массиве. Т.е. интепретатор будет работать с файлами ограниченного размера, скажем так:

const unsigned long maxCodeSize = 1024000; /* максимальный размер входного файла в символах */
unsigned long realCodeSize; // Размер кода в файле realCodeSize < maxCodeSize
char code[maxCodeSize]; // Сам код


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

int main( int argc, char** argv )
{
welcome();
resetRegisters();
readCode( “test.bf “ );
loop ( 0, realCodeSize — 1, regSize, reg );
return 0;
}

Далее определим пару функций для цикла while и копирования стека и собственно выполнения функции.

bool loop( unsigned long from,
unsigned long to,
unsigned long condRegIndx,
unsigned long currReg,
long* registers );

bool runFunction( unsigned long from,
unsigned int to,
unsigned int& retValue);

void copyRegistersTo( long* source, long* destination );

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

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

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

const unsigned long maxLoopCycles = 999999;

Реализуем сначала обратную совместимость. Пусть пока наш интерпретатор сможет выполнять только код Brainfuck-а.
Нам понадобятся функции:

bool makeCommand( char command, long* registers, unsigned long currReg )

unsigned long findLoopEnd( const unsigned long from )


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

Вторая функция исходя из названия находит конец цикла, т.е. символ соответствуюйщий '['.

Таким образом имеем интерпретатор для языка Brainfuck.
К записи прикрепил исходный код, моего интерпретатора с тестовым кодом

$[+<->]<<$>!<>>++++[++++++++++<->]<+++.++++++++++++++++++<<<!>[<-<+>>]>>.<<<!

На код выше мой интерпретатор выведет сумму двух введённых чисел в виде а+b=c.

Удачного… программирования!

P.S.
Если интересно, позже расскажу как реализовывал остальное.
Share post

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 21

    +4
    Неоригинально. Процедурные расширения Brainfuck науке известны давно — хотя бы pbrain. Чтение и запись чисел как чисел — хотя бы COW. Начало и конец комментария не нужны вообще — все символы, кроме команд, считаются комментариями автоматически, в крайнем случае пишем [-][комментарий с любыми символами]. Обнулить ячейку — чем плохо старое доброе [-]?
      0
      Я не ставил целью сделать открытие. Я хотел изобрести велосипед. Сам собрать, сам сварить, самому кататься. Что касательно комментария, то согласен, текст мне нужен только нужен как имя процедуры/функции. Старое доброе [-] долго, но опять же возможно.
      0
      Как говорил один из моих преподавателей, большой поклонник теории формальных языков и построения трансляторов: «А напиши-ка ты мне на своем языке Ханойские Башни». Думаю он и сейчас так говорит :)
        0
        Сурово, но постараюсь :)
          0
          Я к тому, что у нас в то время была курсовая по этому предмету, и мы с другом решили сделать транслятор BF в более человеческий язык и обратно, дополнительно нам была поставлена задача, написать свою VM(ну или транслятор если будет угодно) под эти языки, поэтому было принято решение, делать некий «байткод» в который транслировались бы программы с обоих языков с возможностью также распаковать этот «байткод» в любой язык обратно. Собственно оттуда и фраза про Ханой, правда мы поступили как все студенты — нашли в сети Ханой на BF (кстати помоему тот, который указан в комменарии ниже) прогнали его через свои ретрансляторы и получили Ханой на своем языке :)
            0
            Интересно). А какой был ваш человеческий язык? Когда я брался расширять BF, был соблазн добавить еще пару фич, например, банальное умножить!
              0
              Достаточно простой, там были процедуры и циклы по-моему, умножение если мне не изменяет память было оформлено в процедуру. Сейчас уже всех подробностей не вспомню, а проекта у меня не осталось уже.
                0
                Если я все правильно понял, то нечто подобное делает мой однокурсник. У него дипломный проект переводит с одного языка на другой: EN > RU, например.
          0
          Кажется, кому-то он это уже сказал: roland-illig.de/hanoi.brainfuck.html
          +1
              const unsigned int w = 10;
          
              std::cout << "Registers:";
              for ( unsigned int i = 0; i < regSize; i )
              {
                  std::cout << std::endl;
                  for ( unsigned int w = 0; w < 10; w ++ )
                  {
                      if ( i++ < regSize )
                          std::cout << "R" << i <<"[" << reg[ i - 1] << "] ";
                  }
              }
              std::cout << std::endl;
          


          Мда…

            –1
            Где вы это нашли? Только не говорите у меня в коде. Ибо такой код не может работать, а регистры у меня выдаются очень даже нормально.
              +1
              Почему же не может работать? Может. И работает так, как и задумалось, просто написано очень… специфично…
              Нашел у вас в коде.
                –1
                А как ему работать?
                const unsigned int w = 10; // w - объявлен и определен как константа, не подлежит изменению

                и потом в другом блоке, где w все еще виден, создается другой объект с таким же именем, и даже больше, задается новое значение?

                Разъясните. Такого я не знал.

                P.S. разумеется
                unsigned int w = 10;

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

                P.P.S.
                Стыдно, конечно сознавать, что эта строчка моих рук дело. Строчка совсем не специфичная, она ужасна.
                  0
                  const unsigned int w = 10; // w — объявлен и определен как константа, не подлежит изменению
                  unsigned int w = 0;

                  { } создает новую область видимости, внутри нее можно переопределить переменную таким же именем(бедные компиляторы).

                  #include <stdio.h>
                  int main() {
                      int a = 4;
                      {
                          char a = 42;
                          printf("%c \n", a);
                      }
                      a = 48;
                      printf("%d \n", a);
                      return 0;
                  }
                    0
                    это требование стандарта или специфика некоторых компиляторов? Потому как помню в одно время такой код работал при одном компиляторе, в другом выдалось, что переменная с таким именем не существует.
                    for( int i = 0; i < someConstant; i++)
                    {
                    // ...
                    }

                    for( int i = 0; i < anotherConstant; i++)
                    {
                    // ...
                    }

                      0
                      Вероятно вы имели ввиду:

                      for( int i = 0; i < someConstant; i++)
                      {
                      //…
                      }

                      for(i = 0; i < anotherConstant; i++)
                      {
                      //…
                      }
                        0
                        Да, именно это я и имел ввиду.
                          0
                          Тут другая ситуация, зависит от того, в какой области видимости компилятор объявит переменную, которая объявляется в for(;;), либо в текущей, либо во вложенной.
                          Если в текущей, тогда будет видна и в следующем цикле, если во вложенном, то она недоступна снаружи(что логично).

                          Ну это стандартное поведение для всех языков, которые я щупал =)
            0
            Т.e. все-таки все от компилятора звисит, не стандарт устанавливает.

            P.S.
            Интересно за что мне минуснули в пред. комментах. За вопрос? Мило.
              0
              Вы не поняли. В первом выражении for можно объявить переменную, но она не имеет никакого отношения к области видимости, которая создается { } после ключевого слова, поэтому тут зависит от компилятора. Но ваш случай вполне стандартен.
                +1
                Ок. Спасибо.

            Only users with full accounts can post comments. Log in, please.