NFA.h 1.6 KB

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