1 /* 2 * Copyright 2017 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #ifndef SKSL_NFA 9 #define SKSL_NFA 10 11 #include "src/sksl/lex/NFAState.h" 12 #include "src/sksl/lex/RegexNode.h" 13 14 #include <string> 15 #include <utility> 16 #include <vector> 17 18 /** 19 * A nondeterministic finite automaton for matching regular expressions. The NFA is initialized with 20 * a number of regular expressions, and then matches a string against all of them simultaneously. 21 */ 22 struct NFA { 23 /** 24 * Adds a new regular expression to the set of expressions matched by this automaton, returning 25 * its index. 26 */ addRegexNFA27 int addRegex(const RegexNode& regex) { 28 std::vector<int> accept; 29 // we reserve token 0 for END_OF_FILE, so this starts at 1 30 accept.push_back(this->addState(NFAState(++fRegexCount))); 31 std::vector<int> startStates = regex.createStates(this, accept); 32 fStartStates.insert(fStartStates.end(), startStates.begin(), startStates.end()); 33 return fStartStates.size() - 1; 34 } 35 36 /** 37 * Adds a new state to the NFA, returning its index. 38 */ addStateNFA39 int addState(NFAState s) { 40 fStates.push_back(std::move(s)); 41 return fStates.size() - 1; 42 } 43 44 /** 45 * Matches a string against all of the regexes added to this NFA. Returns the index of the first 46 * (in addRegex order) matching expression, or -1 if no match. This is relatively slow and used 47 * only for debugging purposes; the NFA should be converted to a DFA before actual use. 48 */ 49 int match(std::string s) const; 50 51 int fRegexCount = 0; 52 53 std::vector<NFAState> fStates; 54 55 std::vector<int> fStartStates; 56 }; 57 58 #endif 59