Boost.spirit (x3, boost 1.64): 如何正确实现这个递归规则，可能吗？

Question

这个问题很容易表述。我有一个递归规则，我不知道该规则的综合属性类型，但我还有一些关于内部工作原理的问题。

在我看来，return 类型是 variant<tuple<return_type_of_a, SEQ>, tuple<return_type_of_b, SEQ>>，其中 SEQ 是递归规则，a 和 b 是终结符：

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

以下不被接受，因为规则是递归的，我无法准确地找出 return 类型：

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

我必须知道递归规则的 return 类型吗？
看起来一定有某种类型的类型嵌套，这是递归的自然现象，但如果不扁平化就不可能在编译时计算出return类型。那么在编译时如何计算递归规则的类型呢？有什么扁平化吗？
综合以上规则应该是什么？
将规则重构为：

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

感谢您的帮助。

Answer 1

关于
```
seq = a >> seq | b >> seq;
```
首先也是最重要的：你的语法是严格循环的，从不解析：它将无限递归规则，直到不匹配。我假设你想要这样的东西：
```
expr = var | "!" >> expr;
```
（注意并非所有分支都无条件递归）。
how to implement this recursive rule correctly, is it possible?

是的。教程示例可能会显示这一点。

样本

假设我们有一个非常非常简单的语法，例如

expr = var | '!' >> expr;

我们创建一个 AST 来反映：

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

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

    struct negated {
        expr e;
    };

}

规则

因为expr规则是递归的，我们必须在定义之前声明它：

    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;

剩下的就是递归规则本身：BOOST_SPIRIT_DEFINE

    auto expr_def = var | neg;

    BOOST_SPIRIT_DEFINE(expr)

就这些了。

演示时间

让我们添加一些测试用例：

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

版画

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

并且可选 (#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)))

Boost.spirit (x3, boost 1.64): 如何正确实现这个递归规则，可能吗？

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

c++

recursion

boost

c++14

boost-spirit-x3

样本

规则

演示时间