Реализация парсера пользовательского языка на Haskell

Итак, я выкладываю версию парсера пользовательского языка с поддержкой арифметических выражений с функциями и переменными, написанную на функциональном языке Haskell. С грамматикой языка можно ознакомиться, прочитав мое первое сообщение в этом блоге. Задачей программы, как и прежде, будет построение абстрактного синтаксического дерева (AST) для отдельных инструкций языка. В отличие от версии, написанной на boost::spirit, я не стал реализовывать базовый эвалюатор полученных деревьев, хотя сделать это не сложно.

В качестве лексера и грамматического анализатора я использовал alex и happy соответственно, которые входят в состав Haskell Platform; alex анализирует исходный код лексера (с расширением .x), а happy анализирует исходный код грамматики (с расширением .y). Обе программы генерируют соответствующие файлы с расширением .hs. Фактически, исходные коды лексера и грамматики состоят по большей части из кода на Haskell (все, что находится в этих файлах в фигурных скобках, является валидным кодом Haskell), и лишь небольшое количество мета-объявлений предназначено для предварительной обработки alex и happy.

Описание грамматики языка для happy совместимо с описанием для boost::spirit несмотря на то, что внутренне эти два генератора парсеров реализованы по-разному (happy генерирует LALR парсер, а spirit - парсер с рекурсивным спуском). Хотя проблема левой рекурсии в happy исчезает, и, кроме того, happy предоставляет дополнительные возможности вроде указания приоритета операторов, я не стал изменять реализацию грамматики по сравнению с версией для boost::spirit.

Итак, грамматика нашего пользовательского языка в версии haskell / happy выглядит следующим образом:

Statement : Action Condition { ParseResult $1 $2 }

Action : keep tpt    { KeepTpt }
       | keep edt    { KeepEdt }
       | delete tpt  { DeleteTpt }
       | delete edt  { DeleteEdt }

Condition :: { Subtree }
Condition : if Expression { buildTopTree $2 }

Expression :: { Node }
Expression : OrExpression { $1 }

PrimaryExpression : Function1 { buildFunction1Subtree $1 }
                  | '(' Expression ')' { setPriorityInOperatorTree 0 $2 }
                  | LeafOperand { Leaf $1 }

LeafOperand : Constant { Constant $1 }
            | Variable { Variable $1 }

Constant : double { DoubleValue $1 }
         | integer { IntegerValue $1 }

Variable : identifier '[' integer ',' integer ']' { Vector2 $1 $3 $5 }
         | identifier '[' integer ']' { Vector1 $1 $3 }
         | identifier { Scalar $1 }

Function1 : identifier '(' Expression ')' { Function1 $1 $3 }

OrExpression : AndExpression '|' OrExpression
               { buildOperatorSubtree ( Op ( LogOp Or ) 1 False ) $1 $3 }
             | AndExpression { $1 }

AndExpression : Relation '&' AndExpression
                { buildOperatorSubtree ( Op ( LogOp And ) 2 False ) $1 $3 }
              | Relation { $1 }

Relation : Addition RelOperator Addition
           { buildOperatorSubtree ( Op ( RelOp $2 ) 3 False ) $1 $3 }
         | Addition { $1 }

Addition : Multiplication AddOperator Addition
           { buildOperatorSubtree ( Op ( AddOp $2 ) 4 False ) $1 $3 }
         | Multiplication { $1 }

Multiplication : UnaryExpression MultOperator Multiplication
                 { buildOperatorSubtree ( Op ( MultOp $2 ) 5 False ) $1 $3 }
               | UnaryExpression { $1 }

UnaryExpression : UnaryOperator PrimaryExpression
                  { buildUnaryOperatorSubtree ( Op ( UnaryOp $1 ) 6 True ) $2 }
                | PrimaryExpression { $1 }

UnaryOperator : '-' { UMinus }
              | '!' { Not }

MultOperator : '*' { Mult }
             | '/' { Div }

AddOperator : '+' { Plus }
            | '-' { Minus }

RelOperator : "<=" { LessEqual }
            | ">=" { MoreEqual }
            | "!=" { NotEqual }
            | "<" { Less }
            | ">" { More }
            | "=" { Equal }

happy пользуется определениями токенов из лексера, импортируя его модуль CfLexer. Эти токены (keep, delete, tpt, edt, if, арифметические операторы) сопоставляются с типами лексера и перечислены в секции %token. В фигурных скобках описания грамматики указываются семантические действия, которые должны соответствовать построению объекта необходимого типа, как это сделано и в boost::spirit. Поскольку в Haskell реализован автоматический вывод типов на основе модели Хиндли-Милнера, то формально указывать типы выражений нет необходимости, хотя в двух случаях, для наглядности, я определил типы выражений Condition :: { Subtree } и Expression :: { Node }. Типы выражений определены ниже в этом же файле:

data  Statement =
    ParseResult
    {
        action    :: Action,
        condition :: Subtree
    }

data  Action =
    KeepTpt                  |
    KeepEdt                  |
    DeleteTpt                |
    DeleteEdt
    deriving Show

data  Node =
    Tree Subtree             |
    Leaf LeafOperand
    deriving Show

data  Subtree =
    Subtree
    {
        nodeType :: NodeType,
        children :: [ Node ]
    }
    deriving Show

data  NodeType =
    Operator  Operator       |
    Function  Function
    deriving Show

data  Operator =
    Op
    {
        op         :: OperatorType,
        priority   :: Int,
        hasRLAssoc :: Bool
    }

data  OperatorType =
    Uninitialized            |
    Top                      |
    UnaryOp  UnaryOperator   |
    MultOp   MultOperator    |
    AddOp    AddOperator     |
    RelOp    RelOperator     |
    LogOp    LogOperator

data UnaryOperator =
    UMinus                   |
    Not

data MultOperator =
    Mult                     |
    Div

data AddOperator =
    Plus |
    Minus

data RelOperator =
    LessEqual                |
    MoreEqual                |
    NotEqual                 |
    Less                     |
    More                     |
    Equal

data LogOperator =
    And |
    Or

data  Function =
    FunctionName  String

data  LeafOperand =
    Variable  Variable       |
    Constant  Constant
    deriving Show

data  Constant =
    DoubleValue   Double     |
    IntegerValue  Int

data  Variable =
    Scalar   String          |
    Vector1  String Int      |
    Vector2  String Int Int

data Function1 =
    Function1
    {
        fName :: String,
        fExpr :: Node
    }

Все типы являются алгебраическими в понятии Haskell, то есть создаются с использованием ключевого слова data и могут иметь один и более конструкторов. Некоторые из типов наследуют определения класса Show, что позволит выводить их на экран компьютера. Поскольку дефолтный вывод некоторых типов на экран меня не удовлетворил, я переопределил для них функцию show:

instance Show Operator where
    show = showOperator

showOperator ( Op a _ _ ) = 
    "-op- " ++ case a of
                    Uninitialized   -> "UNINITIALIZED"
                    Top             -> "Top"
                    UnaryOp UMinus  -> "u -"
                    UnaryOp Not     -> "!"
                    MultOp Mult     -> "*"
                    MultOp Div      -> "/"
                    AddOp Plus      -> "+"
                    AddOp Minus     -> "-"
                    RelOp LessEqual -> "<="
                    RelOp MoreEqual -> ">="
                    RelOp NotEqual  -> "!="
                    RelOp Less      -> "<"
                    RelOp More      -> ">"
                    RelOp Equal     -> "="
                    LogOp And       -> "&"
                    LogOp Or        -> "|"

instance Show Function where
    show = showFunction

showFunction ( FunctionName a ) = "-fun- " ++ a

instance Show Variable where
    show = showVariable

showVariable ( Scalar a ) = a
showVariable ( Vector1 a b ) = a ++ "[" ++ show b ++ "]"
showVariable ( Vector2 a b c ) = a ++ "[" ++ show b ++ "," ++ show c ++ "]"

instance Show Constant where
    show = showConstant

showConstant ( DoubleValue a ) = show a
showConstant ( IntegerValue a ) = show a

Окончательный вывод на экран дерева для отдельной инструкции будет осуществляться с помощью функции printResult и ее вспомогательными функциями:

printResult :: Statement -> IO ()
printResult x = do
    putStrLn $ "Result: action = " ++ show ( action x ) ++ ", parsed tree = "
    putStrLn ""
    printSubtree ( condition x ) ""

printSubtree :: Subtree -> String -> IO ()
printSubtree ( Subtree a b ) is = do
    putStrLn $ is ++ case a of
                        Operator aa -> show aa
                        Function aa -> show aa
    printChildren b $ is ++ "    "

printChildren :: [ Node ] -> String -> IO ()
printChildren [] _ = return ()

printChildren ( Tree x : xs ) is = do
    printSubtree x is
    printChildren xs is

printChildren ( Leaf x : xs ) is = do
    putStrLn $ is ++ printLeaf x
    printChildren xs is

printLeaf :: LeafOperand -> String
printLeaf a = case a of
                    Variable aa -> show aa
                    Constant aa -> show aa

При построении AST использовались вспомогательные функции:

buildTopTree :: Node -> Subtree
buildTopTree ( Tree x ) = x
buildTopTree x@( Leaf _ ) =
    Subtree ( Operator $ Op Top 0 False ) [ x ]

buildFunction1Subtree :: Function1 -> Node
buildFunction1Subtree x =
    Tree $ Subtree ( Function . FunctionName $ fName x ) [ fExpr x ]

buildOperatorSubtree :: Operator -> Node -> Node -> Node
buildOperatorSubtree a@( Op _ _ True ) nl nr =
    Tree $ Subtree ( Operator a ) [ nl, nr ]

buildOperatorSubtree a nl nr@( Tree sr@( Subtree ( Operator b ) ( cnrl : _ ) ) )
    | p == priority b =
        Tree $ moveDownLeft ( Subtree ( Operator a ) $
                                      nl : [ getDeepestLeft cnrl p ] ) sr
    | otherwise =
        Tree $ Subtree ( Operator a ) [ nl, nr ]
        where p = priority a

buildOperatorSubtree a nl nr =
    Tree $ Subtree ( Operator a ) [ nl, nr ]

getDeepestLeft :: Node -> Int -> Node
getDeepestLeft x@( Leaf _ ) _ = x

getDeepestLeft x@( Tree ( Subtree ( Operator b ) ( cnl : _ ) ) ) p
    | p == priority b = getDeepestLeft cnl p
    | otherwise = x

getDeepestLeft x _ = x

moveDownLeft :: Subtree -> Subtree -> Subtree
moveDownLeft sl ( Subtree b@( Operator _ ) ( ( Leaf _ ) : cnrr ) ) =
    Subtree b $ Tree sl : cnrr

moveDownLeft sl@( Subtree ( Operator _ ) _ )
             ( Subtree b@( Operator _ )
                       ( ( Tree ( Subtree ( Function _ ) _ ) ) : cnrr ) ) =
    Subtree b $ Tree sl : cnrr

moveDownLeft sl@( Subtree ( Operator a ) _ )
             ( Subtree b@( Operator _ )
                       ( ( Tree csrl@( Subtree ( Operator c ) _ ) ) : cnrr ) )
    | priority a == priority c =
        Subtree b $ Tree ( moveDownLeft sl csrl ) : cnrr
    | otherwise =
        Subtree b $ Tree sl : cnrr

moveDownLeft sl _ = sl

buildUnaryOperatorSubtree :: Operator -> Node -> Node
buildUnaryOperatorSubtree a x = 
    Tree $ Subtree ( Operator a ) [ x ]

setPriorityInOperatorTree :: Int -> Node -> Node
setPriorityInOperatorTree i ( Tree ( Subtree ( Operator ( Op a _ x ) ) y ) ) =
    Tree $ Subtree ( Operator $ Op a i x ) y

setPriorityInOperatorTree _ x = x

Функция buildTopTree проверяет, является ли ее аргумент, представленный типом Node, листом, если это так, то она возвращает простое поддерево (Subtree) с корнем - оператором типа Top и единственным листом - переданным ей аргументом, если же аргумент - дерево, то buildTopTree возвращает его представление типа Subtree. Функция buildOperatorSubtree  и вспомогательные функции getDeepestLeft и moveDownLeft строят поддерево для бинарных операторов и сдвигают лево-ассоциативные операторы (т.е. все бинарные операторы) вправо (т.е. вглубь дерева) относительно операторов с таким же приоритетом: это позволяет исправить правоассоциативные правила грамматики для левоассоциативных операторов. Функция setPriorityInOperatorTree позволяет избежать порчи дерева при сдвиге левоассоциативных операторов для выражений, содержащихся в скобках. Функции buildFunction1Subtree и buildUnaryOperatorSubtree довольно простые и делают то, что от них требует их название.
Это практически все. Осталось упомянуть, что тестовые примеры я поместил в файл cf.hs, а компиляция программы основана на использовании Makefile, поэтому достаточно только распаковать пример и запустить команду make.

Кроме того, хотелось бы сказать несколько слов о сравнительной производительности программ, написанных с использованием boost::spirit и haskell / happy. Я промолчу о скорости компиляции: итак всем понятно, насколько долго будет компилироваться код на C++, использующий шаблонные объявления из boost::spirit. Меня намного больше удивила разница в скорости выполнения откомпилированных программ. Для корректности сравнения я убрал эвалюацию синтаксических деревьев из кода на boost::spirit. Так вот, код на haskell / happy выполнялся на моем компьютере (двухъядерный AMD 64) в среднем порядка 0.04 секунды, код на boost::spirit с включенной оптимизацией -O2: порядка 0.35 сек. (в 10 раз дольше!), а без оптимизации - вообще 3.4 сек., т.е. примерно в 100 раз дольше!

Исходный код примера можно взять здесь.

Обновление примера грамматики с boost::spirit

Обновил пример для грамматики boost::spirit. Порядок построения узлов для бинарных операторов с лево-правой ассоциативностью (т.е. для всех бинарных операторов данной грамматики) был неверен, т.е. в цепочках типа

1 * 2 * 3 / 4

сначала выполнялась операция деления для операндов 3 и 4, затем операция умножения для операнда 2 и результата предыдущей операции и т.д. (на самом деле немного не так, поскольку в исходной версии была предпринята неуклюжая попытка построения правильного дерева, которая, к сожалению, работала только для простых случаев типа 5 * 6 / 7). На данный момент синтаксические деревья для любых сколь угодно сложных выражений парсятся корректно (по крайней мере в тех тестах, которые я написал и добавил в новую версию программы).
Кстати, пока занимался отладкой примера, обнаружил, что python может неверно вычислять арифметические выражения:

$ python
Python 2.6.4 (r264:75706, Jun  4 2010, 18:20:31) 
[GCC 4.4.4 20100503 (Red Hat 4.4.4-2)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 8 * 4 / ( 2 - 7 ) * 6 / 3
-14
>>>

Или я чего-то не понимаю в питоне, или это какой-то баг. В любом случае непонятно, как можно доверять языку, который неправильно вычисляет арифметические выражения. Может им баг засабмиттить?

Вот ссылка на новую версию программы.

В следующий раз выложу аналогичную программу, реализованную на Haskell, она почти готова.

Update:  зафайлил баг в питон, но мне мягко объяснили в чем моя ошибка. Вот дословно комментарий от Mark Dickinson:

It's not a bug:  you're seeing Python's rules for integer division, which do indeed differ from those of (some) other languages when either the divisor or the dividend is negative.  For integers x and y, in Python 2.x, x / y gives the floor of the exact quotient.

>>> -32 / 5
-7
>>> 32 / -5
-7

In Python 3.x, the '/' operator does 'true division', giving you (a floating-point approximation to) the true result:

>>> -32 / 5
-6.4
>>> 32 / -5
-6.4

You can also get this behaviour in Python 2.x if you start your script with 'from __future__ import division'.

See the documentation at:

http://docs.python.org/reference/expressions.html#binary-arithmetic-operations

for more.

В общем, оператор '/' имеет какую-то странную семантику в питоне 2.x

Использование 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, не изменяя синтаксическое правило. Я решил пойти вторым путем, соответствующий оператор выглядит следующим образом:
   

    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;
    }

3. Взгляните на определение правила 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(), которые можно использовать в классах-наследниках для определения дополнительных функций и переменных. Также, в классе-наследнике можно определить соответствующие функции, связанные с обработкой функций и переменных нескалярных типов.

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