Как я писал компилятор Brainfuck для RVM на С (RayFoundation)
(надпись на картинке GEEK)Недавно, в целях исследования теории алгоритмов и машин Тьюринга у меня появилась идея написать свою простенькую виртуальную машину (далее ВМ), со своим байт-кодом, и маленьким языком программирования (ЯП). Основное применение ВМ — выполнение одной функции (например декодирование данных) запрограммированное в байт-коде функции.В качестве ЯП был выбран Тьюринг-полный и простой язык BrainFuck, т.к. для начала его вполне хватит, потом можно его усложнить
Архитектура ВМПервое, что хотелось бы отметить, ВМ должна быть самой простой, по этому, все что она будет уметь это делать преобразование над данными в памяти, поэтому она имеет один (два в будущем) регистра для выполнение базовых битовых, арифметических, логических операций. Второе, тип данных — классический байт (И не надо тут говорить, что в начале было слово. Ибо, в начале был байт, а потом было слово). И инструкции (байт-код) тоже будут длинной 8 бит, т.е. всего можно сделать 256 инструкций, с разными кодами. Хочу заметить, что, как говорил Бабаян (http://habrahabr.ru/post/205168/, habrahabr.ru/post/214377/) железо (ВМ) должно быть связано с алгоритмом (задачей), которую оно выполняет и языком программирования. Третее, список инструкций:
перейти к следующей ячейке r_move_forward перейти к предыдущей ячейке r_move_backward увеличить значение в текущей ячейке на 1 r_increment уменьшить значение в текущей ячейке на 1 r_decrement напечатать значение из текущей ячейки r_print_char ввести извне значение и сохранить в текущей ячейке r_get_char проверка значения в текущей ячейки на ==0, !=0 r_if, r_if_not goto r_goto_address конец программы r_end Далее пойдут интересные куски кода самой VM (полностью тут). Написан на С, но с множеством define вставок, по этому для понимания базового синтаксиса, который использовался необходимо прочитать habrahabr.ru/post/239505/ и знать С.
method (void, executeFunction, RVirtualMachine), RVirtualFunction *function) { uint64_t result = 0; // копируем указатель на исполняемую функцию object→functionExecuting = function; // выводим имя функции RPrintf («RVM. Start Executing Function: \»%s\»\n\n», 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 — %qu\n», object→tickCount); RPrintf («Memory snapshot: {»); $(object→memory, p (RByteArray))); RPrintf (»\n } end memory snapshot\n\n»); } Далее метод, исполняет одиночный байт-код:
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 (»%s\n», 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 result\n»); 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 size\n»); } 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 loop\n»); } 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 loop\n»); } 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!
