Spirit-Qi:如何编写非终端解析器? [英] Spirit-Qi: How can I write a nonterminal parser?
问题描述
我想写一个解析器(作为qi扩展名)，可以使用
通过my_parser(p1, p2, ...)，其中p1, p2, ...是qi解析器表达式.
I want to write a parser (as a qi extension) which can be used
via my_parser(p1, p2, ...) where p1, p2, ... are qi parser expressions.
实际上，我想实现一个best_match解析器，其作用与qi Alternative类似，但它不选择第一个匹配规则，而是选择解释"大部分输入的规则.
Actually, I want to implement a best_matchparser which works like qi alternative, but selects not the first matching rule but the rule which 'explains' most of the input.
给出两个规则simple_id = +(qi::alpha)和complex_id = simple_id >> *(qi::string("::") > simple_id)，它将在输入willy::anton上选择complex_id.并且这样做时不会产生中间属性.这些好处可通过运行时获得，因为需要提前解析.
Given two rules simple_id = +(qi::alpha) and complex_id = simple_id >> *(qi::string("::") > simple_id) it would select complex_id on the input willy::anton. And it would not produce intermediate attributes while doing so. These benefits get payed for with runtime because lookahead parsing is required.
在我看来，这种解析器构造有多个用例. benchmark(p1, ...)作为优化的支持解析器，仅是一个示例.一旦我知道该怎么做，便会提供.
In my view there are several use cases for such a parser construct. benchmark(p1, ...) as a supporting parser for optimization, just one example. I will provide that, once I know how to that.
此解析器将是非终结器.我尝试了一下(辛苦了)，但在qi中找不到我的问题的答案.我的猜测是，C ++机制与c qi紧密集成在一起，以至于没有一个可以理解的切入点，至少对我而言.
This parser would be an non-terminal. I tried (hard), but I can not find answers to my problem within qi. My guess is, that C++ mechanisms are so tightly integrated withc qi, that there is no understandable entry point, at least for me.
实现我想要引入的运算符非常容易.我在下面附加了当前的解决方案.它可以按预期编译，但不完整.
It is quite easy to implement what I want introducing an operator. I append the current solution below. It compiles as expected but is incomplete.
一个qi运算符准备好一个融合::: vector/sequence(无论如何)并对其进行操作.似乎没有图书馆产品可以解决我的问题.甚至make_nary_composite都已经期望将args编译为Elements.
A qi operator gets a fusion::vector/sequence (whatever) ready made and acts on it. There seem to be no library offerings to solve my problem. Even make_nary_composite already expects the args being compiled to Elements.
我尝试了很多，但一切都失败了，所以我不想让您感到无聊.
I tried a lot, everything failed, so I don't want to bore you with that.
我可以想象的一种解决方法是提供一个有状态的运算符,，这将使p1, ...成为合法的qi表达式.然后实现unary_parser best_match或指令来处理该表达式.
,将有两种模式:获取当前(成功)解析器消耗的输入长度，并实际解析从阶段1中选择的输入.包装器首先在模式1中运行该逗号解析器，然后在模式2中运行.很难看，但是可以用.
A workaround which I can imagine could be to provide a stateful operator ,, which would make p1, ... to a legal qi expression. Then implement a unary_parser best_match or directive to process that expression.
The , would get two modes: getting the length of input the current (successful) parser consumes and actually parsing the selected one from phase 1. The wrapper what run that comma parser first in mode 1 and then in mode 2. It might be ugly, but could work.
对于n> 2，运算符实现p1 |= p2 |= ...对于运行时而言是最昂贵的.我很乐意解决这个问题.
The operator implementation p1 |= p2 |= ... is the most expensive regarding runtime for n > 2. I would be happy to get around that.
最小(但仍然合理)的开销将具有best_match(p1, ...).
那有可能吗?
Minimum (but nevertheless reasonable) overhead would have best_match(p1, ...).
Is that possible at all?
因为我对boost :: fusion不太熟悉，所以我也在代码中添加了一些问题(关于融合的方法).
For I am not too experienced with boost::fusion I added some questions to the code as well (how tos regarding fusion).
将实际上是nary非终端解析器的内容压入一元解析器方案中感觉很不对.但是据我所知，这似乎是完成它的唯一方法.非常感谢您能帮助我摆脱困境.
It feels wrong, to press something which actually is a nary non-terminal parser into the unary parser scheme. But with my poor understanding it seems to be the only way to get it done. I'd highly appreciate any help to get me out of this.
我的环境:Boost 1.61，MSVC 2015 Upd 2，目标win32console.
My environment: Boost 1.61, MSVC 2015 Upd 2, target win32console.
进度:
我认为，我正在慢慢地但肯定地得到它.我很高兴看到error_invalid_expression.编译失败，因为以下原型表达式:
I think, I'm getting it slowly but surely. I was very happy to see an error_invalid_expression. Compile failed because of the following proto 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解析器的函数风格用法的表达式.我的测试规则看起来像
This actually is the expression which describes my function-style usage of my best_match parser. My test rule looks like
qitoo::best_match(id, qualified_id, id, qualified_id)
其中，id和qualified_id是上述规则.我想要的一切.
发生错误是因为此表达式没有成员parse.好的.深入研究，我发现qi的元编译器确实支持一元，二进制和nary(这意味着可变参数)解析器.但是它不支持函数样式语法. Qi似乎仅对运算符使用一元，二进制和一元.尽管支持nary类型，但由于qi运算符是二进制最大值，因此它或多或少已经过时.
where id and qualified_id are the rules as mentioned above. All that I want.
The error occurs because this expression does not have a member parse. Okay. Digging deeper I found qi's meta-compiler does support unary, binary and nary (what means variadic) parsers. But it does not support function style syntax. Qi seems to utilize unary, binary and nary for operators only. And allthough the nary type is supported, it is more or less obsolete, because qi operators are binary 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);
}
推荐答案
您的示例
我看不出您的样品对此有何要求.只需对分支进行重新排序，然后意识到短分支只是n = 1的合格案例的特例:使用X3版本)
Your example
I don't see how your sample requires any of this. Just reorder your branches, then realize that the short branch is just a special case of the qualified case with n=1: Live On Coliru¹ (or using X3 version if you prefer).
现在，提到x3了，它有能力使您的生活变得更加轻松！
Now, having mentioned x3, it has the capacity to make your live much easier!
在一般情况下，这就是我想要的:
Here's what I think you wanted, in the general case:
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支持，编辑它以查看！).
Note the fold expression you could use in dispatch if your compiler supports it (Coliru does, edit it to see!).
还要注意关于可跳过(可能是空格)的微妙选择；如果长度比较不重要，请取消注释预跳过.
实时演示
#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]
请注意不同结果，具体取决于备用方法中的解析器表达式.
Note the different results depending on the parser expressions in the alternatives.
这篇关于Spirit-Qi:如何编写非终端解析器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
