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

Источник: habrahabr

За основу я взял язык 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.

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


Страница сайта http://test.interface.ru
Оригинал находится по адресу http://test.interface.ru/home.asp?artId=25744