From 3f1b701ad15458829468ce176ee6cecd16c4b420 Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Tue, 31 Mar 2015 22:52:25 +0200 Subject: generator: add actions and gotos for LR(0) parsers --- src/generator.cpp | 79 ++++++++++++++++++++++++++++++++++++++++------------ src/generator.hpp | 19 +++++++++---- src/parser_state.cpp | 2 +- src/parser_state.hpp | 6 ++-- 4 files changed, 77 insertions(+), 29 deletions(-) diff --git a/src/generator.cpp b/src/generator.cpp index e8fd07b..ec5d1f8 100644 --- a/src/generator.cpp +++ b/src/generator.cpp @@ -34,9 +34,9 @@ namespace solar { std::set generator_t::get_set(const std::string &nonterm) { std::set set; - auto entries = rules.equal_range(nonterm); + auto entries = nonterms.equal_range(nonterm); for (auto entry = entries.first; entry != entries.second; ++entry) - set.insert(entry->second); + set.insert(rules[entry->second]); return set; } @@ -63,7 +63,7 @@ void generator_t::close_set(std::set *set) { } void generator_t::generate_itemsets() { - std::queue, unsigned>> queue; + std::queue, size_t>> queue; { std::set set0 = get_set(""); @@ -95,11 +95,27 @@ void generator_t::generate_itemsets() { close_set(&entry.second); auto added = add_set(entry.second); - transitions.emplace(std::make_pair(cur.second, entry.first), added.first->second); + + if (entry.first.get_type() == SYMBOL_TYPE_NONTERM) + gotos.emplace(std::make_pair(cur.second, entry.first), added.first->second); + else + actions.emplace(std::make_pair(cur.second, entry.first), std::make_pair('s', added.first->second)); if (added.second) queue.push(*added.first); } + + for (const item_t &item : cur.first) { + auto it = rule_ids.find(item); + if (it != rule_ids.end()) { + //if (it->second) { + // for (const symbol_t &term : terminals) + // transitions.emplace(std::make_pair(cur.second, term), std::make_pair('r', it->second)); + //} + + actions.emplace(std::make_pair(cur.second, symbol_t::make_term("")), std::make_pair('r', it->second)); + } + } } } @@ -114,11 +130,11 @@ void generator_t::print_symbol(const symbol_t &sym) { } } -void generator_t::print_item(const item_t &item) { +void generator_t::print_item(const item_t &item, bool point) { printf("%s |=", item.get_lhs().c_str()); for (size_t i = 0; i <= item.get_rhs().size(); i++) { - if (i == item.get_point()) + if (i == item.get_point() && point) printf(" ."); if (i == item.get_rhs().size()) @@ -133,37 +149,64 @@ void generator_t::print_item(const item_t &item) { void generator_t::print_set(const std::set &set) { for (const item_t &item : set) - print_item(item); + print_item(item, true); } -generator_t::generator_t(const std::set &rules0) { - for (item_t rule : rules0) { - rules.emplace(rule.get_lhs(), rule); +generator_t::generator_t(const std::vector &rules0) : rules(rules0) { + for (size_t i = 0; i < rules.size(); i++) { + item_t rule = rules[i]; + + nonterms.emplace(rule.get_lhs(), i); while (rule.has_next()) { - items.emplace(rule.get_next_symbol(), rule); + const symbol_t &sym = rule.get_next_symbol(); + items.emplace(sym, rule); + + if (sym.get_type() != SYMBOL_TYPE_NONTERM) + terminals.insert(sym); + rule.shift(); } + + rule_ids.emplace(rule, i); } generate_itemsets(); + printf("Rules:\n"); + for (size_t i = 0; i < rules.size(); i++) { + printf("(%u) ", unsigned(i)); + print_item(rules[i], false); + } + printf("\n"); + const std::set *setlist[itemsets.size()]; for (const auto &entry : itemsets) setlist[entry.second] = &entry.first; - for (unsigned i = 0; i < itemsets.size(); i++) { - printf("Item %u:\n", i); + for (size_t i = 0; i < itemsets.size(); i++) { + printf("Item %u:\n", unsigned(i)); 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); + printf("Actions:\n"); + for (const auto &a : actions) { + printf("%u ", unsigned(a.first.first)); + + if (a.second.second) { + print_symbol(a.first.second); + printf(" -> %c%u\n", a.second.first, unsigned(a.second.second)); + } + else { + printf("$ -> acc\n"); + } } + printf("\n"); + + printf("Gotos:\n"); + for (const auto &g : gotos) + printf("%u %s -> %u\n", unsigned(g.first.first), g.first.second.get_value().c_str(), unsigned(g.second)); } } diff --git a/src/generator.hpp b/src/generator.hpp index b901785..955739f 100644 --- a/src/generator.hpp +++ b/src/generator.hpp @@ -36,26 +36,33 @@ namespace solar { class generator_t { private: - std::multimap rules; + std::vector rules; + std::map rule_ids; + std::multimap nonterms; + + std::set terminals; + std::multimap items; - std::map, unsigned> itemsets; - std::map, unsigned> transitions; + std::map, size_t> itemsets; + + std::multimap, std::pair> actions; + std::map, unsigned> gotos; void close_set(std::set *set); std::set get_set(const std::string &nonterm); - std::pair, unsigned>::iterator, bool> add_set(const std::set &set) { + std::pair, size_t>::iterator, bool> add_set(const std::set &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_item(const item_t &item, bool point); static void print_set(const std::set &set); public: - generator_t(const std::set &rules0); + generator_t(const std::vector &rules0); }; } diff --git a/src/parser_state.cpp b/src/parser_state.cpp index 94f9c93..f7b9574 100644 --- a/src/parser_state.cpp +++ b/src/parser_state.cpp @@ -53,7 +53,7 @@ void parser_state_t::add_rule_terminal(unsigned char term) { } void parser_state_t::add_rule() { - rules.emplace(current); + rules.emplace_back(current); } } diff --git a/src/parser_state.hpp b/src/parser_state.hpp index b516dee..3798586 100644 --- a/src/parser_state.hpp +++ b/src/parser_state.hpp @@ -28,21 +28,19 @@ #include "item.hpp" -#include - namespace solar { class parser_state_t { private: - std::set rules; + std::vector rules; item_t current; public: parser_state_t() : current("") {} - const std::set & get_rules() const { + const std::vector & get_rules() const { return rules; } -- cgit v1.2.3