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

---
 grammer.h | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

(limited to 'grammer.h')

diff --git a/grammer.h b/grammer.h
index 9b72d3a..a8a3356 100644
--- a/grammer.h
+++ b/grammer.h
@@ -39,11 +39,9 @@ private:
  // Input
  std::vector<Token> tokens;
 
- BNF &bnf; // not const for access via operator[]
+ BNF m_bnf; // not const for access via operator[]
  const std::string m_top;
 
- //std::unordered_map<std::string, std::unordered_set<std::string>> ReverseBNF; // possible parent types of a given type; unused now: remove?
- //std::unordered_map<std::string, std::unordered_set<std::string>> reversedFirst; // possible parent types of first childs of a given type
  std::unordered_map<std::string, std::unordered_set<std::pair<std::string, index_t>, PairHash>> reversedPosFirst; // possible parent types of first childs of a given type
 
  std::deque<index_t> symbol_variants;
@@ -81,12 +79,14 @@ private:
    return h0 ^ (h1 << 1) ^ (h2 << 2);
   }
  };
+ // map combination of non-terminal+terminal symbol combination to list of
+ // possible BNF positions for the specified non-terminal symbol
  std::unordered_map<std::pair<std::string, std::string>, std::vector<size_t>, PairHashSS> m_match_lut;
+ std::unordered_map<std::string, size_t> m_empty_lut; // list of non-terminal symbols that can lead to empty token list (maps to variant)
+
  void fillStartCache();
 
  void constructTree();
- std::vector<std::string> m_symbol_list;
- index_t m_symbol_list_pos{};
 
 public:
  Compiler(BNF& bnf, const std::string& top);
-- 
cgit v1.2.3