summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/generator.cpp44
-rw-r--r--src/generator.hpp7
2 files changed, 33 insertions, 18 deletions
diff --git a/src/generator.cpp b/src/generator.cpp
index 7f5f5e9..e8fd07b 100644
--- a/src/generator.cpp
+++ b/src/generator.cpp
@@ -63,23 +63,22 @@ void generator_t::close_set(std::set<item_t> *set) {
}
void generator_t::generate_itemsets() {
- std::queue<std::set<item_t>> queue;
+ std::queue<std::pair<std::set<item_t>, unsigned>> queue;
{
std::set<item_t> set0 = get_set("");
close_set(&set0);
- add_set(set0);
- queue.push(set0);
+ queue.push(*add_set(set0).first);
}
for (; !queue.empty(); queue.pop()) {
- const std::set<item_t> &cur = queue.front();
+ const auto &cur = queue.front();
const std::set<item_t> empty_set;
std::map<symbol_t, std::set<item_t>> new_sets;
- for (const item_t &item : cur) {
+ for (const item_t &item : cur.first) {
if (!item.has_next())
continue;
@@ -95,12 +94,26 @@ void generator_t::generate_itemsets() {
for (auto &entry : new_sets) {
close_set(&entry.second);
- if (add_set(entry.second).first)
- queue.push(entry.second);
+ auto added = add_set(entry.second);
+ transitions.emplace(std::make_pair(cur.second, entry.first), added.first->second);
+
+ if (added.second)
+ queue.push(*added.first);
}
}
}
+void generator_t::print_symbol(const symbol_t &sym) {
+ switch (sym.get_type()) {
+ case SYMBOL_TYPE_CHAR:
+ printf("'%c'", sym.get_value()[0]);
+ break;
+
+ default:
+ printf("%s", sym.get_value().c_str());
+ }
+}
+
void generator_t::print_item(const item_t &item) {
printf("%s |=", item.get_lhs().c_str());
@@ -111,14 +124,8 @@ void generator_t::print_item(const item_t &item) {
if (i == item.get_rhs().size())
break;
- switch (item.get_rhs()[i].get_type()) {
- case SYMBOL_TYPE_CHAR:
- printf(" '%c'", item.get_rhs()[i].get_value()[0]);
- break;
-
- default:
- printf(" %s", item.get_rhs()[i].get_value().c_str());
- }
+ printf(" ");
+ print_symbol(item.get_rhs()[i]);
}
printf("\n");
@@ -150,6 +157,13 @@ generator_t::generator_t(const std::set<item_t> &rules0) {
print_set(*setlist[i]);
printf("\n");
}
+
+ printf("Transitions:\n");
+ for (const auto &t : transitions) {
+ printf("%u ", t.first.first);
+ print_symbol(t.first.second);
+ printf(" -> %u\n", t.second);
+ }
}
}
diff --git a/src/generator.hpp b/src/generator.hpp
index 880323b..b901785 100644
--- a/src/generator.hpp
+++ b/src/generator.hpp
@@ -39,17 +39,18 @@ private:
std::multimap<std::string, item_t> rules;
std::multimap<symbol_t, item_t> items;
std::map<std::set<item_t>, unsigned> itemsets;
+ std::map<std::pair<unsigned, symbol_t>, unsigned> transitions;
void close_set(std::set<item_t> *set);
std::set<item_t> get_set(const std::string &nonterm);
- std::pair<bool, unsigned> add_set(const std::set<item_t> &set) {
- auto ret = itemsets.emplace(set, itemsets.size());
- return std::make_pair(ret.second, ret.first->second);
+ std::pair<std::map<std::set<item_t>, unsigned>::iterator, bool> add_set(const std::set<item_t> &set) {
+ return itemsets.emplace(set, itemsets.size());
}
void generate_itemsets();
+ static void print_symbol(const symbol_t &sym);
static void print_item(const item_t &item);
static void print_set(const std::set<item_t> &set);