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 { 18 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
