Fix compile error (WIP)

3 files changed, 46 insertions, 36 deletions

diff --git a/grammer.cpp b/grammer.cpp
index 186a4bd..7b26e02 100644
--- a/grammer.cpp
+++ b/grammer.cpp
@@ -13,12 +13,14 @@ void Compiler::clear() {
 
 std::string Compiler::GetTypeOfNode(index_t node_id) const
 {
+ if (node_id >= nodes.size())
+  throw std::runtime_error("GetTypeOfNode(): node_id="s + std::to_string(node_id) + ", nodes.size()="s + std::to_string(nodes.size()));
  return nodes[node_id].type;
 }
 
 bool Compiler::IsRootNode(index_t node_id) const
 {
- auto node& {nodes[node_id]};
+ auto& node {nodes[node_id]};
  return node.parent_node_id == node.node_id;
 }
 
@@ -46,12 +48,17 @@ void Compiler::Validate() const
 void Compiler::DumpTree()
 {
  std::cout << "=== Tree =====================================" << std::endl;
- for (const auto& i : nodes) {
-  std::cout << i.type << std::endl;
+ std::cout << "root_node_id=" << root_node_id << std::endl;
+ for (const auto& node : nodes) {
+  std::cout << node.type << "(" << node.node_id << "): ";
+  for (const auto& child : node.child_ids) {
+   std::cout << " " << child;
+  }
+  std::cout << std::endl;
  }
 }
 
-bool Compiler::RootIsStartSymbol() const
+bool Compiler::rootIsStartSymbol() const
 {
  return GetTypeOfNode(root_node_id) == Top;
 }
@@ -82,10 +89,10 @@ bool Compiler::AllTokensUsed() const
 
 bool Compiler::treeIsComplete() const
 {
- return RootIsStartSymbol() && AllTokensUsed();
+ return nodes.size() > 0 && rootIsStartSymbol() && AllTokensUsed();
 }
 
-std::vector<std::string>& Compiler::getNodeExpectedChilds(node_id)
+std::vector<std::string>& Compiler::getNodeExpectedChilds(index_t node_id)
 {
  std::string& type = nodes[node_id].type;
  index_t& variant = nodes[node_id].variant;
@@ -95,6 +102,8 @@ std::vector<std::string>& Compiler::getNodeExpectedChilds(node_id)
 // returns true if all childs are filled, recursively. Else false with to_fill as hint to node to fill
 bool Compiler::subTreeIsComplete(index_t node_id, index_t& to_fill)
 {
+     std::cout << "DEBUG: " << node_id << " " << nodes.size() << std::endl;
+     DumpTree();
  for (const auto& i : nodes[node_id].child_ids) {
   if (!ChildIdIsToken(i)) { // consider subtrees
    if (!subTreeIsComplete(i, to_fill))
@@ -130,7 +139,7 @@ void Compiler::AddFirstNode()
  std::string node_type;
  index_t node_variant;
  std::deque<std::pair<std::string, index_t>> alternatives; // only for valid elements from alternatives_set
- std::vector<index_t> child_ids;
+ std::vector<int32_t> child_ids;
 
  for (const auto& type : alternatives_set) {
   const auto& variants{bnf[type]};
@@ -152,7 +161,7 @@ void Compiler::AddFirstNode()
  if (node_type == "") // no matching type found
   throw std::runtime_error("Syntax error on first token: "s + child_type + " ("s + tokens[0].value + ")"s);
 
- nodes.emplace_back({0, 0, node_type, node_variant, alternatives, child_ids});
+ nodes.emplace_back(TreeNode{0, 0, node_type, node_variant, alternatives, child_ids});
 
  tokens_used = child_ids.size();
 }
@@ -175,7 +184,7 @@ bool Compiler::AddRootNode()
   std::string node_type;
   index_t node_variant;
   std::deque<std::pair<std::string, index_t>> alternatives; // only for valid elements from alternatives_set
-  std::vector<index_t> child_ids{size_t(1), old_root_node_id};
+  std::vector<int32_t> child_ids{size_t(1), ChildIdFromTokenId(old_root_node_id)};
 
   for (const auto& type : alternatives_set) {
    const auto& variants{bnf[type]};
@@ -197,7 +206,7 @@ bool Compiler::AddRootNode()
   // now add! 
   nodes[old_root_node_id].parent_node_id = new_root_node_id;
   root_node_id = new_root_node_id;
-  nodes.emplace_back({root_node_id, root_node_id, node_type, node_variant, alternatives, child_ids});
+  nodes.emplace_back(TreeNode{root_node_id, root_node_id, node_type, node_variant, alternatives, child_ids});
   // keep tokens_used as is
  }
 
@@ -223,9 +232,9 @@ void Compiler::RemoveLastNode()
  } else if (node.child_ids.empty()) { // No children -> remove leaf
   // We have a parent, otherwise we would have taken previous branch
   TreeNode& parent {nodes[node.parent_node_id]};
-  if (parent.child_ids.empty() || parent.child_ids.last() != node_id)
+  if (parent.child_ids.empty() || parent.child_ids.back() != node_id)
    throw std::runtime_error("Backtrack: Bad child nodes"); // ICE
-  parent.childs_ids.pop_back();
+  parent.child_ids.pop_back();
   nodes.pop_back();
  } else { // In the middle
   throw std::runtime_error("Backtrack in the middle of the tree."); // ICE
@@ -236,7 +245,6 @@ void Compiler::RemoveLastNode()
 void Compiler::ChangeNodeType()
 {
  TreeNode& node {nodes.back()};
- index_t node_id = node.node_id;
 
  if (node.alternatives.empty())
   throw std::runtime_error("No alternatives found during Backtrack"); // ICE
@@ -253,7 +261,7 @@ void Compiler::ChangeNodeType()
 void Compiler::TrackBack()
 {
  // Search backwards for alternatives: last node with alternatives (variant or alt. token)
- while (!nodes.empty() && nodes.last().alternatives.empty()) {
+ while (!nodes.empty() && nodes.back().alternatives.empty()) {
   RemoveLastNode();
  }
 
@@ -271,25 +279,26 @@ void Compiler::TrackBack()
 
 // breadth-first search
 // return: node, child
-std::map<std::string, std::string> Compiler::traverse(lower, upper)
+std::map<std::string, std::string> Compiler::traverse(const std::string& lower, const std::string& upper)
 {
  std::map<std::string, std::string> visited; // node, child
  std::deque<std::pair<std::string, std::string>> todo{{lower, ""}}; // node, child
  
  while (!todo.empty()) {
   auto& [current_node, current_child] = todo.front();
+  std::string& current_node2{current_node}; // workaround for lambda capture below (clang 8)
   todo.pop_front();
 
   auto it {visited.find(current_node)};
   if (it == visited.end()) { // not visited, yet: visit now
-   auto parents_it {reverseBNF.find(current_node)};
+   auto parents_it {ReverseBNF.find(current_node)};
 
-   if (parents_it != reverseBNF.end()) {
+   if (parents_it != ReverseBNF.end()) {
     auto& parents {parents_it->second};
     
     visited[current_node] = current_child;
     
-    std::for_each(parents.begin(), parents.end(), [&](const auto&x) {todo.emplace_back(x, current_node);});
+    std::for_each(parents.begin(), parents.end(), [&](const auto&x) {todo.emplace_back(x, current_node2);});
    }
   }
  }
@@ -328,7 +337,7 @@ index_t Compiler::AddNode(const std::string& child_type, index_t parent_index)
  parent.child_ids.push_back(index);
 
  index_t variant;
- std::deque<std::string> alternatives;
+ std::deque<std::pair<std::string, index_t>> alternatives;
 
  const auto& lists { bnf[parent.type] };
  bool found{false};
@@ -343,7 +352,7 @@ index_t Compiler::AddNode(const std::string& child_type, index_t parent_index)
   }
  }
 
- nodes.emplace_back({parent_index, index, child_type, variant, alternatives, {}});
+ nodes.emplace_back(TreeNode{parent_index, index, child_type, variant, alternatives, std::vector<int32_t>{}});
  //root stays, tokens_used stays
 
  return index;
@@ -368,7 +377,7 @@ bool Compiler::FillTree()
 
  while (!subTreeIsComplete(root_node_id, to_fill)) {
   auto& node {nodes[to_fill]};
-  auto list = GetPath(bnf[node.type][node.variant][node.child_ids.size()], tokens[tokens_used]);
+  auto list = GetPath(bnf[node.type][node.variant][node.child_ids.size()], tokens[tokens_used].type);
   if (list.size() > 0) {
    AddPath(list, to_fill);
   } else {
@@ -378,11 +387,11 @@ bool Compiler::FillTree()
  return true;
 }
 
-Compiler::Compiler(const BNF& bnf, const std::string& Top): bnf(bnf), Top(Top), ReverseBNF{Reverse(bnf)}
+Compiler::Compiler(BNF& bnf, const std::string& Top): bnf(bnf), Top(Top), ReverseBNF{Reverse(bnf)}
 {
 }
 
-Tree Compiler::compile(std::vector<Token> Tokens)
+std::pair<index_t, std::vector<TreeNode>> Compiler::compile(std::vector<Token> Tokens)
 {
  clear();
  tokens = Tokens;
@@ -391,16 +400,17 @@ Tree Compiler::compile(std::vector<Token> Tokens)
   throw std::runtime_error("No tokens!");
 
  while (!treeIsComplete()) {
-  if (!FillTree())
+  if (!FillTree()) {
    TrackBack();
-  else if (!AddRootNode())
+  } else if (!AddRootNode()) {
    TrackBack();
-  else if (!FillTree())
+  } else if (!FillTree()) {
    TrackBack();
+  }
  }
 
  Validate();
 
- return tree;
+ return std::pair<index_t, std::vector<TreeNode>>{root_node_id, nodes};
 }
 
diff --git a/grammer.h b/grammer.h
index 0e9ed32..4f0d235 100644
--- a/grammer.h
+++ b/grammer.h
@@ -30,12 +30,12 @@ private:
  std::vector<TreeNode> nodes;
  
  // Input
- std::vector<std::string> tokens;
+ std::vector<Token> tokens;
 
  // Helper data
  index_t tokens_used{0}; // number of tokens used, this is also the next token index to use
 
- const BNF &bnf;
+ BNF &bnf; // not const for access via operator[]
  const std::string& Top;
 
  std::map<std::string, std::set<std::string>> ReverseBNF; // possible parent types of a given type
@@ -47,26 +47,26 @@ private:
  // Node specific
  std::string GetTypeOfNode(index_t node_id) const;
  bool IsRootNode(index_t node_id) const;
- bool RootIsStartSymbol() const;
+ bool rootIsStartSymbol() const;
  bool AllTokensUsed() const;
  bool treeIsComplete() const;
- std::vector<std::string>& getNodeExpectedChilds(node_id);
+ std::vector<std::string>& getNodeExpectedChilds(index_t node_id);
  bool subTreeIsComplete(index_t node_id, index_t& to_fill);
  size_t CommonPrefix(const std::vector<Token>& tokens, const std::vector<std::string>& types);
  void AddFirstNode();
  bool AddRootNode();
  void RemoveLastNode();
  void ChangeNodeType();
- index_t TrackBack();
+ void TrackBack();
  void Validate() const;
- std::map<std::string, std::string> traverse(lower, upper);
+ std::map<std::string, std::string> traverse(const std::string& lower, const std::string& upper);
  std::vector<std::string> GetPath(std::string upper, std::string lower);
- index_t AddNode(const std::string& name, const std::string& child_type, index_t parent_index);
+ index_t AddNode(const std::string& child_type, index_t parent_index);
  void AddPath(const std::vector<std::string>& path, index_t current_index);
  bool FillTree();
 
 public:
- Compiler(const BNF& bnf, const std::string& Top);
+ Compiler(BNF& bnf, const std::string& Top);
  std::pair<index_t, std::vector<TreeNode>> compile(std::vector<Token> Tokens);
  void DumpTree();
 };
diff --git a/test-lexer.cpp b/test-lexer.cpp
index 3a4ed2a..6733081 100644
--- a/test-lexer.cpp
+++ b/test-lexer.cpp
@@ -95,7 +95,7 @@ TEST_F(Test, BNF) {
  Gram::Compiler compiler(bnf, Top);
  auto Tree = compiler.compile(tokens);
 
- Tree.Dump();
+ compiler.DumpTree();
 }
 
 int main(int argc, char* argv[]) {