From 42b15c6bfad96151912501a7253521f86e4781cb Mon Sep 17 00:00:00 2001 From: Roland Reichwein Date: Sun, 9 Feb 2020 21:53:36 +0100 Subject: Fix compile error (WIP) --- grammer.cpp | 64 +++++++++++++++++++++++++++++++++------------------------- grammer.h | 16 +++++++-------- test-lexer.cpp | 2 +- 3 files changed, 46 insertions(+), 36 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& Compiler::getNodeExpectedChilds(node_id) +std::vector& 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& 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> alternatives; // only for valid elements from alternatives_set - std::vector child_ids; + std::vector 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> alternatives; // only for valid elements from alternatives_set - std::vector child_ids{size_t(1), old_root_node_id}; + std::vector 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 Compiler::traverse(lower, upper) +std::map Compiler::traverse(const std::string& lower, const std::string& upper) { std::map visited; // node, child std::deque> 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 alternatives; + std::deque> 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{}}); //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 Tokens) +std::pair> Compiler::compile(std::vector Tokens) { clear(); tokens = Tokens; @@ -391,16 +400,17 @@ Tree Compiler::compile(std::vector 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>{root_node_id, nodes}; } diff --git a/grammer.h b/grammer.h index 0e9ed32..4f0d235 100644 --- a/grammer.h +++ b/grammer.h @@ -30,12 +30,12 @@ private: std::vector nodes; // Input - std::vector tokens; + std::vector tokens; // Helper data index_t tokens_used{0}; // number of tokens used, this is also the next token index to use - const BNF &bnf; + BNF &bnf; // not const for access via operator[] const std::string& Top; std::map> ReverseBNF; // possible parent types of a given type @@ -47,26 +47,26 @@ private: // Node specific std::string GetTypeOfNode(index_t node_id) const; bool IsRootNode(index_t node_id) const; - bool RootIsStartSymbol() const; + bool rootIsStartSymbol() const; bool AllTokensUsed() const; bool treeIsComplete() const; - std::vector& getNodeExpectedChilds(node_id); + std::vector& getNodeExpectedChilds(index_t node_id); bool subTreeIsComplete(index_t node_id, index_t& to_fill); size_t CommonPrefix(const std::vector& tokens, const std::vector& types); void AddFirstNode(); bool AddRootNode(); void RemoveLastNode(); void ChangeNodeType(); - index_t TrackBack(); + void TrackBack(); void Validate() const; - std::map traverse(lower, upper); + std::map traverse(const std::string& lower, const std::string& upper); std::vector GetPath(std::string upper, std::string lower); - index_t AddNode(const std::string& name, const std::string& child_type, index_t parent_index); + index_t AddNode(const std::string& child_type, index_t parent_index); void AddPath(const std::vector& path, index_t current_index); bool FillTree(); public: - Compiler(const BNF& bnf, const std::string& Top); + Compiler(BNF& bnf, const std::string& Top); std::pair> compile(std::vector Tokens); void DumpTree(); }; diff --git a/test-lexer.cpp b/test-lexer.cpp index 3a4ed2a..6733081 100644 --- a/test-lexer.cpp +++ b/test-lexer.cpp @@ -95,7 +95,7 @@ TEST_F(Test, BNF) { Gram::Compiler compiler(bnf, Top); auto Tree = compiler.compile(tokens); - Tree.Dump(); + compiler.DumpTree(); } int main(int argc, char* argv[]) { -- cgit v1.2.3