summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorMatthias Schiffer <mschiffer@universe-factory.net>2015-04-06 00:22:44 +0200
committerMatthias Schiffer <mschiffer@universe-factory.net>2015-04-06 00:22:44 +0200
commit6fb60a72012f97f846477eb370d1a0706b1b4bc2 (patch)
tree5cc40d0af6a14f3c2b57434419b2fb73bbacf2ac /src
parent696d94d796f76d1d83c740b184f0cf8b9cbfc9d3 (diff)
downloadsolar-6fb60a72012f97f846477eb370d1a0706b1b4bc2.tar
solar-6fb60a72012f97f846477eb370d1a0706b1b4bc2.zip
generator: detect LR(0) conflicts
Diffstat (limited to 'src')
-rw-r--r--src/generator.cpp8
-rw-r--r--src/generator.hpp31
2 files changed, 35 insertions, 4 deletions
diff --git a/src/generator.cpp b/src/generator.cpp
index 6198aba..d63b859 100644
--- a/src/generator.cpp
+++ b/src/generator.cpp
@@ -97,9 +97,9 @@ void generator_t::generate_itemsets() {
auto added = add_set(entry.second);
if (entry.first.get_type() == SYMBOL_TYPE_NONTERM)
- gotos.emplace(std::make_pair(cur.second, entry.first.get_value()), added.first->second);
+ add_goto(cur.second, entry.first.get_value(), added.first->second);
else
- shifts.emplace(std::make_pair(cur.second, entry.first), added.first->second);
+ add_shift(cur.second, entry.first, added.first->second);
if (added.second)
queue.push(*added.first);
@@ -109,9 +109,9 @@ void generator_t::generate_itemsets() {
auto it = rule_ids.find(item);
if (it != rule_ids.end()) {
if (it->second)
- reductions.emplace(cur.second, it->second);
+ add_reduction(cur.second, it->second);
else
- shifts.emplace(std::make_pair(cur.second, symbol_t::make_nonterm("")), 0);
+ add_shift(cur.second, symbol_t::make_nonterm(""), 0);
}
}
}
diff --git a/src/generator.hpp b/src/generator.hpp
index 8178bbd..47ef6bf 100644
--- a/src/generator.hpp
+++ b/src/generator.hpp
@@ -28,6 +28,7 @@
#include "item.hpp"
+#include <stdexcept>
#include <set>
#include <map>
@@ -35,6 +36,13 @@
namespace solar {
class generator_t {
+public:
+ class conflict_error : public std::runtime_error {
+ public:
+ explicit conflict_error(const std::string& what_arg) : std::runtime_error(what_arg) {}
+ explicit conflict_error(const char* what_arg) : std::runtime_error(what_arg) {}
+ };
+
private:
std::vector<std::pair<item_t, std::string>> rules;
std::map<item_t, size_t> rule_ids;
@@ -49,6 +57,8 @@ private:
std::map<size_t, size_t> reductions;
std::map<std::pair<size_t, std::string>, size_t> gotos;
+ std::set<size_t> shift_conflicts;
+
void close_set(std::set<item_t> *set);
std::set<item_t> get_set(const std::string &nonterm);
@@ -56,6 +66,27 @@ private:
return itemsets.emplace(set, itemsets.size());
}
+ void add_reduction(size_t from, size_t to) {
+ if (reductions.count(from))
+ throw conflict_error("reduce/reduce conflict");
+ if (shift_conflicts.count(from))
+ throw conflict_error("shift/reduce conflict");
+
+ reductions.emplace(from, to);
+ }
+
+ void add_shift(size_t from, const symbol_t &sym, size_t to) {
+ if (reductions.count(from))
+ throw conflict_error("shift/reduce conflict");
+
+ shift_conflicts.insert(from);
+ shifts.emplace(std::make_pair(from, sym), to);
+ }
+
+ void add_goto(size_t from, const std::string &nonterm, size_t to) {
+ gotos.emplace(std::make_pair(from, nonterm), to);
+ }
+
void generate_itemsets();
public: