summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorMatthias Schiffer <mschiffer@universe-factory.net>2015-03-31 22:52:25 +0200
committerMatthias Schiffer <mschiffer@universe-factory.net>2015-03-31 23:40:44 +0200
commit3f1b701ad15458829468ce176ee6cecd16c4b420 (patch)
treef237e4925191a002adbcd4745a6288da84c3194a /src
parent342f927aace815c2b6e7903def14d4aca9bc2233 (diff)
downloadsolar-3f1b701ad15458829468ce176ee6cecd16c4b420.tar
solar-3f1b701ad15458829468ce176ee6cecd16c4b420.zip
generator: add actions and gotos for LR(0) parsers
Diffstat (limited to 'src')
-rw-r--r--src/generator.cpp79
-rw-r--r--src/generator.hpp19
-rw-r--r--src/parser_state.cpp2
-rw-r--r--src/parser_state.hpp6
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<item_t> generator_t::get_set(const std::string &nonterm) {
std::set<item_t> 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<item_t> *set) {
}
void generator_t::generate_itemsets() {
- std::queue<std::pair<std::set<item_t>, unsigned>> queue;
+ std::queue<std::pair<std::set<item_t>, size_t>> queue;
{
std::set<item_t> 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<item_t> &set) {
for (const item_t &item : set)
- print_item(item);
+ print_item(item, true);
}
-generator_t::generator_t(const std::set<item_t> &rules0) {
- for (item_t rule : rules0) {
- rules.emplace(rule.get_lhs(), rule);
+generator_t::generator_t(const std::vector<item_t> &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<item_t> *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<std::string, item_t> rules;
+ std::vector<item_t> rules;
+ std::map<item_t, size_t> rule_ids;
+ std::multimap<std::string, size_t> nonterms;
+
+ std::set<symbol_t> terminals;
+
std::multimap<symbol_t, item_t> items;
- std::map<std::set<item_t>, unsigned> itemsets;
- std::map<std::pair<unsigned, symbol_t>, unsigned> transitions;
+ std::map<std::set<item_t>, size_t> itemsets;
+
+ std::multimap<std::pair<unsigned, symbol_t>, std::pair<char, unsigned>> actions;
+ std::map<std::pair<unsigned, symbol_t>, unsigned> gotos;
void close_set(std::set<item_t> *set);
std::set<item_t> get_set(const std::string &nonterm);
- std::pair<std::map<std::set<item_t>, unsigned>::iterator, bool> add_set(const std::set<item_t> &set) {
+ std::pair<std::map<std::set<item_t>, size_t>::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_item(const item_t &item, bool point);
static void print_set(const std::set<item_t> &set);
public:
- generator_t(const std::set<item_t> &rules0);
+ generator_t(const std::vector<item_t> &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 <set>
-
namespace solar {
class parser_state_t {
private:
- std::set<item_t> rules;
+ std::vector<item_t> rules;
item_t current;
public:
parser_state_t() : current("") {}
- const std::set<item_t> & get_rules() const {
+ const std::vector<item_t> & get_rules() const {
return rules;
}