...

3 files changed, 45 insertions, 0 deletions

diff --git a/include/cru/parse/Grammar.hpp b/include/cru/parse/Grammar.hpp
index 5935e703..42649c30 100644
--- a/include/cru/parse/Grammar.hpp
+++ b/include/cru/parse/Grammar.hpp
@@ -35,6 +35,11 @@ class Grammar : public Object {
     return productions_;
   }
 
+  Grammar* Clone() const;
+
+ public:  // Algorithms
+  void EliminateLeftRecursions();
+
  private:
   Nonterminal* start_symbol_;
   std::vector<Terminal*> terminals_;
diff --git a/include/cru/parse/Production.hpp b/include/cru/parse/Production.hpp
index bd05a8c4..8a1331b9 100644
--- a/include/cru/parse/Production.hpp
+++ b/include/cru/parse/Production.hpp
@@ -20,12 +20,19 @@ class Production : public Object {
  public:
   Grammar* GetGrammar() const { return grammar_; }
 
+  String GetName() const { return name_; }
+  void SetName(String name) { name_ = std::move(name); }
+
   Nonterminal* GetLeft() const { return left_; }
   void SetLeft(Nonterminal* left);
 
   const std::vector<Symbol*>& GetRight() const { return right_; }
   void SetRight(std::vector<Symbol*> right);
 
+  bool IsLeftRecursion() const {
+    return !right_.empty() && left_ == right_.front();
+  }
+
  private:
   Grammar* grammar_;
   String name_;
diff --git a/src/parse/Grammar.cpp b/src/parse/Grammar.cpp
index a2dd14d4..3cf43237 100644
--- a/src/parse/Grammar.cpp
+++ b/src/parse/Grammar.cpp
@@ -2,6 +2,8 @@
 #include "cru/parse/Symbol.hpp"
 
 #include <algorithm>
+#include <iterator>
+#include <unordered_map>
 
 namespace cru::parse {
 Grammar::Grammar() {}
@@ -69,4 +71,35 @@ bool Grammar::RemoveProduction(Production* production) {
   return true;
 }
 
+Grammar* Grammar::Clone() const {
+  Grammar* g = new Grammar();
+
+  std::unordered_map<Symbol*, Symbol*> symbol_map;
+
+  for (auto old_terminal : terminals_) {
+    auto new_terminal = g->CreateTerminal(old_terminal->GetName());
+    symbol_map.emplace(old_terminal, new_terminal);
+  }
+
+  for (auto old_nonterminal : nonterminals_) {
+    auto new_nonterminal = g->CreateNonterminal(old_nonterminal->GetName());
+    symbol_map.emplace(old_nonterminal, new_nonterminal);
+  }
+
+  for (auto old_production : productions_) {
+    std::vector<Symbol*> new_right;
+    std::transform(old_production->GetRight().cbegin(),
+                   old_production->GetRight().cend(),
+                   std::back_inserter(new_right),
+                   [&symbol_map](Symbol* old) { return symbol_map[old]; });
+
+    g->CreateProduction(
+        old_production->GetName(),
+        static_cast<Nonterminal*>(symbol_map[old_production->GetLeft()]),
+        std::move(new_right));
+  }
+
+  return g;
+}
+
 }  // namespace cru::parse