1 files changed, 58 insertions, 6 deletions

diff --git a/bnf.cpp b/bnf.cpp
index 32e1175..04a6be9 100644
--- a/bnf.cpp
+++ b/bnf.cpp
@@ -1,8 +1,8 @@
 #include "bnf.h"
 
-std::unordered_map<std::string, std::set<std::string>> Reverse(BNF bnf)
+std::unordered_map<std::string, std::unordered_set<std::string>> Reverse(const BNF& bnf)
 {
- std::unordered_map<std::string, std::set<std::string>> result;
+ std::unordered_map<std::string, std::unordered_set<std::string>> result;
 
  for (const auto& [from, to] : bnf) {
   for (const auto& list : to) {
@@ -11,7 +11,7 @@ std::unordered_map<std::string, std::set<std::string>> Reverse(BNF bnf)
     if (i != result.end()) // already present
      i->second.insert(from);
     else // new element
-     result.emplace(element, std::set{from});
+     result.emplace(element, std::unordered_set{from});
    }
   }
  }
@@ -19,9 +19,9 @@ std::unordered_map<std::string, std::set<std::string>> Reverse(BNF bnf)
  return result;
 }
 
-std::unordered_map<std::string, std::set<std::string>> reverseFirst(BNF bnf)
+std::unordered_map<std::string, std::unordered_set<std::string>> reverseFirst(const BNF& bnf)
 {
- std::unordered_map<std::string, std::set<std::string>> result;
+ std::unordered_map<std::string, std::unordered_set<std::string>> result;
 
  for (const auto& [from, to] : bnf) {
   for (const auto& list : to) {
@@ -31,7 +31,7 @@ std::unordered_map<std::string, std::set<std::string>> reverseFirst(BNF bnf)
     if (i != result.end()) // already present
      i->second.insert(from);
     else // new element
-     result.emplace(element, std::set{from});
+     result.emplace(element, std::unordered_set{from});
    }
   }
  }
@@ -73,3 +73,55 @@ 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;
+}
+