Введение
Добрый день.
Продолжаю писать о около-компиляторных темах. В этот раз затрону вопрос о проектировании и создании интерпретатора, который работает с синтаксическими деревьями.
Рекомендую ознакомиться с предыдущей статьёй — «Пишем 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Легко проследить нужные лексемы из описания нетерминалов:
<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) аналогично. Но сам интерпретатор работать должен штатно.
В качестве примера — рекурсивная функция вычисления факториала (перегруженная кодом, конечно, но это специально чтоб показать возможности языка).
