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 "NFAState.h" 12 #include "RegexNode.h" 13 14 /** 15 * A nondeterministic finite automaton for matching regular expressions. The NFA is initialized with 16 * a number of regular expressions, and then matches a string against all of them simultaneously. 17 */ 18 struct NFA { 19 /** 20 * Adds a new regular expression to the set of expressions matched by this automaton, returning 21 * its index. 22 */ 23 int addRegex(const RegexNode& regex) { 24 std::vector<int> accept; 25 // we reserve token 0 for END_OF_FILE, so this starts at 1 26 accept.push_back(this->addState(NFAState(++fRegexCount))); 27 std::vector<int> startStates = regex.createStates(this, accept); 28 fStartStates.insert(fStartStates.end(), startStates.begin(), startStates.end()); 29 return fStartStates.size() - 1; 30 } 31 32 /** 33 * Adds a new state to the NFA, returning its index. 34 */ 35 int addState(NFAState s) { 36 fStates.push_back(std::move(s)); 37 return fStates.size() - 1; 38 } 39 40 /** 41 * Matches a string against all of the regexes added to this NFA. Returns the index of the first 42 * (in addRegex order) matching expression, or -1 if no match. This is relatively slow and used 43 * only for debugging purposes; the NFA should be converted to a DFA before actual use. 44 */ 45 int match(std::string s) const; 46 47 int fRegexCount = 0; 48 49 std::vector<NFAState> fStates; 50 51 std::vector<int> fStartStates; 52 }; 53 54 #endif 55
