blob: 4dd896ec1276e97cd31419f060892ba95c08758d (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include "bnf.h"
std::unordered_map<std::string, std::set<std::string>> Reverse(BNF bnf)
{
std::unordered_map<std::string, std::set<std::string>> result;
for (const auto& [from, to] : bnf) {
for (const auto& list : to) {
for (const auto& element : list) {
auto i{result.find(element)};
if (i != result.end()) // already present
i->second.insert(from);
else // new element
result.emplace(element, std::set{from});
}
}
}
return result;
}
std::unordered_map<std::string, std::set<std::string>> reverseFirst(BNF bnf)
{
std::unordered_map<std::string, std::set<std::string>> result;
for (const auto& [from, to] : bnf) {
for (const auto& list : to) {
if (list.size() > 0) {
const auto& element{list[0]};
auto i{result.find(element)};
if (i != result.end()) // already present
i->second.insert(from);
else // new element
result.emplace(element, std::set{from});
}
}
}
return result;
}
BNF SubBNF(const BNF& bnf, const std::string& top)
{
BNF result;
std::vector<std::string> todo{top};
while (!todo.empty()) {
std::string current{todo.back()};
todo.pop_back();
auto it = bnf.find(current);
if (it != bnf.end()) {
// add current value
result[it->first] = it->second;
// add sub-tree values if not present yet, but available in original bnf
for (auto& variant: it->second) {
for (auto& child: variant) {
if (result.find(child) == result.end() && bnf.find(child) != bnf.end()) {
todo.push_back(child);
}
}
}
}
}
return result;
}
|
