Учебное пособие / ресурс для реализации ВМ
Я хочу, чтобы в целях самообразования была реализована простая виртуальная машина для динамического языка, предпочитаемая на C. Что-то вроде Lua VM, или Parrot, или Python VM, но проще. Существуют ли какие-либо хорошие ресурсы / учебные пособия по достижению этого, кроме просмотра кода и проектной документации существующих виртуальных машин?
Изменить: зачем закрывать голосование? Я не понимаю - это не программирование. Пожалуйста, прокомментируйте, если есть конкретная проблема с моим вопросом.
6 ответов
Я предполагаю, что вы хотите виртуальную машину, а не просто переводчик. Я думаю, что они две точки на континууме. Интерпретатор работает над чем-то близким к оригинальному представлению программы. ВМ работает на более примитивных (и автономных) инструкциях. Это означает, что вам нужен этап компиляции для перевода одного на другой. Я не знаю, хотите ли вы сначала поработать над этим или у вас еще есть синтаксис ввода.
Для динамического языка вам нужно где-то, где хранятся данные (в виде пар ключ / значение) и некоторые операции, которые воздействуют на него. ВМ поддерживает магазин. Программа, запущенная на нем, представляет собой последовательность инструкций (включая поток управления). Вам необходимо определить набор инструкций. Я бы предложил начать с простого набора, например:
- основные арифметические операции, включая арифметические сравнения, доступ к магазину
- основной поток управления
- встроенная печать
Вы можете использовать подход к вычислениям на основе стека, как это делают многие виртуальные машины. В вышесказанном пока не так много динамики. Чтобы достичь этого, нам нужны две вещи: способность вычислять имена переменных во время выполнения (это просто означает строковые операции) и некоторая обработка кода как данных. Это может быть так же просто, как разрешить ссылки на функции.
Вход в ВМ в идеале должен быть в байт-коде. Если у вас еще нет компилятора, он может быть сгенерирован из базового ассемблера (который может быть частью виртуальной машины).
Сама виртуальная машина состоит из цикла:
1. Look at the bytecode instruction pointed to by the instruction pointer.
2. Execute the instruction:
* If it's an arithmetic instruction, update the store accordingly.
* If it's control flow, perform the test (if there is one) and set the instruction pointer.
* If it's print, print a value from the store.
3. Advance the instruction pointer to the next instruction.
4. Repeat from 1.
Работа с именами вычисляемых переменных может быть сложной: инструкция должна указывать, в каких переменных находятся вычисляемые имена. Это можно сделать, разрешив инструкциям ссылаться на пул строковых констант, предоставленных во входных данных.
Пример программы (в сборке и байт-код):
offset bytecode (hex) source
0 01 05 0E // LOAD 5, .x
3 01 03 10 // .l1: LOAD 3, .y
6 02 0E 10 0E // ADD .x, .y, .x
10 03 0E // PRINT .x
12 04 03 // GOTO .l1
14 78 00 // .x: "x"
16 79 00 // .y: "y"
Предполагаемые коды инструкций:
"LOAD x, k" (01 x k) Load single byte x as an integer into variable named by string constant at offset k.
"ADD k1, k2, k3" (02 v1 v2 v3) Add two variables named by string constants k1 and k2 and put the sum in variable named by string constant k3.
"PRINT k" (03 k) Print variable named by string constant k.
"GOTO a" (04 a) Go to offset given by byte a.
Вам нужны варианты, когда переменные именуются другими переменными и т. Д. (И уровни косвенности сложно обдумать). Ассемблер просматривает аргументы типа "ADD .x, .y, .x" и генерирует правильный байт-код для добавления из строковых констант (а не вычисляемых переменных).
Ну, речь идет не о реализации виртуальной машины в C, но, поскольку это была последняя вкладка, которую я открыл перед тем, как увидел этот вопрос, я чувствую, что мне нужно указать статью о реализации компилятора байт-кода QBASIC и виртуальной машины в JavaScript с использованием <canvas> тег для отображения. Он включает весь исходный код, достаточный для реализации QBASIC для запуска игры "nibbles", и является первым в серии статей о компиляторе и интерпретаторе байт-кода; этот описывает виртуальную машину, и он обещает будущие статьи с описанием компилятора.
Между прочим, я не голосовал за закрытие вашего вопроса, но закрытое голосование, которое вы получили, было дубликатом вопроса прошлого года о том, как узнать о внедрении виртуальной машины. Я думаю, что этот вопрос (об учебнике или о чем-то относительно простом) достаточно отличается от того, что он должен оставаться открытым, но вы можете обратиться к этому вопросу за советом.
Еще один ресурс, на который стоит обратить внимание, - это реализация языка Lua. Это виртуальная машина на основе регистров, которая имеет хорошую репутацию для производительности. Исходный код находится в ANSI C89 и, как правило, очень удобочитаемый.
Как и в большинстве высокопроизводительных скриптовых языков, конечный пользователь видит читаемый высокоуровневый динамический язык (с такими функциями, как замыкания, хвостовые вызовы, неизменяемые строки, числа и хеш-таблицы в качестве основных типов данных, функции в качестве значений первого класса и т. Д.), Исходный текст компилируется в байт-код виртуальной машины для выполнения реализацией виртуальной машины, схема которой в значительной степени соответствует описанию ответа Эдмунда.
Большие усилия были направлены на то, чтобы реализация самой виртуальной машины была переносимой и эффективной. Если требуется еще большая производительность, то для 32-разрядной системы x86 существует своевременный компилятор из байтового кода виртуальной машины и встроенных инструкций, а в 64-разрядной версии он находится в бета-версии.
Для запуска (даже если не C, но C++) вы можете взглянуть на muParser.
Это анализатор математических выражений, использующий простую виртуальную машину для выполнения операций. Я думаю, что даже вам нужно время, чтобы все понять; в любом случае этот код более прост, чем полноценная виртуальная машина, способная запустить настоящую законченную программу. (Кстати, я создаю подобную библиотеку на C# - это ее ранние стадии, но следующие версии позволят компилировать в.NET/VM IL или, возможно, в новую простую виртуальную машину, такую как muParser).
Еще одна интересная вещь - это NekoVM (он выполняет файлы байт-кода.n). Это проект с открытым исходным кодом, написанный на C, и его основной язык (.neko), как полагают, генерируется с помощью технологии компиляции исходного кода. В духе последней темы смотрите Haxe от того же автора (тоже с открытым исходным кодом).
Как и вы, я также изучал виртуальные машины и компиляторы, и одна хорошая книга, которую я могу порекомендовать, - " Проектирование компиляторов: виртуальные машины". Он описывает виртуальные машины для императивных, функциональных, логических и объектно-ориентированных языков, предоставляя набор инструкций для каждой виртуальной машины вместе с руководством по компиляции языка более высокого уровня для этой виртуальной машины. Я реализовал виртуальную машину только для обязательного языка, и это уже было очень полезным упражнением.
Если вы только начинаете, то другой ресурс, который я могу порекомендовать, это PL101. Это интерактивный набор уроков по JavaScript, который проведет вас через процесс реализации синтаксических анализаторов и интерпретаторов для различных языков.
Я опаздываю на вечеринку, но я бы рекомендовал Game Scripting Mastery, который берет вашу руку, чтобы написать рабочий язык сценариев и его виртуальную машину с нуля. И с очень небольшим условием.