пятница, 23 июля 2010 г.

Использование boost::spirit для создания встроенного языка с поддержкой переменных, функций и безопасным преобразованием типов

Необходимость в использовании собственного языка появилась в одном проекте, связанном с моделированием физических процессов (для посвященных - программа основана на библиотеке Geant4, разрабатываемой командой CERN). Суть задачи состояла в написании фильтра для удаления событий из двух результирующих файлов, удовлетворяющих определенным критериям. Проблема заключалась в том, что выбор критериев должен полностью определяться конечным пользователем и запрограммировать все варианты не представлялось возможным да и не имело смысла. Результирующие файлы представляют из себя бинарные архивы, созданные с помощью библиотеки boost::serialization и хранят большие коллекции объектов-событий, тип событий в первом файле назовем tpt, во втором - edt.

Итак, общий смысл разрабатываемого скриптового языка можно представить наглядно следующим мини-скриптом:

    delete edt if Sum( clEDcol ) > 350 * MeV
    keep edt if clEDcol[2,2] + clEDcol[2,3] > Sum( Outer( clEDcol ) )
    delete edt if Sum( Inner( crEDcol ) ) > 200 * MeV
    delete tpt if event > 500
    delete tpt if ! tpt
Как видно из приведенного фрагмента, выражение представляет из себя пару
    действие условие
и должно умещаться в одну строку. Действие указывает нужно ли удалить событие данного типа или же сохранить. Условие представляет из себя пару
    if логическое_выражение
Поскольку выражения будут обрабатываться последовательно сверху вниз, то будет выбрано действие, соответствующее первому условию, вычисленному как true.
Условие представляет из себя логическое выражение. Оно может содержать любые арифметические операции, логические операции, функции с одним аргументом и переменные, в том числе элементы n-мерного вектора типа:
    a[n1,n2]
Под безопасностью преобразования типов я имею ввиду следующее:
  1. Должны правильно соблюдаться целочисленные и вещественные преобразования, например 3/2 должно вычисляться как целое значение 1, а 3/2.0 должно вычисляться как вещественное значение 1.5.
  2. Операторы и функции, ожидающие контекст определенного типа, не должны получать аргументы другого типа (например, при попытке передать в функцию, ожидающую 2-мерный вектор, скалярное значение должно быть сгенерировано исключение).
Вычисление условного выражения выполняется в 2 этапа:
  1. Парсинг условного выражение и создание абстрактного синтаксического дерева (AST).
  2. Рекурсивное вычисление (эвалюация) AST. В процессе вычисления AST выполняется подстановка переменных (а еще лучше, их заранее замапленных адресов) и вычисление функций. Переменные связаны с полями прочитанного объекта либо с помощью вычисления, либо прямым маппингом адреса. В предложенном примере реализовано вычисление двух скалярных функций: Sqr() и Sqrt(). Ни одна переменная не определена. Для добавления функций и переменных достаточно создать новый класс, наследующий CexmcAST::BasicEval и переопределить в нем виртуальные функции GetFunScalarValue() и GetVarScalarValue().
Парсинг условия достаточно выполнить только один раз в начале выполнения программы. Второй этап вычисления нужно выполнять отдельно для каждого прочитанного объекта, так как переменные в выражении фактически связаны (вычисляются или замаплены) с полями объекта. Исключения, связанные с безопасностью преобразования типов, могут быть сгенерированы только на втором этапе вычисления условного выражения, поскольку на первом этапе еще ничего не известно о типах встречающихся функций и переменных.

Абстрактное синтаксическое дерево представляет собой рекурсивный тип, содержащий узлы и листья. Узлы могут содержать 1 (унарные операторы и функции) или 2 (бинарные операторы) детей. Верхушка AST всегда узел, так, для выражения типа
    delete tpt if 0
будет постороено дерево с верхушкой - унарным оператором Top, который возвращает вычисленное значение своего единственного ребенка. Для реализации AST был использован рекурсивный вариант из boost.

Для хранения результатов парсинга выражения я использовал следующий тип:
    struct  ParseResult
    {
        ParseResult() : action( KeepTPT )
        {}

        void  Initialize( void )
        {
            action = KeepTPT;
            expression.children.clear();
            expression.type = Uninitialized;
        }

        Action   action;

        Subtree  expression;
    };
где Action и Subtree определены как
    enum  Action
    {
        KeepTPT,
        KeepEDT,
        DeleteTPT,
        DeleteEDT
    };

    struct  Subtree
    {
        Subtree() : type ( Uninitialized ), hasRLAssoc( false )
        {}

        void  Print( int  level = 0 ) const;

        void  PrintLeaf( const Leaf *  leaf, int  level = 0 ) const;

        std::vector< Node >  children;

        NodeType             type;

        bool                 hasRLAssoc;

        static const int     printIndent = 4;
    };
Структура Subtree - это и есть реализация AST. Node предоставляет выбор между узлом и листом (т.к. дети могут являться и тем и другим), NodeType предоставляет выбор между оператором и функцией:
    typedef std::string                    Function;

    typedef variant< int, double >         Constant;

    typedef variant< Variable, Constant >  Leaf;

    typedef recursive_wrapper< Subtree >   Tree;

    typedef variant< Tree, Leaf >          Node;

    typedef variant< Operator, Function >  NodeType;
Для парсинга выражения необходимо определить формальную грамматику и семантические действия, которые в нашем случае будут заключаться в построениии AST. В boost::spirit для определения семантических действий можно использовать библиотеку boost::phoenix, которая была создана в недрах проекта spirit.
    template  < typename  Iterator >
    struct  Grammar : grammar< Iterator, ParseResult(), space_type >
    {
        Grammar();

        rule< Iterator, ParseResult(), space_type >            statement;

        rule< Iterator, Action(), space_type >                 action;

        rule< Iterator, Subtree(), space_type >                condition;

        rule< Iterator, Node(), space_type >                   expression;

        rule< Iterator, Node(), space_type >                   primary_expr;

        rule< Iterator, Node(), space_type >                   function1;

        rule< Iterator, std::string(), space_type >            identifier;

        rule< Iterator, Leaf(), space_type >                   leaf_operand;

        rule< Iterator, Leaf(), space_type >                   constant;

        rule< Iterator, Leaf(), space_type >                   variable;

        rule< Iterator, Node(), space_type >                   or_expr;

        rule< Iterator, Node(), space_type >                   and_expr;

        rule< Iterator, Node(), space_type >                   relation;

        rule< Iterator, Node(), space_type >                   addition;

        rule< Iterator, Node(), space_type >                   multiplication;

        rule< Iterator, Node(), space_type >                   unary_expr;

        rule< Iterator, Operator(), space_type >               unary_op;

        rule< Iterator, Operator(), space_type >               mult_op;

        rule< Iterator, Operator(), space_type >               add_op;

        rule< Iterator, Operator(), space_type >               rel_op;

        real_parser< double, strict_real_policies< double > >  strict_double;

        function< Compiler >                                   op;
    };


    template  < typename  Iterator >
    Grammar< Iterator >::Grammar() : Grammar::base_type( statement )
    {
        statement = action[ op( _val, _1 ) ] >>
                                        *( condition[ op( _val, _1 ) ] );

        action = lit( "keep" ) >>
                ( lit( "tpt" )[ _val = KeepTPT ] |
                  lit( "edt" )[ _val = KeepEDT ] ) |
                lit( "delete" ) >>
                ( lit ( "tpt" )[ _val = DeleteTPT ] |
                  lit ( "edt" )[ _val = DeleteEDT ] );

        condition = lit( "if" ) >> expression[ op( _val, _1 ) ];

        expression %= or_expr;

        identifier %= lexeme[ alpha >> *( alnum | lit( '_' ) ) ];

        primary_expr = function1[ op( _val, _1 ) ] |
               lit( '(' ) >> expression[ op( _val, _1 ) ] >> lit( ')' ) |
               leaf_operand[ _val = _1 ];

        leaf_operand %= constant | variable;

        constant %= strict_double | int_;

        variable = identifier[ op( _val, _1 ) ] >>
                -( lit( '[' ) >> ( uint_[ op( _val, _1, 0 ) ] - lit( '0' ) ) >>
                   -( lit( ',' ) >> ( uint_[ op( _val, _1, 1 ) ] -
                      lit( '0' ) ) ) >> lit( ']' ) );

        function1 = ( identifier >> lit( '(' ) >> expression >> lit( ')' ) )
                    [ op( _val, _2, _1 ) ];

        or_expr = ( and_expr >> lit( '|' ) >> or_expr )
                  [ op( _val, _1, _2, Or ) ] |
                  and_expr[ _val = _1 ];

        and_expr = ( relation >> lit( '&' ) >> and_expr )
                   [ op( _val, _1, _2, And ) ] |
                   relation[ _val = _1 ];

        relation = ( addition >> rel_op >> addition )
                   [ op( _val, _1, _3, _2 ) ] |
                   addition[ _val = _1 ];

        addition = ( multiplication >> add_op >> addition )
                   [ op( _val, _1, _3, _2 ) ] |
                   multiplication[ _val = _1 ];

        multiplication = ( unary_expr >> mult_op >> multiplication )
                         [ op( _val, _1, _3, _2 ) ] |
                         unary_expr[ _val = _1 ];

        unary_expr = ( unary_op >> primary_expr )[ op( _val, _2, _1 ) ] |
                     primary_expr[ _val = _1 ];

        unary_op = lit( '-' )[ _val = UMinus ] | lit( '!' )[ _val = Not ];

        mult_op = lit( '*' )[ _val = Mult ] | lit( '/' )[ _val = Div ];

        add_op = lit( '+' )[ _val = Plus ] | lit( '-' )[ _val = Minus ];

        rel_op = lit( "<=" )[ _val = LessEq ] |
                 lit( ">=" )[ _val = MoreEq ] |
                 lit( "!=" )[ _val = NotEq ] |
                 lit( '<' )[ _val = Less ] |
                 lit( '>' )[ _val = More ] |
                 lit( '=' )[ _val = Eq ];
    }
Грамматические правила выражаются через вложенные правила, связанные между собой посредством операторов >> и |, и описания семантических действий, заключенных в квадратные скобки после вложенных правил. В простейшем случае правило может представлять собой лексему вида lit( "if" ). Оператор >> создает цепочку сканирования. Для получения соответствия сканируемого текста данному правилу необходимо чтобы вся цепочка соответствовала сканируемому тексту. Оператор | может применяться к цепочкам сканирования или отдельным правилам в выражении и предоставляет парсеру возможность выбора между его операндами: если левый операнд оператора | соответствует сканируемому участку, то будет выбран именно он, иначе парсер попытается выбрать правый операнд.
Правила могут быть рекурсивными, то есть ссылаться в своем определении на самих себя, например правило multiplication содержит в своем определении multiplication. Однако здесь присутствует одно очень важное ограничение: вложенность не должна создавать левую рекурсию, т.е. выражения, в которых явно или неявно определяемое правило входит в собственное выражение слева (причем неважно в какой из ветвей, разделенных оператором |), недопустимы. Например, правило
        multiplication = ( multiplication >> mult_op >> unary_expr )
                         [ op( _val, _1, _3, _2 ) ] |
                         unary_expr[ _val = _1 ];
недопустимо. Его использование не приведет к ошибке компиляции, однако в рантайме программа обязательно упадет.
Самое простое семантическое действие может быть выражено как [ _val = _1 ], здесь используются определенные в boost переменные, _val связана с результирующим правилом и представляет собой ссылку на его сигнатуру. Если посмотреть на определения правил, например правила multiplication:
        rule< Iterator, Node(), space_type >                   multiplication;
то можно заметить, что они могут создаваться с использованием конструкторов некоторых типов - сигнатур, в данном случае сигнатурой является Node(), это означает, что к правилу будет привязан объект типа Node. Переменная _1 - это ссылка на сигнатуру того правила, к которому применяется семантическое действие. Если семантическое действие применяется к выражению, заключенному в круглые скобки (например, цепочке сканирования), то могут быть задействованы переменные _2 и _3, ссылающиеся на сигнатуры правил, входящих в выражение. В простейшем случае, если сигнатуре результирующего правила нужно присвоить сигнатуру всего выражения справа (или, как частный случай, подвыражений, выбранных оператором |), можно использовать оператор %=, например:
        expression %= or_expr;
Более сложные семантические правила реализуются с помощью вспомогательного объекта op типа Compiler, который определен как
    struct  Compiler
    {
        template < typename  A, typename  B = boost::fusion::unused_type,
                   typename  C = boost::fusion::unused_type,
                   typename  D = boost::fusion::unused_type >
        struct  result { typedef void  type; };

        void  operator()( ParseResult &  parseResult, Action  value ) const;

        void  operator()( ParseResult &  parseResult, Subtree &  value ) const;

        void  operator()( Subtree &  ast, Node &  node ) const;

        void  operator()( Node &  self, Node &  left, Node &  right,
                          Operator  value ) const;

        void  operator()( Node &  self, Node &  child, Operator  value ) const;

        void  operator()( Node &  self, Node &  primary ) const;

        void  operator()( Node &  self, Node &  child, std::string &  value )
                                                                        const;

        void  operator()( Leaf &  self, std::string &  name ) const;

        void  operator()( Leaf &  self, int  value, size_t  index ) const;
    };
Реализацию операторов можно увидеть в прилагаемом коде.

Для того, чтобы запустить парсер и заполнить объект типа ParseResult, нужно вызвать функцию phrase_parse():
    phrase_parse( begin, end, customFilterGrammar,
                  CexmcCustomFilter::space, parseResult )
Здесь begin и end - итераторы на начало и конец обрабатываемого текста, customFilterGrammar - объект типа Grammar, parseResult - ссылка на объект типа ParseResult, который будет заполнен в результате действия phrase_parse(). Объект грамматики связан с типом ParseResult через Grammar::base_type, который соответствует правилу statement, сигнатурой которого в свою очередь является ParseResult(). Функция phrase_parse() ограждает пользователя от заботы о пробельных символах во время парсинга. Она возвращает false в случае неудачи, также неудачей можно считать случай частичного совпадения, когда begin не равен end после возвращения из phrase_parse()(итератор begin смещается в процессе парсинга и в случае успеха должен совпасть с end).
Некоторые тонкости реализации грамматики:
  1. Как видно из определений правил, все арифметические и логические правила выражены через правила более высокого приоритета и сами себя - например операциии сложения addition определены через multiplication и addition. Определение операции через операции более высокого приоритета позволяет соблюдать приоритет операций при построении AST. Определение операции через саму себя позволяет выстраивать цепочки этой операции в выражениии, например 4 + 8 + 10 - 2. Исключением являются операции отношения - правило relation, они выражаются только через операции более высокого приоритета, это не позволяет выстраивать их в цепочки. В самом деле, выражение a > 7 > b недопустимо.
  2. Проблема левой рекурсии и левоассоциативности. Взгляните еще раз на определение правила multiplication. Оно выражается через само себя и unary_expr. Запрет левой рекурсии означает, что unary_expr должен стоять левее, чем операнд multiplication. В свою очередь, это означает, что выражение 2 * 5 / 7 будет вычислено как 2 * (5 / 7), что даст неверный результат, так как операции умножения и деления левоассоциативны. Проблему можно решить двумя способами: привести леворекурсивное правило к праворекурсивному (это всегда возможно), или учесть изменение порядка операций в соответствующем операторе () типа Compiler, не изменяя синтаксическое правило. Я решил пойти вторым путем, соответствующий оператор выглядит следующим образом:
  3.     void  Compiler::operator()( Node &  self, Node &  left, Node &  right,
                                    Operator  value ) const
        {
            Subtree &  ast( boost::get< Subtree >( self ) );
    
            ast.children.push_back( left );
            ast.type = value;
    
            Subtree *  astRight( boost::get< Subtree >( &right ) );
    
            if ( ! astRight )
            {
                ast.children.push_back( right );
                return;
            }
    
            bool        hasLessPriorityThanRightOp( false );
            Operator *  rightOp( boost::get< Operator >( &astRight->type ) );
    
            if ( rightOp )
            {
                hasLessPriorityThanRightOp = OperatorPriority::IsLessThan(
                                                                value, *rightOp );
            }
    
            if ( astRight->hasRLAssoc || hasLessPriorityThanRightOp )
            {
                ast.children.push_back( right );
                return;
            }
            ast.children.push_back( astRight->children[ 0 ] );
            Subtree    astResult;
            astResult.children.push_back( self );
            astResult.children.push_back( astRight->children[ 1 ] );
            astResult.type = astRight->type;
            self = astResult;
        }
    
  4. Взгляните на определение правила constant:
            constant %= strict_double | int_;
    
    Правило strict_double - это видоизмененное правило double_, которое не позволяет парсить как double целочисленные значения:
            real_parser< double, strict_real_policies< double > >  strict_double;
    
    Проблема поднималась на форумах (см. например здесь) и было предложено это решение.
После успешного завершения парсинга мы имеем набор (в прилагаемом примере только один) объектов типа ParseResult. Все что остается сделать - это рекурсивно пройтись по выражениям expression этих объектов, подставляя значения переменных и выполняя функции. Для этого предназначен класс CexmcAST::BasicEval:
    class  BasicEval
    {
        protected:
            typedef variant< int, double >  ScalarValueType;

        protected:
            virtual ~BasicEval();

        public:
            bool  operator()( const Subtree &  ast ) const;

        protected:
            ScalarValueType          GetScalarValue( const Node &  node ) const;

            virtual ScalarValueType  GetFunScalarValue( const Subtree &  ast )
                                                                        const;

            virtual ScalarValueType  GetVarScalarValue( const Variable &  var )
                                                                        const;

            ScalarValueType          GetBasicFunScalarValue(
                                        const Subtree &  ast, bool &  result )
                                                                        const;
    };
Единственная публичная функция данного класса: operator(), которая принимает объект типа Subtree в качестве аргумента и вызывает рекурсивную функцию GetScalarValue(). Кроме того, BasicEval предоставляет две виртуальные функции GetFunScalarValue() и GetVarScalarValue(), которые можно использовать в классах-наследниках для определения дополнительных функций и переменных. Также, в классе-наследнике можно определить соответствующие функции, связанные с обработкой функций и переменных нескалярных типов.

Взять исходный код примера можно здесь (с исправлениями, указанными в этом обновлении).

Комментариев нет:

Отправить комментарий