1*c8dee2aaSAndroid Build Coastguard Worker /* 2*c8dee2aaSAndroid Build Coastguard Worker * Copyright 2017 Google Inc. 3*c8dee2aaSAndroid Build Coastguard Worker * 4*c8dee2aaSAndroid Build Coastguard Worker * Use of this source code is governed by a BSD-style license that can be 5*c8dee2aaSAndroid Build Coastguard Worker * found in the LICENSE file. 6*c8dee2aaSAndroid Build Coastguard Worker */ 7*c8dee2aaSAndroid Build Coastguard Worker 8*c8dee2aaSAndroid Build Coastguard Worker #ifndef SKSL_DFA 9*c8dee2aaSAndroid Build Coastguard Worker #define SKSL_DFA 10*c8dee2aaSAndroid Build Coastguard Worker 11*c8dee2aaSAndroid Build Coastguard Worker #include <string> 12*c8dee2aaSAndroid Build Coastguard Worker #include <vector> 13*c8dee2aaSAndroid Build Coastguard Worker 14*c8dee2aaSAndroid Build Coastguard Worker /** 15*c8dee2aaSAndroid Build Coastguard Worker * Tables representing a deterministic finite automaton for matching regular expressions. 16*c8dee2aaSAndroid Build Coastguard Worker */ 17*c8dee2aaSAndroid Build Coastguard Worker struct DFA { DFADFA18*c8dee2aaSAndroid Build Coastguard Worker DFA(std::vector<int> charMappings, std::vector<std::vector<int>> transitions, 19*c8dee2aaSAndroid Build Coastguard Worker std::vector<int> accepts) 20*c8dee2aaSAndroid Build Coastguard Worker : fCharMappings(charMappings) 21*c8dee2aaSAndroid Build Coastguard Worker , fTransitions(transitions) 22*c8dee2aaSAndroid Build Coastguard Worker , fAccepts(accepts) {} 23*c8dee2aaSAndroid Build Coastguard Worker 24*c8dee2aaSAndroid Build Coastguard Worker // maps chars to the row index of fTransitions, as multiple characters may map to the same row. 25*c8dee2aaSAndroid Build Coastguard Worker // starting from state s and looking at char c, the new state is 26*c8dee2aaSAndroid Build Coastguard Worker // fTransitions[fCharMappings[c]][s]. 27*c8dee2aaSAndroid Build Coastguard Worker std::vector<int> fCharMappings; 28*c8dee2aaSAndroid Build Coastguard Worker 29*c8dee2aaSAndroid Build Coastguard Worker // one row per character mapping, one column per state 30*c8dee2aaSAndroid Build Coastguard Worker std::vector<std::vector<int>> fTransitions; 31*c8dee2aaSAndroid Build Coastguard Worker 32*c8dee2aaSAndroid Build Coastguard Worker // contains, for each state, the token id we should report when matching ends in that state (-1 33*c8dee2aaSAndroid Build Coastguard Worker // for no match) 34*c8dee2aaSAndroid Build Coastguard Worker std::vector<int> fAccepts; 35*c8dee2aaSAndroid Build Coastguard Worker }; 36*c8dee2aaSAndroid Build Coastguard Worker 37*c8dee2aaSAndroid Build Coastguard Worker #endif 38