提升::精神表达解析器

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"它告诉我parse failed.然后我尝试将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>- 这真的没有任何乐趣,特别是在凤凰语lambda语义行为中.(我将在下面展示,看起来像什么).

与此同时,我认为你应该阅读圣经文献

• 这里是古老的精神博士(消除左递归); 虽然语法不再适用,但Spirit仍会生成LL递归下降解析器,因此左递归背后的概念仍然适用.下面的代码显示了这适用于Spirit Qi
• 这里: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>

代码的链接在这里:

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

第1步:减少语义操作

首先,我将逐个删除每个运算符的替代解析表达式; 这会导致过度回溯¹.此外,正如您所知,它使语法难以维护.所以,这是一个更简单的变体,它使用一个函数进行语义操作:

_{¹检查使用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惰性占位符用作累积binops的伪局部变量.在整个规则中,您必须使用qi::locals<ast::expression>这种方法.(这是你的问题_r1).
• 现在有明确的期望点,使语法更加健壮
• 该expr规则不再需要有一个自动规则(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函数的方式并不那么有趣!