Boost.spirit (x3, boost 1.64): как правильно реализовать это рекурсивное правило, возможно ли это?

Question

Вопрос легко сформулировать. У меня есть рекурсивное правило, я не знаю синтезированный тип атрибута для правила, но у меня также есть еще несколько вопросов о внутренней работе.

Мне кажется, что возвращаемый тип variant<tuple<return_type_of_a, SEQ>, tuple<return_type_of_b, SEQ>> где SEQ это рекурсивное правило и a а также b являются терминалами:

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

Следующее не принято, потому что правило является рекурсивным, и я не могу точно определить тип возвращаемого значения:

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

1. я должен знать тип возврата рекурсивного правила?
2. похоже, что должен быть какой-то тип вложенности, это естественно для рекурсии, но если он не сплющен, невозможно вычислить возвращаемый тип во время компиляции. Итак, как вычисляется тип для рекурсивного правила во время компиляции? есть ли какое-то уплощение?
3. что должно быть синтезировано из правила выше?
4. это поможет рефакторинг правила:

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

Спасибо за вашу помощь.

Answer 1

1. Около

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

   Прежде всего: ваша грамматика строго круговая и никогда не анализируется: она будет бесконечно повторять правило, пока не будет выполнено несоответствие. Я собираюсь предположить, что вы хотели что-то вроде:

   expr = var | "!" >> expr;
   

   (Обратите внимание, что не все ветки возвращаются безоговорочно).

2. как правильно реализовать это рекурсивное правило, возможно ли это?

   Да. Образцы учебника, вероятно, должны показать это.

Образец

Допустим, у нас есть очень очень простая грамматика, как

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)

Это все.

ДЕМО ВРЕМЯ

Давайте добавим несколько тестовых случаев:

Жить на Колиру

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

Жить на Колиру

<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)))