bnf.cpp


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::map<std::string, std::set<std::string>> Reverse(BNF bnf)
{
 std::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::map<std::string, std::set<std::string>> reverseFirst(BNF bnf)
{
 std::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;
}