使用升压精神，为一个基于堆栈的语言 [英] Using boost spirit for a stack based language
问题描述
我需要解析一个相当简单的基于堆栈的语言，例如
I need to parse a rather simple stack based language, e.g.
1 2 add
3 1 sub
和我在这里面临着两种选择：
and I'm facing two choices here:
- 写我自己的令牌词法分析器，然后进行解析它
- 使用升压精神
我从来没有用过提振精神，但是从我读过左右（文档和示例），我仍无法弥补我心灵上是否会矫枉过正，使用升压精神Lex和解析这个简单的语言，或者如果这将是有意义的，而不是用它推出我自己的词法和语法分析器（事情，我想应该不会太难）的。
I have never used boost spirit but from what I've read around (documentation and examples) I can't still make up my mind on whether it would be overkill to use boost spirit to lex and parse this simple language or if it would make sense to use it instead of rolling out my own lexer and parser (thing that I suppose shouldn't be too hard).
使用会提振精神，为一个简单的基于堆栈的语言象那个上述还清（因为我需要先了解它之前，我可以用它）？
Would using boost spirit for a simple stack based language like the one above pay off (since I need to learn it first before I can use it)?
推荐答案
在类别详尽的探索，让我用灵奇（版本2.x）添加一些飞跨preting堆机X3
In the category "exhaustive explorations", let me add some "on the fly interpreting" stack machines using Spirit Qi (v2.x) and X3
请注意，一个AST-FUL方法（2阶段解析/执行）在
Note that an AST-ful approach (2 stage parse/execute) is shown in the second answer
下面的语义动作必须是组合凤凰用演员：
In Spirit Qi
Here the semantic actions have to be "composed" using Phoenix actors:
<大骨节病> 住在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
注：
- 它变得丑陋（学习曲线是沉重的;另请参见升压精神：＆QUOT;语义的行为是邪恶的＆QUOT;？）
- 的评论意味深长;实际上固定的顺序或者操作数
分和DIV是的不的容易。这会需要一些先进的凤凰城福（的http://www.boost.org/doc/libs/1_59_0/libs/phoenix/doc/html/phoenix/modules/scope/let.html)
- it gets ugly (the learning curve is hefty; See also Boost Spirit: "Semantic actions are evil"?)
- the comments speak volumes; actually fixing that order or operands in
subanddivis not easy. It's gonna require some advanced Phoenix-fu (http://www.boost.org/doc/libs/1_59_0/libs/phoenix/doc/html/phoenix/modules/scope/let.html)
我们的想法是一样的，但是我们可以使用lambda表达式使用正确的功能性成分。
The idea is the same, but we can use proper functional composition using lambdas.
我们甚至用一个助手来动态生成适合沿着解析器前pression binop ：
We even use a helper to dynamically generate the parser expression along with suitable binop:
<大骨节病> 住在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";
}
当然，它打印相同的输出。
Of course it prints the same output.
- 有没有缺点的齐版本有
- 它编译更快（2.9s与9.2s！）
- 注：X3需要C ++ 14
这篇关于使用升压精神，为一个基于堆栈的语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
