summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorMatthias Schiffer <mschiffer@universe-factory.net>2015-04-10 03:04:22 +0200
committerMatthias Schiffer <mschiffer@universe-factory.net>2015-04-10 03:04:22 +0200
commit8feccee75dadbf970b2fb402a8c624ed9b25f041 (patch)
tree897ed0229550ee72bdc69899432161a3dd696371 /src
parent70fc6ba8d2753492b2d4726f2718a2724bbf399a (diff)
downloadsolar-8feccee75dadbf970b2fb402a8c624ed9b25f041.tar
solar-8feccee75dadbf970b2fb402a8c624ed9b25f041.zip
generator_slr: implement first and follow set generation
Diffstat (limited to 'src')
-rw-r--r--src/generator_slr.cpp116
-rw-r--r--src/generator_slr.hpp22
-rw-r--r--src/symbol.hpp5
3 files changed, 142 insertions, 1 deletions
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("");
+ }
};
}