Как грамотно написать интерпретатор?

Question

[Александр Попов]

Здравствуйте,

Я хочу в качестве экспериментальной работы написать на Java базовый интерпретатор JavaScript кода. Без JIT компиляции, без всяких сложных API, самый минимум. Встроенные объекты Math, String, Date, поддержка прототипов, вызов функций, области видимости, основные операторы, работа с переменными, вывод в консоль и алерты.

Но я не идеально знаю Java, и ещё меньше у меня знаний в области проектирования ПО. Прошу подсказать, как грамотно реализовать всё вышеизложенное. Основные вопросы:

1. Как в рантайме правильнее разграничить вызов нативных (реализованных на Java) функций и вызов функций на JavaScript (это весьма разные сущности)?
2. Как оптимальнее хранить scopes? Через Hashtable/HashMap в виде вектора (имитация стека) - нормальное решение?
3. Как правильно организовать поиск функций в цепочке прототипов объекта? Например, мы ищем функцию; она находится в прототипе, ссылку на который мы храним. Но при вызове такая функция должна работать с полями данных исходного объекта, а не прототипа, или прототипа прототипа и т.д. В JavaScript всё будет в такой ситуации работать корректно, а как такое грамотно эмулировать?
4. Эффективный алгоритм разбора выражений тоже не помешал бы. Как быстро разобрать строку, зная приоритеты операторов, корректно выделить все круглые скобки, которые могут быть вложены друг в друга, и т.д. Ссылки на любую литературу, в том числе англоязычную, приветствуются.

Заранее спасибо за советы.

Answer 1

[Даниил Колесниченко]

1. Как в рантайме правильнее разграничить вызов нативных (реализованных на Java) функций и вызов функций на JavaScript (это весьма разные сущности)?

Ну сделай разные классы для разных функций. JS динамически типизированный, так что в основном ты все равно будешь работать с каким-нибудь базовым абстрактным JsValue, от него и унаследуй классы функций. У класса JsValue сделай метод

JsValue call(scope: JsScope, context: JsValue, args: ArrayList<JsValue>)

который кидает TypeError: бла-бла-бла is not a function, а в классах функций (JsNativeFunction и JsFunction) переопредели его чтобы возвращал что-то.

2. Как оптимальнее хранить scopes? Через Hashtable/HashMap в виде вектора (имитация стека) - нормальное решение?

Я не эксперт, но я делал скоуп в виде хешмапа со ссылкой на родительский скоуп (и так по ссылкам можно было соответственно дойти до глобального скоупа), вроде нормальный вариант.

3. Как правильно организовать поиск функций в цепочке прототипов объекта? Например, мы ищем функцию; она находится в прототипе, ссылку на который мы храним. Но при вызове такая функция должна работать с полями данных исходного объекта, а не прототипа, или прототипа прототипа и т.д. В JavaScript всё будет в такой ситуации работать корректно, а как такое грамотно эмулировать?

Не вижу проблемы. x.foo(42) разворачивается во что-то типа этого:

JsObject xVar = scope.getVar("x");
xVar
    .attr("foo")    // ищет атрибут в объекте или в прототипе
    .call(scope, xVar, Arrays.asList(JsInt(42)));

Второй параметр метода call - это и есть контекст, то есть объект у которого вызывается метод.

4. Эффективный алгоритм разбора выражений тоже не помешал бы. Как быстро разобрать строку, зная приоритеты операторов, корректно выделить все круглые скобки, которые могут быть вложены друг в друга, и т.д. Ссылки на любую литературу, в том числе англоязычную, приветствуются.

Тут вряд ли что-то толковое подскажу, кроме как посмотреть в сторону ANTLR и аналогов.

P. S.
Немного литературы по теме

Comments

[Александр Попов]

Спасибо за ответ)

1. Сделать метод call у всех (в базовом классе), а не только у функций - интересная идея, надо будет подумать. Хотя наверное смысла нет, я собираюсь не динамически менять тип сущностей через поле, а создавать каждый раз новую нужного класса (а тип проверять через instanceOf). Они очень легковесные, мне кажется, падения производительности сильного не будет.
2. Нормальный вариант, но вектор наверное лучше тем, что есть ссылка на root scope (он часто нужен, когда какая-нибудь плохо написанная функция пишет переменные в глобальную область без var). Ну или просто ссылку на первый элемент списка хранить в переменной
3. Ну да, в самом деле, вы правы. Просто передавать ссылку на объект надо будет аргументом дополнительно в call

[Даниил Колесниченко]

Александр Попов,
1. Ну тут просто смысл в том что в рантайме обрабатывать попытку "вызова" значений, которые вызывать нельзя, все равно надо, а через оверрайдинг, как мне кажется, это делать удобнее всего.
2. Так нет, если функция пишет переменную без var, переменная не пишется сразу в родительский скоуп. Интерпретатор прыгает по родительским скоупам пока не найдёт где-то объявленную переменную с таким именем, и только если он так по цепочке скоупов дойдёт до глобального и нигде не найдёт такую переменную, то создаст новую в глобальном. Ну и да, ссылку на root scope не проблема хранить и при моём подходе.

[Даниил Колесниченко]

Ещё кстати надо как-то обрабатывать исключения. Я бы сделал так что все выражения возвращают не JsValue а какой-нибудь JsResult - аналог Result в Rust или Either в Haskell. Если вкратце, то у JsResult при таком подходе должно быть два наследника - JsOk, хранящий значение (JsValue) и JsError, хранящий ошибку и всякую дополнительную информацию.

[Даниил Колесниченко]

Вообще я не очень понимаю твою идею со скоупами. Типа во время вызова функции на стек кладётся новый хешмап, а после возвращения значения убирается со стека? А как же замыкания? Или-таки я неправильно понял твою идею?

[Даниил Колесниченко]

То есть я к тому что для работы с замыканиями как мне кажется тебе в любом случае придётся в самом объекте скоупа хранить ссылку на родительский скоуп.
Я делал это так: при создании функции в объекте функции сохраняется ссылка на скоуп в котором функция была создана (closure), потом при вызове функции есть хешмап со значениями переданными в качестве аргументов (argsdict) и также при вызове передаётся собственно скоуп в котором функция вызывается (scope). Соответственно при попытке получить переменную из тела функции порядок был таким: argsdict -> closure -> scope. Это правда не совсем оптимально, потому что фактически у closure и scope часть "предков" - общие, и по ним алгоритм проходился дважды. О том как не проходить по ним дважды тоже надо будет подумать тебе, ну в принципе ничего сложного по идее.

[Александр Попов]

Даниил Колесниченко, а, вон оно что... Учебники, по которым я учил JS, явно не очень написаны. Там говорилось про запись в window, подразумевая поведение внутри функций, которые оюбъявлены прямо в window scope. Спасибо.
Насчёт оверрайдинга - можно так, а можно просто при исполнении разобранной цепочки выражения в этом случае кидать эксепшен или просто писать ошибку юзеру, что обнаружена синтаксическая ошибка. Я на самом деле ещё не очень понял, как следует хранить операторы вызова. С бинарными арифметическими и побитовыми операторами всё ясно: у нас цепочка (в инфиксной или постфиксной форме, не важно) где лежат вперемешку значения и операторы (это разные сущности). Мы с этой цепочкой работаем, исполняя её по частям, с учётом приоритета операторов. А вот как быть с вызовом функции ("выражение(аргументы)"), я вот реально без понятия. Можно считать это таким особым оператором на произвольное число операндов, где важен их порядок (и между собой, и кто будет самым первым (имя функции, по которому её искать)). Но это какой-то вообще кривой и сложно реализуемый подход. Может, проще через какой-то костыль это сделать? Лишь бы он был простым и легко поддерживался :)

[Александр Попов]

Даниил Колесниченко, так идея замыкания ведь в чём? Если я правильно помню - обернуть функцию в ещё одну функцию, передав внешней функции часть аргументов, таких образом "заморозив" их значения для внутренней функции путём использования промежуточного скоупа. Вообще я понял, в чём несостыковка: скоуп надо учитывать тот, который был при объявлении функции, а не при вызове. Окей, тогда твой подход совершенно правильный. Насчёт того, что проходится дважды - да, это плохо. Код, в котором вообще нет замыканий - там эти две цепочки скоупов временами будут совпадать, временами же цепочка скоупов вызова будет содержать цепочку скоупов объявления (наоборот быть не может, мы не можем вызвать снаружи что-то, что объявлено в более вложенном скоупе, например функцию, вложенную в другую функцию). Может, стоит рассматривать сценарий с замыканиями вообще отдельно? В любом случае, есть ещё bind, который занимается тем же самым (может "прибить" к функции контекст, может "прибить" контекст и переменные). И его тоже хорошо бы реализовать.
UPD: Пардон, мы можем вызвать то, что внутри. Но только не напрямую, а если нам кто-то вернёт ссылку на эту функцию внутри переменной :)
UPD2: Как идея найти более длинную из цепочек и пройтись по ней? Ведь когда мы создаём замыкание (через "function(args) { return function ... }(...)"), мы это делаем уже внутри какого-то скоупа. И функция, которую мы получим, при своём вызове всё равно пойдёт вверх по всей этой цепочке. Из этого я делаю вывод, что достаточно лишь посмотреть, где функция была объявлена, и обойти лишь эту цепочку, этого будет достаточно. А эта информация, вроде как, неизменна. Можно один раз сохранить её вместе с функцией в момент её создания как сущности.

[Даниил Колесниченко]

Александр Попов,

мы это делаем уже внутри какого-то скоупа. И функция, которую мы получим, при своём вызове всё равно пойдёт вверх по всей этой цепочке.

Сначала да, но если там ничего не найдёт, пойдёт по цепочке скоупа в котором функция вызывалась.

[Даниил Колесниченко]

Александр Попов, вообще советую почитать
https://tc39.github.io/ecma262
dmitrysoshnikov.com/ecmascript/es5-chapter-3-1-lex...

[Александр Попов]

Даниил Колесниченко, статью прочитал, спасибо. Очень проясняет многие моменты.

Сначала да, но если там ничего не найдёт, пойдёт по цепочке скоупа в котором функция вызывалась.

Однако вот с этим ты не прав, имхо. Только что проверил в Хроме, это не работает. Да и в тексте по ссылке на это нет никаких намёков.

скриншот

[Даниил Колесниченко]

Александр Попов, чёрт, да, похоже ты прав, мой косяк. Ну да, тогда только по одной цепочке достаточно идти.

Answer 2

[Rsa97]

Собственно классика - Книга красного дракона

Answer 3

[Дмитрий Александров]

Открывай исходники штатного (nashorn, rhino) интерпретатора js в яве и читай\смотри как сделано. Кроме того в самой яве есть полноценный апи для сторонних скриптовых языков а кним и примеры.

Comments

[Александр Попов]

Не знал даже, что такое есть, интересно. То есть можно использовать готовый интерпретатор от Sun/Oracle в своём проекте, если лень писать свой?

[Дмитрий Александров]

Александр Попов, да можно и он очень мощный. Можно дергать код и классы явы из js так и наоборот js в яве.
все крайне просто и красиво:

ScriptEngineManager factory = new ScriptEngineManager();
ScriptEngine engine = factory.getEngineByName("nashorn");
engine.eval("print('Hello, World!');");

Дернуть класс явы в js, да запросто:

var MyClass = Java.type("some.package.MyClass");
var my = new MyClass();
my.printMsg("Hello!");

в яве надо будет также как и первом примере все но прочитать в BufferedReader скрипт и сделать engine.eval(полученное_с_ридера).
Тут много примеров еще.

Есть еще другие движки реализующие JSR 223(это и есть спецификация на апи для интеграция скриптовых языков). К примеру Jython, JRuby, luaj. Еще есть апачевский Bean Scripting Framework который реализует базовые фишки спецификации для облегчения написания своих языков или портирования существующих.

[Александр Попов]

Дмитрий Александров, большое спасибо. Я на самом деле ставил немного другую задачу: не интегрировать JS код в Java проект, а попробовать сделать свой браузерный движок. Но в любом случае, всё это крайне увлекательно, буду изучать.

Answer 4

[Ignat Khaylov]

Могу по 4 пункту подсказать: один из эффективных способов разбора строки с операторами является обратная польская запись

Comments

[Александр Попов]

Прочитал, разобрался. Спасибо

Answer 5

[Antonio Solo]

>> 4. Эффективный алгоритм разбора выражений

ищи варианты lex и yacc для java

а вообще тема построения компиляторов/интерпритаторов стара как мир

Comments

[Александр Попов]

А по остальным пунктам не посоветуете ничего?

[Antonio Solo]

Александр Попов, остальные вопросы специфичны для конкретного проекта.

p.s. javascript имеет довольно сложную архитектуру. мне потребовался бы не один день на то что бы спроектировать (хотя бы предварительно) схему разбора. я бы посоветовал для обучения взять что-то попроще - бейсик например.

[Александр Попов]

Antonio Solo, мне же подмножество только нужно. Арифметические операции, строки, массивы, объекты. Basic я во-первых не изучал, а JS знаю весьма неплохо. Плюс я делаю это как заделку к потенциально большему проекту (изначально свой браузерный движок планировался, потом понял, что слишком сложно для меня).