First working lexer

1 files changed, 128 insertions, 21 deletions

diff --git a/minicc.cpp b/minicc.cpp
index d147baa..b392195 100644
--- a/minicc.cpp
+++ b/minicc.cpp
@@ -3,6 +3,7 @@
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
+#include <algorithm>
 #include <deque>
 #include <map>
 #include <memory>
@@ -26,12 +27,6 @@ std::vector<std::string> split(std::string s)
  return result;
 }
 
-std::vector<PathElement> GetPath(std::string Token, BNF ReverseBNF, std::string Top, Terminals terminals = {}, std::vector<PathElement> PreviousPath = {})
-{
- throw std::runtime_error("Compile error");
- return {}; // TODO
-}
-
 auto Reverse(BNF bnf){
  std::map<std::string, std::set<std::string>> result;
 
@@ -53,7 +48,7 @@ auto Reverse(BNF bnf){
 using index_t = size_t;
 
 struct TreeNode {
- index_t parent;
+ index_t parent{};
  std::vector<index_t> childs; // fill char by char
  std::vector<std::string> child_names; // fill always
  std::string name;
@@ -97,26 +92,118 @@ public:
 
   auto reverseRule{reverseBNF.find(node_name)};
   if (reverseRule == reverseBNF.end())
-   throw std::runtime_error("Reverse rule not found: "s + node_name);
+   throw std::runtime_error("Reverse rule not found for "s + node_name);
 
-  std::vector<std::string> children; // default: no children for terminal
   auto rule{bnf.find(node_name)};
   if (rule != bnf.end()) { // multiple variants!
+   throw std::runtime_error("BNF rule for terminal symbol "s + node_name + " found."s);
+  }
+  nodes.emplace(root, TreeNode{0, std::vector<index_t>{}, std::vector<std::string>{}, node_name});
+  return true;
+ }
+
+ std::vector<TreeNode> getParentTreeNode(const BNF& bnf, const std::map<std::string, std::set<std::string>>& reverseBNF) {
+  std::vector<TreeNode> result; // default: empty
+
+  auto& root_name {nodes[root].name};
+  auto bnfParents {reverseBNF.find(root_name)};
+  if (bnfParents == reverseBNF.end())
+   return result;
+
+  for (const auto& parent_node_name : bnfParents->second) {
+   auto lists {bnf.at(parent_node_name)};
+   for (const auto& list : lists) {
+    if (list.size() > 0 && list[0] == root_name) {
+     TreeNode node{0, std::vector<index_t>{root}, list, parent_node_name};
+     result.push_back(node);
+    }
+   }
+  }
+
+  return result;
+ }
+
+ index_t GetLast() {
+  index_t result {root};
+
+  while(result != 0 && nodes[result].childs.size() >= 2) {
+   result = nodes[result].childs[nodes[result].childs.size() - 1];
+  }
+
+  return result;
+ }
+
+ void AddRootNode(const TreeNode& newRootNode) {
+  node_num++;
+  nodes[node_num] = newRootNode;
+  root = node_num;
+  last = node_num;
+ }
+
+ void RemoveRootNode() {
+  root = nodes[root].childs[0];
+  nodes.erase(node_num);
+  node_num--;
+  last = GetLast();
+ }
+
+ // Path from leaf to root
+ std::vector<std::string> GetPath(std::string a, std::string b, const BNF& bnf, const std::map<std::string, std::set<std::string>>& reverseBNF) {
+  std::vector<std::string> result;
+
+  while (a != b) {
+   auto parents {reverseBNF.find(a)};
+   if (parents == reverseBNF.end())
+    return {};
+
    bool hit{false};
-   for (const auto& i : rule->second) {
-    if (i.size() > 0 && i[0] == node_name) {
-     if (hit)
-      throw std::runtime_error("Multiple matching rules found for "s + node_name);
-     children = i;
-     hit = true;
+   for (const auto& parent : parents->second) {
+    for (const auto& list : bnf.at(parent)) {
+     if (list.size() > 0 && list[0] == a) {
+      if (!hit) {
+       result.push_back(a);
+       a = parent;
+       hit = true;
+      } else
+       throw std::runtime_error("Double match for "s + parent + "/"s + a);
+     }
     }
    }
-   if (!hit)
-    throw std::runtime_error("No matching rule found for "s + node_name);
   }
+  if (a == b) {
+   result.push_back(a);
+  }
+  return result;
+ }
 
-  nodes.emplace(root, TreeNode{0, std::vector<index_t>{}, children, node_name});
-  return true;
+ 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)
+ {
+  TreeNode& parent {nodes[parent_index]};
+  node_num++;
+  index_t index = node_num;
+  parent.childs.push_back(index);
+  std::vector<std::string> child_names;
+  auto rule {bnf.find(name)};
+  if (rule != bnf.end()) {
+   for (auto& list : rule->second) {
+    if (list.size() > 0 && list[0] == child_name)
+     child_names = list;
+   }
+  }
+  nodes.emplace(index, TreeNode{parent_index, {}, child_names, name});
+  //root stays
+  last = GetLast();
+
+  return index;
+ }
+
+ 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) {
+  for (int i = path.size() - 1; i >= 0; i--) {
+   std::string child_name;
+   if (i > 0)
+    child_name = path[i - 1];
+   current_index = AddNode(path[i], child_name, current_index, bnf, reverseBNF);
+  }
  }
 
  // try to add character to tree
@@ -131,11 +218,29 @@ public:
    while (current_index != 0) {
     TreeNode& node {nodes[current_index]};
     if (node.childs.size() < node.child_names.size()) { // partially filled node
-     throw std::runtime_error("TODO: partially filled node");
+     std::vector<std::string> list = GetPath(std::string(1, c), node.child_names[node.childs.size()], bnf, reverseBNF);
+     if (list.size() > 0) {
+      AddPath(list, current_index, bnf, reverseBNF);
+      return true;
+     } else {
+      return false; // The path a->b is not available via bnf
+     }
     }
     current_index = node.parent;
    }
-   throw std::runtime_error("TODO: need to add node");
+
+   // Add node at root
+
+   std::vector<TreeNode> parent_nodes = getParentTreeNode(bnf, reverseBNF);
+   if (parent_nodes.size() == 0)
+    throw std::runtime_error("Couldn't add new parent node.");
+
+   for (const auto &i : parent_nodes) {
+    AddRootNode(i);
+    if (Add(c, bnf, reverseBNF))
+     return true;
+    RemoveRootNode();
+   }
 
   }
   return false;
@@ -283,6 +388,7 @@ ProgramNode Compile(std::vector<std::string> Tokens, std::string Top, BNF bnf, T
 
  if (Tokens.size()){
   std::string Token = Tokens[0];
+#if 0
   auto Path = GetPath(Token, ReverseBNF, Top, terminals);
   if (Path.size()) {
    size_t Index{1};
@@ -292,6 +398,7 @@ ProgramNode Compile(std::vector<std::string> Tokens, std::string Top, BNF bnf, T
    }
   } else
    throw std::runtime_error("Invalid token: "s + Token);
+#endif
  } else
   throw std::runtime_error("No tokens!");