c++ - Boost::Spirit 表达式解析器

Question

我的 boost::spirit 解析器有另一个问题。

template<typename Iterator>
struct expression: qi::grammar<Iterator, ast::expression(), ascii::space_type> {
    expression() :
        expression::base_type(expr) {
        number %= lexeme[double_];
        varname %= lexeme[alpha >> *(alnum | '_')];

        binop = (expr >> '+' >> expr)[_val = construct<ast::binary_op<ast::add>>(_1,_2)]
              | (expr >> '-' >> expr)[_val = construct<ast::binary_op<ast::sub>>(_1,_2)]
              | (expr >> '*' >> expr)[_val = construct<ast::binary_op<ast::mul>>(_1,_2)]
              | (expr >> '/' >> expr)[_val = construct<ast::binary_op<ast::div>>(_1,_2)] ;

        expr %= number | varname | binop;
    }

    qi::rule<Iterator, ast::expression(), ascii::space_type> expr;
    qi::rule<Iterator, ast::expression(), ascii::space_type> binop;
    qi::rule<Iterator, std::string(), ascii::space_type> varname;
    qi::rule<Iterator, double(), ascii::space_type> number;
};

这是我的解析器。它解析 "3.1415" 和 "var" 很好，但是当我尝试解析 "1+2" 时它告诉我 解析失败。然后我尝试将 binop 规则更改为

    binop = expr >>
           (('+' >> expr)[_val = construct<ast::binary_op<ast::add>>(_1, _2)]
          | ('-' >> expr)[_val = construct<ast::binary_op<ast::sub>>(_1, _2)]
          | ('*' >> expr)[_val = construct<ast::binary_op<ast::mul>>(_1, _2)]
          | ('/' >> expr)[_val = construct<ast::binary_op<ast::div>>(_1, _2)]);

但是现在当然不能构建AST了，因为_1和_2的设置不同。我只看到像 _r1 这样的东西被提到，但是作为一个新手我不太能理解 boost::phoenix 和 boost::spirit 互动。

如何解决？

Answer 1

我不太清楚您要实现的目标。最重要的是，您不担心运算符关联性吗？我将仅显示基于使用右递归的简单答案 - 这会导致左关联运算符被解析。

您的可见问题的直接答案是兼顾 fusion::vector2<char, ast::expression> - 这真的没什么好玩的，尤其是在 Phoenix lambda 语义 Action 中。 (我将在下面展示它的样子)。

与此同时，我认为您应该阅读 Spirit 文档

• here在旧的 Spirit 文档中(消除左递归)；虽然语法不再适用，但 Spirit 仍会生成 LL 递归下降解析器，因此左递归背后的概念仍然适用。下面的代码显示了这适用于灵气
• here : Qi 示例包含三个 calculator示例，这应该会提示您为什么运算符结合性很重要，以及您将如何表达捕获二元运算符结合性的语法。显然，它还展示了如何支持带括号的表达式 来覆盖默认的求值顺序。

代码:

我有三个可用的代码版本，解析输入如下:

std::string input("1/2+3-4*5");

进入ast::expression像这样分组(使用 BOOST_SPIRIT_DEBUG):

<expr>
  ....
  <success></success>
  <attributes>[[1, [2, [3, [4, 5]]]]]</attributes>
</expr>

The links to the code are here:

• step_#1_reduce_semantic_actions.cpp
• step_#2_drop_rule.cpp
• step_#0_vector2.cpp

第 1 步:Reduce semantic actions

首先，我要摆脱每个运算符的替代解析表达式；这会导致过多的回溯¹。此外，正如您所发现的，它使语法难以维护。因此，这是一个更简单的变体，它使用一个函数来执行语义操作:

<子>¹使用 BOOST_SPIRIT_DEBUG 检查!

static ast::expression make_binop(char discriminant, 
     const ast::expression& left, const ast::expression& right)
{
    switch(discriminant)
    {
        case '+': return ast::binary_op<ast::add>(left, right);
        case '-': return ast::binary_op<ast::sub>(left, right);
        case '/': return ast::binary_op<ast::div>(left, right);
        case '*': return ast::binary_op<ast::mul>(left, right);
    }
    throw std::runtime_error("unreachable in make_binop");
}

// rules:
number %= lexeme[double_];
varname %= lexeme[alpha >> *(alnum | '_')];

simple = varname | number;
binop = (simple >> char_("-+*/") >> expr) 
    [ _val = phx::bind(make_binop, qi::_2, qi::_1, qi::_3) ]; 

expr = binop | simple;

第 2 步:Remove redundant rules, use _val

如您所见，这有可能降低复杂性。现在只是一小步，删除了 binop 中间体(它已经变得相当多余):

number %= lexeme[double_];
varname %= lexeme[alpha >> *(alnum | '_')];

simple = varname | number;
expr = simple [ _val = _1 ] 
    > *(char_("-+*/") > expr) 
            [ _val = phx::bind(make_binop, qi::_1, _val, qi::_2) ]
    > eoi;

如你所见，

• 在 expr 内规则，_val惰性占位符用作累积 binop 的伪局部变量。跨规则，你必须使用 qi::locals<ast::expression>对于这样的方法。 (这是你关于 _r1 的问题)。
• 现在有明确的期望点，使语法更健壮
• expr规则不再需要是自动规则( expr = 而不是 expr %= )

第 0 步:Wrestle fusion types directly

最后，为了好玩和血腥，让我展示一下您如何处理建议的代码，以及 _1、_2 等的移动绑定(bind):

static ast::expression make_binop(
        const ast::expression& left, 
        const boost::fusion::vector2<char, ast::expression>& op_right)
{
    switch(boost::fusion::get<0>(op_right))
    {
        case '+': return ast::binary_op<ast::add>(left, boost::fusion::get<1>(op_right));
        case '-': return ast::binary_op<ast::sub>(left, boost::fusion::get<1>(op_right));
        case '/': return ast::binary_op<ast::div>(left, boost::fusion::get<1>(op_right));
        case '*': return ast::binary_op<ast::mul>(left, boost::fusion::get<1>(op_right));
    }
    throw std::runtime_error("unreachable in make_op");
}

// rules:
expression::base_type(expr) {
number %= lexeme[double_];
varname %= lexeme[alpha >> *(alnum | '_')];

simple = varname | number;
binop %= (simple >> (char_("-+*/") > expr)) 
    [ _val = phx::bind(make_binop, qi::_1, qi::_2) ]; // note _2!!!

expr %= binop | simple;

如您所见，编写 make_binop 并没有那么有趣那样运作!