Альтернативы виртуальной машине на основе стека для переводчика
При создании интерпретатора для другого языка часто рекомендуется создавать виртуальную машину на основе стека, которая может интерпретировать байт-код, сгенерированный фактическим интерпретатором. Интерпретатор тогда будет состоять из двух частей: транслятора, который преобразует инструкции из языка высокого уровня в байт-код для виртуальной машины, и самой виртуальной машины.
У меня такой вопрос: какие существуют альтернативы для интерпретируемых языков? Например, возможно ли (и практично) пропустить виртуальную машину и реализовать все инструкции, используя функции в C? До некоторой степени, мне кажется, это должно быть возможно, но, возможно, вы в конечном итоге внедрили бы какую-то минимальную виртуальную машину для более сложной функциональности. Есть ли другие варианты?
2 ответа
Рекомендуется создавать виртуальные машины на основе стека, поскольку они просты в создании.
Другие распространенные типы ВМ основаны на регистрах, где значения хранятся в регистрах, а не в стеке.
Есть также много других вариантов интерпретаторов и виртуальных машин. У вас может быть компилятор, который генерирует деревья разбора, и интерпретатор, который их интерпретирует (но если он реализован с использованием рекурсивных функций, можно утверждать, что он все еще является виртуальной машиной на основе стека).
Также нередко создавать компиляторы, которые вместо генерации какого-либо машинного кода (для виртуальной машины или для реальной машины) генерируют код для другого языка. C является общим языком назначения для этих типов компиляторов, так как язык C и его компиляторы распространены повсеместно. Но тогда у вас больше нет виртуальной машины или интерпретатора, у вас просто есть компилятор / переводчик.
То, что вы предлагаете, возможно. C на самом деле не позволяет вам манипулировать стеком, и когда вы вызываете функцию, он не знает о локальных переменных вокруг нее, поэтому вам нужно выделить блок памяти в куче, чтобы сохранить какой-то поддельный "стек" пробел ", который вы используете для локальных переменных вашего языка сценариев, и передаете это в каждую функцию (или вставляете в глобальный поток). Вам также понадобится базовый указатель для этого стека для вызовов функций вашего языка сценариев.
Как только вы это сделаете, вы уже сделали большую часть того, что вы сделали бы, чтобы получить основанный на стеке язык. Так что вы могли бы сделать все остальное. Чтобы использовать для этого реальный стек и базовый указатель, вам нужно перейти на уровень машинного языка.
Если ваш язык основан на регистре, ему все еще нужен стек для доступа к локальным переменным (он просто использует его реже), вы просто не используете его в качестве параметров инструкции. Если я могу преступно упростить, виртуальные машины с 3-мя адресными регистрами являются своего рода частным случаем виртуальной машины на основе стека.
Другой подход к интерпретаторам байт-кода состоит в том, чтобы инструкция содержала идентификатор команды, который затем используется в качестве индекса в массиве указателей на функции, каждый из которых реализует одну инструкцию.
Очевидно, что это влияет на производительность. Если ваши инструкции достаточно просты, вы можете сохранить циклы ЦП, внедрив их непосредственно в машинный код и исключив (как правило, незначительные) накладные расходы при вызове функции, и, возможно, даже использовать реальный стек вместо поддельного.
Все зависит от ваших потребностей. В большинстве случаев, особенно если это ваш первый синтаксический анализатор / интерпретатор / виртуальная машина, я бы рекомендовал использовать массив указателей на функции и поддельный стек. Это просто, не слишком сложно для отладки и достаточно быстро на современных машинах. Позже вы всегда можете написать оптимизированную версию, которая работает по-другому.
Например, один из подходов состоит в том, чтобы сгенерировать достаточно машинного кода для вызова функции, а затем вставить указатель на такую функцию в сгенерированный машинный код. Таким образом, каждый скрипт становится блоком скомпилированного кода, но вам не нужно писать полный компилятор. После этого вы можете улучшать отдельные, ключевые инструкции, генерируя для них ассемблер, оставляя менее часто используемые вещи в качестве функций. Это немного улучшает локальность кода, что может помочь в крошечной микрооптимизации. Но только один из многих.
О, около месяца назад я писал о том, как можно создать компилятор (и интерпретатор байт-кода) с точки зрения новичка, что может быть полезно: http://orangejuiceliberationfront.com/how-to-write-a-compiler/