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新手，我不太能理解boost::phoenix和boost::spirit是如何交互的。

如何解决？

- Lanbo

---

还有一个有趣的链接：http://www.gamedev.net/topic/416784-recursive-descent-parsing-handling-left-associativity/ - sehe

Answer 1

我不太清楚你想实现什么，最重要的是，你不担心操作符的结合律吗？我将展示一些基于使用右递归的简单答案 - 这会导致解析左结合运算符。

对于你的可见问题的直接答案是在fusion::vector2<char, ast::expression>中反复搬移 - 这并不是什么乐趣，尤其是在Phoenix lambda语义动作中。 (下面我会展示这是什么样子的)。

同时，我认为你应该阅读Spirit文档

• 这里是旧版Spirit文档中的内容(消除左递归)。虽然语法不再适用，但Spirit仍然生成LL递归下降解析器，因此左递归背后的概念仍然适用。下面的代码展示了这种方法应用于Spirit Qi。
• 这里: Qi示例包含三个calculator示例，这应该能让你知道为什么操作符结合律很重要，以及如何表达捕获二元运算符结合性的语法。显然，它还展示了如何支持括号表达式以覆盖默认的评估顺序。

代码：

我有三个版本的代码可以解析像这样的输入：

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

使用BOOST_SPIRIT_DEBUG将其分组为类似于 ast::expression 的语法树：

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

这里是代码链接：

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

步骤一：减少语义动作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: 删除冗余规则，使用_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惰性占位符作为一个伪本地变量来累积二进制操作。在规则之间，你需要使用qi::locals<ast::expression>来实现这样的方法。(这是关于_r1的问题)
• 现在有明确的期望点，使语法更加健壮。
• expr规则不再需要是auto-rule (expr = 而不是 expr %=)

步骤 0: 直接处理融合类型

最后，为了好玩和血腥，让我展示一下如何处理你提出的代码，以及 _1、_2 等的移位绑定：

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 函数并不是一件有趣的事情！

- sehe