edwardoid Mar 23 2011 at 00:19

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

4 min

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

Tags:

Hubs:

Abnormal programming