summaryrefslogtreecommitdiffhomepage
path: root/grammer.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'grammer.cpp')
-rw-r--r--grammer.cpp64
1 files changed, 37 insertions, 27 deletions
diff --git a/grammer.cpp b/grammer.cpp
index 186a4bd..7b26e02 100644
--- a/grammer.cpp
+++ b/grammer.cpp
@@ -13,12 +13,14 @@ void Compiler::clear() {
std::string Compiler::GetTypeOfNode(index_t node_id) const
{
+ if (node_id >= nodes.size())
+ throw std::runtime_error("GetTypeOfNode(): node_id="s + std::to_string(node_id) + ", nodes.size()="s + std::to_string(nodes.size()));
return nodes[node_id].type;
}
bool Compiler::IsRootNode(index_t node_id) const
{
- auto node& {nodes[node_id]};
+ auto& node {nodes[node_id]};
return node.parent_node_id == node.node_id;
}
@@ -46,12 +48,17 @@ void Compiler::Validate() const
void Compiler::DumpTree()
{
std::cout << "=== Tree =====================================" << std::endl;
- for (const auto& i : nodes) {
- std::cout << i.type << std::endl;
+ std::cout << "root_node_id=" << root_node_id << std::endl;
+ for (const auto& node : nodes) {
+ std::cout << node.type << "(" << node.node_id << "): ";
+ for (const auto& child : node.child_ids) {
+ std::cout << " " << child;
+ }
+ std::cout << std::endl;
}
}
-bool Compiler::RootIsStartSymbol() const
+bool Compiler::rootIsStartSymbol() const
{
return GetTypeOfNode(root_node_id) == Top;
}
@@ -82,10 +89,10 @@ bool Compiler::AllTokensUsed() const
bool Compiler::treeIsComplete() const
{
- return RootIsStartSymbol() && AllTokensUsed();
+ return nodes.size() > 0 && rootIsStartSymbol() && AllTokensUsed();
}
-std::vector<std::string>& Compiler::getNodeExpectedChilds(node_id)
+std::vector<std::string>& Compiler::getNodeExpectedChilds(index_t node_id)
{
std::string& type = nodes[node_id].type;
index_t& variant = nodes[node_id].variant;
@@ -95,6 +102,8 @@ std::vector<std::string>& Compiler::getNodeExpectedChilds(node_id)
// returns true if all childs are filled, recursively. Else false with to_fill as hint to node to fill
bool Compiler::subTreeIsComplete(index_t node_id, index_t& to_fill)
{
+ std::cout << "DEBUG: " << node_id << " " << nodes.size() << std::endl;
+ DumpTree();
for (const auto& i : nodes[node_id].child_ids) {
if (!ChildIdIsToken(i)) { // consider subtrees
if (!subTreeIsComplete(i, to_fill))
@@ -130,7 +139,7 @@ void Compiler::AddFirstNode()
std::string node_type;
index_t node_variant;
std::deque<std::pair<std::string, index_t>> alternatives; // only for valid elements from alternatives_set
- std::vector<index_t> child_ids;
+ std::vector<int32_t> child_ids;
for (const auto& type : alternatives_set) {
const auto& variants{bnf[type]};
@@ -152,7 +161,7 @@ void Compiler::AddFirstNode()
if (node_type == "") // no matching type found
throw std::runtime_error("Syntax error on first token: "s + child_type + " ("s + tokens[0].value + ")"s);
- nodes.emplace_back({0, 0, node_type, node_variant, alternatives, child_ids});
+ nodes.emplace_back(TreeNode{0, 0, node_type, node_variant, alternatives, child_ids});
tokens_used = child_ids.size();
}
@@ -175,7 +184,7 @@ bool Compiler::AddRootNode()
std::string node_type;
index_t node_variant;
std::deque<std::pair<std::string, index_t>> alternatives; // only for valid elements from alternatives_set
- std::vector<index_t> child_ids{size_t(1), old_root_node_id};
+ std::vector<int32_t> child_ids{size_t(1), ChildIdFromTokenId(old_root_node_id)};
for (const auto& type : alternatives_set) {
const auto& variants{bnf[type]};
@@ -197,7 +206,7 @@ bool Compiler::AddRootNode()
// now add!
nodes[old_root_node_id].parent_node_id = new_root_node_id;
root_node_id = new_root_node_id;
- nodes.emplace_back({root_node_id, root_node_id, node_type, node_variant, alternatives, child_ids});
+ nodes.emplace_back(TreeNode{root_node_id, root_node_id, node_type, node_variant, alternatives, child_ids});
// keep tokens_used as is
}
@@ -223,9 +232,9 @@ void Compiler::RemoveLastNode()
} else if (node.child_ids.empty()) { // No children -> remove leaf
// We have a parent, otherwise we would have taken previous branch
TreeNode& parent {nodes[node.parent_node_id]};
- if (parent.child_ids.empty() || parent.child_ids.last() != node_id)
+ if (parent.child_ids.empty() || parent.child_ids.back() != node_id)
throw std::runtime_error("Backtrack: Bad child nodes"); // ICE
- parent.childs_ids.pop_back();
+ parent.child_ids.pop_back();
nodes.pop_back();
} else { // In the middle
throw std::runtime_error("Backtrack in the middle of the tree."); // ICE
@@ -236,7 +245,6 @@ void Compiler::RemoveLastNode()
void Compiler::ChangeNodeType()
{
TreeNode& node {nodes.back()};
- index_t node_id = node.node_id;
if (node.alternatives.empty())
throw std::runtime_error("No alternatives found during Backtrack"); // ICE
@@ -253,7 +261,7 @@ void Compiler::ChangeNodeType()
void Compiler::TrackBack()
{
// Search backwards for alternatives: last node with alternatives (variant or alt. token)
- while (!nodes.empty() && nodes.last().alternatives.empty()) {
+ while (!nodes.empty() && nodes.back().alternatives.empty()) {
RemoveLastNode();
}
@@ -271,25 +279,26 @@ void Compiler::TrackBack()
// breadth-first search
// return: node, child
-std::map<std::string, std::string> Compiler::traverse(lower, upper)
+std::map<std::string, std::string> Compiler::traverse(const std::string& lower, const std::string& upper)
{
std::map<std::string, std::string> visited; // node, child
std::deque<std::pair<std::string, std::string>> todo{{lower, ""}}; // node, child
while (!todo.empty()) {
auto& [current_node, current_child] = todo.front();
+ std::string& current_node2{current_node}; // workaround for lambda capture below (clang 8)
todo.pop_front();
auto it {visited.find(current_node)};
if (it == visited.end()) { // not visited, yet: visit now
- auto parents_it {reverseBNF.find(current_node)};
+ auto parents_it {ReverseBNF.find(current_node)};
- if (parents_it != reverseBNF.end()) {
+ if (parents_it != ReverseBNF.end()) {
auto& parents {parents_it->second};
visited[current_node] = current_child;
- std::for_each(parents.begin(), parents.end(), [&](const auto&x) {todo.emplace_back(x, current_node);});
+ std::for_each(parents.begin(), parents.end(), [&](const auto&x) {todo.emplace_back(x, current_node2);});
}
}
}
@@ -328,7 +337,7 @@ index_t Compiler::AddNode(const std::string& child_type, index_t parent_index)
parent.child_ids.push_back(index);
index_t variant;
- std::deque<std::string> alternatives;
+ std::deque<std::pair<std::string, index_t>> alternatives;
const auto& lists { bnf[parent.type] };
bool found{false};
@@ -343,7 +352,7 @@ index_t Compiler::AddNode(const std::string& child_type, index_t parent_index)
}
}
- nodes.emplace_back({parent_index, index, child_type, variant, alternatives, {}});
+ nodes.emplace_back(TreeNode{parent_index, index, child_type, variant, alternatives, std::vector<int32_t>{}});
//root stays, tokens_used stays
return index;
@@ -368,7 +377,7 @@ bool Compiler::FillTree()
while (!subTreeIsComplete(root_node_id, to_fill)) {
auto& node {nodes[to_fill]};
- auto list = GetPath(bnf[node.type][node.variant][node.child_ids.size()], tokens[tokens_used]);
+ auto list = GetPath(bnf[node.type][node.variant][node.child_ids.size()], tokens[tokens_used].type);
if (list.size() > 0) {
AddPath(list, to_fill);
} else {
@@ -378,11 +387,11 @@ bool Compiler::FillTree()
return true;
}
-Compiler::Compiler(const BNF& bnf, const std::string& Top): bnf(bnf), Top(Top), ReverseBNF{Reverse(bnf)}
+Compiler::Compiler(BNF& bnf, const std::string& Top): bnf(bnf), Top(Top), ReverseBNF{Reverse(bnf)}
{
}
-Tree Compiler::compile(std::vector<Token> Tokens)
+std::pair<index_t, std::vector<TreeNode>> Compiler::compile(std::vector<Token> Tokens)
{
clear();
tokens = Tokens;
@@ -391,16 +400,17 @@ Tree Compiler::compile(std::vector<Token> Tokens)
throw std::runtime_error("No tokens!");
while (!treeIsComplete()) {
- if (!FillTree())
+ if (!FillTree()) {
TrackBack();
- else if (!AddRootNode())
+ } else if (!AddRootNode()) {
TrackBack();
- else if (!FillTree())
+ } else if (!FillTree()) {
TrackBack();
+ }
}
Validate();
- return tree;
+ return std::pair<index_t, std::vector<TreeNode>>{root_node_id, nodes};
}