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