在c ++中的布尔表达式（语法）解析器 [英] Boolean expression (grammar) parser in c++
本文介绍了在c ++中的布尔表达式（语法）解析器的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我想解析一个布尔表达式（在C ++中）。输入表单：
a和b xor（c和d或a和b）;
我只想将这个表达式解析成树，知道优先规则，要么）。
所以上面的表达式应该看起来像：
（a和b）xor （a和b））;
到解析器。
树将是以下形式：
a
和
b
或
c
和
d
xor
a
和
b
输入将通过命令行或以字符串的形式。
我只需要解析器。
有没有任何来源可以帮我做这个？
因为Boost Spirit生成了基于递归下降的解析方法，在表达式模板上，尊重'特异性'（sic）优先规则（如其他人提到的）是相当冗长乏味的。因此，语法缺乏一定的优雅。
抽象数据类型
我使用Boost Variant递归变量支持，注意expr的定义：
struct op_or {}; // tag
struct op_and {}; // tag
struct op_xor {}; // tag
struct op_not {}; // tag
typedef std :: string var;
template< typename tag> struct binop;
template< typename tag> struct unop;
typedef boost :: variant< var，
boost :: recursive_wrapper< unop< op_not> >，
boost :: recursive_wrapper< binop< op_and> >，
boost :: recursive_wrapper< binop< op_xor> >，
boost :: recursive_wrapper< binop< op_or> >
> expr;
（下面的完整来源）
语法规则
以下是所提到的语法定义（略微冗长乏味）。
考虑这种语法最优，它是相当可读的，我们有自己一个静态编译解析器与强类型AST数据类型在大约50行代码。事情可能会更糟。
模板< typename It，typename Skipper = qi :: space_type>
struct parser：qi :: grammar< It，expr（），Skipper>
{
parser（）：parser :: base_type（expr_）
{
使用命名空间qi;
expr_ = or_.alias（）;
or_ =（xor_>>或>> xor_）[_val = phx :: construct< binop< op_or>>（_ 1，_2） xor_ [_val = _1];
xor_ =（and_>>xor>> and_）[_val = phx :: construct< binop< op_xor>（_ 1，_2）] | and_ [_val = _1];
and_ =（not_>>和>> not_）[_val = phx :: construct< binop< op_and>>（_ 1，_2） not_ [_val = _1];
not_ =（not> simple）[_val = phx :: construct< unop< op_not>>（_ 1）] | simple [_val = _1];
simple =（（'> expr_>'）'）| var_）;
var_ = qi :: lexeme [+ alpha]
}
private：
qi :: rule< It，var（），Skipper> var_;
qi :: rule< It，expr（），Skipper> not_，and_，xor_，or_，simple，expr_;
};
在语法树上操作
，你想要评估表达式。现在，我决定只停止打印，所以我不必为命名变量查找表）。
遍历递归变量可能看起来很神秘第一个，但 boost :: static_visitor<> 令人惊讶的简单一旦你得到它的悬念：
struct printer：boost :: static_visitor< void>
{
printer（std :: ostream& os）：_os（os）{}
std :: ostream& _os;
//
void operator（）（const var& v）const {_os< v; }
void operator（）（const binop< op_and>& b）const {print（&，b.oper1，b.oper2）; }
void operator（）（const binop< op_or>& b）const {print（|，b.oper1，b.oper2）; }
void operator（）（const binop< op_xor>& b）const {print（^，b.oper1，b.oper2）; }
void print（const std :: string& op，const expr& l，const expr& r）const
{
_os< （;
boost :: apply_visitor（* this，l）;
_os<< op;
boost :: apply_visitor（* this，r）;
_os <<）;
}
void operator（）（const unop< op_not>& u）const
{
_os< （;
_os<<！;
boost :: apply_visitor（* this，u.oper1）;
_os<
}
};
std :: ostream& operator<<<（std :: ostream& os，const expr& e）
{boost :: apply_visitor（printer（os），e）; return os; }
测试输出：
代码中的测试用例，输出以下内容，通过添加（冗余）括号来演示优先规则的正确处理：
result：（（a& b）^（（c& d）|（a& b）））
result： ; d）|（a& b）））
结果：（a& b）
结果：（a | b）
结果：（a ^ b）
结果：（a a）
结果：（（a）和b）
结果：（！（a& b） ）
完整代码：
#include< boost / spirit / include / qi.hpp>
#include< boost / spirit / include / phoenix.hpp>
#include< boost / spirit / include / phoenix_operator.hpp>
#include< boost / variant / recursive_wrapper.hpp>
命名空间qi = boost :: spirit :: qi;
namespace phx = boost :: phoenix;
struct op_or {};
struct op_and {};
struct op_xor {};
struct op_not {};
typedef std :: string var;
template< typename tag> struct binop;
template< typename tag> struct unop;
typedef boost :: variant< var，
boost :: recursive_wrapper< unop< op_not> >，
boost :: recursive_wrapper< binop< op_and> >，
boost :: recursive_wrapper< binop< op_xor> >，
boost :: recursive_wrapper< binop< op_or> >
> expr;
template< typename tag> struct binop
{
explicit binop（const expr& l，const expr& r）：oper1（1），oper2（r）{}
expr oper1，oper2;
};
template< typename tag> struct unop
{
显式unop（const expr& o）：oper1（o）{}
expr oper1;
};
struct printer：boost :: static_visitor< void>
{
printer（std :: ostream& os）：_os（os）{}
std :: ostream& _os;
//
void operator（）（const var& v）const {_os< v; }
void operator（）（const binop< op_and>& b）const {print（&，b.oper1，b.oper2）; }
void operator（）（const binop< op_or>& b）const {print（|，b.oper1，b.oper2）; }
void operator（）（const binop< op_xor>& b）const {print（^，b.oper1，b.oper2）; }
void print（const std :: string& op，const expr& l，const expr& r）const
{
_os< （;
boost :: apply_visitor（* this，l）;
_os<< op;
boost :: apply_visitor（* this，r）;
_os <<）;
}
void operator（）（const unop< op_not>& u）const
{
_os< （;
_os<<！;
boost :: apply_visitor（* this，u.oper1）;
_os<
}
};
std :: ostream& operator<<<（std :: ostream& os，const expr& e）
{boost :: apply_visitor（printer（os），e）; return os; }
template< typename It，typename Skipper = qi :: space_type>
struct parser：qi :: grammar< It，expr（），Skipper>
{
parser（）：parser :: base_type（expr_）
{
使用命名空间qi;
expr_ = or_.alias（）;
or_ =（xor_>>或>> 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];
simple =（（'> expr_>'）'）| var_）;
var_ = qi :: lexeme [+ alpha]
BOOST_SPIRIT_DEBUG_NODE（expr_）;
BOOST_SPIRIT_DEBUG_NODE（or_）;
BOOST_SPIRIT_DEBUG_NODE（xor_）;
BOOST_SPIRIT_DEBUG_NODE（and_）;
BOOST_SPIRIT_DEBUG_NODE（not_）;
BOOST_SPIRIT_DEBUG_NODE（simple）;
BOOST_SPIRIT_DEBUG_NODE（var_）;
}
private：
qi :: rule< It，var（），Skipper> var_;
qi :: rule< It，expr（），Skipper> not_，and_，xor_，or_，simple，expr_;
};
int main（）
{
for（auto& input：std :: list< std :: string> {
//从OP：
（a和b）xor（（c和d）或（a和b））;，
a和b xor（c和d或a和b）
///更简单的测试：
a and b;，
a或b;，
a xor b;，
;，
not a and b;，
not（a and b）;，
a或b或c;，
} $ b {
auto f（std :: begin（input）），l（std :: end（input））;
parser< decltype（f）> p;
try
{
expr result;
bool ok = qi :: phrase_parse（f，l，p>';'，qi :: space，result）;
if（！ok）
std :: cerr<< invalid input\\\
;
else
std :: cout<< result：<结果< \\\
;
} catch（const qi :: expectation_failure< decltype（f）>& e）
{
std :: cerr< expectation_failure at'< std :: string（e.first，e.last）<< '\\\
;
}
if（f！= l）std :: cerr<< unparsed：'< std :: string（f，l）<< '\\\
;
}
return 0;
}
奖金：
对于奖励点，得到一个完全像OP中所示的树：
static const char indentstep [] =
struct tree_print：boost :: static_visitor< void>
{
tree_print（std :: ostream& os，const std :: string& indent = indentstep）：_os（os），_indent（indent）{}
std :: ostream& _os;
std :: string _indent
void operator（）（const var& v）const {_os<< _indent<< v<< std :: endl; }
void operator（）（const binop< op_and>& b）const {print（and，b.oper1，b.oper2）; }
void operator（）（const binop< op_or>& b）const {print（or，b.oper2，b.oper1）; }
void operator（）（const binop< op_xor>& b）const {print（xor，b.oper2，b.oper1）; }
void print（const std :: string& op，const expr& l，const expr& r）const
{
boost :: apply_visitor（tree_print（_os，_indent + indentstep），l）;
_os<< _indent<< op<< std :: endl;
boost :: apply_visitor（tree_print（_os，_indent + indentstep），r）;
}
void operator（）（const unop< op_not>& u）const
{
_os& _indent<< ！;
boost :: apply_visitor（tree_print（_os，_indent + indentstep），u.oper1）;
}
};
std :: ostream& operator<<<（std :: ostream& os，const expr& e）
{
boost :: apply_visitor（tree_print（os），e）; return os;
}
结果：
a
和
b
或
c
和
d
xor
a $ b b和
b
I want to parse a boolean expression (in C++). Input form:
a and b xor (c and d or a and b);
I just want to parse this expression into a tree, knowing the precedence rule (not,and,xor,or). So the above expression should look something like:
(a and b) xor ((c and d) or (a and b));
to the parser.
And the tree would be of form:
a
and
b
or
c
and
d
xor
a
and
b
The input will be either through command line or in the form of a string. I just need the parser.
Are there any sources that can help me do this?
解决方案
Here is an implementation based on Boost Spirit.
Because Boost Spirit generates recursive descent parsers based on expression templates, honouring the 'idiosyncratic' (sic) precedence rules (as mentioned by others) is quite tedious. Therefore the grammar lacks a certain elegance.
Abstract Data Type
I defined a tree data structure using Boost Variant's recursive variant support, note the definition of expr:
struct op_or {}; // tag
struct op_and {}; // tag
struct op_xor {}; // tag
struct op_not {}; // tag
typedef std::string var;
template <typename tag> struct binop;
template <typename tag> struct unop;
typedef boost::variant<var,
boost::recursive_wrapper<unop <op_not> >,
boost::recursive_wrapper<binop<op_and> >,
boost::recursive_wrapper<binop<op_xor> >,
boost::recursive_wrapper<binop<op_or> >
> expr;
(full source below)
Grammar Rules
The following is the (slightly tedious) grammar definition, as mentioned.
Although I don't consider this grammar optimal, it is quite readable, and we have ourselves a statically compiled parser with strongly typed AST datatype in roughly 50 lines of code. Things could be considerably worse.
template <typename It, typename Skipper = qi::space_type>
struct parser : qi::grammar<It, expr(), Skipper>
{
parser() : parser::base_type(expr_)
{
using namespace qi;
expr_ = or_.alias();
or_ = (xor_ >> "or" >> xor_) [ _val = phx::construct<binop<op_or >>(_1, _2) ] | xor_ [ _val = _1 ];
xor_ = (and_ >> "xor" >> and_) [ _val = phx::construct<binop<op_xor>>(_1, _2) ] | and_ [ _val = _1 ];
and_ = (not_ >> "and" >> not_) [ _val = phx::construct<binop<op_and>>(_1, _2) ] | not_ [ _val = _1 ];
not_ = ("not" > simple ) [ _val = phx::construct<unop <op_not>>(_1) ] | simple [ _val = _1 ];
simple = (('(' > expr_ > ')') | var_);
var_ = qi::lexeme[ +alpha ];
}
private:
qi::rule<It, var() , Skipper> var_;
qi::rule<It, expr(), Skipper> not_, and_, xor_, or_, simple, expr_;
};
Operating on the syntax tree
Obviously, you'd want to evaluate the expressions. For now, I decided to stop at just printing, so I don't have to do the lookup table for named variables :)
Traversing a recursive variant may look cryptic at first, but the boost::static_visitor<> is surprisingly simple once you get the hang of it:
struct printer : boost::static_visitor<void>
{
printer(std::ostream& os) : _os(os) {}
std::ostream& _os;
//
void operator()(const var& v) const { _os << v; }
void operator()(const binop<op_and>& b) const { print(" & ", b.oper1, b.oper2); }
void operator()(const binop<op_or >& b) const { print(" | ", b.oper1, b.oper2); }
void operator()(const binop<op_xor>& b) const { print(" ^ ", b.oper1, b.oper2); }
void print(const std::string& op, const expr& l, const expr& r) const
{
_os << "(";
boost::apply_visitor(*this, l);
_os << op;
boost::apply_visitor(*this, r);
_os << ")";
}
void operator()(const unop<op_not>& u) const
{
_os << "(";
_os << "!";
boost::apply_visitor(*this, u.oper1);
_os << ")";
}
};
std::ostream& operator<<(std::ostream& os, const expr& e)
{ boost::apply_visitor(printer(os), e); return os; }
Test output:
For the test cases in the code, the following is output, demonstrating correct handling of the precedence rules by adding (redundant) parentheses:
result: ((a & b) ^ ((c & d) | (a & b)))
result: ((a & b) ^ ((c & d) | (a & b)))
result: (a & b)
result: (a | b)
result: (a ^ b)
result: (!a)
result: ((!a) & b)
result: (!(a & b))
result: (a | (b | c))
Full Code:
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/variant/recursive_wrapper.hpp>
namespace qi = boost::spirit::qi;
namespace phx = boost::phoenix;
struct op_or {};
struct op_and {};
struct op_xor {};
struct op_not {};
typedef std::string var;
template <typename tag> struct binop;
template <typename tag> struct unop;
typedef boost::variant<var,
boost::recursive_wrapper<unop <op_not> >,
boost::recursive_wrapper<binop<op_and> >,
boost::recursive_wrapper<binop<op_xor> >,
boost::recursive_wrapper<binop<op_or> >
> expr;
template <typename tag> struct binop
{
explicit binop(const expr& l, const expr& r) : oper1(l), oper2(r) { }
expr oper1, oper2;
};
template <typename tag> struct unop
{
explicit unop(const expr& o) : oper1(o) { }
expr oper1;
};
struct printer : boost::static_visitor<void>
{
printer(std::ostream& os) : _os(os) {}
std::ostream& _os;
//
void operator()(const var& v) const { _os << v; }
void operator()(const binop<op_and>& b) const { print(" & ", b.oper1, b.oper2); }
void operator()(const binop<op_or >& b) const { print(" | ", b.oper1, b.oper2); }
void operator()(const binop<op_xor>& b) const { print(" ^ ", b.oper1, b.oper2); }
void print(const std::string& op, const expr& l, const expr& r) const
{
_os << "(";
boost::apply_visitor(*this, l);
_os << op;
boost::apply_visitor(*this, r);
_os << ")";
}
void operator()(const unop<op_not>& u) const
{
_os << "(";
_os << "!";
boost::apply_visitor(*this, u.oper1);
_os << ")";
}
};
std::ostream& operator<<(std::ostream& os, const expr& e)
{ boost::apply_visitor(printer(os), e); return os; }
template <typename It, typename Skipper = qi::space_type>
struct parser : qi::grammar<It, expr(), Skipper>
{
parser() : parser::base_type(expr_)
{
using namespace qi;
expr_ = or_.alias();
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 ];
simple = (('(' > expr_ > ')') | var_);
var_ = qi::lexeme[ +alpha ];
BOOST_SPIRIT_DEBUG_NODE(expr_);
BOOST_SPIRIT_DEBUG_NODE(or_);
BOOST_SPIRIT_DEBUG_NODE(xor_);
BOOST_SPIRIT_DEBUG_NODE(and_);
BOOST_SPIRIT_DEBUG_NODE(not_);
BOOST_SPIRIT_DEBUG_NODE(simple);
BOOST_SPIRIT_DEBUG_NODE(var_);
}
private:
qi::rule<It, var() , Skipper> var_;
qi::rule<It, expr(), Skipper> not_, and_, xor_, or_, simple, expr_;
};
int main()
{
for (auto& input : std::list<std::string> {
// From the OP:
"(a and b) xor ((c and d) or (a and b));",
"a and b xor (c and d or a and b);",
/// Simpler tests:
"a and b;",
"a or b;",
"a xor b;",
"not a;",
"not a and b;",
"not (a and b);",
"a or b or c;",
})
{
auto f(std::begin(input)), l(std::end(input));
parser<decltype(f)> p;
try
{
expr result;
bool ok = qi::phrase_parse(f,l,p > ';',qi::space,result);
if (!ok)
std::cerr << "invalid input\n";
else
std::cout << "result: " << result << "\n";
} catch (const qi::expectation_failure<decltype(f)>& e)
{
std::cerr << "expectation_failure at '" << std::string(e.first, e.last) << "'\n";
}
if (f!=l) std::cerr << "unparsed: '" << std::string(f,l) << "'\n";
}
return 0;
}
Bonus:
For bonus points, to get a tree exactly like shown in the OP:
static const char indentstep[] = " ";
struct tree_print : boost::static_visitor<void>
{
tree_print(std::ostream& os, const std::string& indent=indentstep) : _os(os), _indent(indent) {}
std::ostream& _os;
std::string _indent;
void operator()(const var& v) const { _os << _indent << v << std::endl; }
void operator()(const binop<op_and>& b) const { print("and ", b.oper1, b.oper2); }
void operator()(const binop<op_or >& b) const { print("or ", b.oper2, b.oper1); }
void operator()(const binop<op_xor>& b) const { print("xor ", b.oper2, b.oper1); }
void print(const std::string& op, const expr& l, const expr& r) const
{
boost::apply_visitor(tree_print(_os, _indent+indentstep), l);
_os << _indent << op << std::endl;
boost::apply_visitor(tree_print(_os, _indent+indentstep), r);
}
void operator()(const unop<op_not>& u) const
{
_os << _indent << "!";
boost::apply_visitor(tree_print(_os, _indent+indentstep), u.oper1);
}
};
std::ostream& operator<<(std::ostream& os, const expr& e)
{
boost::apply_visitor(tree_print(os), e); return os;
}
result:
a
and
b
or
c
and
d
xor
a
and
b
这篇关于在c ++中的布尔表达式（语法）解析器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
