diff options
| -rw-r--r-- | TODO | 3 | ||||
| -rw-r--r-- | grammer.cpp | 46 | ||||
| -rw-r--r-- | grammer.h | 3 |
3 files changed, 24 insertions, 28 deletions
@@ -4,3 +4,6 @@ start symbol implicitly from bnf validate bnf: no empty types or values, or empty target lists + +map -> unordered_map +set -> unordered_set diff --git a/grammer.cpp b/grammer.cpp index 8f38e3e..07e527f 100644 --- a/grammer.cpp +++ b/grammer.cpp @@ -105,13 +105,10 @@ bool Compiler::subTreeIsComplete(index_t node_id, index_t& to_fill) return true; } -bool Compiler::StartsWith(const std::vector<Token>& tokens, const std::vector<std::string>& types) +size_t Compiler::CommonPrefix(const std::vector<Token>& tokens, const std::vector<std::string>& types) { - if (tokens.size() < types.size()) - return false; - auto [tokens_it, types_it] = std::mismatch(tokens.begin(), tokens.end(), types.begin(), types.end(), [](const Token& token, const std::string& s){ return token.type == s; }); - return types_it == types.end(); // no mismatch: tokens (types) start wit specified types list + return types_it - types.begin(); // a distance, 0 on no match } void Compiler::AddFirstNode() @@ -127,21 +124,22 @@ void Compiler::AddFirstNode() std::string node_type; index_t node_variant; - std::deque<std::string> alternatives; // only for valid elements from alternatives_set + std::deque<std::pair<std::string, index_t>> alternatives; // only for valid elements from alternatives_set std::vector<index_t> child_ids; for (const auto& type : alternatives_set) { const auto& variants{bnf[type]}; for (int i = 0; i < variants.size(); i++) { const std::vector<std::string> & variant{variants[i]}; - if (StartsWith(tokens, variant)) { // match - if (node_type == "") { + size_t common{}; + if ((common = CommonPrefix(tokens, variant)) > 0) { // match a common prefix + if (node_type == "") { // no match yet node_type = type; node_variant = i; - for (int token_id = 0; token_id < variant.size()) + for (int token_id = 0; token_id < common; token_id++) child_ids.push_back(ChildIdFromTokenId(token_id)); } else - alternatives.push_back(type); // duplicates possible: variants of same type! + alternatives.emplace_back(type, i); } } } @@ -172,7 +170,7 @@ bool Compiler::AddRootNode() std::string node_type; index_t node_variant; - std::deque<std::string> alternatives; // only for valid elements from alternatives_set + std::deque<std::pair<std::string, index_t>> alternatives; // only for valid elements from alternatives_set std::vector<index_t> child_ids{1, old_root_node_id}; for (const auto& type : alternatives_set) { @@ -184,12 +182,12 @@ bool Compiler::AddRootNode() node_type = type; node_variant = i; } else - alternatives.push_back(type); // duplicates possible: variants of same type + alternatives.emplace_back(type, i); // duplicates possible: variants of same type } } } - if (node_type == "") // no matching type found + if (node_type == "") // no matching type found (maybe backtrack possible?) return false; // now add! @@ -232,28 +230,22 @@ void ChangeNodeType() TreeNode& node {nodes.back()}; index_t node_id = node.node_id; - if (node.alternative_types.empty()) + if (node.alternatives.empty()) throw std::runtime_error("No alternatives found during Backtrack"); // ICE - if (node.alternative_types.front() == node.type) { // Keep type, change variant - if (root_node_id == node_id) { // Root node - // TODO ... - } else if (node.child_ids().empty()) { // leaf node - } else - throw std::runtime_error("Backtrack: Can't set alternative in the middle of the tree."); - } else { // Different type - if (root_node_id == node_id) { // Root node - } else if (node.child_ids().empty()) { // leaf node - } else - throw std::runtime_error("Backtrack: Can't set alternative in the middle of the tree."); - } + auto& [type, variant] {node.alternatives.front()}; + + node.type = type; + node.variant = variant; + + node.alternatives.pop_front(); } // throws if no further track back is possible: compile error void Compiler::TrackBack() { // Search backwards for alternatives: last node with alternatives (variant or alt. token) - while (!nodes.empty() && nodes.last().alternative_types.empty()) { + while (!nodes.empty() && nodes.last().alternatives.empty()) { RemoveLastNode(); } @@ -4,6 +4,7 @@ #include "minicc.h" #include <cstdint> +#include <utility> namespace Gram { @@ -16,7 +17,7 @@ struct TreeNode { std::string type; index_t variant; // bnf[type][variant] - std::deque<std::string> alternative_types; // alternatives that we can consider if type fails. Discard after parsing! + std::deque<std::pair<std::string, index_t>> alternatives; // [type][value] alternatives that we can consider on fail. Discard after parsing! std::vector<int32_t> child_ids; // < 0: terminal: token_id; >= 0: non-terminal: node_id; fill token by token }; |