c++ - 递归 Spirit.Qi 语法的段错误

Question

我正在尝试为一种只包含数字和数学表达式的非常简单的语言创建一个非常简单的解析器。最终我计划扩展它，但直到我可以使这些基本版本正常工作。

我已经成功解析:

1
425
1 + 1
1 - 1
1 * 1
1 / 1

没问题。但是我想让它递归，比方说，像这样解析输入:

1 + 2 - 3

我开始出现段错误。我已经对递归语法和段错误进行了一些谷歌搜索，但我似乎无法将我发现的任何东西应用到这个语法上来使其工作。这要么是因为它们不适合我的情况，要么是我未能正确理解我的气语法发生了什么。

我的语法由以下结构组成(包括融合改编):

namespace fun_lang {
    namespace qi = boost::spirit::qi;
    namespace ascii = boost::spirit::ascii;
    namespace phoenix = boost::phoenix;
    namespace fusion = boost::fusion;

    struct number_node {
        long value;
    };

    struct operation_node;

    typedef boost::variant<
        boost::recursive_wrapper<operation_node>,
        number_node
    > node;

    struct operation_node {
        node left, right;
        char op;
    };

    struct program {
        std::vector<node> nodes;
    };
}

BOOST_FUSION_ADAPT_STRUCT(fun_lang::program, (std::vector<fun_lang::node>, nodes));
BOOST_FUSION_ADAPT_STRUCT(fun_lang::number_node, (long, value));
BOOST_FUSION_ADAPT_STRUCT(fun_lang::operation_node, (fun_lang::node, left) (char, op) (fun_lang::node, right));

namespace fun_lang {
    template <typename Iterator, typename Skipper>
    struct fun_grammar : qi::grammar<Iterator, program(), Skipper> {
        fun_grammar() : fun_grammar::base_type(start) {
            using ascii::char_;
            using qi::ulong_;
            using qi::_val;
            using qi::_1;

            using phoenix::push_back;
            using phoenix::at_c;

            expression = (integer | operation)[_val = _1];

            oper = (char_('+') | char_('-') | char_('*') | char_('/'))[_val = _1];
            integer = ulong_[at_c<0>(_val) = _1];

            operation = expression[at_c<0>(_val) = _1] >> oper[at_c<1>(_val) = _1] >> expression[at_c<2>(_val) = _1];

            start = *expression[push_back(at_c<0>(_val), _1)];
        }

        qi::rule<Iterator, program(), Skipper> start;
        qi::rule<Iterator, number_node(), Skipper> integer;
        qi::rule<Iterator, char(), Skipper> oper;
        qi::rule<Iterator, node(), Skipper> expression;
        qi::rule<Iterator, operation_node(), Skipper> operation;
    };
}

一些规则结构基于我为另一种语言编写的 yacc 语法，我将其用作构建这些规则的方式的引用。我不确定是什么导致了段错误，但我知道在运行它时我收到了什么。我试过简化规则，删除一些中间规则，并测试非递归方法。任何非递归的东西似乎都有效，但我见过很多使用递归规则的 Spirit 成功的例子，所以我觉得我不太理解如何表达这些规则。

编辑

为了帮助解决问题，您可以在 ideone 上找到几乎完全相同的拷贝。 . ideone 版本和我在本地拥有的版本之间的唯一区别是，它不是读取文件，而是直接从标准输入中提取文件。

Answer 1

堆栈溢出有两个来源(以段错误结束)。一个是 operation_node 的构造函数和 node . boost::variant ，当默认构造时，使用其第一个模板参数的默认构造对象进行初始化。这是 boost::recursive_wrapper<operation_node> , 它构造了一个 operation_node , 它构造了两个 node s，构造一个boost::recursive_wrapper<operation_node> ，这一直持续到堆栈耗尽。

通常将精神语法中的变体赋予 nil 类型，如 struct nil { };作为防止这种情况发生的第一个论点，并有办法识别未初始化的变体，所以

struct nil { };

typedef boost::variant<
    nil,
    boost::recursive_wrapper<operation_node>,
    number_node
> node;

会解决这个问题。如果你不想使用 nil类型，

typedef boost::variant<
    number_node,
    boost::recursive_wrapper<operation_node>
> node;

也适用于您的情况，因为 number_node可以毫无问题地构建。

另一个堆栈溢出是因为 Boost.Spirit 生成 LL(inf) 解析器(与生成 LALR(1) 解析器的 yacc 相反)，这意味着你得到的是一个递归下降解析器。规则

expression = (integer | operation)[_val = _1];
operation = expression[at_c<0>(_val) = _1] >> oper[at_c<1>(_val) = _1] >> expression[at_c<2>(_val) = _1];

生成一个从operation 派生的解析器进入expression然后回到operation不消耗任何输入。这会递归直到堆栈溢出，这就是您遇到其他段错误的地方。

如果重新制定规则 operation作为

operation = integer[at_c<0>(_val) = _1] >> oper[at_c<1>(_val) = _1] >> expression[at_c<2>(_val) = _1];

这个问题消失了。此外，您必须重写 expression规则为

expression = (operation | integer)[_val = _1];

为了使匹配按照我的预期进行，否则 integer部分将在 operation 之前成功匹配有机会被找到，解析器不会回溯，因为它有一个成功的部分匹配。

另请注意，Spirit 解析器是属性化的；您使用的解析器操作在很大程度上是不必要的。可以像这样重写大部分语法:

expression = operation | integer;

oper = char_("-+*/");
integer = ulong_;

operation = integer >> oper >> expression;