jeudi 8 juin 2017

Why is boost::recursive_wrapper not working in this case (boost::spirit qi)?

I have the following three rules:

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

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

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

Obviously this is recursive, so I use boost::recursive_wrapper and created the following 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;
};

This compiles (see full example below), but when the code attempts to construct an expression object the constructor gets into an infinite loop of calling these three constructors:

#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
...

Thus, Creating an expression creates a boost::variant<boost::recursive_wrapper<ast::expression>, ast::operator_expression> (aka, an expression_node) which creates a boost::recursive_wrapper<ast::expression> which creates an expression which creates... and so on.

How can I solve this?

Here is a full example that compiles, but segfaults when the stack runs full:

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

Aucun commentaire:

Enregistrer un commentaire