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

the question easy formulate. have recursive rule, not know synthesized attribute type rule, have few more questions inner workings.

it looks me return type variant<tuple<return_type_of_a, seq>, tuple<return_type_of_b, seq>> seq recursive rule , a , b terminals:

rule<class myrule, ??> seq = >> seq | b >> seq; 

the following not accepted because rule recursive, , cannot figure out return type exactly:

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

1. must know return type of recursive rule?
2. it looks there must type of type nesting, natural recursion, if not flattened impossible calculate return type @ compile-time. how type recursive rule calculated @ compile-time? there kind of flattening?
3. what should synthesized of rule above?
4. would refactor rule to:

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

thanks help.

1. about

   seq = >> seq | b >> seq; 

   first , foremost: grammar strictly circular , never parses: infinitely recurse rule, until mismatch. i'm going assume wanted like:

   expr = var | "!" >> expr; 

   (note how not branches recurse unconditionally).

2. how implement recursive rule correctly, possible?

   yes. tutorial samples should show this.

sample

let's have very simple grammar like

expr = var | '!' >> expr; 

we create ast 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 expr rule going recursive, have declare before definition:

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

let's imagine it's defined, write 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 recursive rule itself: boost_spirit_define

    auto expr_def = var | neg;      boost_spirit_define(expr) 

that's all.

demo time

let's add 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() {     (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)))