Как я писал компилятор Brainfuck для RVM на С (RayFoundation)

Недавно, в целях исследования теории алгоритмов и машин Тьюринга ^[1] у меня появилась идея написать свою простенькую виртуальную машину (далее ВМ), со своим байт-кодом, и маленьким языком программирования(ЯП). Основное применение ВМ – выполнение одной функции(например декодирование данных) запрограммированное в байт-коде функции.

В качестве ЯП был выбран Тьюринг-полный и простой язык BrainFuck ^[2], т.к. для начала его вполне хватит, потом можно его усложнить

Архитектура ВМ

• Первое, что хотелось бы отметить, ВМ должна быть самой простой, по этому, все что она будет уметь это делать преобразование над данными в памяти, поэтому она имеет один(два в будущем) регистра для выполнение базовых битовых, арифметических, логических операций.
• Второе, тип данных – классический байт (И не надо тут говорить, что в начале было слово. Ибо, в начале был байт, а потом было слово). И инструкции(байт-код) тоже будут длинной 8 бит, т.е. всего можно сделать 256 инструкций, с разными кодами. Хочу заметить, что, как говорил Бабаян (http://habrahabr.ru/post/205168/, habrahabr.ru/post/214377/ ^[3]) железо(ВМ) должно быть связано с алгоритмом(задачей), которую оно выполняет и языком программирования.

Третее, список инструкций:

1. перейти к следующей ячейке r_move_forward
2. перейти к предыдущей ячейке r_move_backward
3. увеличить значение в текущей ячейке на 1 r_increment
4. уменьшить значение в текущей ячейке на 1 r_decrement
5. напечатать значение из текущей ячейки r_print_char
6. ввести извне значение и сохранить в текущей ячейке r_get_char
7. проверка значения в текущей ячейки на ==0, !=0 r_if, r_if_not
8. goto r_goto_address
9. конец программы r_end

Далее пойдут интересные куски кода самой VM (полностью тут ^[4]). Написан на С, но с множеством define вставок, по этому для понимания базового синтаксиса, который использовался необходимо прочитать habrahabr.ru/post/239505/ ^[5] и знать С.

method(void, executeFunction, RVirtualMachine), RVirtualFunction *function) {
    uint64_t result = 0;
    // копируем указатель на исполняемую функцию 
    object->functionExecuting = function;
    // выводим имя функции
    RPrintf("RVM. Start Executing Function : "%s"nn", function->name->baseString);
    // задаем счетчик тактов в 0
    object->tickCount = 0;
    // очищаем память (1кБ)
    $(object, m(setUpDataBlock, RVirtualMachine)) );
    // задаем регистр данных как указательна первый елемент массива
    object->dataRegister = &object->memory->array[0];
    // задаем регистр команд, как указатель на первый елемент тела функции в байт-коде
    object->functionStartAddress = master(object->functionExecuting, RByteArray)->array;
    object->command              = object->functionStartAddress;
    // выполняем по одному байт-коду, пока результат не 1, 
    // или не установлен прерывающий флаг
    while(object->breakFlag == 0 && result != 1) {
        result = $(object, m(executeCode, RVirtualMachine)));
        // инкрементим кол-во тактов
        ++object->tickCount;
    }
    // в конце выполнения – выводим снимок памяти
    RPrintf("nRVM. End Executing Function : "%s"n", function->name->baseString);
    RPrintf("Ticks count for executing is - %qun", object->tickCount);
    RPrintf("Memory snapshot : {");
    $(object->memory, p(RByteArray)) );
    RPrintf("n } end memory snapshotnn");
}

Далее метод, исполняет одиночный байт-код:

method(uint64_t, executeCode, RVirtualMachine)) {
    switch(*object->command) {
        case r_increment : {
            // инкрементируем регистр данных
            ++(*object->dataRegister);
            ++object->command;
        } break;
        case r_decrement : {
            // отнимаем у регистра данных 1
            --(*object->dataRegister);
            ++object->command;
        } break;
// выводы
        // это пока зарезервировано
        case r_print_0_string : {
            RPrintf("%sn", object->dataRegister);
            while(*object->dataRegister != 0) {
                ++object->dataRegister;
                ++object->tickCount;
            }
            ++object->command;
        } break;
	 // выводим символ, если не служебный и не ascii печатаем в HEX
        case r_print_char : {
            if(*object->dataRegister == 'n'
                    || *object->dataRegister == 'r'
                    || *object->dataRegister == 't') {
                RPrintf("%c", *object->dataRegister);
            } else if(*object->dataRegister < 32
                    || *object->dataRegister > 127) {
                RPrintf("%02x ", *object->dataRegister);
            } else {
                RPrintf("%c", *object->dataRegister);
            }
            ++object->command;
        } break;
// ввод
        case r_get_char : {
            *object->dataRegister = getchar();
            ++object->command;
        } break;
// сдвиги (в усложненной версии будут ненужны)
        case r_move_forward : {
            // инкрементируем УКАЗАТЕЛЬ на данные
            ++object->dataRegister;
            ++object->command;
        } break;
        case r_move_backward : {
            // двигаемся назад на одну ячейку
            --object->dataRegister;
            ++object->command;
        } break;
        case r_goto_address : {
            // присваеваем регистру команд указатель, на величину, 
 	      // следующую за командой goto. 
	      // Адрес, относительный указателя на начало функции
            object->command = object->functionStartAddress + *(++object->command);
        } break;
        case r_if : {
            if((*object->dataRegister) != 0) {
                // правдивая инструкция
                object->command += 3; // 3 – из-за байта в аргументе goto
            } else {
                // ложная инструкция
                ++object->command;
            }
        } break;
        case r_if_not : { // добавлено тоже исключительно для brainfuck далее будет выпилена
            if((*object->dataRegister) == 0) {
                // аналогично IF
                object->command += 3; 
            } else {
                ++object->command;
            }
        } break;
// конец работы
        case r_end : {
            RPrintf("nEnd work of RVM.n");
            return 1;
        }
// очень-очень плохой байт-код
        default: {
            RPrintf("RVM. Warning, default case, unhalted resultn");
            return 1;
        }
    }
    return 0;
}

Как можно увидеть, инструкция if имеет интересное строение, т.е. if (false_instruction, reserved byte, true_instruction) место зарезервировано под аргумент иструкции goto, таким образом можно легко строить циклы, основанные на инструкция if и goto.

Далее сам компилятор (адский процессинг строк на С стал чуть менее адским в RayFoundation):

Основной метод для процессинга brainfuck-строки в rasm байт-код:

method(RVirtualFunction *, createFunctionFromBrainFuckSourceCode, RVirtualCompiler), const RCString *sourceCode) {
    if(sourceCode->size != 0) {
        RVirtualFunction *function = $(NULL, c(RVirtualFunction)) );
        // копируем исходники
        object->code = $(sourceCode, m(copy, RCString)) );
        // инициализируем рабочие переменные
        object->deltaToNext = 0;
        object->toPrev      = 0;
        // задаем имя и тело
        function->name               = $(object, m(getFunctionName,          RVirtualCompiler)) );
        master(function, RByteArray) = $(object, m(getBrainFuckFunctionBody, RVirtualCompiler)) );
	  // уничтожаем рабочие исходники
        $(object->code, d(RCString)) );
        RPrintf("RVC. Brainfuck. Processed lines - %qu of %qu, in %qu iterations n", object->lines, object->numberOfLines + 1, object->iterator);
        // вывод байт-кода для отладки
        //  $(function, p(RVirtualFunction)) );
        return function;
    } else {
        RPrintf("Error. RVC. Bad virtual-code sizen");
    }
    return NULL;
}

Теперь метод получение имени:

method(RCString *, getFunctionName, RVirtualCompiler)) {
    if(object->code->size != 0){
        uint64_t place;
        // находим символ начала кода - ':'
        place = indexOfFirstCharacterCString(object->code->baseString, object->code->size, ':');
        // копируем подстроку с именем
        RCString *name = $(object->code, m(getSubstringInRange, RCString)), makeRRange(0, place));
        // удаляем имя и ':' символ из исходников
        $(object->code, m(deleteInRange, RCString)), makeRRange(0, place + 1));
        // удаляем все пробелы
        $(object->code, m(deleteAllCharacters, RCString)), ' ');
	 // считаем количество строк
        object->numberOfLines = $(object->code, m(numberOfRepetitions, RCString)), 'n');
        return name;
    }
    return NULL;
}

Метод получения тела функции:

method(RByteArray *, getBrainFuckFunctionBody, RVirtualCompiler)) {
    RByteArray *body;
    byte        character;
    uint64_t    sizeOfByteCode;
    object->iterator      = 0;
    object->iteratorShift = 0; // сдвиг получается из-за '[' и ']' утроения
    // все [, ] символы будут утроены в байт-коде,
    // из-за r_if инструкции + goto
    object->forwardRepetitions  = $(object->code, m(numberOfRepetitions, RCString)), '[');
    object->backwardRepetitions = $(object->code, m(numberOfRepetitions, RCString)), ']');
    if(object->forwardRepetitions != object->backwardRepetitions) {
	 // если скобочек не хватает
        RPrintf("Warning. RVC (BrainFuck). Count of '[' and ']' isn't equal!");
    }
    // из размера байткода удаляем все 'n', +1 для инструкции r_end
    sizeOfByteCode = object->code->size - object->numberOfLines + 1 + 2 * (object->forwardRepetitions + object->backwardRepetitions);
    body = makeRByteArray(sizeOfByteCode);
    // устанавливаем указатель на тело
    object->body = body;
    // препроцессим посимвольно
    while(object->iterator < object->code->size) {
        character = $(object, m(brainFuckSourceToByteCode, RVirtualCompiler)));
	  // eсли r_ignore не присваеваем байт-код
        if(character != r_ignore) {
            body->array[object->iterator + object->iteratorShift] = character;
        }
        ++object->iterator;
    }
    body->array[object->iterator + object->iteratorShift] = r_end;
    return body;
}

Разбор посимвольно:

method(byte, brainFuckSourceToByteCode, RVirtualCompiler)) {
    byte byteCode;
    switch (object->code->baseString[object->iterator]) {
        case '+': {
            byteCode = r_increment;
        } break;
        case '-': {
            byteCode = r_decrement;
        } break;
        case '.': {
            byteCode = r_print_char;
        } break;
        case '>': {
            byteCode = r_move_forward;
        } break;
        case '<': {
            byteCode = r_move_backward;
        } break;
        case ',': {
            byteCode = r_get_char;
        } break;
        case '[': {
            // complicated case
            uint64_t realPath;
            object->deltaToNext = indexOfLastCharacterCString(&object->code->baseString[object->iterator + object->iteratorShift], object->code->size - object->deltaToNext, ']');
            --object->forwardRepetitions;
            realPath = object->iterator + object->iteratorShift + object->deltaToNext + (object->forwardRepetitions + object->backwardRepetitions) * 2;
            if(realPath > 255) {
                RPrintf("Warning. RVC (BrainFuck). '[' Too long loopn");
            }
            object->body->array[object->iterator + object->iteratorShift]     = r_if;
            object->body->array[object->iterator + object->iteratorShift + 1] = r_goto_address;
            object->body->array[object->iterator + object->iteratorShift + 2] = realPath;
            object->iteratorShift += 2;
            byteCode = r_ignore;
        } break;
        case ']': {
            // complicated case
            uint64_t realPath;
            object->toPrev = indexOfLastCharacterCString(object->code->baseString, object->toPrev ? object->toPrev : object->code->size, '[');
            --object->backwardRepetitions;
            realPath = object->toPrev + (object->forwardRepetitions + object->backwardRepetitions) * 2;
            if(realPath > 255) {
                RPrintf("Warning. RVC (BrainFuck). ']' Too long loopn");
            }
            object->body->array[object->iterator + object->iteratorShift]     = r_if_not;
            object->body->array[object->iterator + object->iteratorShift + 1] = r_goto_address;
            object->body->array[object->iterator + object->iteratorShift + 2] = realPath;
            object->iteratorShift += 2;
            byteCode = r_ignore;
        } break;
        case 'n': {
            ++object->lines;
            object->symbols = 1;
            --object->iteratorShift;
            byteCode = r_ignore;
        } break;
        case ' ': {
            --object->iteratorShift;
            byteCode = r_ignore;
        } break;
        default: {
            byteCode = r_end;
            RPrintf("ERROR. RVC (BrainFuck). Undefined symbol on line: %qu, place: %qu !n", object->lines, object->symbols);
        }
    }
    ++object->symbols;
    return byteCode;
}

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

Пример использования:

#include "RayFoundation/RayFoundation.h"
#include "RVirtualMachine/RVirtualFunction/RVirtualFunction.h"
#include "RVirtualMachine/RVirtualMachine/RVirtualMachine.h"
#include "RVirtualMachine/RVirtualCompiler.h"

int main(int argc, const char *argv[]) {
    // простой привет-мир без циклов
    RVirtualFunction *function = $(RVC, m(createFunctionFromBrainFuckSourceCode, RVirtualCompiler)),
            RS(" My brainfuck hello world : +++++++++++++++++++++++++++++++++++++++++++++n"
                    " +++++++++++++++++++++++++++.+++++++++++++++++n"
                    " ++++++++++++.+++++++..+++.-------------------n"
                    " ---------------------------------------------n"
                    " ---------------.+++++++++++++++++++++++++++++n"
                    " ++++++++++++++++++++++++++.++++++++++++++++++n"
                    " ++++++.+++.------.--------.------------------n"
                    " ---------------------------------------------n"
                    " ----.-----------------------."));
    // исполняем байт-код на RVM-одиночке
    executeRay(function);
    $(function, d(RVirtualFunction)) );
    // тест компилятора множественных циклов
    function = $(RVC, m(createFunctionFromBrainFuckSourceCode, RVirtualCompiler)),
            RS(" Cycles : +++ [ > +++ [.-] <-]")); // печатает '03 02 01' 3 раза
    executeRay(function);
    $(function, d(RVirtualFunction)) );
    // сложный привет-мир с циклом
    function = $(RVC, m(createFunctionFromBrainFuckSourceCode, RVirtualCompiler)),
            RS(" Hard Hello world : ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++n"
                                  " .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.n"
                                  " ------.--------.>+.>."));
    // печатаем функцию как rasm байт-код 
    $(function, p(RVirtualFunction)) );
    executeRay(function);
    $(function, d(RVirtualFunction)) );
    deallocator(function);
    // удаляем одиночку
    deleteRVM();
    return 0;
}

Всем спасибо за внимание. Let's play a game!

Автор: StrangerInRed

Источник ^[6]