如何在Boost Spirit中设置最大递归

问题描述

如果我有递归规则来解析括号，请使用boost :: spirit

Using boost::spirit, if I have a recursive rule to parse parentheses

rule<std::string::iterator, std::string()> term;
term %= string("(") >> *term >> string(")");

如何限制最大递归量?例如，如果我尝试解析一百万个嵌套括号，则会出现段错误，因为已超出堆栈大小.具体来说，这是一个完整的示例.

how do I limit the maximum amount of recursion? For example, if I try to parse a million nested parentheses, I get a segfault because the stack size has been exceeded. To be concrete, here is a complete sample.

#include <iostream>
#include <string>
#include <boost/spirit/include/qi.hpp>

int main(void)
{
    using namespace boost::spirit;
    using namespace boost::spirit::qi;
    const size_t string_size = 1000000;
    std::string str;
    str.resize(string_size);
    for (size_t s=0; s<str.size()/2; ++s)
      {
        str[s]='(';
        str[str.size() - s -1] = ')';
      }

    rule<std::string::iterator, std::string()> term;
    term %= string("(") >> *term >> string(")");
    std::string h;
    parse(str.begin(), str.end(), term, h);
}

我用命令编译了它

g++ simple.cxx -o simple -std=c++11

如果将string_size设置为1000而不是1000000，效果很好.

It works fine if I set string_size to 1000 instead of 1000000.

推荐答案

跟踪qi::local<>或phx::ref()中的深度.

在这种情况下，继承的属性可以很自然地充当qi::local的角色:

In this case an inherited attribute can take the role of the qi::local quite naturally:

qi::rule<std::string::const_iterator, std::string(size_t depth)> term;
qi::_r1_type _depth;
term %=
    qi::eps(_depth < 32) >>
    qi::string("(") >> *term(_depth + 1) >> qi::string(")");

term现在将在深度超过32时失败.

term will now fail when depth exceeds 32.

#include <iostream>
#include <string>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
namespace qi = boost::spirit::qi;

int main(void) {
    for (size_t n : { 2, 4, 8, 16, 32, 64 }) {
        auto const str = [&n] {
            std::string str;
            str.reserve(n);
            while (n--) { str.insert(str.begin(), '('); str.append(1, ')'); }
            return str;
        }();
        std::cout << "Input length " << str.length() << "\n";

        qi::rule<std::string::const_iterator, std::string(size_t depth)> term;
        qi::_r1_type _depth;
        term %=
            qi::eps(_depth < 32) >>
            qi::string("(") >> *term(_depth + 1) >> qi::string(")");

        std::string h;

        auto f = str.begin(), l = str.end();
        bool ok = qi::parse(f, l, term(0u), h);
        if (ok)
            std::cout << "Ok: " << h << "\n";
        else
            std::cout << "Fail\n";

        if (f != l)
            std::cout << "Remaining  unparsed: '" << std::string(f, std::min(f + 40, l)) << "'...\n";
    }
}

输出:

Input length 4
Ok: (())
Input length 8
Ok: (((())))
Input length 16
Ok: (((((((())))))))
Input length 32
Ok: (((((((((((((((())))))))))))))))
Input length 64
Ok: (((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))
Input length 128
Fail
Remaining  unparsed: '(((((((((((((((((((((((((((((((((((((((('...

这篇关于如何在Boost Spirit中设置最大递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！