DFA.h 1.0 KB

12345678910111213141516171819202122232425262728293031323334353637
  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_DFA
  8. #define SKSL_DFA
  9. #include <string>
  10. #include <vector>
  11. /**
  12. * Tables representing a deterministic finite automaton for matching regular expressions.
  13. */
  14. struct DFA {
  15. DFA(std::vector<int> charMappings, std::vector<std::vector<int>> transitions,
  16. std::vector<int> accepts)
  17. : fCharMappings(charMappings)
  18. , fTransitions(transitions)
  19. , fAccepts(accepts) {}
  20. // maps chars to the row index of fTransitions, as multiple characters may map to the same row.
  21. // starting from state s and looking at char c, the new state is
  22. // fTransitions[fCharMappings[c]][s].
  23. std::vector<int> fCharMappings;
  24. // one row per character mapping, one column per state
  25. std::vector<std::vector<int>> fTransitions;
  26. // contains, for each state, the token id we should report when matching ends in that state (-1
  27. // for no match)
  28. std::vector<int> fAccepts;
  29. };
  30. #endif