Top-down algo recognizes first C*+ program

1 files changed, 14 insertions, 7 deletions

diff --git a/grammer.h b/grammer.h
index 39e6884..88cb7b7 100644
--- a/grammer.h
+++ b/grammer.h
@@ -4,6 +4,7 @@
 #include "minicc.h"
 
 #include <cstdint>
+#include <deque>
 #include <unordered_set>
 #include <utility>
 
@@ -16,7 +17,7 @@ struct NodePosition {
  index_t child_pos{}; // 0-based
 };
 
-// TreeNodes are only intermediate. Terminal symbols don't get of TreeNodes
+// TreeNodes are only intermediate. Terminal symbols don't get TreeNodes
 // token_id: index into token list
 // node_id: index into tree node list
 struct TreeNode {
@@ -43,24 +44,24 @@ private:
  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::deque<index_t> symbol_variants;
+ decltype(symbol_variants)::iterator symbol_variants_it;
+
  // Tree specific
  void clear();
  
  // Node specific
  std::string GetTypeOfNode(index_t node_id) const;
  index_t AddNode(const std::string& type, index_t variant, NodePosition pos = {});
- void RemoveNode();
- // Adds Node and Removes it on scope exit (RAII)
+ // Adds actually used Non-Terminal Symbol Removes it on scope exit (RAII)
  class AddNodeGuard {
   Compiler& m_compiler;
  public:
-  AddNodeGuard(Compiler& compiler, const std::string& type, index_t variant, NodePosition pos);
+  AddNodeGuard(Compiler& compiler, index_t variant);
   ~AddNodeGuard();
  };
  void IncNodePosition(NodePosition& pos);
 
- NodePosition begin_pos;
-
  // top-down algorithm
  std::unordered_map<std::string, size_t> m_min; // cache
  size_t minimumSymbolsNeeded(std::string symbol);
@@ -68,15 +69,21 @@ private:
  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);
 
+ void constructTree();
+ std::vector<std::string> m_symbol_list;
+ index_t m_symbol_list_pos{};
+
 public:
  Compiler(BNF& bnf, const std::string& top);
- std::pair<index_t, std::vector<TreeNode>> compile(std::vector<Token> p_tokens);
+ std::vector<TreeNode> compile(std::vector<Token> p_tokens);
  void DumpTree();
 
  friend class ::GrammerTest;
 };
 
+bool ChildIdIsEmpty(int32_t child_id);
 bool ChildIdIsToken(int32_t child_id);
+bool ChildIdIsNode(int32_t child_id);
 index_t TokenIdFromChildId(int32_t child_id);
 int32_t ChildIdFromTokenId(index_t token_id);