Spirit qi解析为抽象语法树以实现嵌套函数 [英] Spirit qi parsing to an Abstract Syntax Tree for nested functions

问题描述

我正在尝试使用Boost的Spirit qi解析器创建一个解析器.它正在解析包含三种类型的值的字符串.常数，变量或函数.这些功能可以相互嵌套.测试字符串是f(a, b) = f(g(z, x), g(x, h(x)), c)，其中a-e是常量，f-r是函数，而s-z是变量.我成功创建了可以正确解析表达式的规则.当我更改将规则解析为

I am trying to create a parser using boost's spirit qi parser. It is parsing a string that contains three types of values. A constant, a variable, or a function. The functions can be nested inside of each other. The test string is f(a, b) = f(g(z, x), g(x, h(x)), c), where a-e are constants, f-r are functions, and s-z are variables. I successfully created a rule that can correctly parse the expression. The trouble arose when I changed the function parsing the rule into a grammar. There were several errors that I was able to fix. I almost got the grammar to parse the expression and turn it into an abstract syntax tree I created. However I got this error about a file contained in the boost library and I could not figure out where it is coming from because I don't understand the compiler message. I was following the example put up on the website for putting data from a parser to a struct using the employee example: http://www.boost.org/doc/libs/1_41_0/libs/spirit/example/qi/employee.cpp

main.cpp

#include "Parser.h"
#include "Term.h"

#include <boost/spirit/include/qi.hpp>
#include <string>
#include <iostream>
#include <list>

using std::string;
using std::cout;
using std::endl;

int main()
{
    cout << "Unification Algorithm" << endl << endl;

    string phrase = "f(a, b) = f(g(z, x), g(x, h(x)), c)";
    string::const_iterator itr = phrase.begin();
    string::const_iterator last = phrase.end();

    cout << phrase << endl;

    // Parser grammar
    Parser<string::const_iterator> g;

    // Output data
    Expression expression;

    if (phrase_parse(itr, last, g, boost::spirit::ascii::space, expression))
    {
        cout << "Expression parsed." << endl;
    }
    else
    {
        cout << "Could not parse expression." << endl;
    }
}

Parser.h

#ifndef _Parser_h_
#define _Parser_h_

#include "Term.h"

#include <boost/spirit/include/qi.hpp>
#include <vector>

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

template <typename Iterator>
struct Parser : qi::grammar<Iterator, Expression(), ascii::space_type>
{
    Parser() : Parser::base_type(expression)
    {
        using qi::char_;

        const_char = char_("a-eA-E");
        fn_char = char_("f-rF-R");
        var_char = char_("s-zS-Z");

        basic_fn = fn_char >> char_('(') >> (const_char | var_char) % char_(',') >> char_(')');
        first_fn_wrapper = fn_char >> char_('(') >> (basic_fn | const_char | var_char) % char_(',') >> char_(')');
        nested_fn = fn_char >> char_('(') >> (first_fn_wrapper | const_char | var_char) % char_(',') >> char_(')');

        expression = nested_fn >> char_("=") >> nested_fn;
    }
    // Constant character a - e
    qi::rule<Iterator, T_Cons, ascii::space_type> const_char;
    // Function character f - r
    qi::rule<Iterator, char(), ascii::space_type> fn_char;
    // Variable character s - z
    qi::rule<Iterator, T_Var, ascii::space_type> var_char;
    // Allows for basic function parsing eg. f(x, y, z)
    qi::rule<Iterator, T_Fn, ascii::space_type> basic_fn;
    // Allows for single nested functions eg. f(g(x), y, z)
    qi::rule<Iterator, T_Fn, ascii::space_type> first_fn_wrapper;
    // Allows for fully nested functions eg. f(g(x, h(y)), z) and so on
    qi::rule<Iterator, T_Fn, ascii::space_type> nested_fn;
    // Full rule for a nested function expression
    qi::rule<Iterator, Expression, ascii::space_type> expression;
};
#endif // _Parser_h_

Term.h

#ifndef _Term_h_
#define _Term_h_

#include <boost/fusion/include/adapt_struct.hpp>
#include <vector>

struct Term
{
    char name;
};

BOOST_FUSION_ADAPT_STRUCT(Term, (char, name))

struct T_Cons : Term
{

};

BOOST_FUSION_ADAPT_STRUCT(T_Cons, (char, name))

struct T_Var : Term
{

};

BOOST_FUSION_ADAPT_STRUCT(T_Var, (char, name))

struct T_Fn : Term
{
    std::vector<Term> * params;

    T_Fn() { params = new std::vector<Term>(); }

    ~T_Fn() { delete params; }
};

BOOST_FUSION_ADAPT_STRUCT(T_Fn, (std::vector<Term>*, params))

struct Expression
{
    Term lh_term;
    Term rh_term;
};

 BOOST_FUSION_ADAPT_STRUCT(Expression, (char, name) (Term, lh_term) (Term, rh_term))

#endif // _Term_h_

我无法链接来自编译器的整个错误消息，因为它非常长，但是这里是最后几条.这些是它给的编译错误:

I cannot link the entire error message from the compiler because it is extremely long, but here are the last few. These are the compile errors that it gave:

boost_1_46_0\boost\mpl\assert.hpp|360|error: no matching function for call to 'assertion_failed(mpl_::failed************ (boost::spirit::qi::grammar<Iterator, T1, T2, T3, T4>::grammar(const boost::spirit::qi::rule<Iterator_, T1_, T2_, T3_, T4_>&, const string&) [with Iterator_ = __gnu_cxx::__normal_iterator<const char*, std::basic_string<char> >; T1_ = Expression; T2_ = boost::proto::exprns_::expr<boost::proto::tag::terminal, boost::proto::argsns_::term<boost::spirit::tag::char_code<boost::spirit::tag::space, boost::spirit::char_encoding::asci|
boost_1_46_0\boost\proto\extends.hpp|540|error: use of deleted function 'boost::proto::exprns_::expr<boost::proto::tag::terminal, boost::proto::argsns_::term<boost::spirit::qi::reference<const boost::spirit::qi::rule<__gnu_cxx::__normal_iterator<const char*, std::basic_string<char> >, Expression(), boost::proto::exprns_::expr<boost::proto::tag::terminal, boost::proto::argsns_::term<boost::spirit::tag::char_code<boost::spirit::tag::space, boost::spirit::char_encoding::ascii> >, 0l>, boost::spirit::unused_type, boost::spirit::unused_type> > >, 0l>:|
boost_1_46_0\boost\proto\detail\expr0.hpp|165|error: no matching function for call to 'boost::spirit::qi::reference<const boost::spirit::qi::rule<__gnu_cxx::__normal_iterator<const char*, std::basic_string<char> >, Expression(), boost::proto::exprns_::expr<boost::proto::tag::terminal, boost::proto::argsns_::term<boost::spirit::tag::char_code<boost::spirit::tag::space, boost::spirit::char_encoding::ascii> >, 0l>, boost::spirit::unused_type, boost::spirit::unused_type> >::reference()'|

推荐答案

更新:显示简化的解析器，并递归ast解析显示的示例表达式

UPDATE Showing a simplified parser with a a recursive ast parsing the sample expression shown

一如既往，断言消息导致了确切的问题:

As always, the assertion message leads to exactly the problem:

        // If you see the assertion below failing then the start rule
        // passed to the constructor of the grammar is not compatible with
        // the grammar (i.e. it uses different template parameters).
        BOOST_SPIRIT_ASSERT_MSG(
            (is_same<start_type, rule<Iterator_, T1_, T2_, T3_, T4_> >::value)
          , incompatible_start_rule, (rule<Iterator_, T1_, T2_, T3_, T4_>));

所以它告诉您应该将语法与开始规则相匹配:您已经拥有

So it tells you you should match the grammar with the start rule: you have

struct Parser : qi::grammar<Iterator, Expression(), ascii::space_type>

但是

qi::rule<Iterator, Expression, ascii::space_type> expression;

很显然，您在此处忘记了括号:

Clearly you forgot parentheses there:

qi::rule<Iterator, Expression(), ascii::space_type> expression;

使用通用库的准则:

其中一些规则"通常适用，但否除外. 2与Boost Spirit特别相关:

Guidelines when using generic libraries:

Some of these "rules" are generically applicable, with the exception of no. 2 which is specifically related to Boost Spirit:

宝宝的脚步；从小(空，偶)开始
1. 以AST开头以完全匹配语法
2. 逐步建立，
3. 编译过程中的每一步

1. baby steps; start small (empty, even)
2. start with the AST to match the grammar exactly
3. build gradually,
4. compiling every step along the way

更新

这是一个大大简化的语法.如前所述，在之前的基本精神规则"中，以AST开头以完全匹配语法:

UPDATE

Here's a much simplified grammar. As mentioned, in the "first rules of spirit" just before, start with the AST to match the grammar exactly:

namespace ast {

    namespace tag {
        struct constant;
        struct variable;
        struct function;
    }

    template <typename Tag> struct Identifier { char name; };

    using Constant = Identifier<tag::constant>;
    using Variable = Identifier<tag::variable>;
    using Function = Identifier<tag::function>;

    struct FunctionCall;

    using Expression = boost::make_recursive_variant<
        Constant,
        Variable,
        boost::recursive_wrapper<FunctionCall>
    >::type;

    struct FunctionCall {
        Function function;
        std::vector<Expression> params;
    };

    struct Equation {
        Expression lhs, rhs;
    };
}

当然，这可能会简单得多，因为所有标识符都只是char，您可以动态进行切换(

Of course this could be much simpler still since all identifiers are just char and you could do the switching dynamically (impression).

现在，语法必须遵循. 1.保持简单 2.仔细设置格式. 3.直接匹配ast， 4..添加调试宏:

Now, the grammar will have to follow. 1. Keep it simple 2. Format carefully 3. Match the ast directly, 4. add debug macros:

template <typename It, typename Skipper = ascii::space_type>
    struct Parser : qi::grammar<It, ast::Equation(), Skipper>
{
    Parser() : Parser::base_type(equation_)
    {
        using namespace qi;

        constant_ = qi::eps >> char_("a-eA-E");
        function_ = qi::eps >> char_("f-rF-R");
        variable_ = qi::eps >> char_("s-zS-Z");

        function_call = function_ >> '(' >> -(expression_ % ',') >> ')';
        expression_   = constant_ | variable_ | function_call;
        equation_     = expression_ >> '=' >> expression_;

        BOOST_SPIRIT_DEBUG_NODES((constant_)(function_)(variable_)(function_call)(expression_)(equation_))
    }
    qi::rule<It, ast::Constant()> constant_;
    qi::rule<It, ast::Function()> function_;
    qi::rule<It, ast::Variable()> variable_;

    qi::rule<It, ast::FunctionCall(), Skipper> function_call;
    qi::rule<It, ast::Expression(),   Skipper> expression_;
    qi::rule<It, ast::Equation(),     Skipper> equation_;
};

请注意，如何完全不需要注释.另请注意，使用expression_递归如何解决您最大的头痛！

Note how the comments have become completely unneeded. Also note how recursively using expression_ solved your biggest headache!

完整程序

在Coliru上直播

Full Program

Live On Coliru

//#define BOOST_SPIRIT_DEBUG
#include <boost/spirit/include/qi.hpp>

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

namespace ast {

    namespace tag {
        struct constant;
        struct variable;
        struct function;
    }

    template <typename Tag> struct Identifier { char name; };

    using Constant = Identifier<tag::constant>;
    using Variable = Identifier<tag::variable>;
    using Function = Identifier<tag::function>;

    struct FunctionCall;

    using Expression = boost::make_recursive_variant<
        Constant,
        Variable,
        boost::recursive_wrapper<FunctionCall>
    >::type;

    struct FunctionCall {
        Function function;
        std::vector<Expression> params;
    };

    struct Equation {
        Expression lhs, rhs;
    };
}

BOOST_FUSION_ADAPT_STRUCT(ast::Constant, (char, name))
BOOST_FUSION_ADAPT_STRUCT(ast::Variable, (char, name))
BOOST_FUSION_ADAPT_STRUCT(ast::Function, (char, name))
BOOST_FUSION_ADAPT_STRUCT(ast::FunctionCall, (ast::Function, function)(std::vector<ast::Expression>, params))
BOOST_FUSION_ADAPT_STRUCT(ast::Equation, (ast::Expression, lhs)(ast::Expression, rhs))

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

template <typename It, typename Skipper = ascii::space_type>
struct Parser : qi::grammar<It, ast::Equation(), Skipper>
{
    Parser() : Parser::base_type(equation_)
    {
        using namespace qi;

        constant_ = qi::eps >> char_("a-eA-E");
        function_ = qi::eps >> char_("f-rF-R");
        variable_ = qi::eps >> char_("s-zS-Z");

        function_call = function_ >> '(' >> -(expression_ % ',') >> ')';
        expression_   = constant_ | variable_ | function_call;
        equation_     = expression_ >> '=' >> expression_;

        BOOST_SPIRIT_DEBUG_NODES((constant_)(function_)(variable_)(function_call)(expression_)(equation_))
    }
    qi::rule<It, ast::Constant()> constant_;
    qi::rule<It, ast::Function()> function_;
    qi::rule<It, ast::Variable()> variable_;

    qi::rule<It, ast::FunctionCall(), Skipper> function_call;
    qi::rule<It, ast::Expression(),   Skipper> expression_;
    qi::rule<It, ast::Equation(),     Skipper> equation_;
};

int main() {
    std::cout << "Unification Algorithm\n\n";

    std::string const phrase = "f(a, b) = f(g(z, x), g(x, h(x)), c)";
    using It = std::string::const_iterator;
    It itr = phrase.begin(), last = phrase.end();

    std::cout << phrase << std::endl;

    Parser<It> g;
    ast::Equation parsed;

    if (phrase_parse(itr, last, g, ascii::space, parsed)) {
        std::cout << "Expression parsed.\n";
    } else {
        std::cout << "Could not parse equation.\n";
    }

    if (itr != last) {
        std::cout << "Remaining unparsed input: '" << std::string(itr,last) << "'\n";
    }
}

这篇关于Spirit qi解析为抽象语法树以实现嵌套函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！