Три черепахи, на которых стоит интерпретатор
В интерпретаторе традиционно выделяют три части: лексер, парсер, «виртуальная машина», которые формируют своеобразный конвейер переработки входного текста исходного кода в вычисленный результат (или те или иные действия по ходу) работы программы.
Архитектура интерпретатора
Лексер
Вход: строка (исходный код).
Выход: массив токенов.
Задача лексера — разбить входную строку на отдельные «атомы», минимальные неделимые части (например: числа и знаки операций). Такие минимальные части называются «токенами».
В конкретном языке программирования (на котором разрабатывается интерпретатор) список токенов представляется в виде массива.
Например, выражение 22 * 33
может быть представлено в виде массива [22, '*', 33]
(обратите внимание, что лексер должен разбивать строку на осмысленные части: в массив попали числа, но не отдельные цифры).
Лексер не делает никакого анализа содержимого.
На уровне лексера можно выполнить ряд второстепенных задач: например, удалить из исходного кода комментарии, сделать первичное приведение типов (преобразовать строки к числам и т. п.).
В средствах автогенерации парсеров зачастую используется более сложный вариант представления отдельного токена: в виде массива, первый элемент которого обозначает тип токена, а второй значение.
Например, выражение 22 * 33
может быть представлено следующим образом:
[ [:NUMBER, 22], [:OPERATOR, '*'], [:NUMBER, 33] ]
Это облегчает дальнейшую обработку токенов в парсере.
Парсер
Вход: массив токенов.
Выход: абстрактное синтаксическое дерево (AST).
Задача парсера — провести синтаксический разбор выражения. Результатом синтаксического разбора является абстрактное синтаксическое дерево (AST) заданной (разработчиком языка) структуры.
Данная часть пишется «по шаблону» с использованием известных методов или автоматизированных средств разработки.
Изучением этих шаблонов и инструментов, в основном, и посвящён данный цикл лекций.
Виртуальная машина (ВМ)
Вход: абстрактное синтаксическое дерево (AST).
Выход: результат вычисления (выполнения) программного кода.
Наконец, финальной частью является сердцевина интерпретатора — «виртуальная машина», которая исполняет код.
Есть разные подходы а архитектуре виртуальной машины и некоторый смысловой дрейф термина.
В наших учебных примерах отсутствует этап компиляции в байт-код и выполняется напрямую AST. Кроме того, наши примеры, фактически, эксплуатируют уже разработанную виртуальную машину языка разработки (RubyVM), поэтому в данном аспекте являются довольно упрощённой моделью разработки собственного языка «с нуля» на уровне, более близком к машинным кодам.
Пример
Код калькулятора инфиксных выражений, организованный в соответствии с описанными частями интерпретатора (в качестве парсера используется алгоритм сортировочной горки, прилагается: infix_calculator.rb
(repl).