Три черепахи, на которых стоит интерпретатор

В интерпретаторе традиционно выделяют три части: лексер, парсер, «виртуальная машина», которые формируют своеобразный конвейер переработки входного текста исходного кода в вычисленный результат (или те или иные действия по ходу) работы программы.

Архитектура интерпретатора

Лексер

Вход: строка (исходный код).

Выход: массив токенов.

Задача лексера — разбить входную строку на отдельные «атомы», минимальные неделимые части (например: числа и знаки операций). Такие минимальные части называются «токенами».

В конкретном языке программирования (на котором разрабатывается интерпретатор) список токенов представляется в виде массива.

Например, выражение 22 * 33 может быть представлено в виде массива [22, '*', 33] (обратите внимание, что лексер должен разбивать строку на осмысленные части: в массив попали числа, но не отдельные цифры).

Лексер не делает никакого анализа содержимого.

На уровне лексера можно выполнить ряд второстепенных задач: например, удалить из исходного кода комментарии, сделать первичное приведение типов (преобразовать строки к числам и т. п.).

В средствах автогенерации парсеров зачастую используется более сложный вариант представления отдельного токена: в виде массива, первый элемент которого обозначает тип токена, а второй значение.

Например, выражение 22 * 33 может быть представлено следующим образом:

[ [:NUMBER, 22], [:OPERATOR, '*'], [:NUMBER, 33] ]

Это облегчает дальнейшую обработку токенов в парсере.

Парсер

Вход: массив токенов.

Выход: абстрактное синтаксическое дерево (AST).

Задача парсера — провести синтаксический разбор выражения. Результатом синтаксического разбора является абстрактное синтаксическое дерево (AST) заданной (разработчиком языка) структуры.

Данная часть пишется «по шаблону» с использованием известных методов или автоматизированных средств разработки.

Изучением этих шаблонов и инструментов, в основном, и посвящён данный цикл лекций.

Виртуальная машина (ВМ)

Вход: абстрактное синтаксическое дерево (AST).

Выход: результат вычисления (выполнения) программного кода.

Наконец, финальной частью является сердцевина интерпретатора — «виртуальная машина», которая исполняет код.

Есть разные подходы а архитектуре виртуальной машины и некоторый смысловой дрейф термина.

В наших учебных примерах отсутствует этап компиляции в байт-код и выполняется напрямую AST. Кроме того, наши примеры, фактически, эксплуатируют уже разработанную виртуальную машину языка разработки (RubyVM), поэтому в данном аспекте являются довольно упрощённой моделью разработки собственного языка «с нуля» на уровне, более близком к машинным кодам.

Пример

Код калькулятора инфиксных выражений, организованный в соответствии с описанными частями интерпретатора (в качестве парсера используется алгоритм сортировочной горки, прилагается: infix_calculator.rb (repl).