Boost Spirit 从简单的加法运算符中消除左递归

Question

我正在尝试使用 boost spirit 为一种简单的语言创建一个解析器。我试图解析的第一个语句是一个简单的数字加法：“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 是 std::shared_ptr 到 AstNodeBase class 的类型定义，DoubleNode 和 AddNode 继承自它。我没有包括这些定义只是为了使 post 简短，但如果需要的话可以。我认为这是不言自明的，这个想法是编写一个 AST。 make_shared_ 实现来自 here.

提前致谢！

Answer 1

你的例子有很多方面。

首先，你使用auto灵气表情。这是无效的，并导致 UB:

Assigning parsers to auto variables
还有
undefined behaviour somewhere in boost::spirit::qi::phrase_parse
boost spirit V2 qi bug associated with optimization level

接下来，您选择使用多态 Ast 节点。这是可能的，但可能效率不高：

How can I use polymorphic attributes with boost::spirit::qi parsers?
还有你可能已经找到了

最后是左递归，因为你的表达式从它自身开始，导致无限递归。解决它的唯一方法是将您的作品拆分为 "levels" 个表达式。这也有助于生成所需的运算符优先级：

 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 { // 

    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

Boost Spirit 从简单的加法运算符中消除左递归

Boost Spirit eliminate left recursion from simple addition operator

c++

boost

boost-spirit

boost-spirit-qi

完整演示