递归 Spirit.Qi 语法的分段错误

Question

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

我已成功解析：

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

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，它构造一个boost::recursive_wrapper<operation_node>，如此往复直到堆栈耗尽。

通常给精神语法中的变体一个像 struct nil { }; 这样的 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;

递归 Spirit.Qi 语法的分段错误

Segmentation fault with recursive Spirit.Qi grammar

c++

boost-spirit-qi