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

    Введение



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

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


    Интерпретатор включает в себя дерево для каждой строки исходного кода, номер текущей строки (нужно для вывода ошибок, и в качестве 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) аналогично. Но сам интерпретатор работать должен штатно.
    В качестве примера — рекурсивная функция вычисления факториала (перегруженная кодом, конечно, но это специально чтоб показать возможности языка).
    • +31
    • 5,6k
    • 8
    Поделиться публикацией

    Похожие публикации

    Комментарии 8

      0
      Посмотреть всё это в работе можно здесь.

      Page does not exist! Read the Full Documentation
      Instructions for setting up username.github.com *

      Да и было бы лучше что бы вы пример запостили куда-то вживую (например pastehtml.com/), а не собирать пример самому из скачаных исходников.
        0
        там не нужно собирать, github предоставляет так же возможность публикации статик-страниц.
        Но как-то не стабильно работает эта функция, сразу не всегда открывает.
        –1
        а micromodal вам больше нравиться нежели jqm?)
          0
          ради 2х простеньких диалогов подойдет имхо практически любой плагин.
          если бы их были десятки, то тогда можно было бы поискать лучший.
          0
          Спасибо. Интересная статья. Разрешите задать несколько дилетантских вопросов?

          Реально ли (теоретически) описать грамматику для ваших анализаторов, чтобы получился интерпретатор С++? Хотя бы без темплейтов.

          Какая пропасть лежит между «деревом исходного кода» и объектным файлом для x86 формата Elf/WinPE? То есть если вообще отказаться от любой оптимизации, насколько сложно из дерева построить объектный файл? Есть ли такие планы на будущее?

          P.S. Одно время я искал русскоязычных разработчиков компиляторов, нашёл, да не тех — один умелец, судя по всему, потерял интерес к своему проекту и пропал из видимости, второй вёл оживлённую переписку, но когда дело дошло до дела — сказал, что он уже давно живёт в США и пишет мемуары, а третий вообще не нашёл нужным общаться.

          P.P.S. Этот вопрос несколько не по теме. Насколько реально создать линкёр, который мог бы связывать объектные файлы разных форматов, а именно Elf и WinPE? И чтобы формат выходного файла чтобы задавался ключом.

            +2
            Реально ли (теоретически) описать грамматику для ваших анализаторов, чтобы получился интерпретатор С++? Хотя бы без темплейтов.

            Вполне, только само собой не LR(0)-анализатор используется, да и большую часть кода генерит «компилятор компиляторов» — yacc.
            Если интересно — ftp.iecc.com/pub/file/c++grammar/
            Какая пропасть лежит между «деревом исходного кода» и объектным файлом для x86 формата Elf/WinPE? То есть если вообще отказаться от любой оптимизации, насколько сложно из дерева построить объектный файл?

            После синтаксического анализа идёт этап семантического (контекстного), который работает не с конкретной синтаксической единицей, а со всем кодом (например, проверка типизации, если объявили int a, а через 10 строк записываем туда float). После этого чаще всего происходит оптимизация (возможно перед оптимизацией перевод во внутренний промежуточный язык, в качестве которого можно использовать и описанный в статье). Далее идёт кодогенерация, это процесс получения байт-кода, понятного машине (виртуальной, а-ля Java, или реальной — x86, arm, ...). А уже потом приходит время «форматтера» — модуля, который собирает получившийся байт-код в один из форматов, ожидаемый на выходе (объектные чаще всего, но можно генерировать сразу в исполняемый, как делает например компилятор fasm). Такие дела. Для простейшего языка, наподобие трехадресного, кодогенерация проста, а сложность форматтера зависит от сложности выходного формата, что логично.
            Есть ли такие планы на будущее?

            Именно ELF/PE не особо интересует в том плане, что существует довольно большое число открытых исходников и компиляторов, и форматтеров. Достаточно умеючи выпилить их из сорцов и использовать в своих проектах.
            P.P.S. Этот вопрос несколько не по теме. Насколько реально создать линкёр, который мог бы связывать объектные файлы разных форматов, а именно Elf и WinPE?

            Иногда возможно, если присутствует необходимая информация, например таблица релокации.
            Чтоб точно ответить на вопрос нужно внимательно изучить и сравнить оба этих формата.
            0
            switch ©
            Ну хабрапарсер как всегда…

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое