提升精神解析器:绕过贪婪的 kleene *
boost spirit parser : getting around the greedy kleene *
我有一个语法,它应该匹配字符序列后跟一个字符,该字符是第一个字符的子集。
例如,
boost::spirit::qi::rule<Iterator, std::string()> grammar = *char_('a', 'z') >> char_('b', 'z').
由于 kleene * 是贪婪运算符,它吞噬了所有东西,没有给第二个解析器留下任何东西,所以它无法匹配像 "abcd"
这样的字符串
有什么办法可以解决这个问题吗?
是的,尽管您的示例缺乏我们了解的上下文。
我们需要知道什么是完全匹配,因为现在 "b" 是有效匹配,而 "bb" 或 "bbb" 是有效匹配。那么当输入为 "bbb" 时,匹配项是什么? (b、bb 还是 bbb?)。
当您(可能)回答 "Obviously, bbb" 时,"bbbb" 会怎样?你什么时候停止接受子集中的字符?想让kleene star不贪心,还想让它一直贪心吗?
上面的对话框很烦人,但目的是让您思考您需要什么。您 不需要 需要非贪婪的 kleene-star。您可能希望对最后一个字符进行验证约束。最有可能的是,如果输入有 "bbba",你 而不是 想要简单地匹配 "bbb",留下 "a"。相反,您可能想停止解析,因为 "bbba" 不是有效标记。
假设...
我会写
grammar = +char_("a-z") >> eps(px::back(_val) != 'a');
意味着我们接受 至少 1 个字符 只要它匹配,断言最后一个字符不是 a
.
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/phoenix_stl.hpp>
namespace qi = boost::spirit::qi;
namespace px = boost::phoenix;
template <typename It>
struct P : qi::grammar<It, std::string()>
{
P() : P::base_type(start) {
using namespace qi;
start = +char_("a-z") >> eps(px::back(_val) != 'a');
}
private:
qi::rule<It, std::string()> start;
};
#include <iomanip>
int main() {
using It = std::string::const_iterator;
P<It> const p;
for (std::string const input : { "", "b", "bb", "bbb", "aaab", "a", "bbba" }) {
std::cout << std::quoted(input) << ": ";
std::string out;
It f = input.begin(), l = input.end();
if (parse(f, l, p, out)) {
std::cout << std::quoted(out);
} else {
std::cout << "(failed) ";
}
if (f != l)
std::cout << " Remaining: " << std::quoted(std::string(f,l));
std::cout << "\n";
}
}
版画
"": (failed)
"b": "b"
"bb": "bb"
"bbb": "bbb"
"aaab": "aaab"
"a": (failed) Remaining: "a"
"bbba": (failed) Remaining: "bbba"
奖金
一种更通用但效率较低的方法是将前导字符与前瞻性断言相匹配,即它不是同类中的最后一个字符:
start = *(char_("a-z") >> &char_("a-z")) >> char_("b-z");
这里的一个好处是不需要使用 Phoenix:
#include <boost/spirit/include/qi.hpp>
namespace qi = boost::spirit::qi;
template <typename It>
struct P : qi::grammar<It, std::string()>
{
P() : P::base_type(start) {
using namespace qi;
start = *(char_("a-z") >> &char_("a-z")) >> char_("b-z");
}
private:
qi::rule<It, std::string()> start;
};
#include <iomanip>
int main() {
using It = std::string::const_iterator;
P<It> const p;
for (std::string const input : { "", "b", "bb", "bbb", "aaab", "a", "bbba" }) {
std::cout << std::quoted(input) << ": ";
std::string out;
It f = input.begin(), l = input.end();
if (parse(f, l, p, out)) {
std::cout << std::quoted(out);
} else {
std::cout << "(failed) ";
}
if (f != l)
std::cout << " Remaining: " << std::quoted(std::string(f,l));
std::cout << "\n";
}
}
我有一个语法,它应该匹配字符序列后跟一个字符,该字符是第一个字符的子集。 例如,
boost::spirit::qi::rule<Iterator, std::string()> grammar = *char_('a', 'z') >> char_('b', 'z').
由于 kleene * 是贪婪运算符,它吞噬了所有东西,没有给第二个解析器留下任何东西,所以它无法匹配像 "abcd"
这样的字符串有什么办法可以解决这个问题吗?
是的,尽管您的示例缺乏我们了解的上下文。
我们需要知道什么是完全匹配,因为现在 "b" 是有效匹配,而 "bb" 或 "bbb" 是有效匹配。那么当输入为 "bbb" 时,匹配项是什么? (b、bb 还是 bbb?)。
当您(可能)回答 "Obviously, bbb" 时,"bbbb" 会怎样?你什么时候停止接受子集中的字符?想让kleene star不贪心,还想让它一直贪心吗?
上面的对话框很烦人,但目的是让您思考您需要什么。您 不需要 需要非贪婪的 kleene-star。您可能希望对最后一个字符进行验证约束。最有可能的是,如果输入有 "bbba",你 而不是 想要简单地匹配 "bbb",留下 "a"。相反,您可能想停止解析,因为 "bbba" 不是有效标记。
假设...
我会写
grammar = +char_("a-z") >> eps(px::back(_val) != 'a');
意味着我们接受 至少 1 个字符 只要它匹配,断言最后一个字符不是 a
.
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/phoenix_stl.hpp>
namespace qi = boost::spirit::qi;
namespace px = boost::phoenix;
template <typename It>
struct P : qi::grammar<It, std::string()>
{
P() : P::base_type(start) {
using namespace qi;
start = +char_("a-z") >> eps(px::back(_val) != 'a');
}
private:
qi::rule<It, std::string()> start;
};
#include <iomanip>
int main() {
using It = std::string::const_iterator;
P<It> const p;
for (std::string const input : { "", "b", "bb", "bbb", "aaab", "a", "bbba" }) {
std::cout << std::quoted(input) << ": ";
std::string out;
It f = input.begin(), l = input.end();
if (parse(f, l, p, out)) {
std::cout << std::quoted(out);
} else {
std::cout << "(failed) ";
}
if (f != l)
std::cout << " Remaining: " << std::quoted(std::string(f,l));
std::cout << "\n";
}
}
版画
"": (failed)
"b": "b"
"bb": "bb"
"bbb": "bbb"
"aaab": "aaab"
"a": (failed) Remaining: "a"
"bbba": (failed) Remaining: "bbba"
奖金
一种更通用但效率较低的方法是将前导字符与前瞻性断言相匹配,即它不是同类中的最后一个字符:
start = *(char_("a-z") >> &char_("a-z")) >> char_("b-z");
这里的一个好处是不需要使用 Phoenix:
#include <boost/spirit/include/qi.hpp>
namespace qi = boost::spirit::qi;
template <typename It>
struct P : qi::grammar<It, std::string()>
{
P() : P::base_type(start) {
using namespace qi;
start = *(char_("a-z") >> &char_("a-z")) >> char_("b-z");
}
private:
qi::rule<It, std::string()> start;
};
#include <iomanip>
int main() {
using It = std::string::const_iterator;
P<It> const p;
for (std::string const input : { "", "b", "bb", "bbb", "aaab", "a", "bbba" }) {
std::cout << std::quoted(input) << ": ";
std::string out;
It f = input.begin(), l = input.end();
if (parse(f, l, p, out)) {
std::cout << std::quoted(out);
} else {
std::cout << "(failed) ";
}
if (f != l)
std::cout << " Remaining: " << std::quoted(std::string(f,l));
std::cout << "\n";
}
}