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

За основу я взял язык 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.
Если интересно, позже расскажу как реализовывал остальное.