为什么 boost::recursive_wrapper 在这种情况下不起作用

Question

我有以下三个规则：

unary_expression =
    ( '(' > expression > ')' )
    | int_;

operator_expression =
    unary_expression >> *(operators > expression);

expression =
    ( '(' > expression > ')' )
    | operator_expression;

显然这是递归的，所以我使用 boost::recursive_wrapper 并创建了以下 AST：

struct expression;
using unary_expression_node = boost::variant<boost::recursive_wrapper<expression>, int>;

struct unary_expression
{
  unary_expression_node m_unary_expression;
};

enum operators { op_eq, op_ne };
struct expression;
struct operator_expression
{
  unary_expression first;
  using second_type = std::vector<std::pair<operators, expression>>;
  second_type second;
};

using expression_node = 
boost::variant<boost::recursive_wrapper<expression>, operator_expression>;

struct expression
{
  expression_node m_expression;
};

这可以编译（参见下面的完整示例），但是当代码尝试构造一个 expression 对象时，构造函数会进入调用这三个构造函数的无限循环：

#11 0x0000000000466066 in ast::expression::expression ...
#12 0x00000000004682e0 in boost::recursive_wrapper<ast::expression>::recursive_wrapper ...
#13 0x000000000046718d in boost::variant<boost::recursive_wrapper<ast::expression>, ast::operator_expression>::variant
...

因此，创建一个表达式会创建一个 boost::variant<boost::recursive_wrapper<ast::expression>, ast::operator_expression>（也称为 expression_node），它会创建一个 boost::recursive_wrapper<ast::expression>，它会创建一个表达式，该表达式会创建...等等。

我该如何解决这个问题？

这是一个完整的编译示例，但在堆栈运行满时出现段错误：

#include <boost/config/warning_disable.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/fusion/include/std_pair.hpp>
#include <iostream>
#include <string>
#include <vector>

namespace ast {

struct expression;
using unary_expression_node = boost::variant<boost::recursive_wrapper<expression>, int>;

struct unary_expression
{
  unary_expression_node m_unary_expression;
};

enum operators { op_eq, op_ne };
struct expression;
struct operator_expression
{
  unary_expression first;
  using second_type = std::vector<std::pair<operators, expression>>;
  second_type second;
};

using expression_node = boost::variant<boost::recursive_wrapper<expression>, operator_expression>;

struct expression
{
  expression_node m_expression;
};

std::ostream& operator<<(std::ostream& os, expression const& expression)
{
  return os << expression.m_expression;
}

std::ostream& operator<<(std::ostream& os, unary_expression const& unary_expression)
{
  return os << unary_expression.m_unary_expression;
}

std::ostream& operator<<(std::ostream& os, operator_expression const& operator_expression)
{
  os << operator_expression.first;
  for (auto& l : operator_expression.second)
  {
    os << ' ' << l.first << ' ' << l.second;
  }
  return os;
}

} // namespace ast

BOOST_FUSION_ADAPT_STRUCT(
  ast::expression,
  (ast::expression_node, m_expression)
)

BOOST_FUSION_ADAPT_STRUCT(
  ast::unary_expression,
  (ast::unary_expression_node, m_unary_expression)
)

BOOST_FUSION_ADAPT_STRUCT(
  ast::operator_expression,
  (ast::unary_expression, first),
  (ast::operator_expression::second_type, second)
)

namespace client
{

namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;

template <typename Iterator>
class expression_grammar : public qi::grammar<Iterator, ast::expression(), qi::space_type>
{
 private:
  qi::symbols<char, ast::operators> operators;
  qi::rule<Iterator, ast::unary_expression(), qi::space_type> unary_expression;
  qi::rule<Iterator, ast::operator_expression(), qi::space_type> operator_expression;
  qi::rule<Iterator, ast::expression(), qi::space_type> expression;

 public:
  expression_grammar() : expression_grammar::base_type(expression, "expression_grammar")
  {
    using qi::double_;
    using qi::char_;
    using qi::int_;

    operators.add
        ("==", ast::op_eq)
        ("!=", ast::op_ne)
    ;

    unary_expression =
        ( '(' > expression > ')' )
        | int_;

    operator_expression =
        unary_expression >> *(operators > expression);

    expression =
        ( '(' > expression > ')' )
        | operator_expression;
  }
};

} // namespace client

int main()
{
  std::string const input{"1 == 1 != 0"};
  using iterator_type = std::string::const_iterator;
  using expression_grammar = client::expression_grammar<iterator_type>;
  namespace qi = boost::spirit::qi;

  expression_grammar program;
  iterator_type iter{input.begin()};
  iterator_type const end{input.end()};
  ast::expression out;
  bool r = qi::phrase_parse(iter, end, program, qi::space, out);

  if (!r || iter != end)
  {
    std::cerr << "Parsing failed." << std::endl;
    return 1;
  }
  std::cout << "Parsed: " << out << std::endl;
}

编辑：

我尝试将事情简化为两个规则（和两个“ast”）：

struct expression;
using unary_expression = boost::variant<boost::recursive_wrapper<expression>, int>;

enum operators { op_eq, op_ne };
struct expression
{
  unary_expression first;
  using second_type = std::vector<std::pair<operators, expression>>;
  second_type second;
};

BOOST_FUSION_ADAPT_STRUCT(
  ast::expression,
  (ast::unary_expression, first),
  (ast::expression::second_type, second)
)

[...]

  unary_expression =
    ( '(' > expression > ')' )
    | int_;

  expression =
    unary_expression >> *(operators > expression);

但这也会导致无限循环。

#18 0x00000000004646f2 in ast::expression::expression
#19 0x00000000004669ac in boost::recursive_wrapper<ast::expression>::recursive_wrapper
#20 0x0000000000465821 in boost::variant<boost::recursive_wrapper<ast::expression>, int>::variant
...

Answer 1

变体默认构造为其第一个元素类型。

这确实直接导致死循环。 (Demo)

解决方法是让默认的variant元素不可重入或使其惰性构造。在这种情况下，您可以简单地重新排列，使 int 成为第一个元素。

更好的是，似乎不需要在结果树中反映运算符优先级层次结构（如规则中所表达的那样），那么为什么不简化为：

struct unary_expression;
struct binary_expression;

enum operators { op_eq, op_ne };

using expression = boost::variant<
    int, 
    boost::recursive_wrapper<unary_expression>,
    boost::recursive_wrapper<binary_expression>
>;

struct unary_expression {
    expression expr;
};

struct binary_expression {
    expression                                    first;
    std::vector<std::pair<operators, expression>> other;
};

这个no longer crashes而且在适配和使用上似乎更简单一些

简化的完整演示

这个完整的演示使用了那个 AST，但添加了一个真正的一元表达式。修复了一些样式问题：

除非您打算让调用者更改船长，否则不要公开船长
使解析器常量
显示未解析的尾随数据（或断言 >> qi::eoi）

Note: I might have changed the precedence rules (specifically, associativity of binary operators). I'm not sure which version you require.

Live On Coliru

//#define BOOST_SPIRIT_DEBUG
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/fusion/include/std_pair.hpp>
#include <iostream>
#include <string>
#include <vector>

namespace ast {
    struct unary_expression;
    struct binary_expression;

    enum operators { op_eq, op_ne };

    using expression = boost::variant<
        int, 
        boost::recursive_wrapper<unary_expression>,
        boost::recursive_wrapper<binary_expression>
    >;

    struct unary_expression {
        bool negated = false;
        expression expr;
    };

    struct binary_expression {
        expression                                    first;
        std::vector<std::pair<operators, expression>> other;
    };

}

BOOST_FUSION_ADAPT_STRUCT(ast::unary_expression, negated, expr)
BOOST_FUSION_ADAPT_STRUCT(ast::binary_expression, first, other)

namespace ast {
    static inline std::ostream& operator<<(std::ostream& os, operators op) { return os << (op==op_eq?"==":"!="); }
    static inline std::ostream& operator<<(std::ostream& os, binary_expression const& e) { 
        os << e.first;
        for (auto& oe : e.other)
            os << " " << oe.first << " " << oe.second;
        return os;
    }
    static inline std::ostream& operator<<(std::ostream& os, unary_expression const& e) {
        return os << (e.negated?"!":"") << "(" << e.expr << ")";
    }
}

namespace client
{
    namespace qi = boost::spirit::qi;

    template <typename Iterator>
    class expression_grammar : public qi::grammar<Iterator, ast::expression()> {
      private:
        qi::symbols<char, ast::operators> operators;
        qi::rule<Iterator, ast::expression()> start;

        qi::rule<Iterator, ast::expression(),        qi::space_type> simple_expression;
        qi::rule<Iterator, ast::unary_expression(),  qi::space_type> unary_expression;
        qi::rule<Iterator, ast::binary_expression(), qi::space_type> binary_expression;
        qi::rule<Iterator, ast::expression(),        qi::space_type> expression;

      public:
        expression_grammar() : expression_grammar::base_type(start, "expression") {
            using namespace qi;

            operators.add
                ("==", ast::op_eq)
                ("!=", ast::op_ne)
                ;

            simple_expression =
                ( '(' > expression > ')' )
                | int_;

            unary_expression = 
                matches['!'] >> simple_expression;

            binary_expression =
                unary_expression >> *(operators > expression);

            expression = binary_expression;

            start = skip(space) [ expression ];

            BOOST_SPIRIT_DEBUG_NODES((expression)(binary_expression)(unary_expression)(simple_expression))
        }
    };

} // namespace client

int main() {
    using It = std::string::const_iterator;
    client::expression_grammar<It> const program;

    std::string const input{"1 == !(1 != 0)"};
    It iter = input.begin(), end = input.end();
    ast::expression out;

    if (parse(iter, end, program, out)) {
        std::cout << "Parsed: " << out << std::endl;
    } else {
        std::cerr << "Parsing failed." << std::endl;
        return 1;
    }

    if (iter != end) {
        std::cout << "Remaining unparsed input: '" << std::string(iter, end) << "'\n";
    }
}

版画

Parsed: (1) == !((1) != (0))

为什么 boost::recursive_wrapper 在这种情况下不起作用

Why is boost::recursive_wrapper not working in this case

c++

boost-spirit

recursive-datastructures

boost-variant

boost-spirit-qi

简化的完整演示