这个问题是"用boost精神迭代更新抽象语法树"的后续问题。
已知:
- 语法分析器允许递归
要求是:
- 解析器的AST必须是BGL图
- 每个解析器步骤的输入可以是一到多个符号
想法:
- 关于精神解析到BGL图的一些基本思想在这里展示。使用boost图库:如何创建图。。。,但并不能完全满足要求,因为我希望能够迭代地解析一对多个符号
- 猜测BGL图和精神解析器必须相互了解,才能在正确的位置填充数据。第一个想法是解析器必须能够处理图的顶点
- 像Using semantic actions/qi::locals这样的解决方案可能适用,但我不确定这是否足以让解析器迭代地处理图
有人对如何解决这个问题有什么想法吗,或者给我指明一些方向吗?
感谢
简而言之:这很难实现。
如果想要将一些数据解析为BGL图,最简单的方法可能是使用BGL图适配器vector_as_graph。如果有这个适配器,并且boost spirit解析器可以解析为向量,那么这是可能的。
enum { r, s, t, u, v, w, x, y, N };
char name[] = "rstuvwxy";
typedef std::vector < std::list < int > > Graph;
Graph g(N);
g[r].push_back(v);
g[s].push_back(r);
g[s].push_back(r);
g[s].push_back(w);
g[t].push_back(x);
g[u].push_back(t);
g[w].push_back(t);
g[w].push_back(x);
g[x].push_back(y);
g[y].push_back(u);
boost::print_graph(g, name);
我使用的解决方案是解析boost spirit域中的给定语法,然后执行到AST的转换,以便表示为BGL图。
最后的想法:需要注意的是,提升精神和BGL领域的学习曲线都相当陡峭。基于此,如果分开,可读性和实现性会更容易。并不是说它无法解决。
响应
最后的想法:应该注意的是,提升精神和BGL领域的学习曲线都相当陡峭。基于此,如果分开,可读性和实现性会更容易。并不是说它无法解决
我同意你的回答。保持事情简单的关键是将关注点分开。(仅仅因为Phoenix允许您将几乎任何东西直接绑定到解析器中,并不意味着这是一个好主意[1]。)
也许这个示例应用程序可以作为灵感?
在Coliru上直播
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <sstream>
using namespace boost;
typedef adjacency_list<setS, vecS, directedS> Graph;
std::vector<std::string> generate_file_data();
void merge_into(std::istream&& is, Graph& into);
int main() {
Graph merged;
for(auto& input: generate_file_data())
merge_into(std::istringstream(input), merged);
print_graph(merged);
}
正如您所看到的,它读取了许多(不同的)文件,并将边合并到merged
图中。
当然,在一个在线演示中,我们没有输入文件,所以我生成了20个顶点中6条随机边的5个随机图(generate_file_data()
)。
有趣的比特在merge_into
:中
#include <boost/spirit/include/qi.hpp>
void merge_into(std::istream&& is, Graph& into) {
namespace qi = boost::spirit::qi;
namespace phx = boost::phoenix;
phx::function<edge_merge_f> merge_edges;
boost::spirit::istream_iterator f(is >> std::noskipws), l;
bool ok = qi::phrase_parse(f, l,
(qi::int_ >> *qi::int_) [ merge_edges(qi::_1, qi::_2, phx::ref(into)) ] % qi::eol,
qi::blank);
assert(ok);
}
这是代码中唯一涉及精神的部分。正如你所看到的,它实际上根本不知道BGL。这个逻辑留给了一个"回调"函数对象edge_merge_f
,它也很琐碎:
struct edge_merge_f {
template <typename...> struct result { typedef void type; }; // for BOOST_RESULT_OF_USE_TR1:
template<typename V, typename Edges, typename G>
void operator()(V const& v, Edges const& edges, G& into) const {
for (auto e : edges)
if (!add_edge(v, e, into).second)
std::cout << "Duplicate edge: (" << v << "," << e << ")n";
}
};
UPDATE作为奖励,通过将
EdgeCallback
作为boost::function
传递给它来将merge_adjacencies
与Graph类型完全解耦的版本:解耦版本。当然,这会降低效率,但它表明了我所说的将事情分开的意思。
这是我机器上的输出(我不播种随机引擎,所以它是可重复的):在Coliru上直播
Duplicate edge: (9,1)
Duplicate edge: (0,4)
0 --> 1 2 4 9
1 -->
2 -->
3 --> 1 7
4 --> 1
5 --> 1 6
6 --> 1 3 5
7 --> 5 6 8
8 --> 3
9 --> 1 2
如果将Graph typedef更改为对边缘容器使用vecS
,则不必更改任何其他内容,结果是:Live-On-Coliru
0 --> 4 9 1 4 2
1 -->
2 -->
3 --> 7 1
4 --> 1
5 --> 1 6
6 --> 1 3 5
7 --> 5 6 8
8 --> 3
9 --> 1 2 1
[1]我想我把你和Boost Spirit联系起来了:";语义行为是邪恶的"?之前:)
完整列表
对于子孙后代(也包括generate_file_data()
):
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <sstream>
using namespace boost;
typedef adjacency_list<setS/*vecS*/, vecS, directedS> Graph;
std::vector<std::string> generate_file_data();
void merge_into(std::istream&& is, Graph& into);
int main() {
Graph merged;
for(auto& input: generate_file_data())
merge_into(std::istringstream(input), merged);
print_graph(merged);
}
////////////////////////////////
// Generating random test data
#include <boost/graph/random.hpp>
#include <boost/random.hpp>
std::vector<std::string> generate_file_data() {
std::vector<std::string> data;
mt19937 prng(42);
for (int i=0; i<5; ++i) {
std::ostringstream oss;
Graph g;
generate_random_graph(g, 10, 4, prng);
for (auto v : make_iterator_range(vertices(g))) {
oss << v << " ";
for (auto const& e : make_iterator_range(out_edges(v, g))) oss << target(e, g) << " ";
oss << "n";
}
data.push_back(oss.str());
}
return data;
}
////////////////////////////////
// Merging edges
namespace {
struct edge_merge_f {
template <typename...> struct result { typedef void type; }; // for BOOST_RESULT_OF_USE_TR1:
template<typename V, typename Edges, typename G>
void operator()(V const& v, Edges const& edges, G& into) const {
for (auto e : edges)
if (!add_edge(v, e, into).second)
std::cout << "Duplicate edge: (" << v << "," << e << ")n";
}
};
}
#include <boost/spirit/include/qi.hpp>
void merge_into(std::istream&& is, Graph& into) {
namespace qi = boost::spirit::qi;
namespace phx = boost::phoenix;
phx::function<edge_merge_f> merge_edges;
boost::spirit::istream_iterator f(is >> std::noskipws), l;
bool ok = qi::phrase_parse(f, l,
(qi::int_ >> *qi::int_) [ merge_edges(qi::_1, qi::_2, phx::ref(into)) ] % qi::eol,
qi::blank);
assert(ok);
}