Парсер булевых выражений (грамматика) в c++

Question

Парсер булевых выражений (грамматика) в c++

Я хочу разобрать булево выражение (на C++). Форма ввода:

a and b xor (c and d or a and b);

Я просто хочу разобрать это выражение в дерево, зная правило старшинства (not,and,xor,or). Таким образом, приведенное выше выражение должно выглядеть примерно так:

(a and b) xor ((c and d) or (a and b));

для синтаксического анализатора.

А дерево будет иметь вид:

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

Есть ли какие-нибудь источники, которые могут помочь мне в этом?

32

c++ parsing boost-spirit

задан Lightness Races with Monica 18 October 2013 в 10:43

1 ответ

Другие вопросы по тегам:

c++ parsing boost-spirit

Похожие вопросы:

score 1 · Answer 1

Я встретился с огромным влиянием производительности, когда я пытался развернуть набор бинарного оператора в примере @sehe. Операторы, которые я добавил, следующим образом;

eq_  = (neq_ >> "eq"  >> eq_ ) [ _val = phx::construct<binop<op_eq>>(_1, _2) ] | neq_   [ _val = _1 ];
neq_ = (gt_ >> "neq"  >> neq_ ) [ _val = phx::construct<binop<op_neq>>(_1, _2) ] | gt_   [ _val = _1 ];
gt_  = (lt_ >> "gt"  >> gt_ ) [ _val = phx::construct<binop<op_gt>>(_1, _2) ] | lt_   [ _val = _1 ];
lt_  = (gte_ >> "lt"  >> lt_ ) [ _val = phx::construct<binop<op_lt>>(_1, _2) ] | gte_   [ _val = _1 ];
gte_ = (lte_ >> "gte"  >> gte_ ) [ _val = phx::construct<binop<op_gte>>(_1, _2) ] | lte_   [ _val = _1 ];
lte_ = (or_ >> "lte"  >> lte_ ) [ _val = phx::construct<binop<op_lte>>(_1, _2) ] | or_   [ _val = _1 ];
or_  = (xor_ >> "or"  >> or_ ) [ _val = phx::construct<binop<op_or >>(_1, _2) ] | xor_   [ _val = _1 ];
xor_ = (and_ >> "xor" >> xor_) [ _val = phx::construct<binop<op_xor>>(_1, _2) ] | and_   [ _val = _1 ];
and_ = (not_ >> "and" >> and_) [ _val = phx::construct<binop<op_and>>(_1, _2) ] | not_   [ _val = _1 ];
not_ = ("not" > simple       ) [ _val = phx::construct<unop <op_not>>(_1)     ] | simple [ _val = _1 ];

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

/*...*/
parser() : parser::base_type(expr_){
/*...*/
expr_ = 
    (
        ( ("not"  >   simple_ [_val = phx::construct<unop<op_not>>(_1)]       )) 
        |
        simple_    [_val = phx::construct<expr>(_1)])

    >> *( 
            ("and"  >>  simple_ [_val = phx::construct<binop<op_and>>(_val, _1)]  )
            |
            ("or"   >>  simple_ [_val = phx::construct<binop<op_or>>(_val, _1)]   )
            |
            ("xor"  >>  simple_ [_val = phx::construct<binop<op_xor>>(_val, _1)]  )
            |
            ("not"  >   simple_ [_val = phx::construct<unop<op_not>>(_val)]       )
            |
            ("gt"   >>  simple_ [_val = phx::construct<binop<op_gt>>(_val, _1)]   )
            |
            ("gte"  >>  simple_ [_val = phx::construct<binop<op_gte>>(_val, _1)]  )
            |
            ("lt"   >>  simple_ [_val = phx::construct<binop<op_lt>>(_val, _1)]   )
            |
            ("lte"  >>  simple_ [_val = phx::construct<binop<op_lte>>(_val, _1)]  )
            |
            ("eq"   >>  simple_ [_val = phx::construct<binop<op_eq>>(_val, _1)]   )
            |
            ("neq"  >>  simple_ [_val = phx::construct<binop<op_neq>>(_val, _1)]  )       
        );

simple_ = (('(' > expr_ > ')') | var_);
var_ = qi::lexeme[ +alpha ];
}
/*...*/
qi::rule<It, var() , Skipper> var_;
qi::rule<It, expr(), Skipper> expr_, simple_; 
};

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