Boost.spirit (x3, boost 1.64): how to implement this recursive rule correctly, is it possible?

Question

The question is easy to formulate. I have a recursive rule, I do not know the synthesized attribute type for the rule, but I also have a few more questions about the inner workings.

It looks to me that the return type is variant<tuple<return_type_of_a, SEQ>, tuple<return_type_of_b, SEQ>> where SEQ is a recursive rule and a and b are terminals:

rule<class myrule, ??> SEQ = a >> SEQ | b >> SEQ;

The following is not accepted because the rule is recursive, and I cannot figure out the return type exactly:

rule<class myrule, decltype (a>> SEQ | b >> SEQ)> seq = a >> seq | b >> seq;

1. must I know the return type of the recursive rule?
2. it looks like there must be some type of type nesting, this is natural to recursion, but if it is not flattened it is impossible to calculate the return type at compile-time. So how is the type for a recursive rule calculated at compile-time? there is any kind of flattening?
3. what should be the synthesized of the rule above?
4. would it help to refactor the rule to:

rule<class myrule, ??> SEQ = (a | b) >> SEQ;

Thanks for your help.

Answer 1

1. About

   seq = a >> seq | b >> seq;
   

   First and foremost: your grammar is strictly circular and never parses: it will infinitely recurse the rule, until mismatch. I'm going to assume you wanted something like:

   expr = var | "!" >> expr;
   

   (Note how not all branches recurse unconditionally).

2. how to implement this recursive rule correctly, is it possible?

   Yes. The tutorial samples should probably show this.

Sample

Let's say we have a very very simple grammar like

expr = var | '!' >> expr;

We create an AST to reflect that:

namespace Ast {
    using var = std::string;
    struct negated;

    using expr = boost::variant<var, boost::recursive_wrapper<negated> >;

    struct negated {
        expr e;
    };

}

The Rules

Because the expr rule is going to be recursive, we have to declare it before its definition:

    static x3::rule<struct expr_, Ast::expr> expr {"expr"};

Let's imagine it's already defined, we would write the sub expressions like:

    auto var = x3::rule<struct var_, Ast::var> {"var"}
             = x3::lexeme [ x3::alpha >> *x3::alnum ];

    auto neg = x3::rule<struct var_, Ast::negated> {"neg"}
             = "!" >> expr;

All that's left is the recursive rule itself: BOOST_SPIRIT_DEFINE

    auto expr_def = var | neg;

    BOOST_SPIRIT_DEFINE(expr)

That's all.

DEMO TIME

Let's add some test cases:

Live On Coliru

#include <boost/spirit/home/x3.hpp>
#include <boost/fusion/adapted/struct.hpp>

namespace Ast {
    using var = std::string;
    struct negated;

    using expr = boost::variant<var, boost::recursive_wrapper<negated> >;

    struct negated {
        expr e;
    };

    static inline std::ostream& operator <<(std::ostream& os, Ast::negated const& n) {
        return os << "NOT(" << n.e << ")";
    }
}

BOOST_FUSION_ADAPT_STRUCT(Ast::negated, e)

namespace Parsers {
    namespace x3 = boost::spirit::x3;

    namespace detail {
        static x3::rule<struct expr_, Ast::expr> expr {"expr"};

        auto var = x3::rule<struct var_, Ast::var> {"var"}
                 = x3::lexeme [ x3::alpha >> *x3::alnum ];

        auto neg = x3::rule<struct var_, Ast::negated> {"neg"}
                 = "!" >> expr;

        auto expr_def = var | neg;

        BOOST_SPIRIT_DEFINE(expr)
    }

    auto demo = x3::skip(x3::space) [ detail::expr ];
}

#include <iostream>

int main() {
    for (std::string const input : { "foo", "! bar", "!!!qux" }) {
        auto f = input.begin(), l = input.end();

        Ast::expr e;

        if (parse(f, l, Parsers::demo, e)) {
            std::cout << "Parsed: " << e << "\n";
        } else {
            std::cout << "Parse failed\n";
        }

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

Prints

Parsed: foo
Parsed: NOT(bar)
Parsed: NOT(NOT(NOT(qux)))

And optionally (#define BOOST_SPIRIT_X3_DEBUG)

Live On Coliru

<expr>
  <try>foo</try>
  <var>
    <try>foo</try>
    <success></success>
    <attributes>[f, o, o]</attributes>
  </var>
  <success></success>
  <attributes>[f, o, o]</attributes>
</expr>
Parsed: foo
<expr>
  <try>! bar</try>
  <var>
    <try>! bar</try>
    <fail/>
  </var>
  <neg>
    <try>! bar</try>
    <expr>
      <try> bar</try>
      <var>
        <try> bar</try>
        <success></success>
        <attributes>[b, a, r]</attributes>
      </var>
      <success></success>
      <attributes>[b, a, r]</attributes>
    </expr>
    <success></success>
    <attributes>[[b, a, r]]</attributes>
  </neg>
  <success></success>
  <attributes>[[b, a, r]]</attributes>
</expr>
Parsed: NOT(bar)
<expr>
  <try>!!!qux</try>
  <var>
    <try>!!!qux</try>
    <fail/>
  </var>
  <neg>
    <try>!!!qux</try>
    <expr>
      <try>!!qux</try>
      <var>
        <try>!!qux</try>
        <fail/>
      </var>
      <neg>
        <try>!!qux</try>
        <expr>
          <try>!qux</try>
          <var>
            <try>!qux</try>
            <fail/>
          </var>
          <neg>
            <try>!qux</try>
            <expr>
              <try>qux</try>
              <var>
                <try>qux</try>
                <success></success>
                <attributes>[q, u, x]</attributes>
              </var>
              <success></success>
              <attributes>[q, u, x]</attributes>
            </expr>
            <success></success>
            <attributes>[[q, u, x]]</attributes>
          </neg>
          <success></success>
          <attributes>[[q, u, x]]</attributes>
        </expr>
        <success></success>
        <attributes>[[[q, u, x]]]</attributes>
      </neg>
      <success></success>
      <attributes>[[[q, u, x]]]</attributes>
    </expr>
    <success></success>
    <attributes>[[[[q, u, x]]]]</attributes>
  </neg>
  <success></success>
  <attributes>[[[[q, u, x]]]]</attributes>
</expr>
Parsed: NOT(NOT(NOT(qux)))