New algo

1 files changed, 36 insertions, 29 deletions

diff --git a/grammer.h b/grammer.h
index 87aa1ad..18719cd 100644
--- a/grammer.h
+++ b/grammer.h
@@ -3,51 +3,58 @@
 #include "bnf.h"
 #include "minicc.h"
 
+#include <cstdint>
+
 namespace Gram {
 
+// TreeNodes are only intermediate. Terminal symbols don't get of TreeNodes
+// token_id: index into token list
+// node_id: index into tree node list
 struct TreeNode {
- index_t parent{};
- std::vector<index_t> childs; // fill Token by Token
- std::vector<std::string> child_types; // fill always
- Token token;
-};
-
-class Tree {
-private:
- std::map<index_t, TreeNode> nodes; // index 0 = non existing; index starting at 1
- index_t node_num{};
- index_t root{};
- index_t last{};
+ index_t parent_node_id{}; // root if parent_node_id == node_id
+ index_t node_id{};
 
-public:
- void clear();
- bool Valid(const std::string& Top) const;
- bool AddFirstNode(const Token& token, const BNF& bnf, const std::map<std::string, std::set<std::string>>& reverseBNF);
- std::vector<TreeNode> getParentTreeNode(const BNF& bnf, const std::map<std::string, std::set<std::string>>& reverseBNF);
- index_t GetLast();
- void AddRootNode(const TreeNode& newRootNode);
- void RemoveRootNode();
- std::vector<std::string> GetPath(std::string a, std::string b, const BNF& bnf, const std::map<std::string, std::set<std::string>>& reverseBNF);
- index_t AddNode(const std::string& name, const std::string& child_name, index_t parent_index, const BNF& bnf, const std::map<std::string, std::set<std::string>>& reverseBNF);
- void AddPath(const std::vector<std::string>& path, index_t current_index, const BNF& bnf, const std::map<std::string, std::set<std::string>>& reverseBNF);
- bool Add(const Token& token, const BNF& bnf, const std::map<std::string, std::set<std::string>>& reverseBNF);
- void Resolve(const BNF& bnf, const std::map<std::string, std::set<std::string>>& reverseBNF);
-
- void Dump();
+ std::string type;
+ index_t variant; // bnf[type][variant]
+ std::deque<std::string> alternative_types; // alternatives that we can consider if type fails. Discard after parsing!
+ std::vector<int32_t> child_ids; // < 0: terminal: token_id; >= 0: non-terminal: node_id; fill token by token
 };
 
 class Compiler
 {
 
 private:
+ // The result
+ index_t root_node_id{};
+ std::vector<TreeNode> nodes;
+ 
+ // Input
+ std::vector<std::string> tokens;
+
+ // Helper data
+ index_t tokens_used{0}; // number of tokens used, this is also the next token index to use
+
  const BNF &bnf;
  const std::string& Top;
 
- std::map<std::string, std::set<std::string>> ReverseBNF;
+ std::map<std::string, std::set<std::string>> ReverseBNF; // possible parent types of a given type
 
 public:
+ // Tree specific
+ void clear();
+ 
+ // Node specific
+ std::string GetTypeOfNode(index_t node_id) const;
+
+ index_t TrackBack();
+ 
+ void Validate(const std::string& Top, const BNF& bnf) const;
+
+ void Dump();
+
  Compiler(const BNF& bnf, const std::string& Top);
- Tree compile(std::vector<Token> Tokens);
+
+ std::pair<index_t, std::vector<TreeNode>> compile(std::vector<Token> Tokens);
 };
 
 } // namespace Gram