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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
#include "bnf.h"
std::unordered_map<std::string, std::unordered_set<std::string>> Reverse(const BNF& bnf)
{
std::unordered_map<std::string, std::unordered_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::unordered_set{from});
}
}
}
return result;
}
std::unordered_map<std::string, std::unordered_set<std::string>> reverseFirst(const BNF& bnf)
{
std::unordered_map<std::string, std::unordered_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::unordered_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;
}
bool isTerminal(const BNF& bnf, const std::string& symbol)
{
return bnf.find(symbol) == bnf.end();
}
std::unordered_set<std::string> getTerminals(const BNF& bnf)
{
std::unordered_set<std::string> result;
for (const auto& [from, to] : bnf) {
for (const auto& list : to) {
for (const auto& element : list) {
if (isTerminal(bnf, element))
result.insert(element);
}
}
}
return result;
}
std::unordered_set<std::pair<std::string, size_t>, PairHash> getEmptyPositions(const BNF& bnf)
{
std::unordered_set<std::pair<std::string, size_t>, PairHash> result;
for (const auto& [from, to] : bnf) {
for (size_t i = 0; i < to.size(); i++) {
const auto& list{to[i]};
if (list.size() == 0)
result.insert({from, i});
}
}
return result;
}
std::unordered_map<std::string, std::unordered_set<std::pair<std::string, index_t>, PairHash>> reversePosFirst(const BNF& bnf)
{
std::unordered_map<std::string, std::unordered_set<std::pair<std::string, index_t>, PairHash>> result;
for (const auto& [from, to] : bnf) {
for (size_t i = 0; i < to.size(); i++) {
const auto& list{to[i]};
if (list.size() > 0) {
const auto& element{list[0]};
auto it{result.find(element)};
if (it != result.end()) // already present
it->second.insert({from, i});
else // new element
result.emplace(element, std::unordered_set<std::pair<std::string, index_t>, PairHash>{{from, i}});
}
}
}
return result;
}
|
