Spirit-Qi: Как я могу написать нетерминальный парсер?
Я хочу написать парсер (как расширение ци), который может быть использован через my_parser(p1, p2, ...) где p1, p2, ... являются выражениями парсера ци.
На самом деле, я хочу реализовать best_matchсинтаксический анализатор, который работает как альтернатива qi, но выбирает не первое правило соответствия, а правило, которое "объясняет" большую часть ввода.
Учитывая два правила simple_id = +(qi::alpha) а также complex_id = simple_id >> *(qi::string("::") > simple_id) было бы выбрать complex_id на входе willy::anton, И он не будет производить промежуточные атрибуты при этом. Эти преимущества оплачиваются во время выполнения, потому что требуется предварительный анализ.
На мой взгляд, есть несколько вариантов использования такой конструкции парсера. benchmark(p1, ...) в качестве вспомогательного анализатора для оптимизации, только один пример. Я предоставлю это, как только я знаю, как к этому.
Этот парсер был бы нетерминальным. Я пытался (изо всех сил), но я не могу найти ответы на мою проблему в ци. Я предполагаю, что механизмы C++ настолько тесно интегрированы с c qi, что нет понятной точки входа, по крайней мере для меня.
Это довольно легко реализовать то, что я хочу, представляя оператора. Я добавляю текущее решение ниже. Он компилируется, как и ожидалось, но не завершен.
Оператор ци получает готовый fusion::vector/sequence (что угодно) и воздействует на него. Кажется, нет никаких библиотечных предложений, чтобы решить мою проблему. Четное make_nary_composite уже ожидает, что args компилируется в Elements,
Я много пробовал, все не получилось, поэтому я не хочу утомлять вас этим.
Обходным путем, который я могу себе представить, может быть предоставление оператора с состоянием ,что бы сделать p1, ... к юридическому выражению ци. Затем реализовать unary_parser best_match или директива для обработки этого выражения. , получит два режима: получение длины ввода, которую использует текущий (успешный) анализатор, и фактический анализ выбранного из фазы 1. Оболочка, запускающая этот анализатор запятой сначала в режиме 1, а затем в режиме 2. Это может быть некрасиво, но может работать
Оператор реализации p1 |= p2 |= ... является самым дорогим в отношении времени выполнения для n > 2. Я был бы счастлив обойти это.
Минимальные (но все же разумные) накладные расходы best_match(p1, ...), Это вообще возможно?
Поскольку я не слишком опытен с boost::fusion, я также добавил некоторые вопросы в код (как в отношении fusion).
Неправильно нажимать что-то, что на самом деле является нетарифным нетерминальным парсером, в схему унарного парсера Но с моим плохим пониманием это кажется единственным способом сделать это. Я очень признателен за любую помощь, чтобы вытащить меня из этого.
Моя среда: Boost 1.61, MSVC 2015 Upd 2, целевая win32console.
ПРОГРЕСС:
Я думаю, я получаю это медленно, но верно. Я был очень рад видеть error_invalid_expression, Сбой компиляции из-за следующего выражения прото:
boost::proto::exprns_::expr<
boost::proto::tagns_::tag::function,boost::proto::argsns_::list5<
const boost::proto::exprns_::expr<
boost::proto::tagns_::tag::terminal,boost::proto::argsns_::term<
mxc::qitoo::tag::best_match
>
,0> &
,const boost::spirit::qi::rule<
iterator_type,std::string (void),
boost::spirit::standard::space_type,
boost::spirit::unused_type,boost::spirit::unused_type> &
,const boost::spirit::qi::rule<
iterator_type,std::string (void),
boost::spirit::standard::space_type,
boost::spirit::unused_type,
boost::spirit::unused_type> &
, const boost::spirit::qi::rule<
iterator_type,std::string (void),
boost::spirit::standard::space_type,
boost::spirit::unused_type,
boost::spirit::unused_type> &
,const boost::spirit::qi::rule<
iterator_type,std::string (void),
boost::spirit::standard::space_type,
boost::spirit::unused_type,
boost::spirit::unused_type> &
>
,5>
Это на самом деле выражение, которое описывает мое использование стиля моего синтаксического анализатора best_match. Мое тестовое правило выглядит так
qitoo::best_match(id, qualified_id, id, qualified_id)
где id а также qualified_id правила, как указано выше. Все что я хочу. Ошибка происходит, потому что это выражение не имеет члена parse, Хорошо. Копаясь глубже, я обнаружил, что мета-компилятор qi поддерживает унарные, двоичные и нариальные (что означает вариационные) парсеры. Но он не поддерживает синтаксис стиля функции. Ци, кажется, использует унарный, двоичный и наарный только для операторов. И хотя nary-тип поддерживается, он более или менее устарел, поскольку операторы qi являются двоичными max.
КОНЕЦ РЕДАКЦИИ ПРОГРЕССА
#include <boost/spirit/home/qi.hpp>
namespace boost {
namespace spirit
{
///////////////////////////////////////////////////////////////////////////
// Enablers
///////////////////////////////////////////////////////////////////////////
template <>
struct use_operator<qi::domain, proto::tag::bitwise_or_assign> // enables |=
: mpl::true_ {};
template <>
struct flatten_tree<qi::domain, proto::tag::bitwise_or_assign> // flattens |=
: mpl::true_ {};
}
}
namespace mxc {
namespace qitoo {
namespace spirit = boost::spirit;
namespace qi = spirit::qi;
namespace fusion = boost::fusion;
template <typename Elements>
struct best_match_parser : qi::nary_parser<mxc::qitoo::best_match_parser<Elements>>
{
// This one does a lookahead parse of each qi expression to find out which rule matches
// most of the input
template <typename Iterator, typename Context, typename Skipper>
struct best_function
{
best_function(Iterator& first, Iterator const& last, Context& context,
Skipper const& skipper, int& best, int& idx, int& size)
: first(first), last(last), context(context), skipper(skipper), best(best),
idx(idx), size(size) {};
template <typename Component>
void operator()(Component& component) const
{
Iterator f = first;
if (component.parse(f, last, context, skipper, qi::unused)) {
// please have a look on how I transport best, idx and size
// into the parser context
//
// I guess, this is a nasty hack and could be done better
// Any advice would be highliy appreciated
int l = f - first;
if (l > size) {
size = l;
best = idx++;
}
idx++;
}
}
private:
int& best;
int& idx;
int& size;
Iterator& first;
Iterator const& last;
Context& context;
Skipper const& skipper;
};
template <typename Context, typename Iterator>
struct attribute
{
// Put all the element attributes in a tuple
typedef typename spirit::traits::build_attribute_sequence <
Elements, Context, spirit::traits::alternative_attribute_transform
, Iterator, qi::domain
>::type all_attributes;
// Ok, now make a variant over the attribute sequence. Note that
// build_variant makes sure that 1) all attributes in the variant
// are unique 2) puts the unused attribute, if there is any, to
// the front and 3) collapses single element variants, variant<T>
// to T.
typedef typename
spirit::traits::build_variant<all_attributes>::type
type;
};
best_match_parser(Elements const& elements_) : elements(elements_), size(0), idx(0), best(-1) {}
template <typename Iterator, typename Context, typename Skipper, typename Attribute>
bool parse(Iterator& first, Iterator const& last
, Context& context, Skipper const& skipper
, Attribute& attr_) const
{
best_function<Iterator, Context, Skipper> f(first, last, context, skipper, best, idx, size);
// find out which parser matches most of the input
fusion::for_each(elements, f);
// best >= 0 if at least one parser was successful
if (best >= 0) {
// now that I have the best parser identified, how do I access it?
// I understand that the next line can not work, but I'm looking for something like that
// --> auto v = fusion::at<boost::mpl::int_<best>>(elements);
};
return false;
}
template <typename Context>
qi::info what(Context& context) const
{
qi::info result("best_match");
fusion::for_each(elements,
spirit::detail::what_function<Context>(result, context));
return result;
}
Elements elements;
mutable int best;
mutable int idx;
mutable int size;
};
}
}
namespace boost {
namespace spirit {
namespace qi {
///////////////////////////////////////////////////////////////////////////
// Parser generators: make_xxx function (objects)
///////////////////////////////////////////////////////////////////////////
template <typename Elements, typename Modifiers>
struct make_composite<proto::tag::bitwise_or_assign, Elements, Modifiers>
: make_nary_composite < Elements, mxc::qitoo::best_match_parser >
{};
}
namespace traits {
///////////////////////////////////////////////////////////////////////////
template <typename Elements>
struct has_semantic_action<mxc::qitoo::best_match_parser<Elements> >
: nary_has_semantic_action<Elements> {};
///////////////////////////////////////////////////////////////////////////
template <typename Elements, typename Attribute, typename Context
, typename Iterator>
struct handles_container<mxc::qitoo::best_match_parser<Elements>, Attribute, Context
, Iterator>
: nary_handles_container<Elements, Attribute, Context, Iterator> {};
}
}
}
namespace qi = boost::spirit::qi;
namespace qitoo = mxc::qitoo;
using iterator_type = std::string::const_iterator;
using result_type = std::string;
template<typename Parser>
void parse(const std::string message, const std::string& input, const std::string& rule, const Parser& parser) {
iterator_type iter = input.begin(), end = input.end();
std::vector<result_type> parsed_result;
std::cout << "-------------------------\n";
std::cout << message << "\n";
std::cout << "Rule: " << rule << std::endl;
std::cout << "Parsing: \"" << input << "\"\n";
bool result = qi::phrase_parse(iter, end, parser, qi::space, parsed_result);
if (result)
{
std::cout << "Parser succeeded.\n";
std::cout << "Parsed " << parsed_result.size() << " elements:";
for (const auto& str : parsed_result)
std::cout << "[" << str << "]";
std::cout << std::endl;
}
else
{
std::cout << "Parser failed" << std::endl;
}
if (iter == end) {
std::cout << "EOI reached." << std::endl;
}
else {
std::cout << "EOI not reached. Unparsed: \"" << std::string(iter, end) << "\"" << std::endl;
}
std::cout << "-------------------------\n";
}
int main()
{
namespace qi = boost::spirit::qi;
qi::rule < iterator_type, std::string(), qi::space_type>
id = (qi::alpha | qi::char_('_')) >> *(qi::alnum | qi::char_('_'));
qi::rule < iterator_type, std::string(), qi::space_type>
qualified_id = id >> *(qi::string("::") > id);
namespace qitoo = mxc::qitoo;
namespace qi = boost::spirit::qi;
parse("best match operator, select second rule"
, "willy::anton::lutz"
, "id |= qualified_id"
, id |= qualified_id);
}
1 ответ
Ваш пример
Я не понимаю, как ваш образец требует всего этого. Просто измените порядок ветвей, а затем поймите, что короткая ветвь - это особый случай квалифицированного случая с n = 1: Live On Coliru ¹ (или, если хотите, с использованием версии X3).
Общий случай
Теперь, упомянув x3, он способен сделать вашу жизнь намного проще!
Вот что, я думаю, вы хотели в общем случае:
namespace parser {
template <typename... Parsers>
struct longest_parser : x3::parser_base {
longest_parser(Parsers... sub) : _alternatives {sub...} { }
template <typename It, typename Ctx, typename Other, typename Attr>
bool parse(It& f, It l, Ctx& ctx, Other const& other, Attr& attr) const {
auto const saved = f;
//// To exclude pre-skip from length comparisons, do pre-skip here:
// x3::skip_over(f, l, ctx);
auto seq = std::make_index_sequence<sizeof...(Parsers)>();
auto best = select_best(f, l, ctx, seq);
//std::cout << "Longest match at index #" << best << "\n";
bool ok = dispatch(f, l, ctx, other, attr, best, seq);
if (!ok)
f = saved;
return ok;
}
private:
template <typename It, typename Ctx, typename P>
size_t length_of(It f, It l, Ctx ctx, P const& p) const {
boost::iterator_range<It> matched;
return x3::raw[p].parse(f, l, ctx, x3::unused, matched)? boost::size(matched) : 0;
}
template <typename It, typename Ctx, size_t... I>
size_t select_best(It f, It l, Ctx& ctx, std::index_sequence<I...>) const {
std::array<size_t, sizeof...(I)> lengths { length_of(f, l, ctx, std::get<I>(_alternatives))... };
return std::distance(lengths.begin(), std::max_element(lengths.begin(), lengths.end()));
}
template <typename It, typename Ctx, typename Other, typename Attr, size_t... I>
bool dispatch(It& f, It l, Ctx& ctx, Other const& other, Attr& attr, size_t targetIdx, std::index_sequence<I...>) const {
//return (real_parse<I>(f, l, ctx, other, attr, targetIdx) || ...);
std::array<bool, sizeof...(I)> b = { real_parse<I>(f, l, ctx, other, attr, targetIdx)... };
return std::accumulate(b.begin(), b.end(), false, std::logical_or<bool>());
}
template <size_t Idx, typename It, typename Ctx, typename Other, typename Attr>
bool real_parse(It& f, It l, Ctx& ctx, Other const& other, Attr& attr, size_t targetIdx) const {
if (targetIdx != Idx)
return false;
return std::get<Idx>(_alternatives).parse(f, l, ctx, other, attr);
}
std::tuple<Parsers...> _alternatives;
};
template <typename... Ps>
longest_parser<Ps...> longest(Ps... p) { return {x3::as_parser(p)...}; }
}
Обратите внимание на выражение сгиба, которое вы можете использовать в dispatch если ваш компилятор поддерживает это (Coliru делает, отредактируйте его, чтобы увидеть!).
Обратите внимание также на тонкий выбор, который можно пропустить (вероятно, пробел); если это не имеет значения для сравнения длин, раскомментируйте предварительный пропуск.
Live Demo
#include <boost/spirit/home/x3.hpp>
#include <type_traits>
#include <iostream>
#include <numeric>
namespace x3 = boost::spirit::x3;
namespace std {
template <typename T> // just for easy debug printing; hack
static std::ostream& operator<<(std::ostream& os, std::vector<T> const& v) {
for (auto& el : v) std::cout << '[' << el << ']';
return os;
}
}
using string_vec = std::vector<std::string>;
using result_type = boost::variant<std::string, double, string_vec>;
template <typename Parser>
void parse(const std::string message, const std::string &input, const std::string &rule, const Parser &parser) {
auto iter = input.begin(), end = input.end();
std::cout << "-------------------------\n";
std::cout << message << "\n";
std::cout << "Rule: " << rule << "\n";
std::cout << "Parsing: '" << input << "'\n";
result_type parsed_result;
bool result = phrase_parse(iter, end, parser, x3::space, parsed_result);
if (result) {
std::cout << "Parsed " << parsed_result << "\n";
} else {
std::cout << "Parser failed\n";
}
if (iter != end)
std::cout << "EOI not reached. Unparsed: '" << std::string(iter, end) << "'\n";
}
namespace parser {
template <typename... Parsers>
struct longest_parser : x3::parser_base {
longest_parser(Parsers... sub) : _alternatives {sub...} { }
template <typename It, typename Ctx, typename Other, typename Attr>
bool parse(It& f, It l, Ctx& ctx, Other const& other, Attr& attr) const {
auto const saved = f;
//// To exclude pre-skip from length comparisons, do pre-skip here:
// x3::skip_over(f, l, ctx);
auto seq = std::make_index_sequence<sizeof...(Parsers)>();
auto best = select_best(f, l, ctx, seq);
//std::cout << "Longest match at index #" << best << "\n";
bool ok = dispatch(f, l, ctx, other, attr, best, seq);
if (!ok)
f = saved;
return ok;
}
private:
template <typename It, typename Ctx, typename P>
size_t length_of(It f, It l, Ctx ctx, P const& p) const {
boost::iterator_range<It> matched;
return x3::raw[p].parse(f, l, ctx, x3::unused, matched)? boost::size(matched) : 0;
}
template <typename It, typename Ctx, size_t... I>
size_t select_best(It f, It l, Ctx& ctx, std::index_sequence<I...>) const {
std::array<size_t, sizeof...(I)> lengths { length_of(f, l, ctx, std::get<I>(_alternatives))... };
return std::distance(lengths.begin(), std::max_element(lengths.begin(), lengths.end()));
}
template <typename It, typename Ctx, typename Other, typename Attr, size_t... I>
bool dispatch(It& f, It l, Ctx& ctx, Other const& other, Attr& attr, size_t targetIdx, std::index_sequence<I...>) const {
//return (real_parse<I>(f, l, ctx, other, attr, targetIdx) || ...);
std::array<bool, sizeof...(I)> b = { real_parse<I>(f, l, ctx, other, attr, targetIdx)... };
return std::accumulate(b.begin(), b.end(), false, std::logical_or<bool>());
}
template <size_t Idx, typename It, typename Ctx, typename Other, typename Attr>
bool real_parse(It& f, It l, Ctx& ctx, Other const& other, Attr& attr, size_t targetIdx) const {
if (targetIdx != Idx)
return false;
return std::get<Idx>(_alternatives).parse(f, l, ctx, other, attr);
}
std::tuple<Parsers...> _alternatives;
};
template <typename... Ps>
longest_parser<Ps...> longest(Ps... p) { return {x3::as_parser(p)...}; }
}
int main() {
auto id = x3::rule<void, std::string> {} = x3::lexeme [ x3::char_("a-zA-Z_") >> *x3::char_("a-zA-Z0-9_") ];
auto qualified = x3::rule<void, string_vec> {} = id % "::";
#define TEST_CASE(label, input, rule) parse(label, input, #rule, rule)
TEST_CASE("unqualified" , "willy" , parser::longest(id, x3::int_, x3::double_));
TEST_CASE("unqualified with whitespace", " willy \t" , parser::longest(id, x3::int_, x3::double_));
TEST_CASE("integral or number" , "123.78::anton::lutz" , parser::longest(id, x3::int_, x3::double_));
TEST_CASE("qualified" , "willy anton::lutz" , parser::longest(id, x3::int_, x3::double_));
TEST_CASE("qualified with whitespace" , "willy \tanton::lutz" , parser::longest(id, x3::int_, x3::double_));
TEST_CASE("unqualified" , "willy" , parser::longest(id, x3::int_, x3::double_, qualified));
TEST_CASE("unqualified with whitespace", " willy \t" , parser::longest(id, x3::int_, x3::double_, qualified));
TEST_CASE("integral or number" , "123.78::anton::lutz" , parser::longest(id, x3::int_, x3::double_, qualified));
TEST_CASE("qualified" , "willy::anton::lutz" , parser::longest(id, x3::int_, x3::double_, qualified));
TEST_CASE("qualified with whitespace" , "willy ::\tanton::lutz", parser::longest(id, x3::int_, x3::double_, qualified));
TEST_CASE("unqualified" , "willy" , parser::longest(x3::int_, x3::double_, qualified));
TEST_CASE("unqualified with whitespace", " willy \t" , parser::longest(x3::int_, x3::double_, qualified));
TEST_CASE("integral or number" , "123.78::anton::lutz" , parser::longest(x3::int_, x3::double_, qualified));
TEST_CASE("qualified" , "willy::anton::lutz" , parser::longest(x3::int_, x3::double_, qualified));
TEST_CASE("qualified with whitespace" , "willy ::\tanton::lutz", parser::longest(x3::int_, x3::double_, qualified));
}
Печать
-------------------------
unqualified
Rule: parser::longest(id, x3::int_, x3::double_)
Parsing: 'willy'
Parsed willy
-------------------------
unqualified with whitespace
Rule: parser::longest(id, x3::int_, x3::double_)
Parsing: ' willy '
Parsed willy
-------------------------
integral or number
Rule: parser::longest(id, x3::int_, x3::double_)
Parsing: '123.78::anton::lutz'
Parsed 123.78
EOI not reached. Unparsed: '::anton::lutz'
-------------------------
qualified
Rule: parser::longest(id, x3::int_, x3::double_)
Parsing: 'willy anton::lutz'
Parsed willy
EOI not reached. Unparsed: 'anton::lutz'
-------------------------
qualified with whitespace
Rule: parser::longest(id, x3::int_, x3::double_)
Parsing: 'willy anton::lutz'
Parsed willy
EOI not reached. Unparsed: 'anton::lutz'
-------------------------
unqualified
Rule: parser::longest(id, x3::int_, x3::double_, qualified)
Parsing: 'willy'
Parsed willy
-------------------------
unqualified with whitespace
Rule: parser::longest(id, x3::int_, x3::double_, qualified)
Parsing: ' willy '
Parsed willy
-------------------------
integral or number
Rule: parser::longest(id, x3::int_, x3::double_, qualified)
Parsing: '123.78::anton::lutz'
Parsed 123.78
EOI not reached. Unparsed: '::anton::lutz'
-------------------------
qualified
Rule: parser::longest(id, x3::int_, x3::double_, qualified)
Parsing: 'willy::anton::lutz'
Parsed [willy][anton][lutz]
-------------------------
qualified with whitespace
Rule: parser::longest(id, x3::int_, x3::double_, qualified)
Parsing: 'willy :: anton::lutz'
Parsed [willy][anton][lutz]
-------------------------
unqualified
Rule: parser::longest(x3::int_, x3::double_, qualified)
Parsing: 'willy'
Parsed [willy]
-------------------------
unqualified with whitespace
Rule: parser::longest(x3::int_, x3::double_, qualified)
Parsing: ' willy '
Parsed [willy]
-------------------------
integral or number
Rule: parser::longest(x3::int_, x3::double_, qualified)
Parsing: '123.78::anton::lutz'
Parsed 123.78
EOI not reached. Unparsed: '::anton::lutz'
-------------------------
qualified
Rule: parser::longest(x3::int_, x3::double_, qualified)
Parsing: 'willy::anton::lutz'
Parsed [willy][anton][lutz]
-------------------------
qualified with whitespace
Rule: parser::longest(x3::int_, x3::double_, qualified)
Parsing: 'willy :: anton::lutz'
Parsed [willy][anton][lutz]
Обратите внимание на различные результаты в зависимости от выражений парсера в альтернативах.