Пишем интерпретатор трехадресного кода / Хабр

Введение

Добрый день.
Продолжаю писать о около-компиляторных темах. В этот раз затрону вопрос о проектировании и создании интерпретатора, который работает с синтаксическими деревьями.
Рекомендую ознакомиться с предыдущей статьёй — «Пишем LR(0)-анализатор. Простыми словами о сложном», потому что в интерпретаторе я не строю синтаксический анализатор с нуля, а использую наработки, описанные в той статье. Ах да, еще один немаловажный момент — писать будем на JavaScript. Я не поклонник этого языка, но считаю что это наиболее удобный для общественности способ посмотреть результат. Не каждый рискнёт качать неизвестно что, да и это всё же сложнее чем просто открыть страничку. Нетипичность инструмента компенсируется «учебностью» примера. Скорость работы не важна (100-150 строк лимит, мне кажется больше никто не захочет набирать того чтобы поиграться с интерпретатором), а понятность кода у JS достаточно велика.

Трехадресный код

Для начала необходимо определиться с тем, что мы интерпретировать. Я выбрал трехадресный код.
Что это? Предполагалось, что это будет промежуточным языком между высокоуровневым кодом и компилируемым байт-кодом. К примеру, Сишная строка:

a = (b + c) * (d - e)

Превратится в такое:

f = b + c
g = d - e
a = f * g

Основной постулат этого языка — каждая команда содержит не более трех операндов. Это позволяет очень просто компилировать промежуточный код в байт-код.
Что же еще кроме арифметических операций будет содержать язык?
В первую очередь это объявления переменных и массивов. Все переменные — целочисленные. Кстати, индекс массива тоже считается операндом, поэтому в бинарных операциях мы не можем использовать массивы, дабы не превысить ограничение в 3 операнда. Переменные могут быть указателями (у нас тип указателя тождественно равен целочисленному).
Логично еще добавить в язык возможность ввода и вывода пользовательских данных. Также нужен контроль за исполнением кода (control flow) — условные и безусловные переходы. Ну и как же обойтись без стека, хотя он не нужен из-за того, что у нас неограниченное число переменных, но всё равно, часто он довольно удобен. Продумав язык, необходимо спроектировать грамматику. Это тоже не очень трудно сделать для нашего синтетического языка.

// строка исходника
<line> = <vars_decl>|<command>
// описание одной переменной
<var_decl> = <ident>|<ident><left_sq_bracket><number><right_sq_bracket>
// список переменных
<var_list> = <var_decl>|<var_list><comma><whitespace><var_decl>
// команда обявления списка
<vars_decl> = <var_keyword><whitespace><var_list>
// команда L: operation
<command> = <ident><colon><whitespace><operation>|<operation>
// операция
<operation> = <io>|<binary>|<control>|<assign>|<stack>
// ввод/вывод in var, out var
<io> = <in_keyword><whitespace><var_output_array>|<out_keyword><whitespace><var_input_array>
// куда можем записывать результат - [массив], переменная, разыменованный указатель
<var_output> = <var_ptr>|<ident>
<var_output_array> = <var_output>|<var_ar>
// массив
<var_ar> = <ident><left_sq_bracket><var_numb><right_sq_bracket>
<var_numb> = <ident>|<number>
// разыменование
<var_ptr> = <asterisk><ident>
// указатель
<var_ref> = <ref><ident>
// откуда можем брать значения - [массив], переменная, разыменованный указатель, указатель на переменную, константа
<var_input_array> = <var_input>|<var_ar>
<var_input> = <var_output>|<var_ref>|<number>
// массивы не доступны, ибо 3хоперандная грамматика
<binary> = <var_output><assign_sign><var_input><operator><var_input>
<operator> = <plus>|<minus>|<asterisk>|<div>|<mod>
// переходы
<control> = <goto>|<if>
// безусловный
<goto> = <goto_keyword><whitespace><ident>
// условный
<if> = <if_keyword><whitespace><var_input><comp_operator><var_input><whitespace><goto>
// присваивание
<assign> = <var_output_array><assign_sign><var_input>|<var_output><assign_sign><var_input_array>
// работа со стеком
<stack> = <pop_keyword><whitespace><var_output_array>|<push_keyword><whitespace><var_input_array>

Все остальные символы (которые есть в правых частях, но нет в левых) — это терминалы, их опишу чуть ниже.

Построение дерева синтаксического разбора

Как я писал раньше, на вход синтаксическому анализатору поступает поток лексем, этот поток производится лексическим анализатором на основе входной строки.
К примеру для строки

if a<b goto L

получим следующий поток лексем — LexKeywordIf, LexWhitespace, LexIdent, LexComp, LexIdent, LexWhitespace, LexKeywordGoto, LexWhitespace, LexIdent.
Легко проследить нужные лексемы из описания нетерминалов:

<ident> = <letter>|<ident><letter>|<ident><digit>
<number> = <digit>|<number><digit>
<plus> = '+'
<minus> = '-'
<div> = '/'
<mod> = '%'
<comp_operator> = '<'|'>'|'>='|'<='|'=='|'!='
<whitespace> = ' '
<pop_keyword> = "pop"
<push_keyword> = "push"
<goto_keyword> = "goto"
<in_keyword> = "in"
<out_keyword> = "out"
<var_keyword> = "var"
<if_keyword> = "if"
<left_sq_bracket> = '['
<right_sq_bracket> = ']'
<colon> = ':'
<asterisk> = '*'
<assign_sign> = '='
<ref> = '&'
<comma> = ','
$ = end of line

Сам код крайне прост, приведу лишь в общем виде:

function GetLex(stream)
{
    var c = stream.get();
    switch ( c )
    {
        case ' ': return {type: LexTypes.LexWhitespace};
        ...
    }
    if (c <= '9' && c >= '0')
        return {type: LexTypes.LexNumber, number: readNumber()};
    if (c > 'z' || c < 'a')
        return {type: LexTypes.LexError};
    var ident = readIdent();
    if (ident == 'pop') return {type: LexTypes.LexKeywordPop};
    ...
    return {type: LexTypes.LexIdent, ident: ident};
}

Теперь у нас есть поток лексем.
Можем его передавать синтаксическому анализатору. Конечно же я выбрал свой LR(0) с заранее сгенеренными таблицами для интерпретатора (как их получать я уже тоже писал). Получилось 82 состояния и 1400 строк форматированного кода под таблицы. Сам код парсера практически не претерпел изменений с аналогичным на C++, стоит лишь упомянуть о самой постройке дерева.
На каждое действие ActionShift мы создаём лист дерева (узел, который не имеет детей), содержащий нашу лексему. А когда сворачиваем правило связываем соответствующие символы правой части в один пучок, который образует новый узел, с указанием нетерминала этого узла (что из себя представляет узел в рамках нашей грамматики). Звучит немного сложно, однако на самом деле все просто, пример дерева для бинарной операции:

Структура интерпретатора и подготовка к запуску

Интерпретатор включает в себя дерево для каждой строки исходного кода, номер текущей строки (нужно для вывода ошибок, и в качестве IP — intruction pointer'a, адреса выполняемого кода), массив меток, массив переменных, собственно стек для стековых операций и пара объектов-хелперов.

Перед запуском необходимо обнулить все объекты. Затем мы выполняем синтаксический разбор каждой из строк. Зачем это делаем? Для того чтобы составить массив меток, так как в команде можем встретить переход на метку, которая располагается дальше в коде, чем выполняемая строка. Поэтому мы выполняем анализ кода перед началом исполнения. Здесь следует еще учесть такой момент, что даже если у нас попадется синтаксически неверная строка, то это не значит что нужно сразу же об этом рапортовать.
Мы можем при интерпретации и не достигнуть этого участка.

Исполнение кода

Я ввёл два режима выполнения — пошаговый и простой. Из названий очевидно что из себя представляет каждый из них.
Код:

function executeLine()
{
    if (input_data.active)
    {
        setTimeout(executeLine, 100);
        return ;
    }

    if (input_data.error)
        return ;
    var line = lines[currentline];
    var ret;
    if (!line.correct)
    {
        addlog('syntax error at position ' + line.pos);
        return ;
    }
    var general = line.tree.childs[0];
    if (general.nonterm == NonTerminals.vars_decl)
        ret = interp_var_list(general.childs[0]);
    else
        ret = interp_operation(general.childs[0]);
    if (!ret)
        return ;
    currentline++;
    if (currentline == linecount)
    {
        addlog('Finish!', true);
        return ;
    }
    if (!step_by_step)
        setTimeout(executeLine, 0);
}

input_data — это первый объект-хелпер. В JavaScript собственная событийная модель, и свои события использовать нет возможности, поэтому когда мы выводим диалог ввода значения (команда in) ставим флаг «заморозки» — input_data.active, означающий то, что нужно дождаться завершения диалога, и только после этого продолжить выполнять код. Второй объект — step_by_step, указывает на то, что используется пошаговый режим, если нет, то опять планируем вызов функции.
Само исполнение примитивно — почти для каждого нетерминала заводим функцию, которая обрабатывает его. И спускаемся по дереву собираем нетерминалы, получая их значения.
Пример обработки нетерминала :

function interp_control_goto(node)
{
    var ident = node.childs[0].lex.ident;
    if (ident in labels)
    {
        currentline = labels[ident] - 1;
        return true;
    }
    if (!check_var(ident))
        return false;
    var val = vars[ident];
    if (val >= linecount)
    {
        addlog('invalid address of code');
        return false;
    }
    currentline = val.value - 1;
    return true;
}

Посмотреть всё это в работе можно здесь, зеркало.
Лучше всего работает в FireFox'e, в Opera (keypress/keydown) не работает часть «фишек» редактора, в Хроме и IE (selectionStart) аналогично. Но сам интерпретатор работать должен штатно.
В качестве примера — рекурсивная функция вычисления факториала (перегруженная кодом, конечно, но это специально чтоб показать возможности языка).