提振精神，递归和堆栈溢出 [英] boost spirit, recursion and stack overflow
本文介绍了提振精神，递归和堆栈溢出的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
为什么在运行时以下code崩溃（它会给出一个堆栈溢出错误）？
Why does the following code crash in run-time (it'll give a stack overflow error)?
#include <boost/any.hpp>
#include <boost/filesystem.hpp>
#include <boost/filesystem/fstream.hpp>
#include <boost/fusion/include/define_struct.hpp>
#include <boost/fusion/adapted.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/variant.hpp>
#include <iostream>
#include <string>
#include <vector>
namespace qi = boost::spirit::qi;
// Helper structs
// types
enum class types { void_t, int_t, double_t, bool_t, string_t };
struct types_ : qi::symbols<char, types>
{
types_()
{
add
("void" , types::void_t)
("int" , types::int_t)
("double" , types::double_t)
("bool" , types::bool_t)
("string" , types::string_t)
;
}
} type;
inline
std::ostream& operator<<(std::ostream& os, const types& type)
{
switch (type)
{
case types::void_t:
os << "void";
break;
case types::int_t:
os << "int";
break;
case types::double_t:
os << "double";
break;
case types::bool_t:
os << "bool";
break;
case types::string_t:
os << "string";
break;
}
return os;
}
// assignment_operators
enum class assignment_operators { basic, addition, subtraction, multiplication, division, modulo, bitwise_and, bitwise_or, bitwise_xor, bitwise_left_shift, bitwise_right_shift };
struct assignment_operators_ : boost::spirit::qi::symbols<char, assignment_operators>
{
assignment_operators_()
{
add
("=" , assignment_operators::basic)
("+=" , assignment_operators::addition)
("-=" , assignment_operators::subtraction)
("*=" , assignment_operators::multiplication)
("/=" , assignment_operators::division)
("%=" , assignment_operators::modulo)
("&=" , assignment_operators::bitwise_and)
("|=" , assignment_operators::bitwise_or)
("^=" , assignment_operators::bitwise_xor)
("<<=" , assignment_operators::bitwise_left_shift)
(">>=" , assignment_operators::bitwise_right_shift)
;
}
} assignment_operator;
inline
std::ostream& operator<<(std::ostream& os, const assignment_operators& assignment_operator)
{
switch (assignment_operator)
{
case assignment_operators::basic:
os << "=";
break;
case assignment_operators::addition:
os << "+=";
break;
case assignment_operators::subtraction:
os << "-=";
break;
case assignment_operators::multiplication:
os << "*=";
break;
case assignment_operators::division:
os << "/=";
break;
case assignment_operators::modulo:
os << "%=";
break;
case assignment_operators::bitwise_and:
os << "&=";
break;
case assignment_operators::bitwise_or:
os << "|=";
break;
case assignment_operators::bitwise_xor:
os << "^=";
break;
case assignment_operators::bitwise_left_shift:
os << "<<=";
break;
case assignment_operators::bitwise_right_shift:
os << ">>=";
break;
}
return os;
}
// relational_operators
enum class relational_operators { equal_to, not_equal_to, greater_than, less_than, greater_than_or_equal_to, less_than_or_equal_to };
struct relational_operators_ : boost::spirit::qi::symbols<char, relational_operators>
{
relational_operators_()
{
add
("==" , relational_operators::equal_to)
("!=" , relational_operators::not_equal_to)
(">" , relational_operators::greater_than)
("<" , relational_operators::less_than)
(">=" , relational_operators::greater_than_or_equal_to)
("<=" , relational_operators::less_than_or_equal_to)
;
}
} relational_operator;
inline
std::ostream& operator<<(std::ostream& os, const relational_operators& relational_operator)
{
switch (relational_operator)
{
case relational_operators::equal_to:
os << "==";
break;
case relational_operators::not_equal_to:
os << "!=";
break;
case relational_operators::greater_than:
os << ">";
break;
case relational_operators::less_than:
os << "<";
break;
case relational_operators::greater_than_or_equal_to:
os << ">=";
break;
case relational_operators::less_than_or_equal_to:
os << "<=";
break;
}
return os;
}
// parameter
BOOST_FUSION_DEFINE_STRUCT(
(), parameter,
(types, type)
(std::string, name)
)
// function_call
BOOST_FUSION_DEFINE_STRUCT(
(), function_call,
(std::string, name)
(std::vector<boost::any>, actual_parameters)
)
// variable_definition
BOOST_FUSION_DEFINE_STRUCT(
(), variable_definition,
(std::string, name)
(boost::any, initializer)
)
// variables_definitions
BOOST_FUSION_DEFINE_STRUCT(
(), variables_definitions,
(types, type)
(std::vector<::variable_definition>, variables)
)
// return_expression
BOOST_FUSION_DEFINE_STRUCT(
(), return_statement,
(boost::any, value)
)
// assignment_expression
BOOST_FUSION_DEFINE_STRUCT(
(), assignment_expression,
(std::string, name)
(assignment_operators, op)
(boost::any, value)
)
// relational_expression
BOOST_FUSION_DEFINE_STRUCT(
(), relational_expression,
(boost::any, left)
(relational_operators, op)
(boost::any, right)
)
// function
typedef boost::any expressions_types;
BOOST_FUSION_DEFINE_STRUCT(
(), function,
(types, ret_type)
(std::string, name)
(std::vector<parameter>, parameters)
(std::vector<expressions_types>, expressions)
)
// preprocessor_directive
BOOST_FUSION_DEFINE_STRUCT(
(), include_preprocessor_directive,
(std::string, file)
)
BOOST_FUSION_DEFINE_STRUCT(
(), define_preprocessor_directive,
(std::string, name)
(boost::any, value)
)
BOOST_FUSION_DEFINE_STRUCT(
(), property_preprocessor_directive,
(std::string, name)
(boost::any, value)
)
typedef boost::variant<::include_preprocessor_directive, ::define_preprocessor_directive, ::property_preprocessor_directive> preprocessor_directives_t;
// mql source
typedef boost::variant<::function, preprocessor_directives_t, ::variables_definitions> mql_source_elements_types;
BOOST_FUSION_DEFINE_STRUCT(
(), mql_source,
(std::vector<mql_source_elements_types>, mql_source_elements)
)
template <typename Iterator, typename Skipper>
struct mql_parser : qi::grammar<Iterator, mql_source(), Skipper>
{
mql_parser() : mql_parser::base_type(start_)
{
identifier_ %= qi::alpha >> *qi::alnum; // foo, bar, some1var
literal_ %= qi::int_ // 1
| qi::double_ // 1.5
| qi::bool_ // true
| ('\'' >> qi::char_ >> '\'') // 's'
| qi::as_string[qi::lexeme['"' >> +(qi::char_ - '"') >> '"']]; // "str"
relational_expression_ %= expression_ >> relational_operator >> expression_; // i == 0
assignment_expression_ %= identifier_ >> assignment_operator >> expression_; // i = 1
expression_ %= relational_expression_ | identifier_ | function_call_ | literal_ | ('(' >> expression_ >> ')');
function_call_ %= identifier_ >> '(' >> (expression_ % ',') >> ')';
variable_definition_ %= identifier_ >> -('=' >> expression_); // int i = 0
variables_definitions_ %= type >> (variable_definition_ % ','); // int i = 0, j = 1
return_statement_ %= "return" >> -(expression_);
param_ %= type >> -identifier_;
function_definition_ %= type >> identifier_ >> '(' >> (param_ % ',') >> ')' >> '{' >> (expression_ % ';') >> ';' >> '}'; // void foo(int bar, double) { foo(); int i = 0; }
include_preprocessor_directive_ %= '#' >> qi::lit("include") >> qi::lexeme[+qi::graph]; // #include <WinUser32.mqh>
define_preprocessor_directive_ %= '#' >> qi::lit("define") >> identifier_ >> literal_; // #define FOO 0
property_preprocessor_directive_ %= '#' >> qi::lit("property") >> identifier_ >> -literal_; // #property stacksize 1024
preprocessor_directive_ %= include_preprocessor_directive_ | define_preprocessor_directive_ | property_preprocessor_directive_; // #include <WinUser32.mqh>
start_ %= qi::eps >> +(function_definition_ | preprocessor_directive_ | (variables_definitions_ >> ';')); // void foo(int bar, double) { foo(); } void bar(int baz, double) { foo(); }
}
qi::rule<Iterator, std::string() > identifier_;
qi::rule<Iterator, parameter() , Skipper> param_;
qi::rule<Iterator, function_call() , Skipper> function_call_;
qi::rule<Iterator, boost::any() , Skipper> literal_;
qi::rule<Iterator, variable_definition() , Skipper> variable_definition_;
qi::rule<Iterator, variables_definitions() , Skipper> variables_definitions_;
qi::rule<Iterator, return_statement() , Skipper> return_statement_;
qi::rule<Iterator, assignment_expression() , Skipper> assignment_expression_;
qi::rule<Iterator, relational_expression() , Skipper> relational_expression_;
qi::rule<Iterator, expressions_types() , Skipper> expression_;
qi::rule<Iterator, function() , Skipper> function_definition_;
qi::rule<Iterator, include_preprocessor_directive() , Skipper> include_preprocessor_directive_;
qi::rule<Iterator, define_preprocessor_directive() , Skipper> define_preprocessor_directive_;
qi::rule<Iterator, property_preprocessor_directive() , Skipper> property_preprocessor_directive_;
qi::rule<Iterator, preprocessor_directives_t() , Skipper> preprocessor_directive_;
qi::rule<Iterator, mql_source() , Skipper> start_;
};
std::string get_file_content(const boost::filesystem::path& file_path)
{
std::string file_content;
boost::filesystem::ifstream f(file_path);
if (f)
{
file_content.append(
(std::istreambuf_iterator<char>(f))
, std::istreambuf_iterator<char>()
);
}
return file_content;
}
int main()
{
const std::string& input_data = get_file_content("input.txt");
mql_source mql_src;
auto itr = input_data.begin();
auto end = input_data.end();
qi::rule<decltype(itr)> skipper =
qi::ascii::space
| ("//" >> *(qi::char_ - qi::eol) >> qi::eol | qi::blank)
| ("/*" >> *(qi::char_ - "*/") >> "*/");
mql_parser<decltype(itr), decltype(skipper)> g;
bool res = qi::phrase_parse(
itr
, end
, g
, skipper
, mql_src
);
if (res && itr == end)
{
std::cout << "Parsing succeeded \n";
}
else
{
std::cout << "Parsing failed \n";
}
}
输入数据：
#include <WinUser32.mqh>
void foo(int bar, double baz) { int lol = 0; }
任何想法应该做些什么来解决？
Any ideas what should be done to fix it?
推荐答案
您所看到的左递归。
左递归不与PEG语法混合。看看这两个规则：
Left recursion doesn't mix with PEG grammars. Look at these two rules:
expression_ %= relational_expression_ | identifier_ | function_call_ | literal_ | ('(' >> expression_ >> ')');
relational_expression_ %= expression_ >> relational_operator >> expression_; // i == 0
展开relational_ex pression：
Expand relational_expression:
expression_ %= expression_ >> ...
你能发现问题吗？精神贪婪地匹配左到右。所以，你告诉它，是否输入可能是一个前pression_，首先检查是否......它可能是一个前pression_：）
Can you spot the problem? Spirit greedily matches left-to-right. So you told it, to check whether input might be an expression_, first check whether... it might be an expression_ :)
因此，通过使左节点更严格修复
So, fix it by making the left node more restrictive:
simple_expr_ %= identifier_ | function_call_ | literal_ | ('(' >> expression_ >> ')');
expression_ %= relational_expression_ | simple_expr_;
relational_expression_ %= simple_expr_ >> relational_operator >> expression_; // i == 0
当然，你在这里需要额外的规则：
Of course, you need the extra rule here:
齐::规则simple_expr _;
qi::rule simple_expr_;
有在语法$ P $等问题，从分析pventing它，所以你会想看看BOOST_SPIRIT_DEBUG，但我没有时间来添加流媒体运营商的AST类型
There are other issues in the grammar preventing it from parsing, so you will want to look at BOOST_SPIRIT_DEBUG but I don't have time to add the streaming operators for your AST types
这篇关于提振精神，递归和堆栈溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
