Рекурсивное правило в Spirit.X3

Я хочу проанализировать рекурсивную грамматику с помощью Boost.Spirit x3, но он не работает из-за проблемы глубины создания экземпляра шаблона.

Грамматика выглядит так:

value: int | float | char | tuple
int: "int: " int_
float: "float: " real_ 
char: "char: " char_
tuple: "tuple: [" value* "]"

Вот пример:

#include <boost/fusion/adapted.hpp>
#include <boost/spirit/home/x3.hpp>
#include <string>
#include <vector>
#include <variant>

struct value: std::variant<int,float,std::vector<value>>
{ 
    using std::variant<int,float,std::vector<value>>::variant;

    value& operator=(float) { return *this; } 
    value& operator=(int) { return *this; } 
    value& operator=(std::vector<value>) { return *this; } 
};

using namespace boost::fusion;
namespace x3 = boost::spirit::x3;

using x3::skip;
using x3::int_;
using x3::real_parser;
using x3::char_;

x3::rule<class value_, value> const value_ = "value";
x3::rule<class o_tuple_, std::vector<value>> o_tuple_ = "tuple";

using float_p = real_parser<float, x3::strict_real_policies<float>>;


const auto o_tuple__def = "tuple: " >> skip(boost::spirit::x3::space)["[" >> value_ % "," >> "]"];
BOOST_SPIRIT_DEFINE(o_tuple_)

const auto value__def
    = ("float: " >> float_p())
    | ("int: " >> int_)
    | o_tuple_
    ;

BOOST_SPIRIT_DEFINE(value_)

int main()
{
  std::string str;
  value val;

  using boost::spirit::x3::parse;
  auto first = str.cbegin(), last = str.cend();
  bool r = parse(first, last, value_, val);
}

Это работает, если строка | o_tuple_ закомментирована (например, без рекурсии).

c++ boost-spirit boost-spirit-x3

Jean-Michaël Celerier 26.08.2017 источник

Ответы (1)

arrow_upward
2
arrow_downward

Это обычная проблема рекурсии в X3. Это еще не решено.

Думаю, я понимаю, что проблема в том, что x3::skip изменяет объект контекста¹. Действительно, отбрасывание заставляет вещь скомпилировать и успешно проанализировать некоторые тривиальные тестовые примеры:

"float: 3.14",
"int: 3.14",
"tuple: [float: 3.14,int: 3]",

Тем не менее, очевидно, что без шкипера не выполняется синтаксический анализ:

// the following _should_ have compiled with the original skip() configuration:
"tuple: [ float: 3.14,\tint: 3 ]",

Теперь я рискну, что вы можете избавиться от проблемы, применив шкипер на верхнем уровне (что означает, что контекст идентичен для всех правил, участвующих в «цикле» создания экземпляра). Если вы это сделаете, вы сразу начнете принимать более гибкие пробелы во вводе:

// the following would not have parsed with the original skip() configuration:
"float:3.14",
"int:3.14",
"tuple:[float: 3.14,int: 3]",
"tuple:[float:3.14,int:3]",
"tuple: [ float:3.14,\tint:3 ]",

Ничто из этого не было бы синтаксическим анализом с исходным подходом, даже если бы он был успешно скомпилирован.

Что для этого нужно

Вот некоторые изменения, которые я внес в код.

удалили бессильные операторы присваивания value::operator= (я не знаю, зачем они у вас были)

добавить код для печати отладочного дампа любого value:

friend std::ostream& operator<<(std::ostream& os, base_type const& v) {
    struct {
        std::ostream& operator()(float const& f) const { return _os << "float:" << f; }
        std::ostream& operator()(int const& i)   const { return _os << "int:" << i; }
        std::ostream& operator()(std::vector<value> const& v) const { 
            _os << "tuple: [";
            for (auto& el : v) _os << el << ",";
            return _os << ']';
        }
        std::ostream& _os;
    } vis { os };

    return std::visit(vis, v);
}

Отбросьте шкипера и выделите ключевые слова из : interpunction:

namespace x3 = boost::spirit::x3;

x3::rule<struct value_class, value> const value_ = "value";
x3::rule<struct o_tuple_class, std::vector<value> > o_tuple_ = "tuple";

x3::real_parser<float, x3::strict_real_policies<float> > float_;

const auto o_tuple__def = "tuple" >> x3::lit(':') >> ("[" >> value_ % "," >> "]");

const auto value__def
    = "float" >> (':' >> float_)
    | "int" >> (':' >> x3::int_)
    | o_tuple_
    ;

BOOST_SPIRIT_DEFINE(value_, o_tuple_)

Теперь решающий шаг: добавьте шкипера на верхнем уровне:
```
const auto entry_point = x3::skip(x3::space) [ value_ ];
```

Создайте хороший тестовый драйвер main():

int main()
{
    for (std::string const str : {
            "",
            "float: 3.14",
            "int: 3.14",
            "tuple: [float: 3.14,int: 3]",
            // the following _should_ have compiled with the original skip() configuration:
            "tuple: [ float: 3.14,\tint: 3 ]",
            // the following would not have parsed with the original skip() configuration:
            "float:3.14",
            "int:3.14",
            "tuple:[float: 3.14,int: 3]",
            "tuple:[float:3.14,int:3]",
            "tuple: [ float:3.14,\tint:3 ]",
            // one final show case for good measure
            R"(
            tuple: [
               int  : 4,
               float: 7e9,
               tuple: [float: -inf],


               int: 42
            ])"
    }) {
        std::cout << "============ '" << str << "'\n";

        //using boost::spirit::x3::parse;
        auto first = str.begin(), last = str.end();
        value val;

        if (parse(first, last, parser::entry_point, val))
            std::cout << "Parsed '" << val << "'\n";
        else
            std::cout << "Parse failed\n";

        if (first != last)
            std::cout << "Remaining input: '" << std::string(first, last) << "'\n";
    }
}

Живая демонстрация

См. Live On Coliru

//#define BOOST_SPIRIT_X3_DEBUG #include <iostream> #include <boost/fusion/adapted.hpp> #include <boost/spirit/home/x3.hpp> #include <string> #include <vector> #include <variant> struct value: std::variant<int,float,std::vector<value>> { using base_type = std::variant<int,float,std::vector<value>>; using base_type::variant; friend std::ostream& operator<<(std::ostream& os, base_type const& v) { struct { std::ostream& operator()(float const& f) const { return _os << "float:" << f; } std::ostream& operator()(int const& i) const { return _os << "int:" << i; } std::ostream& operator()(std::vector<value> const& v) const { _os << "tuple: ["; for (auto& el : v) _os << el << ","; return _os << ']'; } std::ostream& _os; } vis { os }; return std::visit(vis, v); } }; namespace parser { namespace x3 = boost::spirit::x3; x3::rule<struct value_class, value> const value_ = "value"; x3::rule<struct o_tuple_class, std::vector<value> > o_tuple_ = "tuple"; x3::real_parser<float, x3::strict_real_policies<float> > float_; const auto o_tuple__def = "tuple" >> x3::lit(':') >> ("[" >> value_ % "," >> "]"); const auto value__def = "float" >> (':' >> float_) | "int" >> (':' >> x3::int_) | o_tuple_ ; BOOST_SPIRIT_DEFINE(value_, o_tuple_) const auto entry_point = x3::skip(x3::space) [ value_ ]; } int main() { for (std::string const str : { "", "float: 3.14", "int: 3.14", "tuple: [float: 3.14,int: 3]", // the following _should_ have compiled with the original skip() configuration: "tuple: [ float: 3.14,\tint: 3 ]", // the following would not have parsed with the original skip() configuration: "float:3.14", "int:3.14", "tuple:[float: 3.14,int: 3]", "tuple:[float:3.14,int:3]", "tuple: [ float:3.14,\tint:3 ]", // one final show case for good measure R"( tuple: [ int : 4, float: 7e9, tuple: [float: -inf], int: 42 ])" }) { std::cout << "============ '" << str << "'\n"; //using boost::spirit::x3::parse; auto first = str.begin(), last = str.end(); value val; if (parse(first, last, parser::entry_point, val)) std::cout << "Parsed '" << val << "'\n"; else std::cout << "Parse failed\n"; if (first != last) std::cout << "Remaining input: '" << std::string(first, last) << "'\n"; } }

Печать

============ '' Parse failed ============ 'float: 3.14' Parsed 'float:3.14' ============ 'int: 3.14' Parsed 'int:3' Remaining input: '.14' ============ 'tuple: [float: 3.14,int: 3]' Parsed 'tuple: [float:3.14,int:3,]' ============ 'tuple: [ float: 3.14, int: 3 ]' Parsed 'tuple: [float:3.14,int:3,]' ============ 'float:3.14' Parsed 'float:3.14' ============ 'int:3.14' Parsed 'int:3' Remaining input: '.14' ============ 'tuple:[float: 3.14,int: 3]' Parsed 'tuple: [float:3.14,int:3,]' ============ 'tuple:[float:3.14,int:3]' Parsed 'tuple: [float:3.14,int:3,]' ============ 'tuple: [ float:3.14, int:3 ]' Parsed 'tuple: [float:3.14,int:3,]' ============ ' tuple: [ int : 4, float: 7e9, tuple: [float: -inf], int: 42 ]' Parsed 'tuple: [int:4,float:7e+09,tuple: [float:-inf,],int:42,]'

¹ другие директивы тоже, например x3::with<>. Проблема может заключаться в том, что контекст становится расширенным на каждом уровне создания экземпляра вместо «модифицированного» для возврата к исходному типу контекста и завершения цикла создания экземпляра.

sehe 27.08.2017

comment

вау, спасибо за огромный ответ. Дело operator= было связано с тем, что я также пытался изменить рекурсию на более простой тип, например int_ или float_ в моем исходном коде, а затем он не мог компилироваться, потому что он не мог назначить (но удаление skip также исправляет это) - Jean-Michaël Celerier; 27.08.2017

Рекурсивное правило в Spirit.X3

Ответы (1)

Что для этого нужно

Живая демонстрация

Вопросы по теме