C++中的布尔表达式（语法）解析器

Question

我想解析一个布尔表达式（使用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));

传递给解析器。

并且树的形式如下：

                        a
                   and
                        b
               or
                        c
                   and
                        d
        xor
                   a
              and
                   b

输入可以通过命令行或字符串形式进行。我只需要解析程序。

有哪些资源可以帮助我完成这个任务？

- A Gore

---

你可能需要一个解析器库/生成器，比如Yacc、Bison或Boost Spirit。然后你需要确定一个合理的表达式语法。 - Oliver Charlesworth

@OliCharlesworth：虽然Boost Spirit确实是一个库，但我不会把yacc或bison称为“库”，尽管它们都带有一个库。它们更像是解析器生成器（顺便说一句，antlr也是其中之一）。 - Dietmar Kühl

@DietmarKühl：好观点。我已经修改了我的评论。 - Oliver Charlesworth

实际上，C++ 运算符的优先级并不完全如您所指定的那样：它是 (逻辑非/位非) > (位与) > (位异或) > (位或) > (逻辑与) > (逻辑或)。布尔表达式是逻辑而非位运算（除非您想转换为整数），这样做实际上不再使它们成为布尔表达式。我知道它很接近，但对于这种情况，您需要非常具体，否则人们会走不同的路线。 - Martin York

注意：尽管问题没有说明_boost-spirit_，但它在被接受的答案中占据了重要地位，因此已被用作标签以帮助未来搜索。 - Lightness Races in Orbit

Answer 1

这是一个基于Boost Spirit的实现。

由于Boost Spirit基于表达式模板生成递归下降解析器，遵守“个人独特”的优先顺序规则（如其他人所提到的）相当麻烦。因此，该语法缺乏一定的优雅性。

抽象数据类型

我使用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;

语法规则

以下为（稍微枯燥的）语法定义，如前所述。

虽然我不认为这个语法是最优秀的，但它相当易读，并且我们拥有一个大约50行代码的静态编译解析器与强类型的AST数据类型。情况可能会更糟。

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();

        not_ = ("not" > simple       ) [ _val = phx::construct<unop <op_not>>(_1)     ] | simple [ _val = _1 ];
#ifdef RIGHT_ASSOCIATIVE
        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 ];
#else
        or_  = xor_ [ _val = _1 ] >> *("or"  >> xor_ [ _val = phx::construct<binop<op_or>> (_val, _1) ]);
        xor_ = and_ [ _val = _1 ] >> *("xor" >> and_ [ _val = phx::construct<binop<op_xor>>(_val, _1) ]);
        and_ = not_ [ _val = _1 ] >> *("and" >> not_ [ _val = phx::construct<binop<op_and>>(_val, _1) ]);
#endif

        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: ((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)

请注意，与 在 Coliru 上使用 -DRIGHT_ASSOCIATIVE 比较

完整代码：

在 Coliru 上实时演示

#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();

        not_ = ("not" > simple       ) [ _val = phx::construct<unop <op_not>>(_1)     ] | simple [ _val = _1 ];
#ifdef RIGHT_ASSOCIATIVE
        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 ];
#else
        or_  = xor_ [ _val = _1 ] >> *("or"  >> xor_ [ _val = phx::construct<binop<op_or>> (_val, _1) ]);
        xor_ = and_ [ _val = _1 ] >> *("xor" >> and_ [ _val = phx::construct<binop<op_xor>>(_val, _1) ]);
        and_ = not_ [ _val = _1 ] >> *("and" >> not_ [ _val = phx::construct<binop<op_and>>(_val, _1) ]);
#endif

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

奖励：

如果想要获得和原帖中完全一样的树形结构，请参考下面的链接：

在 Coliru 上实时查看

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
        and 
            b
    or  
            c
        and 
            d
xor 
        a
    and 
        b

- sehe

---

作为奖励，我添加了“tree_print”访问者，模仿OP中的ASCII布局 :) - sehe

你好，这是一个很棒的例子。有一件事我没搞明白。如果你尝试传递"a or b or c"，它会失败。你能否发布如何修复你的代码以处理这种情况的方法？ - Sergej Andrejev

在另一个答案中添加了一个评估访问器，以防万一有人感兴趣：如何在Spirit中计算布尔表达式。 - sehe

我不是100%确定，但我认为fix_associativity可以正确地将右结合树转换为左结合树。你能看一下吗（并尝试打破它）？ - llonesmiz

@ThomasMcLeod 很好的观点。这是一个简单的更改，所以我更新了答案以显示两者（默认为左结合），并在Coliru上添加了实时演示。 - sehe

Answer 2

要么像Oli Charlesworth已经提到的那样使用解析器生成器（yacc，bison，antlr；后者在我看来比其他两个更适合C ++，尽管我已经有一段时间没有看过它们），要么创建一个简单的递归下降解析器：对于像您的语言这样简单的语言，这可能是更容易的方法。

- Dietmar Kühl

Answer 3

请参考我的stackoverflow答案，了解如何编写简单的递归下降解析器。

这种方法对于布尔表达式等简单语言非常方便。而且这些概念与您的编程语言基本独立。

- Ira Baxter

Answer 4

如果像我一样，您觉得解析库的开销和特殊性对于这样一个小任务来说太多了，那么您可以非常容易地为您所提出的简单场景编写自己的解析器。请参见此处，其中包含我用C#编写的解析器，以类似于您要求的方式解析简单的C#表达式。

- Kent Boogaart

---

我同意关于个性化的看法，但Lemon解析器生成器在这方面实际上非常出色。它具有非常灵活和干净的最小接口，不会妨碍你（尽管它确实需要你做更多的工作，但词法分析是容易的部分）。 - Chris Lutz

我只是粗略地浏览了一下代码，并对它试图实现的目标完全不了解，但我认为使用 Boost.Spirit 解析器会更短、更易于阅读和理解。 - pmr

@pmr请看一下我的答案，看看你是否同意 :) - sehe

Answer 5

我在尝试扩展 @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 提供的输入。我不知道是什么导致了性能影响，但第二种实现方式在某种程度上解决了这个问题。奇怪。

- Mustafa Kemal GILOR

Answer 6

请查看Mini C示例代码https://github.com/boostorg/spirit/tree/master/example/qi/compiler_tutorial/mini_c。

特别是要查看expression.cpp、expression.hpp、expression_def.hpp和ast.hpp。它提供了一个很好的示例，说明如何将表达式解析为AST。

- gvd

---

@GrzegorzBazior 我认为是这个。 - llonesmiz