Учебное пособие / ресурс по внедрению виртуальной машины
https://stackoverflow.com/questions/2034422
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я хочу с целью самообразования реализовать простую виртуальную машину для динамического языка, предпочитаемого на C.Что-то вроде виртуальной машины Lua, или Parrot, или Python, но проще.Существуют ли какие-либо хорошие ресурсы / учебные пособия по достижению этого, помимо изучения кода и проектной документации существующих виртуальных машин?
Редактировать:зачем закрывать голосование?Я не понимаю - это что, не программирование?Пожалуйста, прокомментируйте, если есть конкретная проблема с моим вопросом.
Решение
Я предполагаю, что вам нужна виртуальная машина, а не простой интерпретатор.Я думаю, что это две точки континуума.Интерпретатор работает над чем-то близким к исходному представлению программы.Виртуальная машина работает с более примитивными (и автономными) инструкциями.Это означает, что вам нужен этап компиляции для перевода одного в другое.Я не знаю, хотите ли вы поработать над этим в первую очередь или у вас уже есть в голове синтаксис ввода.
Для динамического языка вам нужно место, где хранятся данные (в виде пар ключ/значение) и некоторые операции, которые над ними действуют.Виртуальная машина поддерживает хранилище.Программа, выполняющаяся на нем, представляет собой последовательность инструкций (включая поток управления).Вам необходимо определить набор инструкций.Я бы предложил для начала простой набор, например:
- основные арифметические операции, включая арифметические сравнения, доступ к хранилищу
- основной поток управления
- встроенная печать
Возможно, вы захотите использовать для арифметических вычислений подход к вычислениям на основе стека, как это делают многие виртуальные машины.В вышеизложенном пока еще нет особой динамики.Чтобы достичь этого, нам нужны две вещи:возможность вычислять имена переменных во время выполнения (это просто означает строковые операции) и некоторую обработку кода как данных.Это может быть так же просто, как разрешить ссылки на функции.
В идеале ввод в виртуальную машину должен осуществляться в байт-коде.Если у вас еще нет компилятора, его можно сгенерировать с помощью базового ассемблера (который может быть частью виртуальной машины).
Сама виртуальная машина состоит из цикла:
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 для запуска игры «откусывания», и является первой в серии статей о компиляторе и интерпретаторе байт-кода;здесь описывается виртуальная машина, и он обещает, что в будущих статьях будет описываться и компилятор.
Кстати, я не голосовал за закрытие вашего вопроса, но ваш голос за закрытие был дубликатом вопрос прошлого года о том, как узнать о реализации виртуальной машины.Я думаю, что этот вопрос (об учебнике или чем-то относительно простом) достаточно отличается от предыдущего, поэтому его следует оставить открытым, но вы, возможно, захотите обратиться к нему за дополнительным советом.
Еще одним ресурсом, на который следует обратить внимание, является реализация Язык Lua.Это виртуальная машина на основе регистров, которая имеет хорошую репутацию по производительности.Тот Самый исходный код находится в ANSI C89 и, как правило, очень удобочитаем.
Как и в случае с большинством высокопроизводительных скриптовых языков, конечный пользователь видит читаемый динамический язык высокого уровня (с такими функциями, как замыкания, конечные вызовы, неизменяемые строки, числа и хэш-таблицы в качестве основных типов данных, функции в качестве значений первого класса и многое другое).Исходный текст компилируется в байт-код виртуальной машины для выполнения реализацией виртуальной машины, схема которой в значительной степени соответствует описанию Ответ Эдмунда.
Много усилий было потрачено на то, чтобы сохранить саму реализацию виртуальной машины переносимой и эффективной.Если требуется еще большая производительность, a компилятор " как раз вовремя " начиная с байтового кода виртуальной машины и заканчивая собственными инструкциями, существует для 32-разрядной версии x86 и находится в бета-версии для 64-разрядной версии.
Для начала (даже если не С, но С++) вы могли бы взглянуть на МуПарсер.
Это анализатор математических выражений, использующий простой виртуальная машина для выполнения операций.Я думаю, что даже тебе нужно время, чтобы все понять;в любом случае этот код проще, чем полная виртуальная машина, способная запускать настоящий полная программа.(Кстати, я проектирую аналогичная библиотека в C# — это начальная стадия, но следующие версии позволят компилировать в .NET/VM IL. или, может быть, новая простая виртуальная машина, такая как muParser).
Еще одна интересная вещь НекоВМ (он выполняет файлы байт-кода .n).Это проект с открытым исходным кодом написано на Си и его основной язык (.neko), как полагают, создается компилятор исходного кода технологии.В духе прошлой темы см. Хаксе от того же автора (тоже с открытым исходным кодом).
Как и вы, я также изучал виртуальные машины и компиляторы, и могу порекомендовать одну хорошую книгу: Дизайн компилятора:Виртуальные машины.Он описывает виртуальные машины для императивных, функциональных, логических и объектно-ориентированных языков, предоставляя набор инструкций для каждой виртуальной машины, а также руководство по компиляции языка более высокого уровня для этой виртуальной машины.Я реализовал виртуальную машину только для императивного языка, и это уже было очень полезное упражнение.
Если вы только начинаете, я могу порекомендовать еще один ресурс: PL101.Это интерактивный набор уроков по JavaScript, который проведет вас через процесс реализации парсеров и интерпретаторов для различных языков.
Я опаздываю на вечеринку, но я бы порекомендовал Game Scripting Mastery, который поможет вам написать работающий скриптовый язык и его виртуальную машину с нуля.И с очень небольшими предпосылками.
