Пример использования библиотеки boost::spirit

Author / Автор: Сергей Сацкий

Publication date / Опубликовано: 23.09.2005
Version / Версия текста: 1.3

Введение

Задачи лексического, синтаксического и семантического анализа часто встречаются в повседневной практике разработчика программного обеспечения. Чаще всего в качестве входного потока выступает обычный символьный поток. Типичный пример подобного рода задачи - разбор файла настроек для какого-либо программного модуля. Такие задачи обычно решаются с помощью инструментария подобного flex и yacc. Однако для C++ существует более изящное решение. Библиотека boost::spirit позволяет существенно облегчить упомянутые этапы анализа, предлагая при этом компактную и ясную запись, легкую для внесения последующих изменений.

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

Задача

Предположим, что имеется система сбора информации от различных датчиков. Собранные данные необходимо показывать на экране. Однако значение, например, датчика скорости, нужно для одних пользователей отображать в метрах в секунду, а для других - в милях в час. Кроме того, необходимо поддержать различные модели датчиков, которые поставляют измерения в различных единицах. Для решения этой проблемы можно в текстовый файл настроек поместить формулу пересчета, описывающую способ преобразования полученного значения в его экранное представление. А в коде понадобится аналог C++ - функции, подобной представленной ниже:

double Calculate( double  CollectedValue )
{
    double    RequiredValue( 0.0 );
    . . .
        // Расчет значения RequiredValue на основе CollectedValue 
        // по формуле из файла настроек
    . . .
    return RequiredValue;
}

Пересчет значения скорости необходимо выполнять каждый раз, когда значение от датчика обновляется. На основе формулы пересчета, прочитанной из файла настроек, можно построить интерпретатор, однако скорость его работы будет значительно меньше, чем если бы вычисления производила виртуальная машина, код для которой строился бы ровно один раз - в момент чтения формулы.

В статье рассматривается разработка транслятора формулы пересчета и виртуальная машина, производящая требуемые вычисления.

Формализация задачи

Слегка упростим задачу, опустив чтение из формулы пересчета из файла, и реализуем схему, показанную на рисунке 1.

Рисунок 1. Блок схема решения поставленной задачи.

Разработаем два исполняемых модуля: транслятор и виртуальную машину.

Транслятор будет принимать формулу пересчета со стандартного ввода. Результатом его работы будет промежуточный код, выдаваемый на стандартный вывод. В формуле пересчета поддержим основные математические действия, скобки, константы с плавающей точкой, пару тригонометрических функций и ключевое слово value. Ключевое слово value будет означать подстановку значения для производства вычислений. Например, подобная формула пересчета будет корректно обработана транслятором:

value / 1.6 * sin( value + 0.4 )

Виртуальная машина будет принимать входное значение для пересчета как аргумент командной строки, а код для исполнения со стандартного ввода. Результатом работы виртуальной машины будет вычисленное значение, которое будет помещено в стандартный вывод.

В реальном приложении оба эти модуля могут быть совмещены в одном исполняемом модуле. Здесь же они разделены с целью упрощения рассуждений и упрощения возможности повторного использования.

Транслятор

Разумеется, транслятор и виртуальная машина тесно связаны между собой. Транслятор должен учитывать модель, которую использует виртуальная машина, а также набор команд, понимаемый виртуальной машиной.

Одним из самых простых вариантов виртуальных машин является стековая машина. Такая машина хорошо подходит для математических выражений. Любое математическое выражение можно преобразовать к обратной бесскобочной форме, которая, в свою очередь, будет очень близка к последовательности команд для стековой машины, вычисляющей значение выражения.

Однако требовать записывать формулу пересчета в обратной бесскобочной форме было бы неразумно. Человеку привычнее использовать скобки для указания приоритета операций, а для двуместных операций привычнее записывать аргументы слева и справа от символа операции. Требование записи формулы в обратной бесскобочной форме привело бы к большому количеству ошибок, поэтому возложим анализ формулы, записанной в привычной для человека форме, на транслятор.

Перед тем, как приступить к реализации транслятора, необходимо обсудить систему команд виртуальной машины и способ хранения команд. Команды виртуальной машины могут быть закодированы в виде целых чисел, однако, для упрощения процесса отладки, воспользуемся строковым представлением команд. Что касается набора команд, то нам потребуется команда помещения на вершину стека константы типа double, а также команды соответствующие двуместным математическим операциям, унарному минусу и вычислениям значений поддерживаемых функций. Операции, требующие аргументов, будут брать их с вершины стека, передвигая вершину стека, а результаты выполнения операций будут снова помещаться на вершину стека.

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

Например, последовательность команд

PUSH    154.0
PUSH    16.3
ADD

произведет сложение 154 + 16.3, а результат - 170.3 - будет помещен на вершину стека. Таким образом, результатом работы виртуальной машины всегда будет значение, лежащее на вершине стека, а глубина стека при этом должна быть равна единице.

Теперь необходимо обсудить разрешенный синтаксис для записи формул пересчета в деталях. Для определения синтаксиса удобно воспользоваться контекстно-свободной грамматикой (формой Бэкуса-Наура). Библиотека boost::spirit позволяет в C++ коде практически напрямую записать грамматику в форме Бэкуса-Наура. Например, синтаксические графы, описывающие разрешенные формулы пересчета, будут выглядеть так:

Рисунок 2. Синтаксические графы, описывающие разрешенные формулы пересчета.

В C++ коде, использующем библиотеку boost::spirit, эквивалент таких синтаксических графов будет выглядеть следующим образом (оператор разрешения области видимости boost::spirit:: опущен):

    . . .
    Function = 
        ( str_p( "sin" ) >> '(' >> Expression >> ')' )  |
        ( str_p( "cos" ) >> '(' >> Expression >> ')' );

    Double =
        lexeme_d[ (+ureal_p) ]       |
        str_p( "value" );

    Factor =
        Double | Function | '(' >> Expression >> ')'    |   
        ('-' >> Factor)                                 |
        ('+' >> Factor);

    Term =
        Factor
        >> *(   ('*' >> Factor)
            |   ('/' >> Factor)
            );

    Expression =
        Term
        >> *(   ('+' >> Term)
            |   ('-' >> Term)
            );
    . . .

Здесь str_p( . . . ) и ureal_p - парсеры, а lexeme_d - директива, предоставляемые библиотекой (см. [1]). Операторы *, | и >> перегружены библиотекой таким образом, чтобы получившийся синтаксис был максимально близок к форме Бэкуса-Наура.

Следующий этап - это привязка семантических действий к распознанным синтаксическим элементам. boost::spirit поддерживает operator[ ] для таких действий. Например, для распознанных тригонометрических функций привязку функтора PushOperation можно записать так:

    . . .
    Function = 
        ( str_p( "sin" ) >> '(' >> Expression >> ')' )
            [ PushOperation( "SIN", Self.Code ) ]      |
        ( str_p( "cos" ) >> '(' >> Expression >> ')' )
            [ PushOperation( "COS", Self.Code ) ];
    . . .

Функтор можно PushOperation реализуем следующим образом:

struct PushOperation
{
    PushOperation( const string &  cop, vector< string > &  code ) :
        COP( cop ), Code( code )
    {}
    
    void operator() ( char const *  Unused, char const *  End ) const
    {
        Code.push_back( COP );
    }
    
    string              COP;    //!< Code of OPeration
    vector< string > &  Code;   //!< Reference to the code version
};

Функтор добавляет команду виртуальной машины в вектор кода, выполняющего требуемые вычисления.

Содержимое вектора кода будет распечатано на стандартном выводе в конце работы транслятора. Подобным образом можно записать полную грамматику для поддержки требуемого синтаксиса с привязанными нужными семантическими действиями.

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

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

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

class SCalculator
{
    public:
        SCalculator( const vector< string > &  code ) :
            Code( code )
        {
                // The stack size cannot be larger than the code size
            Stack.reserve( Code.size() );
        }
        
        double Calculate( const double &  Value ) 
        {
            . . .
        }

    private:
        vector< string >    Code;       // Code storage
        vector< double >    Stack;      // Working space - stack of doubles
};

Метод Calculate должен сначала очистить стек, на случай многократных вызовов, а затем выполнить все команды из вектора кода:

double SCalculator::Calculate( const double &  Value ) 
{
        // Clear the stack for reuse
    Stack.clear();
            
        // Walk the whole code
    for ( vector< string >::const_iterator  k( Code.begin() );
          k != Code.end(); ++k )
    {
        if ( *k == "ADD" )
        {
            double      Temp( Stack.back() );

            Stack.pop_back();
            Stack[ Stack.size() - 1 ] = Stack.back() + Temp;

            continue;
        }

        if ( *k == "SUB" )

        . . .

    }

    return Stack.back();
}

Остальные команды реализуются похожим образом.

Исходные тексты

Полные исходные тексты транслятора и виртуальной машины, разработанные в статье, можно найти на web сайте автора (http://satsky.spb.ru). Там же доступна сгенерированная по исходным текстам doxygen документация.

Заключение

Библиотека boost::spirit позволяет работать с любыми входными потоками. Ее можно эффективно применять для работы с произвольными двоичными потоками.

Пытливому читателю

В качестве самостоятельной работы читатель может сделать виртуальную машину доступной по сети. Это легко сделать с помощью стандартных средств UNIX, поскольку разработанная виртуальная машина работает со стандартным вводом и выводом. Необходимо добавить пользователя, указав в качестве shell исполняемый модуль виртуальной машины. Теперь можно подключиться с помощью telnet или ssh к машине и пройти авторизацию как вновь созданный пользователь. Консоль станет стандартным вводом и выводом виртуальной машины. Завершив ввод команд виртуальной машины, получим результат вычислений.

Литература

1. Документация по библиотеке boost::spirit (http://www.boost.org)
2. Aho A., Sethi R., Compilers. Principles, Techniques, and Tools. Addison Wesley, 1985
3. Sebesta R. Concepts of Programming Languages. Addison Wesley, 2002