Boost Spirit устраняет левую рекурсию от простого оператора сложения

Question

Я пытаюсь использовать boost Spirit для создания парсера для простого языка. Первым утверждением, которое я пытаюсь разобрать, является простое добавление цифр c: «3.14 + 1». Это ошибка, и мое исследование показывает, что это из-за леворекурсивной реализации, но я не могу обернуть голову вокруг решения, которое не является леворекурсивным. Вот моя реализация синтаксического анализатора:

template<typename Iterator>
struct simple_grammar : qi::grammar<Iterator, AstNodePtr(), ascii::space_type> {

  simple_grammar() : simple_grammar::base_type(start) {
    using qi::double_;
    using qi::_1;
    using qi::_2;
    using qi::_3;

    auto addhelper = '+' >> expression;
    auto add = expression >> addhelper;

    expression = add[qi::_val = make_shared_<AddNode>()(_1, _2)]
               | double_[qi::_val = make_shared_<DoubleNode>()(_1)];

    start = expression;
  }


  qi::rule<Iterator, AstNodePtr(), ascii::space_type> start;
  qi::rule<Iterator, AstNodePtr(), ascii::space_type> expression;
};

AstNodePtr является typedef для std :: shared_ptr для класса AstNodeBase, от которого наследуются DoubleNode и AddNode. Я не включил эти определения просто для того, чтобы пост был коротким, но могу по запросу. Я думаю, это довольно очевидно, идея состоит в том, чтобы составить АСТ. Реализация make_shared_ происходит от здесь .

Заранее спасибо!

Answer 1

В вашем примере есть несколько вещей.

Прежде всего, вы используете auto с выражениями Spirit Qi. Это недопустимо и приводит к UB:

• Назначение синтаксических анализаторов для автоматических переменных
• также boost Spirit Qi Parser не удалось освободить и передать в отладку
• неопределенное поведение где-то в boost :: spirit :: qi :: фраза_parse
• повышение духа V2 ци ошибка, связанная с уровнем оптимизации

Затем вы решили использовать полиморфные c узлы Ast. Это возможно, но, вероятно, не эффективно:

• Как я могу использовать атрибуты polymorphi c с парсерами boost :: spirit :: qi?
• Семанти c действия выполняются несколько раз в boost :: spirit parsing
• , но также создает вектор общих указателей из Spirit Qi , который вы, возможно, нашли

Наконец, есть левая рекурсия, поскольку ваше выражение начинается с самого себя, что приводит к бесконечной рекурсии. Единственный способ решить эту проблему - разделить ваши произведения на «уровни» выражений. Это также помогает генерировать желаемый приоритет оператора:

 expression = term >> char_("-+") >> term;
 term = factor >> char_("*/%") >> factor;
 factor = simple >> char_("^") >> simple;

В вашем случае я бы предложил:

    simple
        = qi::double_
            [_val = make_shared_<DoubleNode>()(_1)]; 
        ;

    expression 
        = (simple >> '+' >> expression)
            [_val = make_shared_<AddNode>()(_1, _2)]
        | simple
        ;

Конечно, вы можете быть проще и чуть менее неэффективными:

    expression 
        = simple [_val = _1] 
        >> *(('+' >> expression)
                [_val = make_shared_<AddNode>()(_val, _0)])
        ;

Полная демонстрация

Live On Coliru

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

namespace { // https://stackoverflow.com/a/21565350/85371

    template <typename T>
    struct make_shared_f
    {
        template <typename... A> struct result 
            { typedef std::shared_ptr<T> type; };

        template <typename... A>
        typename result<A...>::type operator()(A&&... a) const {
            return std::make_shared<T>(std::forward<A>(a)...);
        }
    };
}

template <typename T>
using make_shared_ = boost::phoenix::function<make_shared_f<T> >;

struct AstNode {
    virtual ~AstNode() = default;
};
using AstNodePtr = std::shared_ptr<AstNode>;
struct DoubleNode : AstNode {
    DoubleNode(double) {}
};
struct AddNode : AstNode {
    AddNode(AstNodePtr, AstNodePtr) {}
};

#include <iomanip>

namespace qi = boost::spirit::qi;

template<typename Iterator>
struct simple_grammar : qi::grammar<Iterator, AstNodePtr()> {

    simple_grammar() : simple_grammar::base_type(start) {
        using namespace qi::labels;

        simple
            = qi::double_
                [_val = make_shared_<DoubleNode>()(_1)]; 
            ;

        expression 
            = simple [_val = _1] 
            >> *(('+' >> expression)
                    [_val = make_shared_<AddNode>()(_val, _1)])
            ;

        start = qi::skip(qi::space) [ expression ];
        BOOST_SPIRIT_DEBUG_NODES((start)(expression)(simple))
    }
  private:
    qi::rule<Iterator, AstNodePtr()> start;
    qi::rule<Iterator, AstNodePtr(), qi::space_type> expression;
    // implicit lexemes
    qi::rule<Iterator, AstNodePtr()> simple;
};

int main() {
    simple_grammar<std::string::const_iterator> g;

    for (std::string const input : {
            "1 + 2",
            "3.14"
            })
    {
        auto f = begin(input), l = end(input);
        AstNodePtr ast;
        if (qi::parse(f, l, g, ast)) {
            std::cout << "Succeeded: " << boost::core::demangle(typeid(*ast).name()) << "\n";
        } else {
            std::cout << "Failed\n";
        }

        if (f!=l)
            std::cout << "Remaining unparsed " << std::quoted(std::string(f,l)) << "\n";
    }
}

Печать

Succeeded: AddNode
Succeeded: DoubleNode