4

我正在尝试将“1.0 + 2.0 + 3.0 + ...”形式的表达式解析为 AST。我有以下用于二进制操作的 AST 节点（最后是完整的最小代码示例）：

struct binop_t
{
    expression_t lhs, rhs;
};

我想使用“BOOST_FUSION_ADAPT_STRUCT”宏来允许这个结构由 boost:spirit::qi::rule 合成：

BOOST_FUSION_ADAPT_STRUCT
(
    client::ast::binop_t,
    (client::ast::expression_t, lhs)
    (client::ast::expression_t, rhs)
)

换句话说，二元运算 AST 节点 (binop_t) 需要两个操作数 - 应操作的左侧 (lhs) 和右侧 (rhs) 表达式。我可以使用以下 qi::grammar 将“1.0+ ( 2.0+(3.0+4.0))”形式的表达式解析到这个 AST 节点中：

qi::rule<Iterator, ast::literal_t(), ascii::space_type> literal;
qi::rule<Iterator, ast::binop_t(), ascii::space_type> binop;
qi::rule<Iterator, ast::expression_t(), ascii::space_type> primary_expr;
qi::rule<Iterator, ast::expression_t(), ascii::space_type> expr;

expr = binop.alias();

binop = primary_expr > qi::lit('+') > primary_expr;

primary_expr = (qi::lit('(') > expr > qi::lit(')')) 
             | literal
             ;

literal = qi::double_;

但是，我很难理解如何修改此语法，以便它可以在不使用括号的情况下解析此类表达式（例如“1+2+3+4+...”）。

我查看了“calc4.cpp”Boost Spirit 示例，并注意到它仅使用以下 AST 节点进行二进制操作（例如添加）：

struct operation
{
    optoken operator_;
    operand operand_;
};

这个例子和我想要做的不同之处在于，这个例子纯粹根据一元操作列表定义了用于合成二元操作节点的语法。一元操作列表被合成为一个称为“程序”的 AST 节点：

struct program
{
    operand first;
    std::list<operation> rest;
};

在示例中使用以下语法合成了整个内容：

    qi::rule<Iterator, ast::program(), ascii::space_type> expression;
    qi::rule<Iterator, ast::program(), ascii::space_type> term;
    qi::rule<Iterator, ast::operand(), ascii::space_type> factor;

        expression =
            term
            >> *(   (char_('+') >> term)
                |   (char_('-') >> term)
                )
            ;

        term =
            factor
            >> *(   (char_('*') >> factor)
                |   (char_('/') >> factor)
                )
            ;

        factor =
                uint_
            |   '(' >> expression >> ')'
            |   (char_('-') >> factor)
            |   (char_('+') >> factor)
            ;

在这个语法中，“表达式”规则产生一个“程序”，它是一个操作列表。我们从“表达式”的语法规则中可以看出，它在语法中使用了 Kleene 星：

*((char_('+') >> term)

这就是语法能够解析关联二元运算链的方式，例如“1+2+3+4+...”。这个文法的属性是list，它与“程序”AST节点的定义相匹配。计算器“eval”函数然后简单地迭代“程序”中的操作列表，将操作从左到右应用于操作数：

    int operator()(program const& x) const
    {
        int state = boost::apply_visitor(*this, x.first);
        BOOST_FOREACH(operation const& oper, x.rest)
        {
            state = (*this)(oper, state);
        }
        return state;
    }

我还查看了“mini-c”Boost Spirit 示例，它具有非常相似的 AST 设计，其中没有二元运算符 AST 节点（只有一个接受单个操作数的单个“运算符”节点）。

以下是迄今为止我实现的程序的完整、最小的代码示例。回顾一下，我的问题是：我如何修改这个程序，以便它能够从“1+2+3+4+...”这样的表达式合成一棵 binop_t AST 节点树，而无需在输入文本：

#include <boost/variant.hpp>
#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix_core.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <iostream>
#include <string>
#include <exception>

using boost::variant;
using boost::recursive_wrapper;

namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
namespace phoenix = boost::phoenix;

namespace client { namespace ast {

    struct literal_t;
    struct binop_t;

    typedef variant< recursive_wrapper<literal_t>,
                     recursive_wrapper<binop_t>
                   > expression_t;

    struct literal_t
    {
        double value;       
    };

    struct binop_t
    {
        expression_t lhs, rhs;
    };
}} // ns

BOOST_FUSION_ADAPT_STRUCT
(
    client::ast::literal_t,
    (double, value)
)

BOOST_FUSION_ADAPT_STRUCT
(
    client::ast::binop_t,
    (client::ast::expression_t, lhs)
    (client::ast::expression_t, rhs)
)

namespace client {
    template <typename Iterator>
    struct grammar_t : qi::grammar<Iterator, ast::expression_t(), ascii::space_type>
    {
        qi::rule<Iterator, ast::literal_t(), ascii::space_type> literal;
        qi::rule<Iterator, ast::binop_t(), ascii::space_type> binop;
        qi::rule<Iterator, ast::expression_t(), ascii::space_type> primary_expr;
        qi::rule<Iterator, ast::expression_t(), ascii::space_type> expr;

        grammar_t() : grammar_t::base_type(expr)
        {
            expr = binop.alias();

            binop = primary_expr > qi::lit('+') > primary_expr;

            primary_expr = (qi::lit('(') > expr > qi::lit(')')) 
                         | literal;

            literal = qi::double_;

            expr.name("expr");
            binop.name("binop");
            literal.name("literal");
            qi::debug(expr);
            qi::debug(binop);
            qi::debug(literal);
        }
    };
} // ns

int main()
{
    try
    {
        string input = "0.1 + 1.2 ";
        std::string::const_iterator begin = input.begin();
        std::string::const_iterator end = input.end();  

        typedef std::string::const_iterator iterator_type;
        client::grammar_t<iterator_type> g;

        client::ast::expression_t ast;

        bool status;    
        status = qi::phrase_parse(begin, end, g, ascii::space, ast);
        EXPECT_TRUE(status);
        EXPECT_TRUE(begin == end);
    } catch (std::exception& e)
    {
        cout << e.what() << endl;
    }
}
4

1 回答 1

3

Freenode 上##spirit IRC 频道上的 VeXocide 解决了这个问题 ( http://codepad.org/wufmFufE )。答案是修改语法如下：

    expr = binop.alias();

    binop = primary_expr >> qi::lit('+') >> (binop | primary_expr);

    primary_expr = (qi::lit('(') >> expr >> qi::lit(')'))
                 | literal;            

    literal = qi::double_;

这个语法创建了一个正确的递归，能够合成我正在寻找的解析树。

给遇到相同问题的人的提示：如果没有 Spirit 调试语句，如果您为 Boost Spirit 提供左递归语法，则会由于堆栈溢出而导致 Seg Fault。如果您打开调试语句，它将打印出“无限”量的文本，告诉您解析器中出现了问题。

于 2013-05-22T14:14:07.580 回答