From 8feccee75dadbf970b2fb402a8c624ed9b25f041 Mon Sep 17 00:00:00 2001
From: Matthias Schiffer <mschiffer@universe-factory.net>
Date: Fri, 10 Apr 2015 03:04:22 +0200
Subject: generator_slr: implement first and follow set generation

---
 src/generator_slr.cpp | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++
 src/generator_slr.hpp |  22 +++++++++-
 src/symbol.hpp        |   5 +++
 3 files changed, 142 insertions(+), 1 deletion(-)

diff --git a/src/generator_slr.cpp b/src/generator_slr.cpp
index 69bb1a0..a8e081a 100644
--- a/src/generator_slr.cpp
+++ b/src/generator_slr.cpp
@@ -25,3 +25,119 @@
 
 
 #include "generator_slr.hpp"
+
+
+namespace solar {
+
+void generator_slr_t::generate_first_sets() {
+	std::set<item_t> items;
+
+	for (const std::string &nonterm : get_nonterminals())
+		first_sets.insert(std::make_pair(nonterm, std::set<symbol_t>()));
+
+	for (const rule_t &rule : get_grammar().rules)
+		items.insert(rule.item);
+
+	bool changed = true;
+	while (changed) {
+		changed = false;
+
+		for (const item_t &item : items) {
+			std::set<symbol_t> &current = first_sets[item.get_lhs()];
+
+			if (!item.has_next()) {
+				changed = changed || current.insert(symbol_t::empty()).second;
+				continue;
+			}
+
+			const symbol_t &sym = item.get_next_symbol();
+
+			if (sym.get_type() != SYMBOL_TYPE_NONTERM) {
+				changed = changed || current.insert(sym).second;
+				continue;
+			}
+
+			for (const symbol_t &sym2 : first_sets[sym.get_value()]) {
+				changed = changed || current.insert(sym2).second;
+
+				if (sym2 == symbol_t::empty()) {
+					item_t next = item;
+					next.shift();
+					changed = changed || items.insert(next).second;
+				}
+			}
+		}
+	}
+}
+
+void generator_slr_t::generate_follow_sets() {
+	generate_first_sets();
+
+	for (const std::string &nonterm : get_nonterminals())
+		follow_sets.insert(std::make_pair(nonterm, std::set<symbol_t>()));
+
+	follow_sets[""].insert(symbol_t::empty());
+
+	bool changed = true;
+
+	while (changed) {
+		changed = false;
+
+		for (const rule_t &rule : get_grammar().rules) {
+			for (item_t item = rule.item; item.has_next(); item.shift()) {
+				const symbol_t &sym = item.get_next_symbol();
+				if (sym.get_type() != SYMBOL_TYPE_NONTERM)
+					continue;
+
+				const std::set<symbol_t> &lhs = follow_sets[item.get_lhs()];
+				std::set<symbol_t> &rhs = follow_sets[sym.get_value()];
+
+				item_t next = item;
+				next.shift();
+
+				bool next_empty = false;
+
+				if (next.has_next()) {
+					const symbol_t &next_sym = next.get_next_symbol();
+
+					if (next_sym.get_type() == SYMBOL_TYPE_NONTERM) {
+						for (const symbol_t &sym2 : first_sets[next_sym.get_value()]) {
+							if (sym2 == symbol_t::empty())
+								next_empty = true;
+							else
+								changed = changed || rhs.insert(sym2).second;
+						}
+					}
+					else {
+						changed = changed || rhs.insert(next_sym).second;
+					}
+				}
+				else {
+					next_empty = true;
+				}
+
+				if (next_empty) {
+					for (const symbol_t &sym2 : lhs)
+						changed = changed || rhs.insert(sym2).second;
+				}
+			}
+		}
+	}
+}
+
+bool generator_slr_t::has_reduce_conflict(size_t from, const symbol_t &sym) {
+	return reductions.count(std::make_pair(from, sym));
+}
+
+void generator_slr_t::add_reduction(size_t from, size_t rule) {
+	const item_t &item = get_grammar().rules[rule].item;
+	for (const symbol_t sym : follow_sets[item.get_lhs()]) {
+		if (get_shifts().count(std::make_pair(from, sym)))
+			throw conflict_error("shift/reduce conflict");
+
+		if (!reductions.insert(std::make_pair(std::make_pair(from, sym), rule)).second)
+			throw conflict_error("reduce/reduce conflict");
+	}
+}
+
+}
diff --git a/src/generator_slr.hpp b/src/generator_slr.hpp
index 9a2cd42..53ea89d 100644
--- a/src/generator_slr.hpp
+++ b/src/generator_slr.hpp
@@ -32,8 +32,28 @@
 namespace solar {
 
 class generator_slr_t : public generator_t {
+private:
+	std::map<std::pair<size_t, symbol_t>, size_t> reductions;
+
+	std::map<std::string, std::set<symbol_t>> first_sets;
+	std::map<std::string, std::set<symbol_t>> follow_sets;
+
+	void generate_first_sets();
+	void generate_follow_sets();
+
+protected:
+	virtual bool has_reduce_conflict(size_t from, const symbol_t &sym);
+	virtual void add_reduction(size_t from, size_t rule);
+
 public:
-	generator_slr_t(const grammar_t &grammar) : generator_t(grammar) {}
+	const std::map<std::pair<size_t, symbol_t>, size_t> & get_reductions() const {
+		return reductions;
+	}
+
+	generator_slr_t(const grammar_t &grammar) : generator_t(grammar) {
+		generate_follow_sets();
+		generate();
+	}
 };
 
 }
diff --git a/src/symbol.hpp b/src/symbol.hpp
index 0e79eb6..e468d37 100644
--- a/src/symbol.hpp
+++ b/src/symbol.hpp
@@ -49,6 +49,7 @@ struct symbol_t : public std::tuple<symbol_type_t, std::string>  {
 		return std::get<1>(*this);
 	}
 
+
 	static symbol_t make_nonterm(const std::string &value) {
 		return symbol_t(SYMBOL_TYPE_NONTERM, value);
 	}
@@ -61,6 +62,10 @@ struct symbol_t : public std::tuple<symbol_type_t, std::string>  {
 		char v[2] = {char(value), 0};
 		return symbol_t(SYMBOL_TYPE_CHAR, v);
 	}
+
+	static symbol_t empty() {
+		return make_term("");
+	}
 };
 
 }
-- 
cgit v1.2.3