c++ - 将 boost spirit 用于基于堆栈的语言

Question

我需要解析一种相当简单的基于堆栈的语言，例如

1 2 add
3 1 sub

我在这里面临两个选择:

1. 为标记编写我自己的词法分析器，然后继续解析它
2. 使用 boost spirit

我从未使用过 boost spirit，但根据我所阅读的内容(文档和示例)，我仍然不能确定使用 boost spirit 来 lex 和解析这种简单的语言是否会过大，或者如果使用它而不是推出我自己的词法分析器和解析器是有意义的(我认为这应该不会太难)。

将 boost spirit 用于像上面那种基于堆栈的简单语言会有返回吗(因为我需要先学习它才能使用它)？

Answer 1

在“详尽探索”类别中，让我添加一些使用 Spirit Qi (v2.x) 和 X3 的“即时解释”堆栈机器

Note that an AST-ful approach (2 stage parse/execute) is shown in the second answer

灵气中

这里的语义 Action 必须使用 Phoenix actor 来“组合”:

Live On Coliru

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/repository/include/qi_distinct.hpp>
#include <iostream>
#include <deque>

namespace qi = boost::spirit::qi;
namespace px = boost::phoenix;
namespace qr = boost::spirit::repository::qi;

using Stack = std::deque<int>;

namespace actors {

    struct pop {
        Stack& s_;

        Stack::value_type operator()() const {
            Stack::value_type v = s_.back();
            s_.pop_back();
            return v;
        }
    };

    struct push {
        Stack& s_;
        template <typename V> void operator()(V const& v) const {
            s_.push_back(v);
        }
    };

    struct dump {
        Stack& s_;
        void operator()() const {
            std::copy(s_.begin(), s_.end(), std::ostream_iterator<Stack::value_type>(std::cout, " "));
            std::cout << "\n";
        }
    };
}

int main() {
    Stack stack_;

    boost::spirit::istream_iterator f(std::cin >> std::noskipws), l; // Note the noskipws!
    bool ok;

    {
        using namespace qi;
        px::function<actors::pop>  pop_  = actors::pop{ stack_ };
        px::function<actors::push> push_ = actors::push{ stack_ };
        px::function<actors::dump> dump_ = actors::dump{ stack_ };

        ok = phrase_parse(f, l, 
               *(
                   eps [ dump_() ] >> 
                   (lexeme [ qr::distinct(graph) [
                          lit("add") [ push_(  pop_() + pop_()) ]
                        | lit("sub") [ push_(- pop_() + pop_()) ] // bit hackish
                        | lit("mul") [ push_(pop_() * pop_()) ]
                        | lit("div") [ push_(pop_() / pop_()) ] // TODO fix order
                        | lit("pop") [ pop_() ]
                      ] ] 
                    | int_ [ push_(_1) ]
                  )
                ), space);
    }

    if (!ok)
        std::cout << "Parse failed\n";

    if (f != l)
        std::cout << "Unparsed program data: '" << std::string(f,l) << "'\n";
}

打印

1 
1 2 
3 
3 3 
3 3 1 
3 2 
6 

注意事项:

• 它变得丑陋(学习曲线很长；另见 Boost Spirit: "Semantic actions are evil"?)
• 评论很有说服力；实际上，在 sub 和 div 中修复该顺序或操作数并不容易。这需要一些高级凤凰符 ( http://www.boost.org/doc/libs/1_59_0/libs/phoenix/doc/html/phoenix/modules/scope/let.html )

spirit X3

想法是一样的，但我们可以使用 lambda 来使用适当的函数组合。

我们甚至使用一个助手来动态生成解析器表达式以及合适的 binop:

Live On Coliru

#include <boost/spirit/home/x3.hpp>
#include <boost/spirit/include/support_istream_iterator.hpp>
#include <iostream>
#include <deque>
#include <cassert>

int main() {
    std::deque<int> stack_;

    boost::spirit::istream_iterator f(std::cin >> std::noskipws), l; // Note the noskipws!
    bool ok;

    {
        using namespace boost::spirit::x3;
        struct stack_tag {};

        auto binop = [](auto id, auto f) {
            auto apply = [=](auto& ctx) {
                auto& s = get<stack_tag>(ctx);
                assert(s.size()>=2);

                auto rhs = s.back(); s.pop_back();
                auto lhs = s.back(); s.pop_back();
                s.push_back(f(lhs, rhs));
            };

            return lexeme[as_parser(id) >> !graph] [apply];
        };

        auto push = [](auto& ctx) {
            auto& s = get<stack_tag>(ctx);
            s.push_back(_attr(ctx));
        };

        auto dump = [](auto& ctx) {
            auto& s = get<stack_tag>(ctx);
            std::copy(s.begin(), s.end(), std::ostream_iterator<int>(std::cout, " "));
            std::cout << "\n";
        };

        auto instr   = binop("add", [](auto a, auto b) { return a + b; })
                     | binop("sub", [](auto a, auto b) { return a - b; })
                     | binop("mul", [](auto a, auto b) { return a * b; })
                     | binop("div", [](auto a, auto b) { return a / b; })
                     | int_ [ push ]
                     ;

        auto parser  = skip(space) [ *(eps [ dump ] >> instr) >> eps/*post-skip*/ ];
        auto machine = with<stack_tag>(stack_) [parser];

        ok = parse(f, l, machine);
    }

    if (!ok)
        std::cout << "Parse failed\n";

    if (f != l)
        std::cout << "Unparsed program data: '" << std::string(f,l) << "'\n";
}

当然它会打印相同的输出。

• 它没有 Qi 版本的任何缺点
• 编译速度更快(2.9 秒对 9.2 秒!)
• 注意:X3 需要 C++14