From cd6c436cb70c4323c7d14ebd74f89bb0914649f2 Mon Sep 17 00:00:00 2001
From: Roland Reichwein <mail@reichwein.it>
Date: Tue, 31 Mar 2020 18:46:49 +0200
Subject: Optimization: Replace head recursion by tail recursion in matching

---
 bnf.cpp | 53 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 53 insertions(+)

(limited to 'bnf.cpp')

diff --git a/bnf.cpp b/bnf.cpp
index 04a6be9..b2d0472 100644
--- a/bnf.cpp
+++ b/bnf.cpp
@@ -68,6 +68,59 @@ BNF SubBNF(const BNF& bnf, const std::string& top)
  return result;
 }
 
+namespace {
+
+ bool isHeadRecursive(const std::vector<std::string>& list, const std::string& symbol) {
+  if (list.size() > 0 && list[0] == symbol)
+   return true;
+  return false;
+ }
+
+ bool isHeadRecursive(const std::vector<std::vector<std::string>>& lists, const std::string& symbol) {
+  for (const auto& list: lists) {
+   if (isHeadRecursive(list, symbol))
+    return true;
+  }
+  return false;
+ }
+
+} // anonymous namespace
+
+// Change head recursion to tail recursion
+BNF removeHeadRecursion(const BNF& bnf)
+{
+ std::unordered_map<std::string, std::vector<std::vector<std::string>>> result;
+
+ for (const auto& [from, to]: bnf) {
+  if (isHeadRecursive(to, from)) { // modify rule by adding additional one
+   std::string from_ext = from + "-ext";
+   if (bnf.find(from_ext) != bnf.end())
+    throw std::runtime_error("ICE: Symbol "s + from_ext + " already exists in original BNF");
+
+   std::vector<std::vector<std::string>> to_new;
+   std::vector<std::vector<std::string>> to_ext{{}}; // starts with empty list as first element
+   for (const auto& list: to) {
+    if (isHeadRecursive(list, from)) {
+     std::vector<std::string> list_new{list.begin() + 1, list.end()};
+     list_new.push_back(from_ext);
+     to_ext.push_back(list_new);
+    } else {
+     std::vector<std::string> list_new{list.begin(), list.end()};
+     list_new.push_back(from_ext);
+     to_new.push_back(list_new);
+    }
+   }
+
+   result[from] = to_new;
+   result[from_ext] = to_ext;
+  } else { // just add
+   result[from] = to;
+  }
+ }
+
+ return result;
+}
+
 bool isTerminal(const BNF& bnf, const std::string& symbol)
 {
  return bnf.find(symbol) == bnf.end();
-- 
cgit v1.2.3