diff options
Diffstat (limited to 'grammer.h')
| -rw-r--r-- | grammer.h | 26 |
1 files changed, 21 insertions, 5 deletions
@@ -5,6 +5,7 @@ #include <cstdint> #include <deque> +#include <tuple> #include <unordered_set> #include <utility> @@ -41,8 +42,9 @@ private: BNF &bnf; // not const for access via operator[] const std::string m_top; - std::unordered_map<std::string, std::set<std::string>> ReverseBNF; // possible parent types of a given type; unused now: remove? - std::unordered_map<std::string, std::set<std::string>> reversedFirst; // possible parent types of first childs of a given type + //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; decltype(symbol_variants)::iterator symbol_variants_it; @@ -63,12 +65,26 @@ private: void IncNodePosition(NodePosition& pos); // top-down algorithm - std::unordered_map<std::string, size_t> m_min; // cache - size_t minimumSymbolsNeeded(std::string symbol); - size_t minimumSymbolsNeeded(std::vector<std::string> symbol_list); + std::unordered_map<std::string, size_t> m_min; // cache for MinimumSymbolsNeeded + size_t minimumSymbolsNeeded(const std::string& symbol); + size_t minimumSymbolsNeeded(const std::vector<std::string>& symbol_list); bool match(std::string symbol, size_t begin, size_t end); bool match(std::vector<std::string> symbol_list, size_t begin, size_t end); + // start / end cache + struct TupleHash { + size_t operator()(const std::tuple<std::string,size_t,std::string>& t) const noexcept + { + size_t h0 {std::hash<std::string>{}(std::get<0>(t))}; + size_t h1 {std::hash<size_t >{}(std::get<1>(t))}; + size_t h2 {std::hash<std::string>{}(std::get<2>(t))}; + return h0 ^ (h1 << 1) ^ (h2 << 2); + } + }; + std::unordered_set<std::tuple<std::string, size_t, std::string>, TupleHash> m_start_cache; + bool canStartWith(const std::string& non_terminal, size_t variant, const std::string& terminal) const; + void fillStartCache(); + void constructTree(); std::vector<std::string> m_symbol_list; index_t m_symbol_list_pos{}; |