Разбор Spirit qi в абстрактном синтаксическом дереве для вложенных функций

Question

Я пытаюсь создать парсер с использованием Boos Spirit Spirit Qi Parser. Он анализирует строку, содержащую три типа значений. Константа, переменная или функция. Функции могут быть вложены друг в друга. Тестовая строка f(a, b) = f(g(z, x), g(x, h(x)), c), где a-e являются постоянными, f-r являются функциями, и s-z переменные. Я успешно создал правило, которое может правильно проанализировать выражение. Проблема возникла, когда я изменил функцию разбора правила на грамматику. Было несколько ошибок, которые мне удалось исправить. Я почти получил грамматику, чтобы разобрать выражение и превратить его в абстрактное синтаксическое дерево, которое я создал. Однако я получил эту ошибку о файле, содержащемся в библиотеке надстроек, и я не мог понять, откуда он исходит, потому что я не понимаю сообщения компилятора. Я следовал примеру, приведенному на веб-сайте, для помещения данных из синтаксического анализатора в структуру с использованием примера сотрудника: 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_

Я не могу связать полное сообщение об ошибке от компилятора, потому что оно очень длинное, но вот последние несколько. Это ошибки компиляции, которые он дал:

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()'|

Answer 1

ОБНОВЛЕНИЕ Показывает упрощенный синтаксический анализатор с рекурсивным анализом ast, показанным примером выражения

Как всегда, сообщение об утверждении приводит именно к проблеме:

        // 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_>));

Таким образом, он говорит вам, что вы должны сопоставить грамматику с правилом запуска: у вас есть

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

но

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

Очевидно, вы забыли скобки там:

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

Рекомендации по использованию универсальных библиотек:

Некоторые из этих "правил" применимы в целом, за исключением "нет". 2, которая конкретно связана с Boost Spirit:

1. шаги малыша; начать с малого (пусто, даже)
2. начать с AST, чтобы точно соответствовать грамматике
3. строить постепенно,
4. составляя каждый шаг по пути

ОБНОВИТЬ

Вот очень упрощенная грамматика. Как уже упоминалось, в "первых правилах духа" как раз перед этим, начните с AST, чтобы точно соответствовать грамматике:

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 и вы могли бы динамически переключаться ( впечатление).

Теперь грамматика должна будет следовать. 1. Сохраняйте простоту. 2. Тщательно форматируйте. 3. Соответствуйте ast напрямую, 4. добавьте отладочные макросы:

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_ решил вашу самую большую головную боль!

Полная программа

Жить на Колиру

//#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";
    }
}

Answer 2

Ванильное решение C++ _{(согласно популярному запросу)}

Я скомпилировал его с MSVC 2013.
Отсутствие неограниченной поддержки союзов привело меня к дублированию трех возможных значений аргумента.

Есть обходные пути для этого ограничения, но _{(как и многие другие вещи в C++)} они довольно грязные, поэтому я не допустил их, чтобы ограничить запутывание кода.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

// possible token types
enum tTokenType {
    T_CONST,  // s-z
    T_VAR,    // a-e
    T_FUNC,   // f-r
    T_EQUAL,  // =
    T_COMMA,  // ,
    T_OBRACE, // (
    T_CBRACE, // )
    T_SPACE,  // ' ' or '\t'
    T_ERROR,  // anything but spaces
    T_EOI     // end of input
};

// tokens
struct tToken {
    tTokenType _type;  // lexical element type
    char       _value; // the actual const/var/func letter
    size_t     _index; // position in translation unit

    static const string constants, variables, functions, spacing;
    static const char * type_name[];

    tToken(tTokenType t, size_t index) : _type(t), _value(0), _index(index) {}

    static tTokenType type(char c)
    {
        if (constants.find(c) != string::npos) return T_CONST;
        if (variables.find(c) != string::npos) return T_VAR;
        if (functions.find(c) != string::npos) return T_FUNC;
        if (spacing  .find(c) != string::npos) return T_SPACE;
        if (c == '=')                          return T_EQUAL;
        if (c == ',')                          return T_COMMA;
        if (c == '(')                          return T_OBRACE;
        if (c == ')')                          return T_CBRACE;
        return T_ERROR;
    }

    tToken(char c, size_t index) : _value(c), _index(index)
    {
        _type = type(c);
    }

    void croak(tTokenType type)
    {
        string err(_index - 1, '-');
        cerr << err << "^ expecting " << type_name[(int)type] << "\n";
    }
};
const string tToken::variables("abcde");
const string tToken::functions("fghijklmnopqr");
const string tToken::constants("stuvwxyz");
const string tToken::spacing  (" \t");
const char * tToken::type_name[] = { "constant", "variable", "function", "=", ",", "(", ")", "space", "error", "end of input" };

// parser
class Parser {
    friend class Compiler;
    string _input; // remaining program input
    size_t _index; // current token index (for error tracking)

    void skip_spaces(void)
    {
        while (_input.length() != 0 && tToken::type(_input[0]) == T_SPACE) next();
    }

    void next(void)
    {
        _input.erase(0, 1);
        _index++;
    }

public:
    void read (string program)
    {
        _input = program;
        _index = 0;
        skip_spaces();
    }

    tToken get(void)
    {
        tToken res = peek();
        next();
        skip_spaces();
        return res;
    }

    tToken peek(void)
    {
        if (_input.length() == 0) return tToken(T_EOI, _index);
        return tToken (_input[0], _index);
    }

    tToken accept(tTokenType type)
    {
        tToken t = get();
        return (t._type == type) ? t : tToken (T_ERROR, _index-1);
    }

    bool consume(tTokenType type)
    {
        tToken t = get();
        bool res = t._type == type;
        if (!res) t.croak(type);
        return res;
    }
};

// syntactic elements
struct tSyntacticElement {
    char name;
    bool valid;

    tSyntacticElement() : name('?'), valid(false) {}
    tSyntacticElement(char c) : name(c), valid(false) {}
};

class tConstant : private tSyntacticElement  {
    friend class tArgument;
    tConstant() {}
    tConstant(tToken t) : tSyntacticElement(t._value) { }
};

class tVariable : private tSyntacticElement  {
    friend class tArgument;
    tVariable() {}
    tVariable(tToken t) : tSyntacticElement(t._value) { }

};

class tFunCall : private tSyntacticElement {
    friend class Compiler;
    friend class tProgram;
    friend class tArgument;
    vector<tArgument>params;

    tFunCall() {}
    tFunCall(tToken t) : tSyntacticElement(t._value) { }
    void add_argument(tArgument a);

    string dump(void);
};

class tArgument {
    friend class Compiler;
    friend class tProgram;
    friend class tFunCall;
    tTokenType type;

    // MSVC 2013 does not support unrestricted unions, so for the 
    // sake of simplicity I'll leave it as 3 separate attributes
    tConstant c; 
    tVariable v;
    tFunCall  f;

    tArgument() {}

    tArgument(tToken val) : type(val._type)
    {
        if (val._type == T_CONST) c = val;
        if (val._type == T_VAR  ) v = val;
    }
    tArgument(tFunCall  f) : type(T_FUNC ), f(f) {}

    string dump(void)
    {
        if (type == T_VAR)   return string("$") + v.name;
        if (type == T_CONST) return string("#") + c.name;
        if (type == T_FUNC)  return f.dump();
        return "!";
    }
};

class tProgram  {
    friend class Compiler;
    tArgument left;
    tArgument right;
    bool valid;

    string dump(void) { return left.dump() + " = " + right.dump(); }
};

// syntactic analyzer

void tFunCall::add_argument(tArgument a) { params.push_back(a); }

string tFunCall::dump(void)
{
    string res(1, name);
    res += '(';
    // it's 2015 and still no implode() in C++...
    for (size_t i = 0; i != params.size(); i++)
    {
        res += params[i].dump();
        if (i != params.size() - 1) res += ',';
    }
    res += ')';
    return res;
}

class Compiler {
    Parser parser;
    tProgram program;

    tFunCall parse_function(void)
    {
        tToken f = parser.accept(T_FUNC);
        tFunCall res (f);
        parser.accept(T_OBRACE);
        for (;;)
        {
            tArgument a = parse_argument();
            res.add_argument(a);
            tToken next = parser.get();
            if (next._type == T_CBRACE) break;
            if (next._type != T_COMMA) return res;
        }
        res.valid = true;
        return res;
    }

    tArgument parse_argument(void)
    {
        tToken id = parser.peek();
        if (id._type == T_FUNC)  return parse_function();
        id = parser.get();
        if (id._type == T_CONST) return id;
        if (id._type == T_VAR)   return id;
        return tArgument(tToken (T_ERROR, id._index));
    }

public:
    void analyze(string input)
    {
        parser.read(input);
        cerr << input << "\n";

        program.left = parse_argument();
        program.valid &= parser.consume(T_EQUAL);
        program.right = parse_argument();
        program.valid &= parser.consume(T_EOI);
    }

    string dump(void)
    {
        return program.dump();
    }
};

int main(int argc, char * argv[])
{
    Compiler compiler;
//  compiler.analyze("f(a, b) = f(g(z, x), g(x, h(x)), c)");
    compiler.analyze(argv[1]);
    cout << compiler.dump();
    return 0;
}

грамматика

Учитывая довольно краткое определение проблемы, я изобрел грамматику, которая должна как минимум соответствовать входным данным теста:

program : argument = argument
argument: variable
        | constant
        | fun_call
fun_call: fun_name ( arg_list )
arg_list: argument
        | argument , arg_list

анализ

Учитывая простоту синтаксиса, разбор довольно прост.
Каждый символ в основном является чем-то действительным, пробелом или чем-то недопустимым.
Пространства используются незаметно, поэтому анализатор получает только полезные токены для обработки.

анализировать

Поскольку я делаю это голыми руками, я просто определяю функцию для каждого грамматического правила (программа, fun_call, arg_list, аргумент).

Грамматика носит прогнозирующий характер (не могу вспомнить, как она называется в шикарных книгах, может быть, LL1?), И в ней нет арифметических выражений, поэтому код является относительно легким.

Отчет об ошибках

Бах, просто самый низкий минимум, и я на самом деле не проверял это.

Правильная обработка ошибок может легко удвоить размер кода (даже при использовании yacc), поэтому я подвел черту рано.

Недопустимые символы будут заменены на "!", А некоторые ожидаемые символы будут указаны в подобии вывода винтажных компиляторов Си.

Попытки повторной синхронизации абсолютно не предпринимаются, поэтому опечатка внутри вызова функции (особенно дисбаланс скобок), скорее всего, приведет к тому, что оставшаяся часть блока перевода будет отброшена в корзину.

Использование трудно заработанного синтаксического дерева

Могучему компилятору удается выплевывать эквивалент ввода.

Просто чтобы показать, что что-то было сделано помимо обрезки пробелов, переменным предшествует '$', а константам - '#' (показывая прискорбное отсутствие воображения).

Образец вывода

ExpressionCompiler "f(a) = z"
f(a) = z
f($a) = #z

ExpressionCompiler "f(a) = f(c,z)"
f(a) = f(c,z)
f($a) = f($c,#z)

ExpressionCompiler "f(a, b) = f(g(z, x), g(x, h(x)), c)"
f(a, b) = f(g(z, x), g(x, h(x)), c)
f($a,$b) = f(g(#z,#x),g(#x,h(#x)),$c)

ExpressionCompiler "f(a, b) + f(g(z, x), g(x, h(x)), c)"
f(a, b) + f(g(z, x), g(x, h(x)), c)
-------^ expecting =
f($a,$b) = f(g(#z,#x),g(#x,h(#x)),$c)

ExpressionCompiler "f(A, b) = f(g(z, x), g(x, h(x)), c)"
f(A, b) = f(g(z, x), g(x, h(x)), c)
f(!,$b) = f(g(#z,#x),g(#x,h(#x)),$c)

ExpressionCompiler "f(a, b) = K(g(z, x), g(x, h(x)), c)"
f(a, b) = K(g(z, x), g(x, h(x)), c)
----------^ expecting end of input
f($a,$b) = !